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...