Master DSA One Problem at a Time

Next Greater Element – Understanding Element Relationships in Arrays Problem Statement Given two distinct 0-indexed integer arrays nums1 and nums2 , where nums1 is a subset of nums2 , return an array of the next greater element for each element in nums1 corresponding to its position in nums2 . The next greater element of a number x in nums2 is the first greater number to the right of x in nums2 . If it does not exist, return -1 Example Input: nums1 = [4,1,2] nums2 = [1,3,4,2] Output: [-1, 3, -1] Explanation: For 4 , there is no number greater than it to its right in nums2 . For 1 , the next greater number is 3 . For 2 , there is no greater number to the right. Best Data Structure for the Job To efficiently solve this problem, we use a stack in combination with a hash map . The stack helps us track elements in a decreasing order while scanning nums2 from right to left, enabling us to find the next greater element for each number efficiently. The hash map i...

Special Grid Generator – Divide and Rule in Action Problem Statement You're given a non-negative integer N , and you need to generate a 2^N × 2^N grid filled with integers from 0 to 4^N - 1 . The twist? The grid has to be special , satisfying all the following rules: All numbers in the top-right quadrant must be smaller than those in the bottom-right quadrant. All numbers in the bottom-right quadrant must be smaller than those in the bottom-left quadrant. All numbers in the bottom-left quadrant must be smaller than those in the top-left quadrant. Each of the four quadrants must recursively also be a special grid. Note: A 1x1 grid (when N = 0) is trivially special. Example Let’s take N = 1 (so grid size = 2x2) Output: [[3, 0], [2, 1]] Explanation: Top-right quadrant: 0 Bottom-right quadrant: 1 Bottom-left quadrant: 2 Top-left quadrant: 3 Ordering: 0 < 1 < 2 < 3 — perfect. Each quadrant is 1x1, which is trivially special. Best Data Structure for ...

Count Fixed-Bound Subarrays — Satisfying MinK and MaxK Problem Statement You are given an array of integers nums and two integers minK and maxK . A fixed-bound subarray of nums is a subarray that satisfies the following conditions: The minimum value in the subarray is equal to minK . The maximum value in the subarray is equal to maxK . Your task is to return the number of fixed-bound subarrays in nums . Example 1: Input : nums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5 Output : 2 Explanation : The fixed-bound subarrays are [1, 3, 5] and [1, 3, 5, 2] . Best Technique – Sliding Window + Boundary Tracking This problem can be tricky because you need to ensure the subarray contains both the minimum and maximum values exactly. We can efficiently solve this using a sliding window technique, maintaining boundaries to ensure that the subarrays stay valid. Different Approaches: Approach 1: Brute Force with Set Tracking We could try every possible subarray and check if it m...

Count Interesting Subarrays — Modulo Frequency Check Problem Statement You’re given a 0-indexed integer array nums , along with two integers: modulo and k . A subarray nums[l..r] is considered interesting if: Let cnt be the number of indices i in range [l..r] such that nums[i] % modulo == k . The subarray is interesting if cnt % modulo == k . Your mission: Return the number of such interesting subarrays. Example 1 Input: nums = [3, 2, 4], modulo = 2, k = 1 Output: 3 Explanation: Interesting subarrays: [3] , [3,2] , [3,2,4] → All have exactly 1 element satisfying num % 2 == 1 . Best Technique — Prefix Sum with HashMap Magic This isn’t your typical sum or window problem. It’s about modulo arithmetic + prefix counts . We care about how many indices so far have nums[i] % modulo == k . Let’s map this into an elegant prefix sum pattern: If prefixCount[j] - prefixCount[i] % modulo == k , then nums[i+1..j] is interesting . Rearranged: Let prefix[j] % ...

Count Complete Subarrays — Match Distinct Count in Subarrays Problem Statement You’re given an array of positive integers nums . A complete subarray is defined as a subarray that contains all the distinct elements present in the entire array. Your task is to count the number of complete subarrays in nums . Explanation: The total number of distinct elements in the array is 3: {1, 2, 3}. Now, let’s find all subarrays that also contain all 3: [1,3,1,2] [1,3,1,2,2] [3,1,2] [3,1,2,2] So, there are 4 complete subarrays . Best Technique – Sliding Window + At-Most K Trick This problem might seem like just a subarray count, but it tests your ability to: Recognize a fixed-size condition inside variable-sized subarrays Use a hash map or frequency counter for distinct element tracking Leverage the at-most-k sliding window pattern Let’s explore multiple ways to solve this—from brute force to optimal—and see what each one teaches us. Different Approaches: ...

Minimum Rabbits in the Forest – Decoding the Puzzle This problem challenges our ability to reason through indirect information. Given a set of answers from rabbits about how many others share their color, our goal is to estimate the minimum number of rabbits that could be present in the forest. Let’s analyze this step-by-step and explore both brute force and optimized solutions with a focus on edge cases and estimation logic. Problem Statement You are given an integer array answers where each answers[i] represents a rabbit’s response to the question: "How many rabbits have the same color as you?" Your task is to determine the minimum number of rabbits that could be in the forest based on these answers. Example 1: Input: [1, 1, 2] Output: 5 Explanation: The two rabbits answering "1" can be in one group of 2. The rabbit answering "2" implies a group of 3, but only one has been seen, so two more must exist unseen. Best Data Structure The ...

Valid Parentheses – Keeping Brackets in Check Problem Statement Given a string s containing just the characters '(' , ')' , '{' , '}' , '[' , and ']' , determine if the input string is valid . A string is valid if: Open brackets are closed by the same type of brackets. Open brackets are closed in the correct order. Every close bracket has a corresponding open bracket. Best Data Structure for the Job Stack is the MVP here. Why? Perfect for Last In, First Out (LIFO) logic Helps track nested and sequential brackets Efficient and intuitive for validation problems like this on Different Approaches 1)Brute Force with Replacements Keep removing valid pairs like "()" , "{}" , and "[]" until nothing can be removed. If the string becomes empty, it was valid. public boolean isValid (String s) { while (s.contains( "()" ) || s.contains( "[]" ) || s.contains( "{}" ))...