Road2Geeks

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