Master DSA One Problem at a Time

Find the First Occurrence of Needle in Haystack Problem Statement Implement a function strStr(haystack, needle) that returns the index of the first occurrence of needle in haystack , or -1 if needle is not part of haystack . Example : Input: haystack = "sadbutsad" , needle = "sad" Output: 0 Explanation: "sad" occurs at index 0 and 6 . The first occurrence is at 0 . Best Data Structure for Solving the Problem Since we're dealing with string pattern matching, a simple String traversal with two-pointer or substring comparison is efficient here. Multiple Approaches Approach 1: Built-in Method (Quick & Easy) Idea : Use Java's built-in indexOf() function. It's optimized under the hood and handles all edge cases. public int strStr (String haystack, String needle) { return haystack.indexOf(needle); } Approach 2: Manual Sliding Window (Interview-Ready) Idea : Slide a window of size needle.length() across haysta...

String to Integer (atoi)  Problem Statement Implement the myAtoi(string s) function that converts a string into a 32-bit signed integer ( int ) using the following rules: Parsing Rules Whitespace : Skip all leading whitespace characters. Sign : Check for an optional '+' or '-' sign. Digits : Convert digits until a non-digit is found. Clamp : If the number exceeds 32-bit range: [-2^31, 2^31 - 1] = [-2147483648, 2147483647] return the clamped value. Return : The resulting integer. Example  Input: s = " -042" Output: -42 Multiple Approaches Approach 1: Brute Force with Built-in Functions (Not Allowed in Interviews) Idea : Use built-in parsing and catching exceptions. public int myAtoi (String s) { s = s.trim(); try { return Integer.parseInt(s.split( "[^0-9+-]" )[ 0 ]); } catch (Exception e) { return 0 ; } } Approach 2: Manual Parsing with Overflow Detection (Optimal) Idea : Process ...

Domino Chain Reaction – Final State of Falling Dominoes Problem Statement: You're given a string representing a row of dominoes. Each domino can be: 'L' : Pushed to the left 'R' : Pushed to the right '.' : Upright and not pushed Each second: A domino falling to the left pushes the adjacent left domino A domino falling to the right pushes the adjacent right domino If a domino receives force from both sides simultaneously, it stays upright Return the final state of the dominoes after all movement stops. Example: Input : "RR.L" Output : "RR.L" Explanation : The leftward falling domino does not affect the earlier rightward chain due to the time difference. Best Data Structure for the Job: Use an integer array to simulate forces across the dominoes. This approach captures direction and intensity efficiently. Different Approaches Approach 1: Brute Force Simulation Simulate each second, updating the state of do...

Edit Distance Problem – Minimum Operations to Convert One String to Another Problem Statement: You are given two strings S1 and S2 . Your task is to convert S1 to S2 using the following allowed operations: Insert a character Delete a character Replace a character Find the minimum number of operations required to make the transformation. Example 1: Input: S1 = "horse" , S2 = "ros" Output: 3 Explanation: Operations: replace 'h' → 'r', remove 'r', remove 'e' Best Technique – Dynamic Programming This is a classic 2D DP problem. Let dp[i][j] represent the minimum edit distance between the first i characters of S1 and the first j characters of S2 . We build up the solution by comparing characters from both strings and checking for 3 possible operations: insert, delete, replace. Different Approaches: Approach 1: Brute Force (Recursion) Try all possibilities recursively: insert, delete, or replace. This ...

Zigzag Conversion – Mastering Directional Patterns in Strings Problem Statement You're given a string s and an integer numRows . Your task is to return a new string that represents the original string written in a zigzag pattern over numRows , and then read line by line. For example, if s = "PAYPALISHIRING" and numRows = 3 , the zigzag would look like: P A H N A P L S I I G Y I R Reading row by row: "PAHNAPLSIIGYIR" Best Data Structure for the Job The most suitable data structure for this problem is an array of StringBuilder s. Each StringBuilder will represent a row in the zigzag pattern. They're fast for appending and don't require manual resizing. Efficient in both time and space for this use case. Avoid using a matrix or list of lists — they add unnecessary complexity. Different Approaches 1. Brute Force with 2D Character Grid This approach simulates placing each character into a 2D grid. After the simulat...

 Score It Like You Mean It – ASCII Vibes Only Ever wondered what happens when characters in a string get compared like rival contestants on a talent show? This problem’s got them lining up, back-to-back, and we're judging them based on how different they sound — literally. The score of a string is defined as the sum of absolute differences between ASCII values of adjacent characters . Yup, that's it. No tricks, no data structure drama. Just straight-up character comparisons with some ASCII math. Let’s dive into the different ways to get this done. Best Data Structure for the Job Honestly? None. All we need is the string itself and some basic math. This is a no-fluff, iterate-and-score kind of problem. We don’t need arrays, maps, or stacks — just a good ol’ loop (or stream, if you're feeling fancy). Different Approaches Approach 1: The Classic For-Loop This is the most intuitive way. Just loop through the string from the second character onward and compute the absolu...

  Longest Palindromic Substring  This might seem like a string manipulation task at first, but it's a golden opportunity to understand techniques like brute force exploration, expanding from center, and dynamic programming — all while strengthening your grip on substring logic and indexing. Let’s explore how to solve this problem using three different approaches: brute force , expand around center , and dynamic programming . The Best Data Structure for Solving It (And Why!) When dealing with substrings, two things are crucial: Knowing how to efficiently iterate through all possible substrings. Being able to check if a substring is a palindrome in a smart way. Brute force gives us the raw idea. Expand-around-center improves on it with a clever trick. Dynamic programming brings in structure and memory for optimization. Let’s dive in! Different Approaches – From Brute Force to Optimized 1)Brute Force (Naive Approach) This approach checks all possible substrin...