Road2Geeks

Problem Overview The Product of Array Except Self is a classic problem that tests your understanding of array traversal and optimization. The task is simple to state but tricky to implement efficiently. Given an integer array nums , you need to return an array such that each element at index i is equal to the product of all the elements in nums except nums[i] . The challenge is that: Division is not allowed The solution must run in O(n) time Initial Thoughts At first glance, it feels natural to compute the total product of the array and divide it by the current element. However, this approach fails because division is forbidden and handling zeroes becomes messy. This pushed me to think differently — instead of excluding the current element, why not multiply everything around it? That’s where the prefix and suffix product pattern comes in. Key Insight: Prefix & Suffix Products For every index i : Prefix product → product of all elements to t...

Minimum Window Substring – Sliding Window Approach While solving the Minimum Window Substring problem, I initially struggled to manage window validity correctly. The key challenge was ensuring that the current window contains all characters of the target string with correct frequency , while still keeping the window as small as possible. Problem Intuition The problem is a classic example of a variable-size sliding window . We expand the window to the right until it becomes valid, and once valid, we try to shrink it from the left to find the minimum-length substring. To efficiently check window validity, instead of rechecking all characters every time, we maintain a frequency map and a counter that tracks how many characters are still required. Approach Create a frequency map of the target string. Use two pointers ( l and r ) to represent the sliding window. Expand the window by moving r . Decrease the required count only when a needed character is found. ...

LeetCode 424 – Longest Repeating Character Replacement (Sliding Window) Today, I solved another LeetCode problem, but this one truly clicked only after watching an intuition-based explanation. I followed this YouTube video to understand the thought process behind the solution: 👉 Watch the intuition video here Initially, the problem felt tricky because it mixes string manipulation with window resizing logic. But once I understood why sliding window works here , the implementation became much clearer. 🧠 Problem Intuition The goal is to find the longest substring that can be converted into a string of repeating characters by replacing at most k characters. Instead of checking all substrings (which would be inefficient), we use a sliding window approach. Inside the window: We track the frequency of each character. We keep note of the most frequent character in the window. If the number of characters to replace exceeds k , we shrink the window. The ke...

Longest Substring Without Repeating Characters (Sliding Window) This problem is one of the most important questions to understand the Sliding Window pattern. The goal is to find the length of the longest substring that contains only unique characters . Problem Statement Given a string s , find the length of the longest substring without repeating characters. Intuition A substring is always continuous, which makes this problem a perfect candidate for the sliding window technique . We maintain a window that always contains unique characters. Whenever a duplicate character appears, we shrink the window from the left until the duplicate is removed. At every step, we track the maximum window size. Approach Use two pointers l (left) and r (right). Use a set to store characters in the current window. Expand the window by moving r . If a duplicate is found, shrink the window by moving l . Update the maximum length after each valid window. Python Solution...

Maximum Average Subarray I – Sliding Window Optimization Explained While solving LeetCode – Maximum Average Subarray I , I initially implemented a straightforward sliding window solution. Although the logic was correct, it resulted in a Time Limit Exceeded (TLE) error. This problem became a good learning example of why optimization matters and how prefix sums can drastically improve performance. Initial Approach (Naive Sliding Window) My first solution calculated the average of every window of size k by slicing the array and computing the sum each time. Array slicing takes O(k) Summing also takes O(k) This happens for each window → O(n) times Overall time complexity becomes O(n × k) , which causes TLE for large inputs. This solution works logically but is inefficient due to repeated recalculation of sums. Optimized Approach Using Prefix Sum To avoid recalculating sums, I switched to using a prefix sum array . Each index in the prefix array stores...

Trapping Rain Water – My Learning Journey (From Intuition to Two Pointers) Today I worked on the Trapping Rain Water problem, and honestly, it was not easy at first. I couldn’t directly come up with the solution, so I decided to step back and focus on understanding the intuition instead of forcing the code. To build that intuition, I watched this video, which helped me understand how water is actually trapped between bars: Reference Video: https://www.youtube.com/watch?v=TCaBnVIllrQ Key Intuition The most important realization for this problem is: Water trapped at any index depends on the maximum height on its left and the maximum height on its right . Mathematically: water[i] = min(max_left, max_right) - height[i] If this value is negative, no water can be trapped at that position. Approach 1: Brute Force (Time Limit Exceeded) My first approach was very straightforward. For each index, I calculated: Maximum height on the left Maximum he...

LeetCode 15 – 3Sum (Two Pointer Approach) Given an integer array nums , the task is to find all unique triplets [nums[i], nums[j], nums[k]] such that: i ≠ j ≠ k nums[i] + nums[j] + nums[k] = 0 No duplicate triplets are allowed Key Idea The problem can be reduced to a combination of: Sorting the array Fixing one element Using the two-pointer technique to find the remaining two numbers This transforms the problem into a repeated Two Sum search on a sorted array. Step-by-Step Approach 1. Sort the Array Sorting allows us to: Use two pointers efficiently Skip duplicate values easily Stop early when the numbers become positive 2. Fix One Element We iterate through the array and fix one element nums[i] . The goal becomes finding two numbers whose sum is -nums[i] . 3. Apply Two Pointers Left pointer l = i + 1 Right pointer r = n - 1 Move pointers based on the sum: If sum is too small → move l forward If sum is...

Problem Overview In the Container With Most Water problem, you are given an array where each element represents the height of a vertical line drawn at that index. The goal is to find two lines that, together with the x-axis, form a container capable of holding the maximum amount of water. Problem Visualization Each value in the array represents a vertical line. The water trapped between any two lines depends on the distance between them (width) and the shorter of the two lines (height). #source - Leetcode In the diagram above, the highlighted lines form the container that holds the maximum water. Even though some lines are taller, the distance between them is smaller, resulting in less area. Key Insight The amount of water a container can store is calculated using: area = min(height[left], height[right]) × (right - left) As the pointers move inward, the width always decreases. Therefore, the onl...

Problem Overview In the Two Sum II – Input Array Is Sorted problem, we are given a sorted array of integers and a target value. The task is to find two numbers such that their sum equals the target and return their 1-based indices . Why Sorting Matters The key constraint of this problem is that the input array is already sorted in non-decreasing order. This allows us to make informed decisions about how to move through the array without checking every possible pair. Optimal Strategy: Two Pointer Technique Instead of using a brute-force nested loop or a hash map, we can use two pointers to solve the problem in linear time. One pointer starts at the beginning of the array, and the other starts at the end. How the Algorithm Works Initialize a left pointer at the start of the array. Initialize a right pointer at the end of the array. Calculate the sum of the values at both pointers. If the...

Problem Overview The Squares of a Sorted Array problem provides a sorted integer array that may contain negative and positive numbers. The task is to return a new array consisting of the squares of each number, sorted in non-decreasing order. Why the Naive Approach Is Not Optimal A simple solution is to square every element and then sort the resulting array. While this works correctly, it results in a time complexity of O(n log n) , which is not optimal for this problem. Key Insight Squaring the numbers breaks the original sorted order because large negative values can produce larger squares than positive values. However, the largest squared value will always come from one of the two ends of the array. Optimal Approach: Two Pointers with Reverse Fill To achieve an O(n) solution, we use the two-pointer technique along with a reverse write strategy. Two pointers are placed at the beginning and end of the ...

Problem Overview In this problem, we are given a string that may contain letters, numbers, spaces, and special characters. Our task is to determine whether the string is a valid palindrome after removing all non-alphanumeric characters and ignoring letter case. Key Observations Only letters ( a–z , A–Z ) and digits ( 0–9 ) matter. Uppercase and lowercase letters should be treated as equal. The original order of characters must be respected. Optimal Strategy: Two Pointer Technique Instead of creating a new filtered string, we use two pointers to scan the original string from both ends. This allows us to validate the palindrome in a single pass while using constant extra space. How the Algorithm Works Initialize two pointers: Left pointer at the start of the string Right pointer at the end of the string Move the left pointer forward until it points to an alphanumer...

Best Time to Buy and Sell Stock – LeetCode 121 (O(n) One-Pass Solution) The Best Time to Buy and Sell Stock problem from LeetCode 121 is a classic array and greedy problem frequently asked in coding interviews. The goal is to maximize profit by choosing a single day to buy and a later day to sell. Problem Statement You are given an array prices , where prices[i] represents the price of a stock on day i . You may complete at most one transaction (buy once and sell once). Input: prices = [7,1,5,3,6,4] Output: 5 Input: prices = [7,6,4,3,1] Output: 0 If no profit is possible, return 0 . Key Observations You must buy before you sell Only one transaction is allowed The selling day must come after the buying day Approach 1: Brute Force (Not Optimal) The brute force approach checks every possible pair of buying and selling days and calculates the profit. for i in range(n): for j in range(i+1, n): profit = max(profit, prices[j] - prices...

Product-Based DSA Roadmap: Pattern Mastery How to use: Focus on ONE pattern at a time. Do not move to the next pattern until you can solve the current pattern's problems without looking at the solution. Phase 1: The Essentials (Arrays & Strings) Pattern Problem Name Difficulty Link Two Pointers Sorted arrays, Pairs Valid Palindrome Easy Solve Squares of a Sorted Array Easy Solve Two Sum II - Input Array Is Sorted Medium Solve Con...

Rotate Array – LeetCode 189 (In-Place O(1) Space Solution) The Rotate Array problem from LeetCode 189 is a classic array manipulation question frequently asked in coding interviews. The goal is to rotate an array to the right by k steps while modifying the array in-place . This problem helps build a strong understanding of array indexing, space optimization, and algorithmic thinking. Problem Statement Given an integer array nums , rotate the array to the right by k steps. The rotation must be done in-place, meaning no new array should be returned. Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Key Observations If k is greater than the array length, rotation repeats We can optimize using k = k % n Extra memory usage should be minimized Approach 1: Brute Force Rotation A simple solution is to move the last element to the front, repeating the process k times. class Solution: def rotate(self, nums, k): n = len(nums) ...

Majority Element in an Array Given an integer array nums of size n , the task is to find the majority element . A majority element is defined as the element that appears more than ⌊n / 2⌋ times in the array. It is guaranteed that the majority element always exists. Problem Example Input: nums = [3, 2, 3] Output: 3 Input: nums = [2,2,1,1,1,2,2] Output: 2 Approach 1: Using Counter (Easy to Understand) A straightforward approach is to count the frequency of each element and return the one with the maximum count. Python Code from collections import Counter class Solution: def majorityElement(self, nums): freq = Counter(nums) max_count = max(freq.values()) for key in freq: if freq[key] == max_count: return key Complexity Analysis Time Complexity: O(n) Space Complexity: O(n) Although this solution is simple and readable, it us...

LeetCode 80 — Remove Duplicates from Sorted Array II 1) my first approach (Counter + new list) — why it fails the constraints this code correctly computes the desired result but violates the problem requirements: Uses extra memory: Counter(nums) and the temporary list n both use O(n) space. Not strictly in-place: The problem requires modifying nums in-place with O(1) extra space. Order risk: Using a frequency map is unnecessary and could break the required stable relative order depending on iteration (avoid it). from collections import Counter class Solution: def removeDuplicates(self, nums: List[int]) -> int: c = Counter(nums) n = [] for i in c: if c[i] >= 2: n.append(i) n.append(i) elif c[i] < 2: n.append(i) for i in range(len(n)): nums[i] = n[i] return len(n) 2) Optimal in-pla...

LeetCode 26 — Remove Duplicates from Sorted Array 1)approach 1 (Using extra list — not optimal) Works correctly but uses extra space and has O(n²) behavior because if i not in uniques is an O(n) check for each element. class Solution: def removeDuplicates(self, nums: List[int]) -> int: uniques = [] for i in nums: if i not in uniques: uniques.append(i) k = len(uniques) for i in range(k): nums[i] = uniques[i] return k Complexity: Time O(n²), Space O(n). Not in-place as required by the problem. 2) Optimal two-pointer solution (Front write — O(n), O(1) space) This is the recommended in-place approach for a sorted array: keep a write pointer p that marks the last unique position. class Solution: def removeDuplicates(self, nums: List[int]) -> int: if not nums: return 0 p = 0 for i in range(1, len(nums)): ...

LeetCode 27 — Remove Element Solution 1 (Optimal) This version is in-place, single-pass, O(n) time and O(1) space. It preserves the relative order of kept elements. class Solution: def removeElement(self, nums: List[int], val: int) -> int: p = 0 for i in nums: if i != val: nums[p] = i p += 1 return p Solution 2(Optimal) This version is in-place, single-pass, O(n) time and O(1) space. It preserves the relative order of kept elements. class Solution: def removeElement(self, nums: List[int], val: int) -> int: l, r = 0, len(nums) - 1 while l return l Common Mistakes Modifying the list while iterating with for x in nums plus remove or pop — this changes indices and skips elements. Returning the modified list instead of the new length . Trying to maintain order with an algorithm designed to minimize writes (e.g., two-pointer-swap) without noting that order...

Evolving My Solution to “Merge Sorted Array” A practical, beginner-friendly walkthrough showing four versions of my code (from a naive approach to the optimal in-place two-pointer solution). Includes explanations, complexity and ready-to-paste code. Problem Summary You are given two sorted arrays: nums1 with size m + n (first m are valid) nums2 with size n Goal: Merge nums2 into nums1 in sorted order in-place . Version 1 — Beginner Approach (Extra List) I merged into a new list then copied back. Works, but not in-place and uses extra memory. class Solution: def merge(self, nums1, m, nums2, n): result = [] p1 = 0 p2 = 0 for _ in range(m+n): if p1 >= m: result.extend(nums2[p2:n]) break elif p2 >= n: result.extend(nums1[p1:m]) break elif nu...