Road2Geeks

Linked List Cycle Detection using Floyd’s Algorithm (LeetCode 141) Detecting a cycle in a singly linked list is a classic problem that can be solved efficiently using Floyd’s Tortoise and Hare algorithm. Optimal Approach: Two Pointers (Cleaner Loop) This is the most readable and interview-preferred implementation. It uses two pointers moving at different speeds. class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False Alternate Implementation (Non-Cleaner Loop) Below is a logically correct version that performs additional checks inside the loop to avoid null pointer access. class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: slow_pointer = fast_pointer = head ...

Longest Conseive Sequence – From TLE to Optimal O(n) The Longest Consecutive Sequence problem looks simple at first, but it easily leads to a Time Limit Exceeded (TLE) error if we are not careful with repeated work. In this post, I’ll explain where the TLE comes from and how a small optimization makes the solution run in linear time. Problem Overview Given an unsorted array of integers, we need to find the length of the longest sequence of consecutive numbers. The solution must run in O(n) time. Initial Thought Process (Why TLE Happens) A common approach is to check for every number and keep extending the sequence forward ( x, x+1, x+2... ). While lookup using a hash structure is O(1), the same sequence gets counted multiple times, leading to unnecessary repeated work. In the worst case (like a fully consecutive array), this turns into O(n²) , which causes TLE. Key Optimization The fix is surprisingly small but powerful: Only start counting when the current nu...

Group Anagrams in Python – Optimal Hashing Approach (LeetCode 49) The Group Anagrams problem is a classic hashing question frequently asked in coding interviews. The goal is to group strings that are anagrams of each other, meaning they contain the same characters with the same frequencies but possibly in a different order. In this post, I’ll explain an optimal Python solution using character frequency counting, which avoids sorting and achieves better performance. 🔍 Problem Overview You are given an array of strings. Your task is to group all strings that are anagrams of each other and return them as a list of groups. Two strings are anagrams if: They contain the same characters Each character appears the same number of times 💡 Key Intuition Instead of sorting every string (which costs O(k log k) time), we represent each word using a fixed-size frequency array of 26 characters. Since the English alphabet has only 26 lowercase letters, the freq...

Problem Overview An anagram is formed when two strings contain the same characters with the same frequency, but possibly in a different order. The task is to determine whether two given strings are valid anagrams of each other. Key Observation Since character order does not matter in an anagram, comparing strings position by position is ineffective. What actually matters is the frequency of each character in both strings. Optimal Approach Using HashMaps We use two hashmaps (dictionaries) to count the frequency of characters in both strings. If both maps are identical, the strings are anagrams. Traverse the first string and count character frequencies Traverse the second string and count character frequencies Compare both frequency maps Python Code Implementation class Solution: def isAnagram(self, s: str, t: str) -> bool: s_map = {} t_map = {} for ch in s: s_map[ch] = s_map.get(ch, 0) + 1 for ch in t: ...

Two Sum Problem – From Confusion to Clear Intuition The Two Sum problem is one of those classic interview questions that looks simple, but can easily trap you into an inefficient approach if you don’t recognize the pattern early. Initially, I also thought about checking every possible pair, but that quickly leads to a slow solution. Problem Statement (In Simple Words) You are given an array of integers and a target value. Your task is to return the indices of the two numbers such that they add up to the target. Each input has exactly one solution, and you cannot use the same element twice. Brute Force Thought Process The first idea that naturally comes to mind is: for every number, check all other numbers to see if their sum equals the target. While this works logically, it results in O(n²) time complexity, which is not optimal. Key Insight That Changes Everything Instead of asking: “Which two numbers add up to the target?” I reframed the question as: “For the current...

Problem Background While solving the Continuous Subarray Sum problem on LeetCode, I initially felt confident because the word subarray immediately triggered my sliding window intuition. I had been practicing two pointers and sliding window patterns consistently, so my brain naturally tried to force that approach here. Why Sliding Window Failed for Me I tried hard to find a condition to either expand or shrink the window. But no matter how I looked at it, something felt off. The sum does not behave monotonically There is no clear rule to shrink the window Checking divisibility by k gives no directional hint That’s when I realized this problem does not belong to the sliding window family. The confusion I was facing was actually a signal that I was applying the wrong pattern. The YouTube Insight That Changed Everything After watching a YouTube tutorial focused only on intuition, one key idea finally clicked: If the same remainder appears again while taking pre...

Problem Overview The problem Subarray Sum Equals K asks us to find the total number of continuous subarrays whose sum is equal to a given value k . At first glance, this looks like a simple array problem, but it becomes tricky because: Subarrays must be continuous Elements can be negative A brute force approach would be too slow Brute Force Thinking The most straightforward approach is to try all possible subarrays and check their sums. However, this takes O(n²) time, which leads to a Time Limit Exceeded (TLE) for large inputs. This forced me to look for an optimized approach that avoids recomputing sums again and again. Key Insight: Prefix Sum Instead of recalculating subarray sums, we can store cumulative sums. Let prefixSum[i] represent the sum of elements from index 0 to i . If the sum of a subarray from index j+1 to i is equal to k , then: prefixSum[i] − prefixSum[j] = k Rearranging this gives: prefixSum[j] = prefixSum[i] − k T...

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