Search Blogs

Showing results for "Array"

Found 30 results

Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Try the QuestionBefore reading the solution, try solving the problem yourself:👉 https://leetcode.com/problems/search-in-rotated-sorted-array/Attempting the problem first helps build strong algorithmic intuition, which is extremely valuable during coding interviews.Problem StatementYou are given an integer array nums that was originally sorted in ascending order with distinct elements.Example of a sorted array:[0,1,2,4,5,6,7]Before the array is provided to the function, it may have been rotated at some pivot index k.After rotation, the array structure becomes:[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]For example:Original Array[0,1,2,4,5,6,7]Rotated by 3 positions[4,5,6,7,0,1,2]You are also given an integer target.The goal is to return the index of the target element in the array.If the element does not exist, return:-1Important ConstraintThe algorithm must run in O(log n) time complexity, which strongly suggests using Binary Search.Example WalkthroughExample 1Inputnums = [4,5,6,7,0,1,2]target = 0Output4Explanation:0 exists at index 4Example 2Inputnums = [4,5,6,7,0,1,2]target = 3Output-1Explanation:3 does not exist in the arrayExample 3Inputnums = [1]target = 0Output-1Understanding the Core ChallengeIf the array were fully sorted, the problem would be straightforward because binary search could directly be applied.Example:[1,2,3,4,5,6,7]However, due to rotation:[4,5,6,7,0,1,2]the array is no longer globally sorted.But an important observation makes the problem solvable.Key ObservationEven after rotation:At least one half of the array is always sorted.For example:[4,5,6,7,0,1,2] Left part → sorted Right part → sortedThis property allows the use of binary search with additional conditions.Approach 1 — Linear Scan (Brute Force)The simplest method is to iterate through the entire array and check each element.AlgorithmTraverse the array from start to end.Compare every element with the target.Return the index if found.Codefor(int i = 0; i < nums.length; i++){ if(nums[i] == target){ return i; }}return -1;Time ComplexityO(n)Space ComplexityO(1)Although simple, this solution does not satisfy the required O(log n) complexity.Approach 2 — Modified Binary SearchA better solution uses binary search with sorted half detection.IdeaAt every step:Calculate the middle index.Determine which half of the array is sorted.Check if the target lies inside that sorted half.Adjust the search range accordingly.Implementationpublic int search(int[] nums, int target) { int l = 0; int r = nums.length - 1; while(l <= r){ int mid = l + (r - l) / 2; if(nums[mid] == target){ return mid; } // left half sorted if(nums[l] <= nums[mid]){ if(nums[l] <= target && target < nums[mid]){ r = mid - 1; }else{ l = mid + 1; } } // right half sorted else{ if(nums[mid] < target && target <= nums[r]){ l = mid + 1; }else{ r = mid - 1; } } } return -1;}Time ComplexityO(log n)Space ComplexityO(1)This is the most common interview solution.Approach 3 — Find Rotation Point Then Apply Binary SearchAnother elegant strategy is to first locate the minimum element in the rotated array, which represents the rotation index (pivot).Once the pivot is known, the array can be logically split into two sorted subarrays.Example:[4,5,6,7,0,1,2] ^ pivotTwo sorted sections exist:[4,5,6,7][0,1,2]After identifying the pivot:Decide which part may contain the target.Apply standard binary search on that portion.Step 1 — Finding the Minimum Element (Rotation Pivot)The smallest element indicates where the rotation happened.Function to Find Minimum Valuepublic int findMinIndex(int[] nums){ int l = 0; int r = nums.length - 1; while(l < r){ int mid = l + (r - l) / 2; if(nums[mid] > nums[r]){ l = mid + 1; }else{ r = mid; } } return l;}Why This WorksIf:nums[mid] > nums[r]the minimum element must be on the right side.Otherwise, it lies on the left side (including mid).Step 2 — Standard Binary SearchAfter determining which half contains the target, a normal binary search is applied.public int binarySearch(int[] nums, int l, int r, int target){ while(l <= r){ int mid = l + (r - l) / 2; if(nums[mid] == target){ return mid; } else if(nums[mid] < target){ l = mid + 1; } else{ r = mid - 1; } } return -1;}Complete Solution (Pivot + Binary Search)class Solution { public int findMinIndex(int[] nums){ int l = 0; int r = nums.length - 1; while(l < r){ int mid = l + (r - l) / 2; if(nums[mid] > nums[r]){ l = mid + 1; }else{ r = mid; } } return l; } public int binarySearch(int[] nums, int l, int r, int target){ while(l <= r){ int mid = l + (r - l) / 2; if(nums[mid] == target){ return mid; } else if(nums[mid] < target){ l = mid + 1; } else{ r = mid - 1; } } return -1; } public int search(int[] nums, int target) { int pivot = findMinIndex(nums); if(nums[pivot] <= target && target <= nums[nums.length - 1]){ return binarySearch(nums, pivot, nums.length - 1, target); } return binarySearch(nums, 0, pivot - 1, target); }}Time ComplexityFinding pivot:O(log n)Binary search:O(log n)Total complexity:O(log n)Space ComplexityO(1)No additional memory is used.Key Takeaways✔ The array is sorted but rotated✔ A rotation creates two sorted sections✔ Binary search can still be applied✔ Either detect the sorted half directly or locate the pivot first✔ Both optimized approaches achieve O(log n) complexityFinal ThoughtsThis problem is a classic binary search variation frequently asked in coding interviews. It evaluates the ability to:Recognize structural patterns in arraysAdapt binary search to non-standard conditionsMaintain optimal algorithmic complexityUnderstanding this pattern also helps solve related problems such as:Find Minimum in Rotated Sorted ArraySearch in Rotated Sorted Array IIFind Rotation Count in ArrayMastering these concepts significantly strengthens binary search problem-solving skills for technical interviews.

Binary SearchJavaRotated Sorted ArrayLeetCodeMedium

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Try the QuestionBefore reading the explanation, try solving the problem yourself:👉 https://leetcode.com/problems/peak-index-in-a-mountain-array/Solving it first helps strengthen your problem-solving intuition, especially for binary search problems.Problem StatementYou are given an integer array arr that is guaranteed to be a mountain array.A mountain array is defined as an array where:Elements strictly increase until a peak element.After the peak, elements strictly decrease.Example:[0, 2, 5, 7, 6, 3, 1] ^ peakYour task is to return the index of the peak element.Constraints3 <= arr.length <= 10^50 <= arr[i] <= 10^6arr is guaranteed to be a mountain arrayImportant implications:The peak always exists.There will be exactly one peak.The array strictly increases before the peak and strictly decreases after it.Example WalkthroughExample 1Inputarr = [0,1,0]Visualization0 1 0 ^Output1Example 2Inputarr = [0,2,1,0]Visualization0 2 1 0 ^Output1Example 3Inputarr = [0,10,5,2]Visualization0 10 5 2 ^Output1Understanding the Mountain Array StructureA mountain array always looks like this:increasing → peak → decreasingGraphically: peak /\ / \ / \Because of this structure:Before the peak → numbers increaseAfter the peak → numbers decreaseThis property makes the problem perfect for binary search.Approach 1 — Brute Force (Check Every Element)The simplest way is to check every element and determine if it is greater than its neighbors.AlgorithmTraverse the array from index 1 to n-2.For each element check:arr[i] > arr[i-1] AND arr[i] > arr[i+1]If true, return i.Implementationpublic int peakIndexInMountainArray(int[] arr) { for(int i = 1; i < arr.length - 1; i++){ if(arr[i] > arr[i-1] && arr[i] > arr[i+1]){ return i; } } return -1;}Time ComplexityO(n)We may need to check every element.Space ComplexityO(1)Approach 2 — Linear Scan Using Increasing TrendSince the array first increases then decreases, we can detect where the increase stops.Key IdeaTraverse the array and check when:arr[i] > arr[i+1]This means we reached the peak.Implementationpublic int peakIndexInMountainArray(int[] arr) { for(int i = 0; i < arr.length - 1; i++){ if(arr[i] > arr[i+1]){ return i; } } return -1;}Example0 2 5 7 6 3 1 ^At index 3:7 > 6So index 3 is the peak.Time ComplexityO(n)Space ComplexityO(1)Approach 3 — Modified Binary Search (Optimal Solution)Because the array has a mountain structure, binary search can be used.Core IntuitionCompare:arr[mid]arr[mid+1]Two situations are possible.Case 1 — Increasing Slopearr[mid] < arr[mid+1]Example:1 3 5 7 ^This means the peak is on the right side.Move the search space to the right.left = mid + 1Case 2 — Decreasing Slopearr[mid] > arr[mid+1]Example:7 5 3 1 ^This means the peak lies on the left side including mid.right = midOptimal Java Implementationclass Solution { public int peakIndexInMountainArray(int[] arr) { int i = 0; int j = arr.length - 1; while(i < j){ int mid = i + (j - i) / 2; if(arr[mid] < arr[mid + 1]){ i = mid + 1; } else{ j = mid; } } return i; }}Step-by-Step ExampleArray[0,2,5,7,6,3,1]Iteration 1mid = 3arr[mid] = 7arr[mid+1] = 6Decreasing slope → move left.Iteration 2Search space narrows until:peak index = 3Time ComplexityO(log n)Binary search halves the search space each iteration.Space ComplexityO(1)No extra memory is required.Why Binary Search Works HereBecause the array behaves like a mountain curve.If you are standing at index mid:If the right side is higher, go right.If the left side is higher, go left.Eventually you will reach the top of the mountain (the peak).Key Takeaways✔ A mountain array increases then decreases✔ There is exactly one peak✔ Brute force and linear scan work in O(n) time✔ Binary search exploits the mountain structure✔ Optimal solution runs in O(log n) timeFinal ThoughtsThis problem is a classic example of binary search applied to array patterns rather than sorted values.Understanding the slope comparison technique used here will help solve other problems such as:Find Peak ElementMountain Array SearchBitonic Array ProblemsMastering these patterns significantly improves binary search problem-solving skills for coding interviews.

LeetCodeBinary SearchMountain ArrayMediumJava

Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Try the QuestionBefore reading the explanation, try solving the problem yourself:👉 https://leetcode.com/problems/search-in-rotated-sorted-array-ii/Practicing the problem first helps develop stronger problem-solving intuition, especially for binary search variations.Problem StatementYou are given an integer array nums that is sorted in non-decreasing order.Example of a sorted array:[0,1,2,4,4,4,5,6,6,7]Before being passed to your function, the array may be rotated at some pivot index k.After rotation, the structure becomes:[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]Example:Original array[0,1,2,4,4,4,5,6,6,7]Rotated at index 5[4,5,6,6,7,0,1,2,4,4]You are also given an integer target.Your task is to determine:Return true if the target exists in the arrayReturn false if the target does not existThe goal is to minimize the number of operations, which suggests using Binary Search.Example WalkthroughExample 1Inputnums = [2,5,6,0,0,1,2]target = 0OutputtrueExplanation:0 exists in the arrayExample 2Inputnums = [2,5,6,0,0,1,2]target = 3OutputfalseExplanation:3 does not exist in the arrayUnderstanding the Core ChallengeThis problem is very similar to the classic problem:Search in Rotated Sorted Array (LeetCode 33).However, there is an important difference.Difference Between the Two ProblemsProblemArray ValuesRotated Sorted ArrayAll elements are distinctRotated Sorted Array IIArray may contain duplicatesDuplicates introduce ambiguity during binary search.Why Duplicates Make the Problem HarderIn the previous problem, we relied on this rule:If nums[left] <= nums[mid]→ left half is sortedBut duplicates can break this assumption.Example:nums = [1,0,1,1,1]If:left = 0mid = 2right = 4Then:nums[left] = 1nums[mid] = 1nums[right] = 1Here we cannot determine which half is sorted.This is the main complication introduced by duplicates.Key Idea to Handle DuplicatesWhen the values at left, mid, and right are the same, the algorithm cannot decide which half is sorted.To resolve this situation, we shrink the search space:left++right--This gradually removes duplicate values and allows binary search to continue.Modified Binary Search StrategyThe algorithm works as follows:Step 1Calculate the middle index.Step 2If the middle element equals the target:return trueStep 3If duplicates block decision-making:nums[left] == nums[mid] == nums[right]Then move both pointers inward:left++right--Step 4Otherwise, determine which half is sorted and apply normal binary search logic.Java Implementationclass Solution { public boolean search(int[] nums, int target) { int l = 0; int r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] == target) return true; // Handle duplicates if (nums[l] == nums[mid] && nums[mid] == nums[r]) { l++; r--; } // Left half sorted else if (nums[l] <= nums[mid]) { if (nums[l] <= target && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } // Right half sorted else { if (nums[mid] < target && target <= nums[r]) { l = mid + 1; } else { r = mid - 1; } } } return false; }}Step-by-Step ExampleArray:[2,5,6,0,0,1,2]target = 0Iteration 1mid = 6value = 0Target found immediately.return trueTime ComplexityBest CaseO(log n)When duplicates do not interfere with binary search decisions.Worst CaseO(n)When many duplicate values force the algorithm to shrink the search space one element at a time.Example worst case:[1,1,1,1,1,1,1,1,1]Binary search cannot divide the array effectively.Space ComplexityO(1)The algorithm only uses a few variables and does not require extra memory.Follow-Up: How Do Duplicates Affect Runtime?Without duplicates, binary search always reduces the search space by half.Time Complexity → O(log n)With duplicates, we sometimes cannot determine which half is sorted.In such cases, we shrink the search space linearly:left++right--This may degrade performance to:Worst Case → O(n)However, in most practical cases the algorithm still performs close to logarithmic time.Key Takeaways✔ The array is sorted but rotated✔ Duplicates introduce ambiguity in binary search✔ Special handling is required when nums[left] == nums[mid] == nums[right]✔ The algorithm combines binary search with duplicate handling✔ Worst-case complexity may degrade to O(n)Final ThoughtsThis problem is a natural extension of the rotated sorted array search problem. It tests your ability to adapt binary search to more complex conditions.Understanding this pattern is valuable because similar techniques appear in many interview problems involving:Rotated arraysBinary search edge casesHandling duplicates in sorted data structuresMastering this approach strengthens both algorithmic thinking and interview preparation.

LeetCodeBinary SearchRotated Sorted ArrayJavaMedium

LeetCode 123 — Best Time to Buy and Sell Stock III | At Most Two Transactions Explained

🚀 Try This Problem First!Before reading the solution, attempt it yourself on LeetCode — you will learn much more that way.🔗 Problem Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/What Is the Problem Asking?You have a list of stock prices, one for each day. You are allowed to buy and sell the stock, but with one important restriction — you can make at most two transactions in total. A transaction means one buy followed by one sell.You cannot hold two stocks at the same time, meaning you must sell whatever you are holding before you buy again.Your job is to find the maximum profit you can make by doing at most two transactions. If there is no way to make any profit, return 0.Example to build intuition: prices = [3, 3, 5, 0, 0, 3, 1, 4]If you buy on day 4 (price 0) and sell on day 6 (price 3), profit = 3. Then buy on day 7 (price 1) and sell on day 8 (price 4), profit = 3. Total profit = 6. That is the best you can do.Constraints:1 ≤ prices.length ≤ 10⁵0 ≤ prices[i] ≤ 10⁵Why Is This Harder Than the Previous Stock Problems?In LeetCode 121, you could only make one transaction — so you just found the best single buy-sell pair.In LeetCode 122, you could make unlimited transactions — so you greedily collected every upward price movement.Here, you are limited to exactly two transactions. Greedy does not work anymore because sometimes skipping a small profit early on allows you to make a much bigger combined profit across two trades. You need a smarter strategy.The Big Idea Behind the SolutionHere is a simple way to think about it.If you are allowed two transactions, you can imagine drawing a dividing line somewhere in the price array. The first transaction happens entirely on the left side of that line. The second transaction happens entirely on the right side.So the problem becomes:For every possible dividing position, find the best profit on the left side and the best profit on the right side.Add them together.The maximum sum across all dividing positions is your answer.The challenge is doing this efficiently without checking every position with a nested loop, which would be O(N²) and too slow.Approach 1 — Left-Right Prefix DPThe idea:Instead of trying every split point from scratch, precompute the answers in advance.Build a leftProfit array where leftProfit[i] stores the best single transaction profit you can make using prices from day 0 to day i.Build a rightProfit array where rightProfit[i] stores the best single transaction profit you can make using prices from day i to the last day.Then for every index i, the answer if you split at i is simply leftProfit[i] + rightProfit[i]. Take the maximum across all indices.How to build leftProfit:Go left to right. Keep track of the minimum price seen so far. At each day i, the best profit you could make ending at or before day i is either the same as the day before, or selling today at today's price minus the minimum price seen so far. Take whichever is larger.How to build rightProfit:Go right to left. Keep track of the maximum price seen so far from the right. At each day i, the best profit you could make starting at or after day i is either the same as the day after, or buying today at today's price and selling at the maximum price seen to the right. Take whichever is larger.Dry Run — prices = [3, 3, 5, 0, 0, 3, 1, 4]Building leftProfit left to right, tracking minimum price seen:Day 0 → min=3, leftProfit[0] = 0 (nothing to compare yet) Day 1 → min=3, best profit = 3-3 = 0, leftProfit[1] = max(0, 0) = 0 Day 2 → min=3, best profit = 5-3 = 2, leftProfit[2] = max(0, 2) = 2 Day 3 → min=0, best profit = 0-0 = 0, leftProfit[3] = max(2, 0) = 2 Day 4 → min=0, best profit = 0-0 = 0, leftProfit[4] = max(2, 0) = 2 Day 5 → min=0, best profit = 3-0 = 3, leftProfit[5] = max(2, 3) = 3 Day 6 → min=0, best profit = 1-0 = 1, leftProfit[6] = max(3, 1) = 3 Day 7 → min=0, best profit = 4-0 = 4, leftProfit[7] = max(3, 4) = 4leftProfit = [0, 0, 2, 2, 2, 3, 3, 4]Building rightProfit right to left, tracking maximum price seen:Day 7 → max=4, rightProfit[7] = 0 (nothing to compare yet) Day 6 → max=4, best profit = 4-1 = 3, rightProfit[6] = max(0, 3) = 3 Day 5 → max=4, best profit = 4-3 = 1, rightProfit[5] = max(3, 1) = 3 Day 4 → max=4, best profit = 4-0 = 4, rightProfit[4] = max(3, 4) = 4 Day 3 → max=4, best profit = 4-0 = 4, rightProfit[3] = max(4, 4) = 4 Day 2 → max=5, best profit = 5-5 = 0, rightProfit[2] = max(4, 0) = 4 Day 1 → max=5, best profit = 5-3 = 2, rightProfit[1] = max(4, 2) = 4 Day 0 → max=5, best profit = 5-3 = 2, rightProfit[0] = max(4, 2) = 4rightProfit = [4, 4, 4, 4, 4, 3, 3, 0]Combining at each index: Index 0 → 0 + 4 = 4 Index 1 → 0 + 4 = 4 Index 2 → 2 + 4 = 6 Index 3 → 2 + 4 = 6 Index 4 → 2 + 4 = 6 Index 5 → 3 + 3 = 6 Index 6 → 3 + 3 = 6 Index 7 → 4 + 0 = 4Maximum = 6 ✅Implementation code:class Solution { public int maxProfit(int[] prices) { int lefProf[] = new int[prices.length]; int rigProf[] = new int[prices.length]; int j = 1; int i = 0; int coL = 1; while (i < j && j < prices.length) { if (prices[i] > prices[j]) { i = j; if (coL - 1 != -1) { lefProf[coL] = lefProf[coL - 1]; } coL++; } else { int max = prices[j] - prices[i]; if (coL - 1 != -1) { lefProf[coL] = Math.max(lefProf[coL - 1], max); coL++; } else { lefProf[coL] = max; coL++; } } j++; } int ii = prices.length - 2; int jj = prices.length - 1; int coR = prices.length - 2; while (ii >= 0) { if (prices[ii] > prices[jj]) { jj = ii; if (coR + 1 < prices.length) { rigProf[coR] = rigProf[coR + 1]; } coR--; } else { int max = prices[jj] - prices[ii]; if (coR + 1 < prices.length) { rigProf[coR] = Math.max(rigProf[coR + 1], max); coR--; } else { rigProf[coR] = max; coR--; } } ii--; } int maxAns = 0; for (int k = 0; k < lefProf.length; k++) { maxAns = Math.max(maxAns, lefProf[k] + rigProf[k]); } return maxAns; }}The approach here is exactly right. You are building the left and right profit arrays using a two pointer scanning technique — the same idea as LeetCode 121 but applied twice, once going forward and once going backward. The manual counters coL and coR make it a bit harder to follow, but the logic underneath is solid.Here is the same approach written in a cleaner way so it is easier to read and debug:class Solution { public int maxProfit(int[] prices) { int n = prices.length; int[] leftProfit = new int[n]; int[] rightProfit = new int[n]; int minPrice = prices[0]; for (int i = 1; i < n; i++) { minPrice = Math.min(minPrice, prices[i]); leftProfit[i] = Math.max(leftProfit[i - 1], prices[i] - minPrice); } int maxPrice = prices[n - 1]; for (int i = n - 2; i >= 0; i--) { maxPrice = Math.max(maxPrice, prices[i]); rightProfit[i] = Math.max(rightProfit[i + 1], maxPrice - prices[i]); } int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = Math.max(maxProfit, leftProfit[i] + rightProfit[i]); } return maxProfit; }}Time Complexity: O(N) — three separate linear passes through the array. Space Complexity: O(N) — two extra arrays of size N.Approach 2 — Four Variable State Machine DPThe idea:Instead of building arrays, what if you could track everything in just four variables and solve it in a single pass?Think about what is happening at any point in time as you go through the prices. You are always in one of these situations:You have bought your first stock and are currently holding it. You have sold your first stock and are sitting on that profit. You have bought your second stock (using the profit from the first sale) and are holding it. You have sold your second stock and collected your total profit.These four situations are your four states. For each one, you always want to know — what is the best possible profit I could have in this state up to today?Here is how each state updates as you look at a new price:buy1 — This represents the best outcome after buying the first stock. Buying costs money, so this is negative. As you see each new price, you ask: is it better to have bought on some earlier day, or to buy today? You keep whichever gives you the least cost, which means the highest value of negative price.sell1 — This represents the best profit after completing the first transaction. As you see each new price, you ask: is it better to have sold on some earlier day, or to sell today using the best buy1 we have? Selling today means adding today's price on top of buy1.buy2 — This represents the best outcome after buying the second stock. The key insight here is that you are not starting from zero — you already have the profit from the first transaction in your pocket. So buying the second stock costs today's price but you subtract it from sell1. As you see each new price, you ask: is it better to have bought the second stock earlier, or to buy today using the profit from sell1?sell2 — This is your final answer. It represents the best total profit after completing both transactions. As you see each new price, you ask: is it better to have completed both transactions earlier, or to sell the second stock today using the best buy2 we have?The beautiful thing is that all four updates happen in order on every single day, in one pass through the array. Each variable feeds into the next — buy1 feeds sell1, sell1 feeds buy2, buy2 feeds sell2.Dry Run — prices = [3, 3, 5, 0, 0, 3, 1, 4]We start with buy1 and buy2 as very negative (not yet bought anything) and sell1 and sell2 as 0 (no profit yet).Day 0, price = 3: buy1 = max(-∞, -3) = -3. Best cost to buy first stock is spending 3. sell1 = max(0, -3+3) = 0. Selling immediately gives no profit. buy2 = max(-∞, 0-3) = -3. Best cost to buy second stock after first sale is 3. sell2 = max(0, -3+3) = 0. No total profit yet.Day 1, price = 3: Nothing changes — same price as day 0.Day 2, price = 5: buy1 = max(-3, -5) = -3. Still best to have bought at price 3. sell1 = max(0, -3+5) = 2. Selling today at 5 after buying at 3 gives profit 2. buy2 = max(-3, 2-5) = -3. Buying second stock today costs too much relative to first profit. sell2 = max(0, -3+5) = 2. Completing both trades gives 2 so far.Day 3, price = 0: buy1 = max(-3, -0) = 0. Buying today at price 0 is the best possible first buy. sell1 = max(2, 0+0) = 2. Selling today at 0 gives nothing — keep the 2 from before. buy2 = max(-3, 2-0) = 2. Using the profit of 2 and buying today at 0 gives buy2 = 2. sell2 = max(2, 2+0) = 2. Selling second stock today at 0 gives nothing extra.Day 4, price = 0: Nothing changes — same price as day 3.Day 5, price = 3: buy1 = max(0, -3) = 0. Still best to have bought at price 0. sell1 = max(2, 0+3) = 3. Selling today at 3 after buying at 0 gives profit 3. buy2 = max(2, 3-3) = 2. Buying second stock today at 3 using sell1=3 gives 0. Keep 2. sell2 = max(2, 2+3) = 5. Selling second stock today at 3 after buy2=2 gives total 5.Day 6, price = 1: buy1 = max(0, -1) = 0. Still best to have bought at 0. sell1 = max(3, 0+1) = 3. Selling today at 1 gives less than 3 — no change. buy2 = max(2, 3-1) = 2. Buying second stock at 1 using sell1=3 gives 2 — same as before. sell2 = max(5, 2+1) = 5. No improvement yet.Day 7, price = 4: buy1 = max(0, -4) = 0. No change. sell1 = max(3, 0+4) = 4. Selling today at 4 after buying at 0 gives profit 4 — new best. buy2 = max(2, 4-4) = 2. No improvement. sell2 = max(5, 2+4) = 6. Selling second stock today at 4 with buy2=2 gives total 6 — new best.Output: 6 ✅class Solution { public int maxProfit(int[] prices) { int buy1 = Integer.MIN_VALUE; int sell1 = 0; int buy2 = Integer.MIN_VALUE; int sell2 = 0; for (int price : prices) { buy1 = Math.max(buy1, -price); sell1 = Math.max(sell1, buy1 + price); buy2 = Math.max(buy2, sell1 - price); sell2 = Math.max(sell2, buy2 + price); } return sell2; }}Time Complexity: O(N) — single pass through the array. Space Complexity: O(1) — only four integer variables, no extra arrays.Approach 3 — Generalizing to At Most K TransactionsOnce you understand Approach 2, there is a natural question — what if instead of two transactions, you were allowed K transactions? That is exactly LeetCode 188.Instead of four hardcoded variables, you use two arrays of size K. buy[j] tracks the best outcome after the j-th buy and sell[j] tracks the best outcome after the j-th sell. The logic is identical to Approach 2, just in a loop.For this problem set K = 2 and it gives the same answer:class Solution { public int maxProfit(int[] prices) { int k = 2; int[] buy = new int[k]; int[] sell = new int[k]; Arrays.fill(buy, Integer.MIN_VALUE); for (int price : prices) { for (int j = 0; j < k; j++) { buy[j] = Math.max(buy[j], (j == 0 ? 0 : sell[j - 1]) - price); sell[j] = Math.max(sell[j], buy[j] + price); } } return sell[k - 1]; }}Time Complexity: O(N × K) — for K=2 this is effectively O(N). Space Complexity: O(K) — two small arrays of size K.If you understand this, LeetCode 188 becomes a five minute problem.Comparing All Three ApproachesApproach 1 — Left-Right Prefix DP (Your Approach)You build two arrays — one scanning left to right, one scanning right to left — and combine them. This is the most visual and intuitive approach. It is easy to explain because you are essentially solving LeetCode 121 twice from opposite ends and adding the results. The downside is it uses O(N) extra space for the two arrays.Approach 2 — Four Variable State MachineYou solve the entire problem in a single pass using just four variables. No arrays, no extra memory. This is the most efficient and elegant solution. Once you understand what each variable represents, the code almost writes itself. This is what most interviewers are hoping to see.Approach 3 — General K-Transaction DPThis is Approach 2 extended to handle any number of transactions using arrays instead of hardcoded variables. Solving LeetCode 123 with this approach means you have already solved LeetCode 188 as a bonus.Mistakes That Catch Most PeopleTrying to use the greedy approach from LeetCode 122: Adding every upward price movement does not work when you are limited to two transactions. You need to pick the two best non-overlapping windows, not collect everything.Buying twice without selling in between: The state machine prevents this naturally — buy2 depends on sell1, so you can never enter the second buy before completing the first sell.Initializing buy variables to 0: Both buy1 and buy2 must start at Integer.MIN_VALUE. Setting them to 0 implies you bought a stock for free, which is wrong and will give inflated profits.Returning the wrong variable: Always return sell2, not buy2 or sell1. sell2 is the only variable that represents a completed two-transaction profit.Where This Fits in the Stock SeriesLeetCode 121 — One transaction only. Find the single best buy-sell pair. [ Blog is also avaliable on this - Read Now ]LeetCode 122 — Unlimited transactions. Collect every upward price movement greedily. [ Blog is also avaliable on this - Read Now ]LeetCode 188 — At most K transactions. Direct extension of Approach 3 above.LeetCode 309 — Unlimited transactions but with a cooldown day after every sale.LeetCode 714 — Unlimited transactions but with a fee charged on every transaction.Each problem adds one new constraint on top of the previous one. If you understand LeetCode 123 deeply — especially Approach 2 — every other problem in this series becomes a small modification of the same framework.Key Takeaways✅ When you are limited to two transactions, greedy fails. You need to find two non-overlapping windows that together give maximum profit.✅ The left-right prefix DP approach is the most intuitive — precompute the best single transaction from both ends, then combine at every split point.✅ The four variable state machine solves it in one pass with O(1) space. Each variable tracks the best outcome for one state — buy1 feeds sell1, sell1 feeds buy2, buy2 feeds sell2.✅ Always initialize buy variables to Integer.MIN_VALUE to represent "not yet bought anything."✅ Understanding Approach 3 here means LeetCode 188 is already solved — just change the hardcoded 2 to K.Happy Coding! This problem is the turning point in the stock series where DP becomes unavoidable — once you crack it, the rest of the series feels manageable. 🚀

LeetCodeDynamic ProgrammingHardJavaDSAPrefix DPArraysStock Series

Stack Problems Explained: NGR, NGL, NSR, NSL — The Four-Problem Family You Must Master

IntroductionAmong all the problems built around the Stack data structure, four stand out as a family — they appear repeatedly in coding interviews, competitive programming, and real-world software systems. These four are the Next Greater to the Right (NGR), Next Greater to the Left (NGL), Next Smaller to the Right (NSR), and Next Smaller to the Left (NSL).What makes them special is not just their individual solutions — it is the fact that all four are solved by a single elegant technique called the Monotonic Stack. Learn the pattern once, and you have all four in your toolkit permanently.This guide breaks down each problem with a full solution, step-by-step dry run, edge cases, and the exact reasoning behind every decision in the code. Whether you are preparing for a technical interview or simply want to deeply understand this pattern — you are in the right place.The Story That Makes This ClickBefore any code, let us understand this family of problems with one real-world story.Imagine you are standing in a queue at a cricket stadium. Everyone in the queue has a different height. You are standing somewhere in the middle. You look to your right and ask — who is the first person taller than me? That is your Next Greater Element to the Right (NGR).Now you look to your left — who is the first person taller than me on this side? That is your Next Greater to the Left (NGL).Now instead of taller, you ask shorter — who is the first shorter person to my right? That is Next Smaller to the Right (NSR).And shorter to your left? That is Next Smaller to the Left (NSL).Same queue. Same people. Four different questions. Four different answers. This is exactly what these four problems are about — and they all share the same solution pattern.What Is a Monotonic Stack?A monotonic stack is just a regular stack with one rule — elements inside it are always maintained in a specific order, either always increasing or always decreasing from bottom to top.You never enforce this rule explicitly. It happens naturally as you pop elements that violate the order before pushing a new one. This popping step is the key insight — the moment you pop an element, you have found its answer for the current element being processed.This one pattern solves all four problems. Only two small details change between them — the direction of traversal and the comparison condition inside the while loop.The Four Problems — Quick ReferenceProblemDirectionWhat You WantProblem LinksNGRTraverse Right to LeftFirst greater on right"Next Greater Element GFG"NGLTraverse Left to RightFirst greater on left"Previous Greater Element GFG"NSRTraverse Right to LeftFirst smaller on right"Next Smaller Element GFG"NSLTraverse Left to RightFirst smaller on left"Previous Smaller Element GFG"Problem 1 — Next Greater Element to Right (NGR)GFG Problem: Search "Next Greater Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 32.95% | Submissions: 515K+The QuestionFor each element in the array, find the first element to its right that is strictly greater than it. If none exists, return -1.Input: [1, 3, 2, 4] Output: [3, 4, 4, -1]Input: [6, 8, 0, 1, 3] Output: [8, -1, 1, 3, -1]Real World ExampleThink of the stock market. You have daily closing prices: [1, 3, 2, 4]. For each day, you want to know — on which future day will the price first exceed today's price? Day 1 has price 1, first exceeded on Day 2 with price 3. Day 2 has price 3, first exceeded on Day 4 with price 4. Day 3 has price 2, also first exceeded on Day 4 with price 4. Day 4 has no future day, so -1. This is exactly NGR — and it is literally used in financial software to detect price breakout points.The IntuitionThe brute force is obvious — for every element, scan everything to its right and find the first greater one. That works but it is O(n²). For an array of 10⁶ elements that becomes 10¹² operations. It will time out on any large input.The stack insight is this — traverse right to left. As you move left, the stack always holds elements you have already seen on the right side. These are the candidates for being the next greater element. Before pushing the current element, pop all stack elements that are smaller than or equal to it. Why? Because the current element is blocking them — for any future element to the left, the current element will always be encountered first, so those smaller popped elements can never be an answer for anything. Whatever remains on top of the stack after popping is the answer for the current element.Step-by-Step Dry RunArray: [1, 3, 2, 4], traversing right to left.i=3, element is 4. Stack is empty. Answer for index 3 is -1. Push 4. Stack: [4]i=2, element is 2. Top of stack is 4, which is greater than 2. Answer for index 2 is 4. Push 2. Stack: [4, 2]i=1, element is 3. Top of stack is 2, which is not greater than 3. Pop 2. Top is now 4, which is greater than 3. Answer for index 1 is 4. Push 3. Stack: [4, 3]i=0, element is 1. Top of stack is 3, which is greater than 1. Answer for index 0 is 3. Push 1. Stack: [4, 3, 1]Answers collected right to left: [-1, 4, 4, 3] After Collections.reverse(): [3, 4, 4, -1] ✓The Code// NGR — Next Greater Element to Rightclass Solution {public ArrayList<Integer> nextLargerElement(int[] arr) {ArrayList<Integer> result = new ArrayList<>();Stack<Integer> st = new Stack<>();// Traverse from RIGHT to LEFTfor (int i = arr.length - 1; i >= 0; i--) {// Pop all elements smaller than or equal to current// They can never be the answer for any element to the leftwhile (!st.empty() && arr[i] >= st.peek()) {st.pop();}// Whatever is on top now is the next greater elementif (st.empty()) {result.add(-1);} else {result.add(st.peek());}// Push current — it is a candidate for elements to the leftst.push(arr[i]);}// Collected answers right to left, so reverse before returningCollections.reverse(result);return result;}}Edge CasesAll elements decreasing — Input: [5, 4, 3, 2, 1] Output: [-1, -1, -1, -1, -1] Every element has no greater element to its right. Traversing right to left, each new element is larger than everything already in the stack, so the stack gets cleared and the answer is always -1.All elements increasing — Input: [1, 2, 3, 4, 5] Output: [2, 3, 4, 5, -1] Each element's next greater is simply the next element in the array. The last element always gets -1 since nothing exists to its right.All elements equal — Input: [3, 3, 3, 3] Output: [-1, -1, -1, -1] Equal elements do not count as greater. The pop condition uses >= so equals get removed from the stack, ensuring duplicates never answer each other.Single element — Input: [7] Output: [-1] Nothing to the right, always -1.Why only 32.95% accuracy on GFG? Most people either forget to reverse the result at the end, use the wrong comparison in the while loop, or submit a brute force O(n²) solution that times out on large inputs.Problem 2 — Next Greater Element to Left / Previous Greater Element (NGL)GFG Problem: Search "Previous Greater Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 68.93% | Submissions: 7K+The QuestionFor each element in the array, find the first element to its left that is strictly greater than it. If none exists, return -1.Input: [10, 4, 2, 20, 40, 12, 30] Output: [-1, 10, 4, -1, -1, 40, 40]Real World ExampleImagine you are a junior employee at a company. For each person in the office, you want to know — who is the first senior person sitting to their left who earns more? This is NGL. It is used in organizational hierarchy systems, salary band analysis tools, and even in database query optimizers to find the nearest dominant record on the left side.The IntuitionThis is the mirror image of NGR. Instead of traversing right to left, we traverse left to right. The stack holds elements we have already seen from the left side — these are candidates for being the previous greater element. For each new element, pop everything from the stack that is smaller than or equal to it. Whatever remains on top is the first greater element to its left. Then push the current element for future use.No reverse is needed here because we are already going left to right and building the result in order.Step-by-Step Dry RunArray: [10, 4, 2, 20, 40, 12, 30], traversing left to right.i=0, element is 10. Stack is empty. Answer is -1. Push 10. Stack: [10]i=1, element is 4. Top is 10, greater than 4. Answer is 10. Push 4. Stack: [10, 4]i=2, element is 2. Top is 4, greater than 2. Answer is 4. Push 2. Stack: [10, 4, 2]i=3, element is 20. Top is 2, not greater than 20. Pop 2. Top is 4, not greater. Pop 4. Top is 10, not greater. Pop 10. Stack is empty. Answer is -1. Push 20. Stack: [20]i=4, element is 40. Top is 20, not greater. Pop 20. Stack empty. Answer is -1. Push 40. Stack: [40]i=5, element is 12. Top is 40, greater than 12. Answer is 40. Push 12. Stack: [40, 12]i=6, element is 30. Top is 12, not greater than 30. Pop 12. Top is 40, greater than 30. Answer is 40. Push 30. Stack: [40, 30]Result: [-1, 10, 4, -1, -1, 40, 40] ✓ No reverse needed.The Code// NGL — Next Greater Element to Left (Previous Greater Element)class Solution {static ArrayList<Integer> preGreaterEle(int[] arr) {Stack<Integer> st = new Stack<>();ArrayList<Integer> result = new ArrayList<>();// Traverse LEFT to RIGHT — no reverse neededfor (int i = 0; i <= arr.length - 1; i++) {// Pop all elements smaller than or equal to currentwhile (!st.empty() && arr[i] >= st.peek()) {st.pop();}// Top of stack is the previous greater elementif (!st.empty() && st.peek() > arr[i]) {result.add(st.peek());} else {result.add(-1);}// Push current for future elementsst.push(arr[i]);}return result;}}Edge CasesStrictly increasing array — Input: [10, 20, 30, 40] Output: [-1, -1, -1, -1] Each new element is larger than everything before it, so the stack always gets fully cleared. No previous greater exists for any element.First element is always -1 — regardless of its value, the first element has nothing to its left. The stack is empty at i=0, so the answer is always -1 for index 0. This is guaranteed by the logic.Duplicate values — Input: [5, 5, 5] Output: [-1, -1, -1] Equal elements do not qualify as greater. The pop condition uses >= so duplicates get removed from the stack and never answer each other.Problem 3 — Next Smaller Element to Right (NSR)GFG Problem: Search "Next Smaller Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 36.26% | Submissions: 225K+The QuestionFor each element in the array, find the first element to its right that is strictly smaller than it. If none exists, return -1.Input: [4, 8, 5, 2, 25] Output: [2, 5, 2, -1, -1]Input: [13, 7, 6, 12] Output: [7, 6, -1, -1]Real World ExampleYou work at a warehouse. Shelves have items of weights: [4, 8, 5, 2, 25] kg. For each item, the system needs to find the first lighter item sitting to its right on the shelf — this is used to optimize load balancing and shelf arrangement algorithms. Item of 4 kg — first lighter to the right is 2 kg. Item of 8 kg — first lighter is 5 kg. Item of 5 kg — first lighter is 2 kg. Items of 2 kg and 25 kg have no lighter item to their right, so -1.The IntuitionNSR is structurally identical to NGR — we traverse right to left and collect answers, then reverse. The only change is the pop condition. In NGR we popped elements smaller than or equal to current because we wanted greater. Here we want smaller, so we pop elements greater than or equal to current. After popping, whatever remains on top is the first smaller element to the right.Step-by-Step Dry RunArray: [4, 8, 5, 2, 25], traversing right to left.i=4, element is 25. Stack is empty. Answer is -1. Push 25. Stack: [25]i=3, element is 2. Top is 25, which is greater than or equal to 2. Pop 25. Stack is empty. Answer is -1. Push 2. Stack: [2]i=2, element is 5. Top is 2, which is less than 5. Answer is 2. Push 5. Stack: [2, 5]i=1, element is 8. Top is 5, which is less than 8. Answer is 5. Push 8. Stack: [2, 5, 8]i=0, element is 4. Top is 8, which is greater than or equal to 4. Pop 8. Top is 5, which is greater than or equal to 4. Pop 5. Top is 2, which is less than 4. Answer is 2. Push 4. Stack: [2, 4]Answers collected right to left: [-1, -1, 2, 5, 2] After Collections.reverse(): [2, 5, 2, -1, -1] ✓The Code// NSR — Next Smaller Element to Rightclass Solution {static ArrayList<Integer> nextSmallerEle(int[] arr) {Stack<Integer> st = new Stack<>();ArrayList<Integer> result = new ArrayList<>();// Traverse RIGHT to LEFTfor (int i = arr.length - 1; i >= 0; i--) {// Pop elements greater than or equal to current// Opposite of NGR — we want smaller, so clear the bigger oneswhile (!st.empty() && arr[i] <= st.peek()) {st.pop();}// Top is now the next smaller elementif (!st.empty() && st.peek() < arr[i]) {result.add(st.peek());} else {result.add(-1);}st.push(arr[i]);}Collections.reverse(result);return result;}}Edge CasesStrictly decreasing array — Input: [5, 4, 3, 2, 1] Output: [4, 3, 2, 1, -1] Each element's next smaller is simply the next element in the array. Last element is always -1.Strictly increasing array — Input: [1, 2, 3, 4, 5] Output: [-1, -1, -1, -1, -1] No element has a smaller element to its right since the array only grows.Last element is always -1 — nothing exists to its right regardless of its value.Single element — Input: [42] Output: [-1]Why 36.26% accuracy on GFG? The most common mistake is keeping the NGR pop condition (arr[i] >= st.peek()) and only changing the problem description in your head. The pop condition must flip to arr[i] <= st.peek() for NSR. Forgetting this gives completely wrong answers that look plausible, which makes the bug hard to spot.Problem 4 — Next Smaller Element to Left / Previous Smaller Element (NSL)GFG Problem: Search "Previous Smaller Element" on GeeksForGeeksThe QuestionFor each element in the array, find the first element to its left that is strictly smaller than it. If none exists, return -1.Input: [4, 8, 5, 2, 25] Output: [-1, 4, 4, -1, 2]Real World ExampleSame warehouse. Now the system looks left instead of right. For the item weighing 8 kg, the first lighter item to its left is 4 kg. For 25 kg, the first lighter to its left is 2 kg. For 4 kg, nothing lighter exists to its left so -1. For 2 kg, nothing lighter to its left so -1. This kind of lookback query appears in time-series analysis, price history tracking, and sensor data processing.The IntuitionNSL is the mirror of NSR, exactly as NGL was the mirror of NGR. We traverse left to right (no reverse needed). We maintain a stack of candidates from the left. For each element, pop all elements greater than or equal to it — they cannot be the answer since they are not smaller. Whatever remains on top is the first smaller element to the left. Push current and move on.Step-by-Step Dry RunArray: [4, 8, 5, 2, 25], traversing left to right.i=0, element is 4. Stack is empty. Answer is -1. Push 4. Stack: [4]i=1, element is 8. Top is 4, which is less than 8. Answer is 4. Push 8. Stack: [4, 8]i=2, element is 5. Top is 8, which is greater than or equal to 5. Pop 8. Top is 4, which is less than 5. Answer is 4. Push 5. Stack: [4, 5]i=3, element is 2. Top is 5, greater than or equal to 2. Pop 5. Top is 4, greater than or equal to 2. Pop 4. Stack is empty. Answer is -1. Push 2. Stack: [2]i=4, element is 25. Top is 2, which is less than 25. Answer is 2. Push 25. Stack: [2, 25]Result: [-1, 4, 4, -1, 2] ✓ No reverse needed.The Code// NSL — Next Smaller Element to Left (Previous Smaller Element)class Solution {static ArrayList<Integer> prevSmallerEle(int[] arr) {Stack<Integer> st = new Stack<>();ArrayList<Integer> result = new ArrayList<>();// Traverse LEFT to RIGHT — no reverse neededfor (int i = 0; i < arr.length; i++) {// Pop elements greater than or equal to currentwhile (!st.empty() && arr[i] <= st.peek()) {st.pop();}// Top is the previous smaller elementif (!st.empty() && st.peek() < arr[i]) {result.add(st.peek());} else {result.add(-1);}st.push(arr[i]);}return result;}}Edge CasesFirst element is always -1 — nothing exists to its left. Stack is empty at i=0 every time.All same elements — Input: [5, 5, 5, 5] Output: [-1, -1, -1, -1] Equal elements do not qualify as smaller. The condition arr[i] <= st.peek() ensures equals are popped and never answer each other.Single element — Input: [9] Output: [-1]The Master Cheat SheetThis is the one table to save and refer to whenever you encounter any of these four problems.VariantTraverse DirectionPop ConditionReverse Result?NGR — Next Greater RightRight to Leftarr[i] >= st.peek()YesNGL — Next Greater LeftLeft to Rightarr[i] >= st.peek()NoNSR — Next Smaller RightRight to Leftarr[i] <= st.peek()YesNSL — Next Smaller LeftLeft to Rightarr[i] <= st.peek()NoTwo rules to remember forever:Rule 1 — Direction. If you are looking to the right, traverse right to left and reverse at the end. If you are looking to the left, traverse left to right and no reverse is needed.Rule 2 — Pop Condition. If you want a greater element, pop when arr[i] >= st.peek() to clear out smaller useless candidates. If you want a smaller element, pop when arr[i] <= st.peek() to clear out bigger useless candidates.Mix these two rules and you derive all four variants instantly without memorizing anything separately.Common Mistakes to AvoidWrong pop condition — Using > instead of >= in the while loop. This causes duplicate values to wrongly answer each other. Always use >= for greater problems and <= for smaller problems inside the while loop.Forgetting to reverse — For right-to-left traversals (NGR and NSR), you collect answers from right to left. You must call Collections.reverse() before returning. Skipping this is the single most common reason for wrong answers on these problems.Not checking empty stack before peek — Always check !st.empty() before calling st.peek(). An empty stack peek throws EmptyStackException at runtime and will crash your solution.Wrong if-condition after the while loop — After the while loop, the if-condition must use strict comparison. For NGR use st.peek() > arr[i]. For NSR use st.peek() < arr[i]. These must be strict — no equals sign here.Confusing traversal direction with answer direction — You traverse right to left for NGR but the answer array is filled left to right. The reverse at the end handles this. Do not try to index directly into the result array to compensate — just use reverse.Time and Space ComplexityAll four problems run in O(n) time and use O(n) space.Even though there is a while loop nested inside the for loop, each element is pushed into the stack exactly once and popped from the stack at most once. So across the entire traversal, the total number of push and pop operations combined is at most 2n — which gives O(n) overall. This is the beauty of the monotonic stack.Why These Four Problems Matter Beyond GFGThese four patterns are not just textbook exercises. They appear as the hidden sub-problem inside some of the hardest stack questions:-Largest Rectangle in Histogram uses NSR and NSL to find the left and right boundaries of each bar.Trapping Rain Water uses NGR and NGL to determine the water level above each position.Stock Span Problem is literally NGL applied directly to stock prices.Sum of Subarray Minimums uses NSR and NSL together to count contributions of each element.Once you master these four patterns deeply, a whole family of hard problems that previously seemed unapproachable suddenly becomes a matter of recognizing the pattern and applying it.Also on This BlogIf you are building your stack foundation from scratch, check out the complete deep-dive here → Stack Data Structure in Java: The Complete Guide — covering everything from what a stack is, LIFO principle, all three implementations, every operation with code, and six practice problems.

MonotonicStackNextGreaterElementStackProblemsJavaGeeksForGeeksStackPattern

Understanding HashMap and Hashing Techniques: A Complete Guide

What is HashMap?HashMap is a non-linear data structure that lives inside Java's collection framework, alongside other structures like Trees and Graphs (see the generated image above). What makes it special? It uses a clever technique called hashing to store and retrieve data at blazing speeds.Think of hashing as a smart address system. It converts large keys (like long strings or big numbers) into smaller values that work as array indices. This simple trick transforms your data lookup from slow O(n)O(n) or O(log⁡n)O(logn) operations into lightning-fast O(1)O(1) access times!Understanding Hashing MappingsBefore diving deeper, let's understand the four types of hashing mappings:One-to-one mapping — Each key maps to exactly one indexMany-to-one mapping — Multiple keys can map to the same indexOne-to-many mapping — One key maps to multiple indicesMany-to-many mapping — Multiple keys map to multiple indicesHashMap primarily uses one-to-one and many-to-one mapping strategies to achieve its performance goals.The Problem: Why Not Just Use Arrays?Let's say you want to store 7 elements with keys: 1, 5, 23, 57, 234, 678, and 1000.Using direct indexing (where key = array index), you'd need an array of size 1000 just to store 7 items! That leaves 993 empty slots wasting precious memory. Imagine having a parking lot with 1000 spaces for just 7 cars — totally inefficient!This is the exact problem hash functions solve.Hash Functions: The SolutionA hash function takes your key and calculates which array index to use. The beauty? You can now store those same 7 elements in an array of just size 10!The most common hash function uses the modulus operator:hash(key)=keymod array sizehash(key)=keymodarray sizeExample: With array size = 10:Key 57 → Index: 57mod 10=757mod10=7Key 234 → Index: 234mod 10=4234mod10=4Key 1000 → Index: 1000mod 10=01000mod10=0Now you only need an array of size 10 instead of 1000. Problem solved!Three Popular Hash Function TypesModulus MethodThe most widely used technique. Divide the key by array size (or a prime number) and use the remainder as the index.index=keymod sizeindex=keymodsizeMid Square MethodSquare the key value, then extract the middle digits to form your hash value.Example: Key = 57 → 572=3249572=3249 → Extract middle digits "24"Folding HashingDivide the key into equal parts, add them together, then apply modulus.Example: Key = 123456Split into: 12, 34, 56Sum: 12+34+56=10212+34+56=102Apply modulus: 102mod 10=2102mod10=2The Collision ProblemHere's the catch: sometimes two different keys produce the same index. This is called a collision.Example:Key 27 → 27mod 10=727mod10=7Key 57 → 57mod 10=757mod10=7Both keys want index 7! We need smart strategies to handle this.Collision Resolution: Two Main TechniquesTechnique 1: Open Chaining (Separate Chaining)Mapping Type: Many-to-oneWhen a collision happens, create a linked list at that index and store all colliding values in sorted order.Example: Keys 22 and 32 both map to index 2:Index 2: [22] → [32] → nullAdvantage: Simple and works well in practiceDrawback: If too many collisions occur, the linked list becomes long and searching degrades to O(n)O(n). However, Java's collection framework uses highly optimized hash functions that achieve amortized O(1)O(1) time complexity.Technique 2: Closed Addressing (Open Addressing)Mapping Type: One-to-manyInstead of creating a list, find another empty slot in the array. There are three approaches:Linear ProbingWhen collision occurs, check the next index. If it's occupied, keep checking the next one until you find an empty slot.Hash Function:h(x)=xmod sizeh(x)=xmodsizeOn Collision:h(x)=(h(x)+i)mod sizeh(x)=(h(x)+i)modsizewhere i=0,1,2,3,…i=0,1,2,3,…Example: Keys 22 and 32 both map to index 2:Store 22 at index 2Try 32 at index 2 → occupiedCheck index 3 → empty, store 32 thereProblems:Clustering: Keys bunch together in adjacent indices, slowing down searchesDeleted Slot Problem: When you delete a key, it creates an empty slot that breaks the search chainThe Deleted Slot Problem Explained:Keys 22 and 32 are at indices 2 and 3Delete key 22 from index 2Now when searching for key 32, the algorithm reaches index 2 (empty), thinks key 32 doesn't exist, and stops searching!Solution: Mark deleted slots with a special marker (like -1) or perform rehashing after deletions.Quadratic ProbingSame concept as linear probing, but instead of checking consecutive slots, jump in quadratic increments: 1, 4, 9, 16, 25...Hash Function:h(x)=xmod sizeh(x)=xmodsizeOn Collision:h(x)=(h(x)+i2)mod sizeh(x)=(h(x)+i2)modsizewhere i=0,1,2,3,…i=0,1,2,3,…Advantage: Significantly reduces clusteringDrawback: Still suffers from the deleted slot problemDouble HashingThe most sophisticated approach! Uses two different hash functions to create unique probe sequences for each key.First Hash Function:h1(x)=xmod sizeh1(x)=xmodsizeSecond Hash Function:h2(x)=prime−(xmod prime)h2(x)=prime−(xmodprime)On Collision:h(x)=(h1(x)+i×h2(x))mod sizeh(x)=(h1(x)+i×h2(x))modsizewhere i=0,1,2,3,…i=0,1,2,3,…Advantage: Effectively avoids clustering and provides the best performance among probing techniquesLoad Factor: The Performance IndicatorThe load factor tells you how full your hash table is:Load Factor=Number of elementsArray sizeLoad Factor=Array sizeNumber of elementsPerformance GuidelinesLoad Factor ≤ 0.5 → Good performance, fast operations Load Factor > 0.7 → Poor performance, time to rehash ExamplesBad Load Factor:Array size = 10, Elements = 8Load Factor = 8/10=0.88/10=0.8Action: Rehash the array (typically double the size)Good Load Factor:Array size = 200, Elements = 100Load Factor = 100/200=0.5100/200=0.5Action: No changes needed, performing optimallyWhat is Rehashing?When the load factor exceeds the threshold (usually 0.7), the hash table is resized — typically doubled in size. All existing elements are then rehashed and redistributed into the new larger array. This maintains optimal performance as your data grows.Performance SummaryHashMap delivers exceptional average-case performance:Insertion: O(1)O(1)Deletion: O(1)O(1)Search: O(1)O(1)However, in the worst case (many collisions with poor hash functions), operations can degrade to O(n)O(n).The key to maintaining O(1)O(1) performance:Use a good hash functionChoose an appropriate collision resolution strategyMonitor and maintain a healthy load factorRehash when necessaryConclusionHashMap is one of the most powerful and frequently used data structures in programming. By understanding hashing techniques, collision resolution strategies, and load factors, you can write more efficient code and make better design decisions.Whether you're building a cache, implementing a frequency counter, or solving complex algorithm problems, HashMap is your go-to tool for fast data access!

hashmapdata-structureshashingjavaalgorithmscollision-resolutiontime-complexity

LeetCode 1365: How Many Numbers Are Smaller Than the Current Number | Java Solution, Intuition, Dry Run & Complexity Analysis

IntroductionIn this problem, we are given an integer array nums.For every element in the array, we must calculate how many numbers are smaller than the current number.The result should be stored in another array where:Each index contains the count of smaller numbersComparison must be done against every other elementWe cannot count the element itselfThis is a beginner-friendly array problem that teaches comparison logic and nested loop thinking.Problem StatementGiven the array nums, return an array answer such that:answer[i] = count of numbers smaller than nums[i]Question LinkProblem Link -: Leetcode 1365ExampleInputnums = [8,1,2,2,3]Output[4,0,1,1,3]Explanation8 → four smaller numbers → 1,2,2,31 → no smaller number2 → one smaller number → 12 → one smaller number → 13 → three smaller numbers → 1,2,2Understanding the ProblemWe need to check:For every element:How many values in the array are smaller than it?This means:Compare one number with all other numbersCount valid smaller valuesStore count in answer arrayIntuitionThe simplest idea is:Pick one numberCompare it with every elementCount smaller numbersSave resultRepeat for all indicesSince constraints are small:nums.length <= 500Brute force works perfectly.ApproachWe use two loops:Outer loop → selects current numberInner loop → compares with all numbersIf:nums[j] < nums[i]Then increase count.Java Solutionclass Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int i = 0; int j = 1; int ans[] = new int[nums.length]; int cou = 0; while(i < nums.length){ if(i != j && nums[i] > nums[j]){ cou++; } j++; if(j == nums.length){ ans[i] = cou; i++; cou = 0; j = 0; } } return ans; }}Code ExplanationVariablesiCurrent element index.jUsed for comparison.couStores count of smaller numbers.ans[]Final result array.Step-by-Step LogicStep 1Pick current number using:iStep 2Compare with every number using:jStep 3If another value is smaller:nums[i] > nums[j]Increase count.Step 4Store count.Step 5Move to next element.Dry RunInputnums = [8,1,2,2,3]First Element = 8Compare with:NumberSmaller?1Yes2Yes2Yes3YesCount = 4ans[0] = 4Second Element = 1No smaller number.ans[1] = 0Third Element = 2Smaller number:1Count = 1ans[2] = 1Final Answer[4,0,1,1,3]Time ComplexityWe compare every element with every other element.ComplexityO(N²)Because:Outer loop = NInner loop = NTotal:N × NSpace ComplexityWe only store output array.ComplexityO(N)Better Clean Version (Recommended)Your logic works, but interviewers usually prefer readable code.class Solution { public int[] smallerNumbersThanCurrent(int[] nums) { int n = nums.length; int[] ans = new int[n]; for(int i = 0; i < n; i++) { int count = 0; for(int j = 0; j < n; j++) { if(i != j && nums[j] < nums[i]) { count++; } } ans[i] = count; } return ans; }}Optimized ApproachSince:0 <= nums[i] <= 100We can use frequency counting.This gives:O(N + K)Where:N = array sizeK = range of valuesCommon Mistakes1. Comparing Same IndexWrong:nums[i] > nums[i]Correct:i != j2. Forgetting Reset CountWrong:count keeps increasingCorrect:count = 0after each iteration.3. Index Out Of BoundsAlways ensure:j < nums.lengthInterview TipsThis problem teaches:Nested loopsArray traversalCounting logicComparison problemsBrute force thinkingInterviewers may ask:Can you optimize it?Answer:Use counting sort or prefix frequency.FAQsIs this problem easy?Yes. It is beginner-friendly.Is brute force accepted?Yes.Constraints are small.Can we optimize?Yes.Using counting frequency array.Is this asked in interviews?Yes.Especially for beginners.Final ThoughtsLeetCode 1365 is a simple array problem that helps build strong fundamentals.You learn:How comparisons workHow nested loops solve counting problemsHow to convert logic into output arrays

LeetCodeEasyTwo PointerArrayJava

Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Try the QuestionBefore reading the explanation, try solving the problem yourself:👉 https://leetcode.com/problems/find-peak-element/Attempting the problem first helps develop algorithmic intuition, especially for binary search problems.Problem StatementYou are given a 0-indexed integer array nums.Your task is to find the index of a peak element.What is a Peak Element?A peak element is an element that is strictly greater than its immediate neighbors.For an element nums[i] to be a peak:nums[i] > nums[i-1]nums[i] > nums[i+1]However, the array boundaries have a special rule.Boundary RuleYou can imagine that:nums[-1] = -∞nums[n] = -∞This means:The first element only needs to be greater than the second element.The last element only needs to be greater than the second last element.Constraints1 <= nums.length <= 1000-2^31 <= nums[i] <= 2^31 - 1nums[i] != nums[i + 1] for all valid iImportant implications:Adjacent elements are never equal.The array always has at least one peak.Understanding the Problem with ExamplesExample 1Inputnums = [1,2,3,1]Visualization1 2 3 1^Here:3 > 23 > 1So 3 is a peak element.Output2(index of value 3)Example 2Inputnums = [1,2,1,3,5,6,4]Visualization1 2 1 3 5 6 4^ ^Possible peaks:26Valid outputs:1 or 5Either peak index is acceptable.Key ObservationsImportant facts about peak elements:Every array must contain at least one peak.If numbers keep increasing, the last element will be a peak.If numbers keep decreasing, the first element will be a peak.If the array has ups and downs, peaks exist in the middle.This guarantees a solution exists.Approach 1 — Linear Scan (Brute Force)The simplest approach is to check each element and see whether it satisfies the peak condition.AlgorithmTraverse the array.Check if the current element is greater than neighbors.Return the index if found.Examplenums = [1,2,3,1]Check:1 < 22 < 33 > 2 and 3 > 1 → PeakImplementationpublic int findPeakElement(int[] nums) {for(int i = 0; i < nums.length; i++){boolean left = (i == 0) || nums[i] > nums[i-1];boolean right = (i == nums.length-1) || nums[i] > nums[i+1];if(left && right){return i;}}return -1;}Time ComplexityO(n)Space ComplexityO(1)Although simple, this solution does not satisfy the required O(log n) complexity.Approach 2 — Binary Search Using Peak ConditionsInstead of scanning the entire array, we can use binary search.Key IdeaIf we are at index mid, compare it with the neighbors.Three situations may occur.Case 1 — Peak Foundnums[mid-1] < nums[mid] > nums[mid+1]Then:mid is the peakCase 2 — Increasing Slopenums[mid] < nums[mid+1]Example:1 3 5 7^This means the peak must exist on the right side.Move search to the right.Case 3 — Decreasing Slopenums[mid] < nums[mid-1]Example:7 5 3 1^Peak exists on the left side.Move search to the left.Implementationint i = 1;int j = nums.length - 2;while(i <= j){int mid = i + (j - i)/2;if(nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1]){return mid;}else if(nums[mid] < nums[mid+1]){i = mid + 1;}else{j = mid - 1;}}Time ComplexityO(log n)Space ComplexityO(1)Approach 3 — Optimized Binary Search (Most Elegant Solution)A simpler and more elegant version of binary search exists.Core IntuitionCompare:nums[mid]nums[mid + 1]Two possibilities exist.Case 1 — Increasing Slopenums[mid] < nums[mid+1]Example:1 2 3 4^The peak must exist on the right side.Move:left = mid + 1Case 2 — Decreasing Slopenums[mid] > nums[mid+1]Example:4 3 2 1^Peak exists on the left side including mid.Move:right = midThis gradually narrows down to the peak.Final Optimized Implementationclass Solution {public int findPeakElement(int[] nums) {int i = 0;int j = nums.length - 1;while(i < j){int mid = i + (j - i) / 2;if(nums[mid] < nums[mid + 1]){i = mid + 1;}else{j = mid;}}return i;}}Step-by-Step ExampleArray[1,2,1,3,5,6,4]Iteration 1mid = 3nums[mid] = 3nums[mid+1] = 5Increasing slope → move right.Iteration 2mid = 5nums[mid] = 6nums[mid+1] = 4Decreasing slope → move left.Eventually:peak index = 5Value:6Why This Binary Search WorksThe array behaves like a mountain landscape.Example visualization:/\/ \/ \__If you stand at mid:If the right side is higher, go right.If the left side is higher, go left.This guarantees that you will eventually reach a peak.Time ComplexityO(log n)Each iteration cuts the search space in half.Space ComplexityO(1)Only a few variables are used.Key Takeaways✔ A peak element is greater than its neighbors✔ The array always contains at least one peak✔ Binary search can be applied using slope comparison✔ The optimized solution only compares nums[mid] and nums[mid+1]✔ The final algorithm runs in O(log n) timeFinal ThoughtsThis problem is an excellent example of applying binary search beyond sorted arrays.Instead of searching for a value, binary search is used here to locate a structural property of the array (a peak).Understanding this pattern is extremely valuable because similar logic appears in many interview problems involving:Mountain arraysBitonic arraysOptimization search problemsMastering this approach will significantly improve your binary search problem-solving skills for technical interviews.

LeetCodeBinary SearchMediumJava

Stack Data Structure in Java: The Complete In-Depth Guide

1. What Is a Stack?A Stack is a linear data structure that stores elements in a sequential order, but with one strict rule — you can only insert or remove elements from one end, called the top.It is one of the simplest yet most powerful data structures in computer science. Its strength comes from its constraint. Because everything happens at one end, the behavior of a stack is completely predictable.The formal definition: A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle — the element inserted last is the first one to be removed.Here is what a stack looks like visually: ┌──────────┐ │ 50 │ ← TOP (last inserted, first removed) ├──────────┤ │ 40 │ ├──────────┤ │ 30 │ ├──────────┤ │ 20 │ ├──────────┤ │ 10 │ ← BOTTOM (first inserted, last removed) └──────────┘When you push 60 onto this stack, it goes on top. When you pop, 60 comes out first. That is LIFO.2. Real-World AnalogiesBefore writing a single line of code, it helps to see stacks in the real world. These analogies will make the concept permanently stick.A Pile of Plates In a cafeteria, clean plates are stacked on top of each other. You always pick the top plate. You always place a new plate on top. You never reach into the middle. This is a stack.Browser Back Button Every time you visit a new webpage, it gets pushed onto a history stack. When you press the Back button, the browser pops the most recent page off the stack and takes you there. The page you visited first is at the bottom — you only reach it after going back through everything else.Undo Feature in Text Editors When you type in a document and press Ctrl+Z, the most recent action is undone first. That is because every action you perform is pushed onto a stack. Undo simply pops from that stack.Call Stack in Programming When a function calls another function, the current function's state is pushed onto the call stack. When the inner function finishes, it is popped off and execution returns to the outer function. This is the literal stack your programs run on.A Stack of Books Put five books on a table, one on top of another. You can only take the top book without knocking the pile over. That is a stack.3. The LIFO Principle ExplainedLIFO stands for Last In, First Out.It means whatever you put in last is the first thing to come out. This is the exact opposite of a Queue (which is FIFO — First In, First Out).Let us trace through an example step by step:Start: Stack is empty → []Push 10 → [10] (10 is at the top)Push 20 → [10, 20] (20 is at the top)Push 30 → [10, 20, 30] (30 is at the top)Pop → returns 30 (30 was last in, first out) Stack: [10, 20]Pop → returns 20 Stack: [10]Peek → returns 10 (just looks, does not remove) Stack: [10]Pop → returns 10 Stack: [] (stack is now empty)Every single operation happens only at the top. The bottom of the stack is never directly accessible.4. Stack Operations & Time ComplexityA stack supports the following core operations:OperationDescriptionTime Complexitypush(x)Insert element x onto the top of the stackO(1)pop()Remove and return the top elementO(1)peek() / top()Return the top element without removing itO(1)isEmpty()Check if the stack has no elementsO(1)isFull()Check if the stack has reached its capacity (Array only)O(1)size()Return the number of elements in the stackO(1)search(x)Find position of element from top (Java built-in only)O(n)All primary stack operations — push, pop, peek, isEmpty — run in O(1) constant time. This is what makes the stack so efficient. It does not matter whether the stack has 10 elements or 10 million — these operations are always instant.Space complexity for a stack holding n elements is O(n).5. Implementation 1 — Using a Static ArrayThis is the most fundamental way to implement a stack. We use a fixed-size array and a variable called top to track where the top of the stack currently is.How it works:top starts at -1 (stack is empty)On push: increment top, then place the element at arr[top]On pop: return arr[top], then decrement topOn peek: return arr[top] without changing it// StackUsingArray.javapublic class StackUsingArray { private int[] arr; private int top; private int capacity; // Constructor — initialize with a fixed capacity public StackUsingArray(int capacity) { this.capacity = capacity; arr = new int[capacity]; top = -1; } // Push: add element to the top public void push(int value) { if (isFull()) { System.out.println("Stack Overflow! Cannot push " + value); return; } arr[++top] = value; System.out.println("Pushed: " + value); } // Pop: remove and return top element public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } return arr[top--]; } // Peek: view the top element without removing public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return arr[top]; } // Check if stack is empty public boolean isEmpty() { return top == -1; } // Check if stack is full public boolean isFull() { return top == capacity - 1; } // Return current size public int size() { return top + 1; } // Display all elements public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); for (int i = top; i >= 0; i--) { System.out.print(arr[i] + " "); } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingArray stack = new StackUsingArray(5); stack.push(10); stack.push(20); stack.push(30); stack.push(40); stack.push(50); stack.push(60); // This will trigger Stack Overflow stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 10Pushed: 20Pushed: 30Pushed: 40Pushed: 50Stack Overflow! Cannot push 60Stack (top → bottom): 50 40 30 20 10Peek: 50Pop: 50Pop: 40Stack (top → bottom): 30 20 10Size: 3Key Points about Array Implementation:Fixed size — you must declare capacity upfrontVery fast — direct array index accessStack Overflow is possible if capacity is exceededMemory is pre-allocated even if stack is not full6. Implementation 2 — Using an ArrayListAn ArrayList-based stack removes the fixed-size limitation. The ArrayList grows dynamically, so you never have to worry about stack overflow due to capacity.How it works:The end of the ArrayList acts as the topadd() is used for pushremove(size - 1) is used for popget(size - 1) is used for peek// StackUsingArrayList.javaimport java.util.ArrayList;public class StackUsingArrayList { private ArrayList<Integer> list; // Constructor public StackUsingArrayList() { list = new ArrayList<>(); } // Push: add to the end (which is our top) public void push(int value) { list.add(value); System.out.println("Pushed: " + value); } // Pop: remove and return the last element public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } int top = list.get(list.size() - 1); list.remove(list.size() - 1); return top; } // Peek: view the last element public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return list.get(list.size() - 1); } // Check if stack is empty public boolean isEmpty() { return list.isEmpty(); } // Return size public int size() { return list.size(); } // Display elements from top to bottom public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); for (int i = list.size() - 1; i >= 0; i--) { System.out.print(list.get(i) + " "); } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingArrayList stack = new StackUsingArrayList(); stack.push(5); stack.push(15); stack.push(25); stack.push(35); stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Is Empty: " + stack.isEmpty()); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 5Pushed: 15Pushed: 25Pushed: 35Stack (top → bottom): 35 25 15 5Peek: 35Pop: 35Pop: 25Stack (top → bottom): 15 5Is Empty: falseSize: 2Key Points about ArrayList Implementation:Dynamic size — grows automatically as neededNo overflow riskSlight overhead compared to raw array due to ArrayList internalsExcellent for most practical use cases7. Implementation 3 — Using a LinkedListA LinkedList-based stack is the most memory-efficient approach when you do not know the stack size in advance. Each element (node) holds data and a pointer to the next node. The head of the LinkedList acts as the top of the stack.How it works:Each node stores a value and a reference to the node below itPush creates a new node and makes it the new headPop removes the head node and returns its valuePeek returns the head node's value without removing it// StackUsingLinkedList.javapublic class StackUsingLinkedList { // Inner Node class private static class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } private Node top; // Head of the linked list = top of stack private int size; // Constructor public StackUsingLinkedList() { top = null; size = 0; } // Push: create new node and link it to top public void push(int value) { Node newNode = new Node(value); newNode.next = top; // new node points to current top top = newNode; // new node becomes the new top size++; System.out.println("Pushed: " + value); } // Pop: remove and return top node's data public int pop() { if (isEmpty()) { System.out.println("Stack Underflow! Stack is empty."); return -1; } int value = top.data; top = top.next; // move top pointer to next node size--; return value; } // Peek: return top node's data without removing public int peek() { if (isEmpty()) { System.out.println("Stack is empty."); return -1; } return top.data; } // Check if empty public boolean isEmpty() { return top == null; } // Return size public int size() { return size; } // Display elements from top to bottom public void display() { if (isEmpty()) { System.out.println("Stack is empty."); return; } System.out.print("Stack (top → bottom): "); Node current = top; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } // Main method to test public static void main(String[] args) { StackUsingLinkedList stack = new StackUsingLinkedList(); stack.push(100); stack.push(200); stack.push(300); stack.push(400); stack.display(); System.out.println("Peek: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Pop: " + stack.pop()); stack.display(); System.out.println("Size: " + stack.size()); }}```**Output:**```Pushed: 100Pushed: 200Pushed: 300Pushed: 400Stack (top → bottom): 400 300 200 100Peek: 400Pop: 400Pop: 300Stack (top → bottom): 200 100Size: 2Key Points about LinkedList Implementation:Truly dynamic — each node allocated only when neededNo wasted memory from pre-allocationSlightly more memory per element (each node carries a pointer)Ideal for stacks where size is completely unknown8. Java's Built-in Stack ClassJava provides a ready-made Stack class inside java.util. It extends Vector and is thread-safe by default.// JavaBuiltinStack.javaimport java.util.Stack;public class JavaBuiltinStack { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); // Push elements stack.push(10); stack.push(20); stack.push(30); stack.push(40); System.out.println("Stack: " + stack); // Peek — look at top without removing System.out.println("Peek: " + stack.peek()); // Pop — remove top System.out.println("Pop: " + stack.pop()); System.out.println("After pop: " + stack); // Search — returns 1-based position from top System.out.println("Search 20: position " + stack.search(20)); // isEmpty System.out.println("Is Empty: " + stack.isEmpty()); // Size System.out.println("Size: " + stack.size()); }}```**Output:**```Stack: [10, 20, 30, 40]Peek: 40Pop: 40After pop: [10, 20, 30]Search 20: position 2Is Empty: falseSize: 3Important Note: In modern Java development, it is often recommended to use Deque (specifically ArrayDeque) instead of Stack for better performance, since Stack is synchronized and carries the overhead of Vector.// Using ArrayDeque as a stack (modern preferred approach)import java.util.ArrayDeque;import java.util.Deque;public class ModernStack { public static void main(String[] args) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(10); // pushes to front stack.push(20); stack.push(30); System.out.println("Top: " + stack.peek()); System.out.println("Pop: " + stack.pop()); System.out.println("Stack: " + stack); }}9. Comparison of All ImplementationsFeatureArrayArrayListLinkedListJava StackArrayDequeSizeFixedDynamicDynamicDynamicDynamicStack Overflow RiskYesNoNoNoNoMemory UsagePre-allocatedAuto-growsPer-node overheadAuto-growsAuto-growsPush TimeO(1)O(1) amortizedO(1)O(1)O(1)Pop TimeO(1)O(1)O(1)O(1)O(1)Peek TimeO(1)O(1)O(1)O(1)O(1)Thread SafeNoNoNoYesNoBest ForKnown size, max speedGeneral useUnknown/huge sizeLegacy codeModern Java10. Advantages & DisadvantagesAdvantagesAdvantageExplanationSimple to implementVery few rules and operations to worry aboutO(1) operationsPush, pop, and peek are all constant timeMemory efficientNo extra pointers needed (array-based)Supports recursionThe call stack is itself a stackEasy undo/redoNatural fit for reversible action trackingBacktrackingPerfectly suited for maze, puzzle, and game solvingExpression evaluationPowers compilers and calculatorsDisadvantagesDisadvantageExplanationLimited accessCannot access elements in the middle directlyFixed size (array)Array-based stacks overflow if size is exceededNo random accessYou cannot do stack[2] — only top is accessibleMemory waste (array)Pre-allocated array wastes space if underusedNot suitable for all problemsMany problems need queues, trees, or graphs insteadStack overflow in recursionVery deep recursion can overflow the JVM call stack11. Real-World Use Cases of StackUnderstanding when to use a stack is just as important as knowing how to implement one. Here is where stacks show up in real software:Function Call Management (Call Stack) Every time your Java program calls a method, the JVM pushes that method's frame onto the call stack. When the method returns, the frame is popped. This is why you see "StackOverflowError" when you write infinite recursion.Undo and Redo Operations Text editors, image editors (Photoshop), and IDEs use two stacks — one for undo history and one for redo history. Every action pushes onto the undo stack. Ctrl+Z pops from it and pushes to the redo stack.Browser Navigation Your browser maintains a back-stack and a forward-stack. Visiting a new page pushes to the back-stack. Pressing Back pops from it and pushes to the forward-stack.Expression Evaluation and Conversion Compilers use stacks to evaluate arithmetic expressions and convert between infix, prefix, and postfix notations. For example: 3 + 4 * 2 must be evaluated considering operator precedence — this is done with a stack.Balanced Parentheses Checking Linters, compilers, and IDEs use stacks to check if brackets are balanced: {[()]} is valid, {[(])} is not.Backtracking Algorithms Maze solving, N-Queens, Sudoku solvers, and depth-first search all use stacks (explicitly or via recursion) to backtrack to previous states when a path fails.Syntax Parsing Compilers parse source code using stacks to match opening and closing constructs like if/else, try/catch, { and }.12. Practice Problems with Full SolutionsHere is where things get really interesting. These problems will sharpen your stack intuition and prepare you for coding interviews.Problem 1 — Reverse a String Using a StackDifficulty: EasyProblem: Write a Java program to reverse a string using a Stack.Approach: Push every character of the string onto a stack, then pop them all. Since LIFO reverses the order, the characters come out reversed.// ReverseString.javaimport java.util.Stack;public class ReverseString { public static String reverse(String str) { Stack<Character> stack = new Stack<>(); // Push all characters for (char c : str.toCharArray()) { stack.push(c); } // Pop all characters to build reversed string StringBuilder reversed = new StringBuilder(); while (!stack.isEmpty()) { reversed.append(stack.pop()); } return reversed.toString(); } public static void main(String[] args) { System.out.println(reverse("hello")); // olleh System.out.println(reverse("java")); // avaj System.out.println(reverse("racecar")); // racecar (palindrome) System.out.println(reverse("datastructure")); // erutcurtasatad }}Problem 2 — Check Balanced ParenthesesDifficulty: Easy–MediumProblem: Given a string containing (, ), {, }, [, ], determine if the brackets are balanced.Approach: Push every opening bracket onto the stack. When you see a closing bracket, check if it matches the top of the stack. If it does, pop. If it does not, the string is unbalanced.// BalancedParentheses.javaimport java.util.Stack;public class BalancedParentheses { public static boolean isBalanced(String expr) { Stack<Character> stack = new Stack<>(); for (char c : expr.toCharArray()) { // Push all opening brackets if (c == '(' || c == '{' || c == '[') { stack.push(c); } // For closing brackets, check the top of stack else if (c == ')' || c == '}' || c == ']') { if (stack.isEmpty()) return false; char top = stack.pop(); if (c == ')' && top != '(') return false; if (c == '}' && top != '{') return false; if (c == ']' && top != '[') return false; } } // Stack must be empty at the end for a balanced expression return stack.isEmpty(); } public static void main(String[] args) { System.out.println(isBalanced("{[()]}")); // true System.out.println(isBalanced("{[(])}")); // false System.out.println(isBalanced("((()))")); // true System.out.println(isBalanced("{]")); // false System.out.println(isBalanced("")); // true (empty is balanced) }}Problem 3 — Reverse a Stack (Without Extra Data Structure)Difficulty: Medium–HardProblem: Reverse all elements of a stack using only recursion — no array or extra stack allowed.Approach: This is a classic recursion problem. You need two recursive functions:insertAtBottom(stack, item) — inserts an element at the very bottom of the stackreverseStack(stack) — pops all elements, reverses, and uses insertAtBottom to rebuild// ReverseStack.javaimport java.util.Stack;public class ReverseStack { // Insert an element at the bottom of the stack public static void insertAtBottom(Stack<Integer> stack, int item) { if (stack.isEmpty()) { stack.push(item); return; } int top = stack.pop(); insertAtBottom(stack, item); stack.push(top); } // Reverse the stack using insertAtBottom public static void reverseStack(Stack<Integer> stack) { if (stack.isEmpty()) return; int top = stack.pop(); reverseStack(stack); // reverse the remaining stack insertAtBottom(stack, top); // insert popped element at bottom } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println("Before: " + stack); // [1, 2, 3, 4, 5] reverseStack(stack); System.out.println("After: " + stack); // [5, 4, 3, 2, 1] }}Problem 4 — Evaluate a Postfix ExpressionDifficulty: MediumProblem: Evaluate a postfix (Reverse Polish Notation) expression. Example: "2 3 4 * +" should return 14 because it is 2 + (3 * 4).Approach: Scan left to right. If you see a number, push it. If you see an operator, pop two numbers, apply the operator, and push the result.// PostfixEvaluation.javaimport java.util.Stack;public class PostfixEvaluation { public static int evaluate(String expression) { Stack<Integer> stack = new Stack<>(); String[] tokens = expression.split(" "); for (String token : tokens) { // If it's a number, push it if (token.matches("-?\\d+")) { stack.push(Integer.parseInt(token)); } // If it's an operator, pop two and apply else { int b = stack.pop(); // second operand int a = stack.pop(); // first operand switch (token) { case "+": stack.push(a + b); break; case "-": stack.push(a - b); break; case "*": stack.push(a * b); break; case "/": stack.push(a / b); break; } } } return stack.pop(); } public static void main(String[] args) { System.out.println(evaluate("2 3 4 * +")); // 14 → 2 + (3*4) System.out.println(evaluate("5 1 2 + 4 * + 3 -")); // 14 → 5+((1+2)*4)-3 System.out.println(evaluate("3 4 +")); // 7 }}Problem 5 — Next Greater ElementDifficulty: MediumProblem: For each element in an array, find the next greater element to its right. If none exists, output -1.Example: Input: [4, 5, 2, 10, 8] → Output: [5, 10, 10, -1, -1]Approach: Iterate right to left. Maintain a stack of candidates. For each element, pop all stack elements that are smaller than or equal to it — they can never be the answer for any element to the left. The top of the stack (if not empty) is the next greater element.// NextGreaterElement.javaimport java.util.Stack;import java.util.Arrays;public class NextGreaterElement { public static int[] nextGreater(int[] arr) { int n = arr.length; int[] result = new int[n]; Stack<Integer> stack = new Stack<>(); // stores elements, not indices // Traverse from right to left for (int i = n - 1; i >= 0; i--) { // Pop elements smaller than or equal to current while (!stack.isEmpty() && stack.peek() <= arr[i]) { stack.pop(); } // Next greater element result[i] = stack.isEmpty() ? -1 : stack.peek(); // Push current element for future comparisons stack.push(arr[i]); } return result; } public static void main(String[] args) { int[] arr1 = {4, 5, 2, 10, 8}; System.out.println(Arrays.toString(nextGreater(arr1))); // [5, 10, 10, -1, -1] int[] arr2 = {1, 3, 2, 4}; System.out.println(Arrays.toString(nextGreater(arr2))); // [3, 4, 4, -1] int[] arr3 = {5, 4, 3, 2, 1}; System.out.println(Arrays.toString(nextGreater(arr3))); // [-1, -1, -1, -1, -1] }}Problem 6 — Sort a Stack Using RecursionDifficulty: HardProblem: Sort a stack in ascending order (smallest on top) using only recursion — no loops, no extra data structure.// SortStack.javaimport java.util.Stack;public class SortStack { // Insert element in correct sorted position public static void sortedInsert(Stack<Integer> stack, int item) { if (stack.isEmpty() || item > stack.peek()) { stack.push(item); return; } int top = stack.pop(); sortedInsert(stack, item); stack.push(top); } // Sort the stack public static void sortStack(Stack<Integer> stack) { if (stack.isEmpty()) return; int top = stack.pop(); sortStack(stack); // sort remaining sortedInsert(stack, top); // insert top in sorted position } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(34); stack.push(3); stack.push(31); stack.push(98); stack.push(92); stack.push(23); System.out.println("Before sort: " + stack); sortStack(stack); System.out.println("After sort: " + stack); // smallest on top }}13. Summary & Key TakeawaysA stack is a simple, elegant, and powerful data structure. Here is everything in one place:What it is: A linear data structure that follows LIFO — Last In, First Out.Core operations: push (add to top), pop (remove from top), peek (view top), isEmpty — all in O(1) time.Three ways to implement it in Java:Array-based: fast, fixed size, risk of overflowArrayList-based: dynamic, easy, slightly more overheadLinkedList-based: truly dynamic, memory-efficient per-element, best for unknown sizesWhen to use it:Undo/redo systemsBrowser navigationBalancing brackets and parenthesesEvaluating mathematical expressionsBacktracking problemsManaging recursive function callsDepth-first searchWhen NOT to use it:When you need random access to elementsWhen insertion/deletion is needed from both ends (use Deque)When you need to search efficiently (use HashMap or BST)Modern Java recommendation: Prefer ArrayDeque over the legacy Stack class for non-thread-safe scenarios. Use Stack only when you need synchronized access.The stack is one of those data structures that once you truly understand, you start seeing it everywhere — in your browser, in your IDE, in recursive algorithms, and deep within the operating system itself.This article covered everything from the fundamentals of the Stack data structure to multiple Java implementations, time complexity analysis, real-world applications, and six practice problems of increasing difficulty. Bookmark it as a reference and revisit the practice problems regularly — they are the real test of your understanding.

DataStructuresJavaStackDataStructureLIFO

LeetCode 3488 — Closest Equal Element Queries: A Complete Walkthrough from Brute Force to Optimal

If you have been grinding LeetCode lately, you have probably run into problems where your first clean-looking solution times out and forces you to rethink from scratch. LeetCode 3488 is exactly that kind of problem. This article walks through the complete thought process — from the naive approach that got me TLE, to the intuition shift, to the final optimized solution in Java.You can find the original problem here: LeetCode 3488 — Closest Equal Element Queries at Problem LinkUnderstanding the ProblemYou are given a circular array nums and an array of queries. For each query queries[i], you must find the minimum distance between the element at index queries[i] and any other index j such that nums[j] == nums[queries[i]]. If no such other index exists, the answer is -1.The critical detail here is the word circular. The array wraps around, which means the distance between two indices i and j in an array of length n is not simply |i - j|. It is:min( |i - j| , n - |i - j| )You can travel either clockwise or counterclockwise, and you take whichever path is shorter.Breaking Down the ExamplesExample 1nums = [1, 3, 1, 4, 1, 3, 2], queries = [0, 3, 5]For query index 0, the value is 1. Other indices holding 1 are 2 and 4. Circular distances are min(2, 5) = 2 and min(4, 3) = 3. The minimum is 2.For query index 3, the value is 4. It appears nowhere else in the array. Answer is -1.For query index 5, the value is 3. The other 3 sits at index 1. Circular distance is min(4, 3) = 3. Answer is 3.Output: [2, -1, 3]Example 2nums = [1, 2, 3, 4], queries = [0, 1, 2, 3]Every element is unique. Every query returns -1.Output: [-1, -1, -1, -1]First Attempt — Brute ForceMy first instinct was straightforward. For each query, scan the entire array, collect every index that matches the queried value, compute the circular distance to each, and return the minimum. Clean logic, easy to reason about, and dead simple to implement.while (i != queries.length) { int max = Integer.MAX_VALUE; for (int j = 0; j < nums.length; j++) { int target = nums[queries[i]]; if (nums[j] == target && j != queries[i]) { // Linear distance between the two indices int right = Math.abs(j - queries[i]); // Distance going the other direction around the ring int left = nums.length - right; // True circular distance is the shorter of the two int dist = Math.min(right, left); max = Math.min(max, dist); } } lis.add(max == Integer.MAX_VALUE ? -1 : max); i++;}This got TLE immediately, and once you look at the constraints it is obvious why. Both nums.length and queries.length can be up to 10^5. For every query you are scanning every element, giving you O(n × q) time — which in the worst case is 10 billion operations. No judge is going to wait for that.Rethinking the Approach — Where Is the Waste?After the TLE, the question I asked myself was: what work is being repeated unnecessarily?The answer was obvious in hindsight. Every time a query asks about a value like 3, the brute force scans the entire array again looking for every index that holds 3. If ten different queries all ask about value 3, you are doing that scan ten times. You are finding the same indices over and over.The fix is to do that work exactly once, before any query is processed. You precompute a map from each value to all the indices where it appears. Then for every query you simply look up the relevant list and work within it.That observation reduces the precomputation to O(n) — one pass through the array. The question then becomes: once you have that sorted list of indices for a given value, how do you find the closest one to your query index efficiently?The Key Insight — You Only Need Two NeighboursHere is the insight that makes this problem elegant. The index list for any value is sorted in ascending order because you build it by iterating left to right through the array. If your query index sits at position mid inside that sorted list, then by definition every index to the left of mid - 1 is farther away than arr[mid - 1], and every index to the right of mid + 1 is farther away than arr[mid + 1].This means you never need to compare against all duplicates. You only ever need to check the immediate left and right neighbours of your query index within the sorted list.The one subtlety is the circular wrap. Because the array itself is circular, the left neighbour of the very first element in the list is actually the last element in the list, since you can wrap around the ring. This is handled cleanly with modular arithmetic: (mid - 1 + n) % n for the left neighbour and (mid + 1) % n for the right.The Optimized Solution — HashMap + Binary SearchStep 1 — Precompute the index mapIterate through nums once and build a HashMap mapping each value to a list of all indices where it appears. The lists are sorted by construction since you insert indices in order.Step 2 — Binary search to locate the query indexFor a given query at index q, look up the index list for nums[q]. Binary search the list to find the position of q within it. This runs in O(log n) rather than O(n).Step 3 — Check immediate neighbours and compute circular distancesOnce you have the position mid, fetch arr[(mid + 1) % n] and arr[(mid - 1 + n) % n]. For each, compute the circular distance using min(|diff|, totalLength - |diff|). Return the smaller of the two.Full Annotated Java Solutionclass Solution { public List<Integer> solveQueries(int[] nums, int[] queries) { int c = 0; // Precompute: map each value to the sorted list of indices where it appears. // Since we iterate left to right, the list is sorted by construction. HashMap<Integer, List<Integer>> mp = new HashMap<>(); for (int i = 0; i < nums.length; i++) { mp.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i); } List<Integer> lis = new ArrayList<>(); while (c != queries.length) { // Retrieve the sorted index list for the value at the queried position List<Integer> arr = mp.get(nums[queries[c]]); int n = arr.size(); int i = 0; int j = n - 1; int min = -1; while (i <= j) { int mid = i + (j - i) / 2; if (arr.get(mid) == queries[c]) { // Only one occurrence in the entire array — no duplicate exists if (n == 1) { min = -1; } else { // Circular neighbour to the right within the index list int right = arr.get((mid + 1) % n); // Circular neighbour to the left within the index list int left = arr.get((mid - 1 + n) % n); // Compute circular distance to the right neighbour int d1 = Math.abs(right - queries[c]); int distRight = Math.min(d1, nums.length - d1); // Compute circular distance to the left neighbour int d2 = Math.abs(left - queries[c]); int distLeft = Math.min(d2, nums.length - d2); // The answer is the closer of the two neighbours min = Math.min(distLeft, distRight); } break; } else if (arr.get(mid) > queries[c]) { // Query index is smaller — search the left half j = mid - 1; } else { // Query index is larger — search the right half i = mid + 1; } } lis.add(min); c++; } return lis; }}Complexity AnalysisTime Complexity: O(n log n)Building the HashMap takes O(n). For each of the q queries, binary search over the index list takes O(log n) in the worst case. Total: O(n + q log n), which simplifies to O(n log n) given the constraint that q ≤ n.Space Complexity: O(n)The HashMap stores every index exactly once across all its lists, so total space used is O(n).Compared to the brute force O(n × q), this is the difference between ~1.7 million operations and ~10 billion operations at the constraint limits.Common PitfallsMixing up the two values of n. Inside the solution, n refers to arr.size() — the number of occurrences of a particular value. But when computing circular distance, you need nums.length — the full array length. These are different numbers and swapping them silently produces wrong answers.Forgetting the + n in the left neighbour formula. Writing (mid - 1) % n when mid is 0 produces -1 in Java, since Java's modulo preserves the sign of the dividend. Always write (mid - 1 + n) % n.Not handling the single-occurrence case. If a value appears only once, n == 1, and the neighbour formula wraps around to the element itself, giving a distance of zero — which is completely wrong. Guard against this explicitly before running the neighbour logic.What This Problem Teaches YouThe journey from brute force to optimal here follows a pattern worth internalizing.The brute force was correct but repeated work. Recognizing that repeated work and lifting it into a precomputation step is the single move that makes this problem tractable. The HashMap does that.Once you have a sorted structure, binary search is almost always the right tool to find a position within it. And once you have a position in a sorted structure, you only ever need to look at adjacent elements to find the nearest one — checking anything further is redundant by definition.These are not tricks specific to this problem. They are transferable patterns that appear across dozens of medium and hard problems on the platform. Internalizing them — rather than memorizing solutions — is what actually builds problem-solving ability over time.

ArraysHashMapBinary SearchCircular ArraysMediumLeetCodeJava

Find Minimum in Rotated Sorted Array – Binary Search Explained | LeetCode Medium 153

🔗 Try This Problem FirstPlatform: LeetCodeProblem Number: 153👉 Practice here: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/🧠 Problem UnderstandingYou are given a sorted array that has been rotated between 1 and n times.Example:Original sorted array:[0,1,2,4,5,6,7]After rotation:[4,5,6,7,0,1,2]Your task: 👉 Return the minimum element from this rotated array. 👉 Time complexity must be O(log n). 👉 All elements are unique.🔍 Key ObservationIn a rotated sorted array:The array is divided into two sorted halves.The minimum element is the pivot point where rotation happened.One half will always be sorted.We can use Binary Search to find where the sorted order breaks.Example:[4,5,6,7,0,1,2] ↑ Minimum🚀 Approach 1: Brute Force (Not Allowed by Constraint)IdeaScan entire array and track minimum.int min = nums[0];for(int i = 1; i < nums.length; i++){ min = Math.min(min, nums[i]);}return min;ComplexityTime: O(n)Space: O(1)❌ Not acceptable because problem requires O(log n).🚀 Approach 2: Binary Search (Optimal – O(log n))💡 Core IdeaCompare nums[mid] with nums[right].There are only two possibilities:Case 1: nums[mid] > nums[right]Minimum is in right half.[4,5,6,7,0,1,2]mid rMove left pointer:l = mid + 1Case 2: nums[mid] <= nums[right]Minimum is in left half including mid.[4,5,6,7,0,1,2]mid rMove right pointer:r = mid✅ Optimized Codeclass Solution { public int findMin(int[] nums) { int l = 0; int r = nums.length - 1; while (l < r) { int mid = l + (r - l) / 2; if (nums[mid] > nums[r]) { l = mid + 1; } else { r = mid; } } return nums[r]; }}📊 Dry RunInput:nums = [4,5,6,7,0,1,2]Steplrmidnums[mid]Action106377 > 2 → l = 4246511 <= 2 → r = 5345400 <= 1 → r = 4Stop44--Return nums[4]✅ Output = 0🧩 Why This WorksIf middle element is greater than rightmost, rotation point is to the right.If middle element is smaller than or equal to rightmost, minimum is on the left side.We continuously shrink search space until l == r.That position holds the minimum element.⏱ Time & Space ComplexityMetricValueTime ComplexityO(log n)Space ComplexityO(1)Because:We eliminate half of the array each iteration.No extra space is used.⚠️ Important Edge CasesArray size = 1[10] → 10Already sorted (no visible rotation)[11,13,15,17] → 11Rotation at last position[1,2,3,4,5] → 1🎯 Interview InsightThis problem teaches:Modified Binary SearchIdentifying sorted halvesHandling rotated arraysUnderstanding pivot logicThis is a very common FAANG interview question and often appears in variations like:Search in Rotated Sorted ArrayFind Peak ElementMinimum in Rotated Array with Duplicates🏁 Final TakeawayBrute force works but violates constraint.Binary search is the correct approach.Compare mid with right.Shrink search space until pointers meet.Return nums[l] or nums[r].

LeetcodeMediumBinary Search

Intersection of Two Arrays

LeetCode Problem 349Link of the Problem to try -: LinkGiven two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order. Example 1:Input: nums1 = [1,2,2,1], nums2 = [2,2]Output: [2]Example 2:Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]Output: [9,4]Explanation: [4,9] is also accepted. Constraints:1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000Solution: Using HashMap and HashSet for IntersectionCore Objective: The primary goal of this problem is to identify common elements between two arrays and return them as a unique set. To achieve this efficiently, we utilize a combination of a HashMap for quick lookup and a HashSet to handle uniqueness in the result.Logic & Implementation:Populate Lookup Table: We begin by iterating through the first array (nums1) and storing its elements in a HashMap. This allows us to verify the existence of any number in $O(1)$ average time.Identify Intersection: Next, we iterate through the second array (nums2). For each element, we check if it exists within our HashMap.Handle Uniqueness: If a match is found, we add the element to a HashSet. This is a crucial step because the problem requires the output to contain unique elements, even if a common number appears multiple times in the input arrays.Final Conversion: Since the required return type is an array, we determine the size of our HashSet to initialize the result array. Using a for-each loop, we transfer the values from the Set into the array and return it as the final answer.Code Implementation:public int[] intersection(int[] nums1, int[] nums2) { // HashMap to store elements from the first array for lookup HashMap<Integer, Integer> mp = new HashMap<>(); // HashSet to store unique common elements HashSet<Integer> ms = new HashSet<>(); // Populate the map with elements from nums1 for (int i = 0; i < nums1.length; i++) { if (mp.containsKey(nums1[i])) { continue; } mp.put(nums1[i], i); } // Check for common elements in nums2 for (int i = 0; i < nums2.length; i++) { if (mp.containsKey(nums2[i])) { ms.add(nums2[i]); // HashSet ensures duplicates are not added } } // Convert the HashSet to the final integer array int[] ans = new int[ms.size()]; int co = 0; for (int i : ms) { ans[co] = i; co++; } return ans;}

LeetCodeArrayEasyHashMap

LeetCode 462: Minimum Moves to Equal Array Elements II | Java Solution Explained (Median Approach)

IntroductionLeetCode 462 is a classic mathematical and greedy problem.We are given an integer array where each operation allows us to:Increment an element by 1Decrement an element by 1Our task is to make all numbers equal while using the minimum number of moves.At first glance, this may look like a simple array problem.But the hidden concept behind this question is:Median propertyGreedy optimizationAbsolute difference minimizationThis problem is extremely popular in coding interviews because it tests logical thinking more than coding complexity.# Problem LinkProblem StatementYou are given an integer array nums.In one move:You can increase an element by 1Or decrease an element by 1You must make all array elements equal.Return the minimum number of operations required.Example 1Input:nums = [1,2,3]Output:2Explanation:[1,2,3]→ [2,2,3]→ [2,2,2]Total operations = 2Example 2Input:nums = [1,10,2,9]Output:16Key ObservationWe need to choose one target value such that all numbers move toward it.Question:Which target gives minimum total moves?Answer:MedianMedian minimizes the sum of absolute differences.Why Median Works?Suppose:nums = [1,2,3,10]If target = 2|1-2| + |2-2| + |3-2| + |10-2|= 1 + 0 + 1 + 8= 10If target = 5|1-5| + |2-5| + |3-5| + |10-5|= 4 + 3 + 2 + 5= 14Median gives minimum moves.Approach 1: Brute ForceIn this approach, we try every possible value as target.For each target:Calculate total operations neededStore minimum answerAlgorithmFind minimum and maximum elementTry every value between themCompute total movesReturn minimumJava Code (Brute Force)class Solution {public int minMoves2(int[] nums) {int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;for (int num : nums) {min = Math.min(min, num);max = Math.max(max, num);}int result = Integer.MAX_VALUE;for (int target = min; target <= max; target++) {int moves = 0;for (int num : nums) {moves += Math.abs(num - target);}result = Math.min(result, moves);}return result;}}Time ComplexityO(N × Range)Very slow for large values.Approach 2: Sorting + Median (Optimal)This is the best and most commonly used approach.IdeaSort arrayPick median elementCalculate total absolute differenceStepsStep 1: Sort ArraySorting helps us easily find median.Step 2: Pick MedianMedian index = n / 2Step 3: Calculate MovesFor every element:moves += abs(median - value)Optimal Java Solutionclass Solution {public int minMoves2(int[] nums) {Arrays.sort(nums);int mid = nums.length / 2;int ans = 0;for (int i = 0; i < nums.length; i++) {int diff = Math.abs(nums[mid] - nums[i]);ans += diff;}return ans;}}Code ExplanationStep 1: Sort ArrayArrays.sort(nums);Sorting allows median calculation.Step 2: Get Medianint mid = nums.length / 2;Middle element becomes target.Step 3: Compute DifferenceMath.abs(nums[mid] - nums[i])Find distance from median.Step 4: Add All Movesans += diff;Store total moves.Approach 3: Two Pointer OptimizationAfter sorting, we can use two pointers.Instead of calculating absolute difference manually, we can pair smallest and largest values.IdeaAfter sorting:moves += nums[right] - nums[left]Because both numbers will meet toward median.Java Code (Two Pointer)class Solution {public int minMoves2(int[] nums) {Arrays.sort(nums);int left = 0;int right = nums.length - 1;int moves = 0;while (left < right) {moves += nums[right] - nums[left];left++;right--;}return moves;}}Why Two Pointer Works?Because:Median minimizes total distancePairing smallest and largest values gives direct movement cost.Dry RunInput:nums = [1,10,2,9]Sort:[1,2,9,10]Median:9Operations:|1-9| = 8|2-9| = 7|9-9| = 0|10-9| = 1Total:16Time ComplexitySortingO(N log N)TraversingO(N)TotalO(N log N)Space ComplexityO(1)Ignoring sorting stack.Common Mistakes1. Using Average Instead of MedianMany people think average gives minimum.Wrong.Average minimizes squared difference.Median minimizes absolute difference.2. Forgetting SortingMedian requires sorted order.3. Overflow IssueValues can be large.Sometimes use:long ansfor safer calculation.4. Using Wrong Median IndexCorrect:n / 2Edge CasesCase 1Single element array.Answer = 0Case 2All elements already equal.Answer = 0Case 3Negative numbers.Algorithm still works.FAQsQ1. Why median gives minimum moves?Median minimizes total absolute difference.Q2. Can average work?No.Average does not minimize absolute distance.Q3. Is sorting necessary?Yes.Sorting helps us easily find median.Q4. Which approach is best?Sorting + median approach.Interview InsightInterviewers ask this problem to test:Median property understandingGreedy optimizationMathematical thinkingArray manipulationConclusionLeetCode 462 is one of the most important median-based interview questions.The major learning is:Median minimizes total absolute differenceSorting makes finding median easySum of distances gives answerOnce you understand why median works, this question becomes very simple.

MathMedianMediumLeetCodeJavaArrayTwo PointerSorting

Floor in a Sorted Array – Binary Search Explained with Story & Visuals | GeeksforGeeks

Problem StatementPlatform: GeeksforGeeksYou are given a sorted array arr[] and an integer x. Your task is to find the index of the largest element in the array that is less than or equal to x.Return -1 if no such element exists.If multiple elements equal the floor, return the last occurrence.Example:Input: arr = [1, 2, 8, 10, 10, 12, 19], x = 11Output: 4✅ The largest element ≤ 11 is 10. The last occurrence is at index 4.👉 Try this problem here: GeeksforGeeks – Floor in a Sorted ArrayIntuition: What is “Floor” and Why It MattersImagine climbing stairs:You want to step as high as possible without going past a certain height.That step is your floor – the largest number ≤ x.In arrays:The floor of x is the largest number smaller than or equal to x.Because the array is sorted, we can search efficiently with binary search instead of checking every element.This is faster and helps you handle large arrays with millions of elements.Multiple Approaches1️⃣ Linear Search (Easy but Slow)Check each element from left to right. If it’s ≤ x, update the answer.int ans = -1;for(int i = 0; i < arr.length; i++){if(arr[i] <= x){ans = i; // store last occurrence}}return ans;Time Complexity: O(n) – slow for large arraysSpace Complexity: O(1) – constant memory2️⃣ Binary Search (Fast & Efficient)Binary search cuts the search space in half at every step.int ans = -1;int low = 0, high = arr.length - 1;while(low <= high){int mid = low + (high - low)/2;if(arr[mid] == x){ans = mid; // candidate floorlow = mid + 1; // move right for last occurrence} else if(arr[mid] < x){ans = mid; // candidate floorlow = mid + 1;} else {high = mid - 1; // too large, move left}}return ans;Time Complexity: O(log n) – very fastSpace Complexity: O(1) – no extra spaceDry Run / Step-by-StepInput: arr = [1, 2, 8, 10, 10, 12, 19], x = 11Steplowhighmidarr[mid]ansAction1063103arr[mid] < x → move right2465123arr[mid] > x → move left3444104arr[mid] < x → move right454--4low > high → stop, return 4✅ Finds floor = 10 at index 4.Code Explanation in Simple Wordsans = -1 → stores best candidate for floor.Use low and high as binary search boundaries.mid = low + (high - low)/2 → safe midpoint.If arr[mid] <= x, it can be the floor → move right to find last occurrence.If arr[mid] > x, move left → floor is smaller.Loop ends when low > high, return ans.Edge Cases to Rememberx < arr[0] → return -1 (floor doesn’t exist)x ≥ arr[n-1] → return last index (floor is last element)Duplicates → always return last occurrenceStory-Based Visual Example: “Alice’s Book Shelf Adventure” 📚Scenario:Alice is a librarian.Books are arranged by height on a shelf.She has a new book and wants to place it next to the tallest book shorter than or equal to hers.Instead of checking each book, she uses a binary search approach to find the position quickly."Alice is scanning the bookshelf, which represents a sorted array: [1, 2, 8, 10, 10, 12, 19]. She is thinking where to place her new book labeled 11. This step represents the initial step of the floor algorithm, understanding the array elements.""Alice places the book labeled 11 right after the last 10 on the shelf. This demonstrates finding the floor: the largest number ≤ 11 is 10, and the book is positioned next to it, illustrating the last occurrence logic.""From a top view, Alice is scanning all the books. This shows how binary search would conceptually divide the array: she quickly decides which section the book 11 belongs to without checking every book, demonstrating efficient search.""Alice has successfully placed the book 11 at the correct position. The floor of 11 is 10 (index 4). This visual confirms the algorithm’s result: the new element is positioned immediately after the last element ≤ x, exactly as binary search would determine."Why This Problem is ImportantStrengthens binary search skillsTeaches last occurrence / boundary conditions handlingMakes you think algorithmically, not just about numbersStory-based learning improves retention and understandingConclusionLinear search: easy but slow (O(n))Binary search: fast, elegant (O(log n))Multiple dry run steps make it easy to followStory-based images make abstract concepts concrete and memorable

GeeksforGeeksBinary SearchEasy

LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

Try the ProblemYou can solve the problem here:https://leetcode.com/problems/find-unique-binary-string/Problem DescriptionYou are given an array nums containing n unique binary strings, where each string has length n.Your task is to return any binary string of length n that does not appear in the array.Important ConditionsEach string consists only of '0' and '1'.Every string in the array is unique.The output must be a binary string of length n.If multiple valid answers exist, any one of them is acceptable.ExamplesExample 1Inputnums = ["01","10"]Output"11"ExplanationPossible binary strings of length 2:00011011Since "01" and "10" are already present, valid answers could be:00 or 11Example 2Inputnums = ["00","01"]Output"11"Another valid output could be:10Example 3Inputnums = ["111","011","001"]Output101Other valid answers include:000010100110Constraintsn == nums.length1 <= n <= 16nums[i].length == nnums[i] consists only of '0' and '1'All strings in nums are uniqueImportant ObservationThe total number of binary strings of length n is:2^nBut the array contains only:n stringsSince 2^n grows very quickly and n ≤ 16, there are many possible binary strings missing from the array. Our goal is simply to construct one of those missing strings.Thinking About the ProblemBefore jumping into coding, it's useful to think about different strategies that could help us generate a binary string that does not appear in the array.Possible Ways to Think About the ProblemWhen approaching this problem, several ideas may come to mind:Generate all possible binary strings of length n and check which one is missing.Store all strings in a HashSet or HashMap and construct a candidate string to verify whether it exists.Manipulate existing strings by flipping bits to create new combinations.Use a mathematical trick that guarantees the new string is different from every string in the list.Each of these approaches leads to a different solution strategy.In this article, we will walk through these approaches and understand how they work.Approach 1: Brute Force – Generate All Binary StringsIdeaThe simplest idea is to generate every possible binary string of length n and check whether it exists in the given array.Since there are:2^n possible binary stringsWe can generate them one by one and return the first string that does not appear in nums.StepsConvert numbers from 0 to (2^n - 1) into binary strings.Pad the binary string with leading zeros so its length becomes n.Check if that string exists in the array.If not, return it.Time ComplexityO(2^n * n)This works because n is at most 16, but it is still not the most elegant approach.Approach 2: HashMap + Bit Flipping (My Approach)IdeaWhile solving this problem, another idea is to store all given binary strings inside a HashMap for quick lookup.Then we can try to construct a new binary string by flipping bits from the existing strings.The intuition is simple:If the current character is '0', change it to '1'.If the current character is '1', change it to '0'.By flipping bits at different positions, we attempt to build a new binary combination.Once the string is constructed, we check whether it already exists in the map.If the generated string does not exist, we return it as our answer.Java Implementation (My Solution)class Solution { public String findDifferentBinaryString(String[] nums) { int len = nums[0].length(); // HashMap to store all given binary strings HashMap<String, Integer> mp = new HashMap<>(); for(int i = 0; i < nums.length; i++){ mp.put(nums[i], i); } int cou = 0; String ans = ""; for(int i = 0; i < nums.length; i++){ if(cou < len){ // Flip the current bit if(nums[i].charAt(cou) == '0'){ ans += '1'; cou++; } else{ ans += '0'; cou++; } }else{ // If generated string does not exist in map if(!mp.containsKey(ans)){ return ans; } // Reset and try building again ans = ""; cou = 0; } } return ans; }}Time ComplexityO(n²)Because we iterate through the array and perform string operations.Space ComplexityO(n)For storing the strings in the HashMap.Approach 3: Cantor’s Diagonalization (Optimal Solution)IdeaA clever mathematical observation allows us to construct a string that must differ from every string in the array.We build a new string such that:The first character differs from the first string.The second character differs from the second string.The third character differs from the third string.And so on.By ensuring that the generated string differs from each string at least at one position, it is guaranteed not to exist in the array.This technique is known as Cantor’s Diagonalization.Java Implementationclass Solution { public String findDifferentBinaryString(String[] nums) { int n = nums.length; StringBuilder result = new StringBuilder(); for(int i = 0; i < n; i++){ // Flip the diagonal bit if(nums[i].charAt(i) == '0'){ result.append('1'); } else{ result.append('0'); } } return result.toString(); }}Time ComplexityO(n)We only traverse the array once.Space ComplexityO(n)For storing the resulting string.Comparison of ApproachesApproachTime ComplexitySpace ComplexityNotesBrute ForceO(2^n * n)O(n)Simple but inefficientHashMap + Bit FlippingO(n²)O(n)Constructive approachCantor DiagonalizationO(n)O(n)Optimal and elegantKey TakeawaysThis problem highlights an interesting concept in algorithm design:Sometimes the best solution is not searching for the answer but constructing one directly.By understanding the structure of the input, we can generate a result that is guaranteed to be unique.ConclusionThe Find Unique Binary String problem can be solved using multiple strategies, ranging from brute force enumeration to clever mathematical construction.While brute force works due to the small constraint (n ≤ 16), more elegant solutions exist. Using hashing or constructive approaches improves efficiency and demonstrates deeper algorithmic thinking.Among all approaches, the Cantor Diagonalization technique provides the most efficient and mathematically guaranteed solution.Understanding problems like this helps strengthen skills in string manipulation, hashing, and constructive algorithms, which are commonly tested in coding interviews.

Binary StringsHashingCantor DiagonalizationLeetCodeMedium

Left and Right Sum Differences

LeetCode 2574: Left and Right Sum Differences (Java)The Left and Right Sum Difference problem is a classic array manipulation challenge. It tests your ability to efficiently calculate prefix and suffix values—a skill essential for more advanced algorithms like "Product of Array Except Self."🔗 ResourcesProblem Link: LeetCode 2574 - Left and Right Sum Differences📝 Problem StatementYou are given a 0-indexed integer array nums. You need to return an array answer of the same length where:answer[i] = |leftSum[i] - rightSum[i]|leftSum[i] is the sum of elements to the left of index i.rightSum[i] is the sum of elements to the right of index i.💡 Approach 1: The Three-Array Method (Beginner Friendly)This approach is highly intuitive. We pre-calculate all left sums and all right sums in separate arrays before computing the final difference.The LogicPrefix Array: Fill pref[] by adding the previous element to the cumulative sum.Suffix Array: Fill suff[] by iterating backward from the end of the array.Result: Loop one last time to calculate Math.abs(pref[i] - suff[i]).Java Implementationpublic int[] leftRightDifference(int[] nums) {int n = nums.length;int[] pref = new int[n];int[] suff = new int[n];int[] ans = new int[n];// Calculate Left Sums (Prefix)for (int i = 1; i < n; i++) {pref[i] = pref[i - 1] + nums[i - 1];}// Calculate Right Sums (Suffix)for (int i = n - 2; i >= 0; i--) {suff[i] = suff[i + 1] + nums[i + 1];}// Combine resultsfor (int i = 0; i < n; i++) {ans[i] = Math.abs(pref[i] - suff[i]);}return ans;}Time Complexity: O(n)Space Complexity: O(n) (Uses extra space for pref and suff arrays).🚀 Approach 2: The Running Sum Method (Space Optimized)In technical interviews, you should aim for O(1) extra space. Instead of storing every suffix sum, we calculate the Total Sum first and derive the right sum using logic.The LogicWe use the mathematical property:Right Sum = Total Sum - Left Sum - Current ElementBy maintaining a single variable leftSum that updates as we iterate, we can calculate the result using only the output array.Java Implementationpublic int[] leftRightDifference(int[] nums) {int n = nums.length;int[] ans = new int[n];int totalSum = 0;int leftSum = 0;// 1. Get the total sum of all elementsfor (int num : nums) {totalSum += num;}// 2. Calculate rightSum and difference on the flyfor (int i = 0; i < n; i++) {int rightSum = totalSum - leftSum - nums[i];ans[i] = Math.abs(leftSum - rightSum);// Update leftSum for the next indexleftSum += nums[i];}return ans;}Time Complexity: O(n)Space Complexity: O(1) (Excluding the output array).📊 Summary ComparisonFeatureApproach 1Approach 2Space ComplexityO(n) (Higher)O(1) (Optimal)Logic TypeStorage-basedMathematicalUse CaseBeginnersInterviewsKey TakeawayWhile Approach 1 is easier to visualize, Approach 2 is more professional. It shows you can handle data efficiently without unnecessary memory allocation, which is critical when dealing with large-scale systems.

LeetCodePrefixSuffix

LeetCode 1855 Maximum Distance Between Pair of Values | Two Pointer Java Solution

IntroductionLeetCode 1855 – Maximum Distance Between a Pair of Values is a classic problem that beautifully demonstrates the power of the Two Pointer technique on sorted (non-increasing) arrays.At first glance, it may feel like a brute-force problem—but using the right observation, it can be solved efficiently in O(n) time.In this article, we will cover:Problem intuitionWhy brute force failsOptimized two-pointer approach (your solution)Alternative approachesTime complexity analysis🔗 Problem LinkLeetCode: Maximum Distance Between a Pair of ValuesProblem StatementYou are given two non-increasing arrays:nums1nums2A pair (i, j) is valid if:i <= jnums1[i] <= nums2[j]👉 Distance = j - iReturn the maximum distance among all valid pairs.ExamplesExample 1Input:nums1 = [55,30,5,4,2]nums2 = [100,20,10,10,5]Output:2Key InsightThe most important observation:Both arrays are NON-INCREASING👉 This allows us to use two pointers efficiently instead of brute force.❌ Naive Approach (Brute Force)IdeaTry all (i, j) pairsCheck conditionsTrack maximumComplexityTime: O(n × m) ❌👉 This will cause TLE for large inputs (up to 10⁵)✅ Optimized Approach: Two PointersIntuitionUse two pointers:i → nums1j → nums2We try to:Expand j as far as possibleMove i only when necessaryKey LogicIf nums1[i] <= nums2[j] → valid → increase jElse → move i forwardJava Codeclass Solution { public int maxDistance(int[] nums1, int[] nums2) { int i = 0; // pointer for nums1 int j = 0; // pointer for nums2 int max = Integer.MIN_VALUE; // Traverse both arrays while (i < nums1.length && j < nums2.length) { // Valid pair condition if (nums1[i] <= nums2[j] && i <= j) { // Update maximum distance max = Math.max(max, j - i); // Try to expand distance by moving j j++; } else if (nums1[i] >= nums2[j]) { // nums1[i] is too large → move i forward i++; } else { // Just move j forward j++; } } // If no valid pair found, return 0 return max == Integer.MIN_VALUE ? 0 : max; }}Step-by-Step Dry RunInput:nums1 = [55,30,5,4,2]nums2 = [100,20,10,10,5]Execution:(0,0) → valid → distance = 0Move j → (0,1) → invalid → move iContinue...Final best pair:(i = 2, j = 4) → distance = 2Why This WorksArrays are sorted (non-increasing)Moving j increases distanceMoving i helps find valid pairs👉 No need to re-check previous elementsComplexity AnalysisTime ComplexityO(n + m)Each pointer moves at most once through the array.Space ComplexityO(1) (no extra space used)Alternative Approach: Binary SearchIdeaFor each i in nums1:Use binary search in nums2Find farthest j such that:nums2[j] >= nums1[i]ComplexityO(n log m)Code (Binary Search Approach)class Solution { public int maxDistance(int[] nums1, int[] nums2) { int max = 0; for (int i = 0; i < nums1.length; i++) { int left = i, right = nums2.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums2[mid] >= nums1[i]) { max = Math.max(max, mid - i); left = mid + 1; } else { right = mid - 1; } } } return max; }}Two Pointer vs Binary SearchApproachTimeSpaceTwo PointerO(n + m) ✅O(1)Binary SearchO(n log m)O(1)👉 Two pointer is optimal hereKey TakeawaysUse two pointers when arrays are sortedAlways look for monotonic propertiesAvoid brute force when constraints are largeGreedy pointer movement can optimize drasticallyCommon Interview PatternsThis problem is related to:Two pointer problemsSliding windowBinary search on arraysGreedy expansionConclusionThe Maximum Distance Between a Pair of Values problem is a great example of how recognizing array properties can drastically simplify the solution.By using the two-pointer technique, we reduce complexity from O(n²) to O(n)—a massive improvement.Frequently Asked Questions (FAQs)1. Why do we use two pointers?Because arrays are sorted, allowing linear traversal.2. Why not brute force?It is too slow for large inputs (10⁵).3. What is the best approach?👉 Two-pointer approach

MediumLeetCodeJavaArrayBinary SearchTwo Pointer

Ceil in a Sorted Array – Binary Search Explained with Story & Visuals | GeeksforGeeks

Try This Problem FirstPlatform: GeeksforGeeks👉 Try this problem here: Ceil in a Sorted Array – GeeksforGeeksProblem StatementYou are given a sorted array arr[] and an integer x. Your task is to find the index of the smallest element in the array that is greater than or equal to x.If no such element exists, return -1.If multiple elements equal the ceil, return the first occurrence.Example:Input: arr = [1, 2, 8, 10, 11, 12, 19], x = 5Output: 2Explanation: Smallest element ≥ 5 is 8 at index 2.IntuitionThink of the problem as finding the first step you can reach without falling short:The ceil of x is the smallest number ≥ x.Since the array is sorted, we can use binary search to quickly locate the answer instead of checking each element.Linear search is simple but slow for large arrays. Binary search gives an efficient O(log n) solution.Multiple Approaches1️⃣ Linear Search (Easy to Understand)int ans = -1;for(int i = 0; i < arr.length; i++){if(arr[i] >= x){ans = i; // first occurrencebreak;}}return ans;Time Complexity: O(n)Space Complexity: O(1)✅ Works for small arrays❌ Slow for large arrays2️⃣ Binary Search (Optimized & Fast)int ans = -1;int low = 0, high = arr.length - 1;while(low <= high){int mid = low + (high - low)/2;if(arr[mid] == x){ans = mid;high = mid - 1; // move left for first occurrence} else if(arr[mid] > x){ans = mid; // candidate ceilhigh = mid - 1; // move left} else {low = mid + 1; // arr[mid] < x → move right}}return ans;Time Complexity: O(log n)Space Complexity: O(1)✅ Efficient for large arrays✅ Automatically returns first occurrenceDry RunInput: arr = [1, 2, 8, 10, 11, 12, 19], x = 5Steplowhighmidarr[mid]ansAction1063103arr[mid] > x → move left202123arr[mid] < x → move right322282arr[mid] > x → move left421--2low > high → stop, return 2✅ Binary search finds ceil = 8 at index 2.Why This Problem is ImportantTeaches binary search for first occurrenceStrengthens understanding of ceil/floor conceptsVisualization through story improves understanding and retentionPrepares for coding interviews and competitive programmingConclusionLinear search: simple but slow (O(n))Binary search: fast and efficient (O(log n))Story-based visualization helps learn, not just memorizeUsing numbers on books in images makes abstract concepts concrete

GeeksForGeeksEasyBinary SearchSorted Array

Mastering Binary Search – LeetCode 704 Explained

IntroductionBinary Search is one of the most fundamental and powerful algorithms in computer science. If you're preparing for coding interviews, mastering Binary Search is absolutely essential.In this blog, we’ll break down LeetCode 704 – Binary Search, explain the algorithm in detail, walk through your Java implementation, analyze complexity, and recommend additional problems to strengthen your understanding.You can try this problem -: Problem Link📌 Problem OverviewYou are given:A sorted array of integers nums (ascending order)An integer targetYour task is to return the index of target if it exists in the array. Otherwise, return -1.Example 1Input: nums = [-1,0,3,5,9,12], target = 9Output: 4Example 2Input: nums = [-1,0,3,5,9,12], target = 2Output: -1Constraints1 <= nums.length <= 10⁴All integers are uniqueThe array is sorted in ascending orderRequired Time Complexity: O(log n)🚀 Understanding the Binary Search AlgorithmBinary Search works only on sorted arrays.Instead of checking each element one by one (like Linear Search), Binary Search:Finds the middle element.Compares it with the target.Eliminates half of the search space.Repeats until the element is found or the search space is empty.Why is it Efficient?Every iteration cuts the search space in half.If the array size is n, the number of operations becomes:log₂(n)This makes it extremely efficient compared to linear search (O(n)).🧠 Step-by-Step AlgorithmInitialize two pointers:low = 0high = nums.length - 1While low <= high:Calculate middle index:mid = low + (high - low) / 2If nums[mid] == target, return midIf target > nums[mid], search right half → low = mid + 1Else search left half → high = mid - 1If loop ends, return -1💻 Your Java Code ExplainedHere is your implementation:class Solution {public int search(int[] nums, int target) {int high = nums.length-1;int low = 0;while(low <= high){int mid = low+(high-low)/2;if(target == nums[mid] ){return mid;}else if(target > nums[mid]){low = mid+1;}else{high = mid-1;}}return -1;}}🔍 Code Breakdown1️⃣ Initialize Boundariesint high = nums.length - 1;int low = 0;You define the search space from index 0 to n-1.2️⃣ Loop Conditionwhile(low <= high)The loop continues as long as there is a valid search range.3️⃣ Safe Mid Calculationint mid = low + (high - low) / 2;This is preferred over:(low + high) / 2Why?Because (low + high) may cause integer overflow in large arrays.Your approach prevents that.4️⃣ Comparison Logicif(target == nums[mid])If found → return index.else if(target > nums[mid])low = mid + 1;Search in right half.elsehigh = mid - 1;Search in left half.5️⃣ Not Found Casereturn -1;If the loop finishes without finding the target.⏱ Time and Space ComplexityTime Complexity: O(log n)Each iteration halves the search space.Space Complexity: O(1)No extra space used — purely iterative.🔥 Why This Problem Is ImportantLeetCode 704 is:The foundation of all Binary Search problemsA template questionFrequently asked in interviewsRequired to understand advanced problems like:Search in Rotated Sorted ArrayFind First and Last PositionPeak ElementBinary Search on Answer📚 Recommended Binary Search Practice ProblemsAfter solving this, practice these in order:🟢 Easy35. Search Insert Position69. Sqrt(x)278. First Bad Version🟡 Medium34. Find First and Last Position of Element in Sorted Array33. Search in Rotated Sorted Array74. Search a 2D Matrix875. Koko Eating Bananas (Binary Search on Answer)🔴 Advanced Pattern Practice1011. Capacity To Ship Packages Within D Days410. Split Array Largest SumThese will help you master:Lower bound / upper boundBinary search on monotonic functionsSearching in rotated arraysSearching in 2D matricesBinary search on answer pattern🎯 Final ThoughtsBinary Search is not just a single algorithm — it’s a pattern.If you truly understand:How the search space shrinksWhen to move left vs rightHow to calculate mid safelyLoop conditions (low <= high vs low < high)You can solve 50+ interview problems easily.LeetCode 704 is the perfect starting point.Master this template, and you unlock an entire category of problems.

Binary SearchLeetCodeEasy

Max Consecutive Ones III – Sliding Window with Limited Flips

IntroductionLeetCode 1004: Max Consecutive Ones III is a classic sliding window problem that challenges your understanding of arrays, window manipulation, and frequency counting.The goal is to find the longest subarray of consecutive 1's in a binary array if you are allowed to flip at most K zeros to 1’s.This problem is an excellent example of transforming a brute-force solution into a linear-time efficient approach using the sliding window pattern.If you’d like to try solving the problem first, you can attempt it here: Try the problem on LeetCode: https://leetcode.com/problems/max-consecutive-ones-iii/Problem UnderstandingYou are given:A binary array nums containing only 0's and 1'sAn integer k representing the maximum number of zeros you can flipYou need to return the length of the longest contiguous subarray of 1's after flipping at most k zeros.Examples:Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2Output: 6Explanation: Flip two zeros to get [1,1,1,0,0,1,1,1,1,1,1].Longest consecutive ones = 6.Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3Output: 10Explanation: Flip three zeros to get longest consecutive ones of length 10.A naive approach would check every possible subarray, flip zeros, and count consecutive ones:Time Complexity: O(n²) → too slow for large arraysInefficient for constraints up to 10⁵ elementsKey Idea: Sliding Window with Zero CountInstead of brute-force, notice that:We only care about how many zeros are in the current windowWe can maintain a sliding window [i, j]Keep a counter z for zeros in the windowExpand the window by moving jIf z exceeds k, shrink the window from the left by moving i and decrementing z for each zero removedIntuition:The window always contains at most k zerosThe length of the window gives the maximum consecutive ones achievable with flipsThis allows linear traversal of the array with O(1) space, making it optimal.Approach (Step-by-Step)Initialize pointers: i = 0, j = 0Initialize z = 0 (zeros count in current window) and co = 0 (max length)Iterate j from 0 to nums.length - 1:If nums[j] == 0, increment zCheck z:If z <= k: window is valid → update co = max(co, j - i + 1)Else: shrink window by moving i until z <= k, decrement z for zeros leaving windowContinue expanding window with jReturn co as the maximum consecutive onesOptimization:Only need one variable for zeros countAvoids recomputing sums or scanning subarrays repeatedlyImplementation (Java)class Solution { public int longestOnes(int[] nums, int k) { int co = 0; // maximum length of valid window int i = 0, j = 0; // window pointers int z = 0; // count of zeros in current window while (j < nums.length) { if (nums[j] == 0) { z++; // increment zeros count } if (z <= k) { co = Math.max(co, j - i + 1); // valid window j++; } else { // shrink window until zeros <= k while (z > k) { if (nums[i] == 0) { z--; } i++; } co = Math.max(co, j - i + 1); j++; } } return co; }}Dry Run ExampleInput:nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2Execution:Window [i, j]Zeros zValid?Max length co[0,0] → [1]0Yes1[0,2] → [1,1,1]0Yes3[0,3] → [1,1,1,0]1Yes4[0,4] → [1,1,1,0,0]2Yes5[0,5] → [1,1,1,0,0,0]3No → shrink i5[3,8] → [0,0,1,1,1,1]2Yes6Output:6Complexity AnalysisTime Complexity: O(n) → Each element is visited at most twice (once when j moves, once when i moves)Space Complexity: O(1) → Only counters and pointers usedEdge Cases Consideredk = 0 → cannot flip any zeros, just count consecutive onesArray with all 1’s → return full lengthArray with all 0’s → return min(k, length)Single element arrays → works correctlySliding Window Pattern ImportanceThis problem is a perfect example of the sliding window pattern:Use a window to track a condition (max zeros allowed)Expand and shrink dynamically based on constraintsEfficiently computes maximum/minimum contiguous subarray lengthsIt also demonstrates counting with limited violations – a key interview concept.ConclusionBy tracking zeros with a sliding window, we convert a naive O(n²) problem into O(n) linear time.Understanding this pattern allows you to solve:Max consecutive ones/zeros problemsLongest substring/subarray with constraintsSubarray problems with limited replacements or violationsOnce mastered, this approach applies to many binary array and string problems efficiently.

SlidingWindowBinaryArrayLeetCodeMedium

Intersection of Two Arrays II

LeetCode Problem 350Link of the Problem to try -: LinkGiven two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order. Example 1:Input: nums1 = [1,2,2,1], nums2 = [2,2]Output: [2,2]Example 2:Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]Output: [4,9]Explanation: [9,4] is also accepted. Constraints:1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000Solution:In this question we can build a frequency HashMap of each element and then add into the array as per it's frequency is that is a very important thing in this question to do.For creating frequency we will use getOrDefault() method in HashMap that is very useful for creating frequency as this method returns the value of that key if that key is not exist then whatever value we give that value is considered as default value for us.So, back to question here we simply create a map creating frequency of each element and if the element came again we simply increase the frequency of it then we create a ArrayList because we don't know about the size of array here so we use ArrayList after this we will iterate again on the second array and try to find that element in the map also we check it's frequency should be more than 0 and we add in the List also we decreasing the frequency of the element in the loop.At last we simply take all the elements of ArrayList and put into a array of size of that ArrayList because our questions want's ans in array that's why we have to do this step otherwise our ans is in the ArrayList and this is how we find duplicates of the number of times that element appears in both array.Code: public int[] intersect(int[] nums1, int[] nums2) { HashMap<Integer, Integer> mp = new HashMap<>(); for (int i = 0; i < nums1.length; i++) { // If you are not interested in writing getOrDefault then you can write via if statement as well // int cou =1; // if(mp.containsKey(nums1[i])){ // // int nu = mp.get(nums1[i]); // mp.put(nums1[i],mp.get(nums1[i])+1); // continue; // } // mp.put(nums1[i],cou); // Another way mp.put(nums1[i], mp.getOrDefault(nums1[i], 0) + 1); } List<Integer> lis = new ArrayList<>(); for (int i = 0; i < nums2.length; i++) { if (mp.containsKey(nums2[i]) && mp.get(nums2[i]) > 0) { lis.add(nums2[i]); } mp.put(nums2[i], mp.getOrDefault(nums2[i], 0) - 1); } int[] ans = new int[lis.size()]; for (int i = 0; i < ans.length; i++) { ans[i] = lis.get(i); } return ans; }

LeetcodeEasyHashMapHashSet

Longest Subarray of 1's After Deleting One Element – Sliding Window Approach

IntroductionLeetCode 1493: Longest Subarray of 1's After Deleting One Element is a neat sliding window problem that tests your ability to dynamically adjust a window while handling a constraint: deleting exactly one element.The task is to find the longest subarray of 1's you can get after deleting one element from the array.This problem is an excellent example of how sliding window with zero counting can convert a potentially brute-force solution into an O(n) linear solution.If you’d like to try solving the problem first, you can attempt it here:Try the problem on LeetCode:https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/Problem UnderstandingYou are given:A binary array nums containing only 0’s and 1’sYou must delete exactly one elementYour task: Return the length of the longest non-empty subarray of 1’s after deleting one element.Examples:Input: nums = [1,1,0,1]Output: 3Explanation: Delete element at index 2 → [1,1,1]. Longest subarray of 1's = 3.Input: nums = [0,1,1,1,0,1,1,0,1]Output: 5Explanation: Delete element at index 4 → [0,1,1,1,1,1,0,1]. Longest subarray of 1's = 5.Input: nums = [1,1,1]Output: 2Explanation: Must delete one element → longest subarray = 2.A naive approach would try removing each element and scanning for the longest subarray →Time Complexity: O(n²) → too slow for nums.length up to 10⁵Inefficient for large arraysKey Idea: Sliding Window with At Most One ZeroNotice the following:Deleting one element is equivalent to allowing at most one zero in the subarrayWe can use a sliding window [i, j] and a counter z for zeros in the windowExpand j while z <= 1If z > 1, shrink the window from the left until z <= 1The length of the window (j - i) gives the maximum length of consecutive 1’s after deleting one elementIntuition:Only one zero is allowed in the window because deleting that zero would turn the window into all 1'sThis converts the problem into a linear sliding window problem with zero countingApproach (Step-by-Step)Initialize i = 0, j = 0 for window pointersInitialize z = 0 → number of zeros in current windowInitialize co = 0 → maximum length of valid subarrayIterate j over nums:If nums[j] == 0, increment zCheck z:If z <= 1: window is valid → update co = max(co, j - i)If z > 1: shrink window from i until z <= 1Continue expanding the windowReturn co as the maximum length after deleting one elementOptimization:Only need one zero counter and window pointersAvoid recomputing subarray lengths repeatedlyImplementation (Java)class Solution {public int longestSubarray(int[] nums) {int i = 0, j = 0; // window pointersint co = 0; // max lengthint z = 0; // count of zeros in windowwhile (j < nums.length) {if (nums[j] == 0) {z++; // increment zero count}if (z <= 1) {co = Math.max(co, j - i); // valid windowj++;} else {// shrink window until at most one zerowhile (z > 1) {if (nums[i] == 0) {z--;}i++;}co = Math.max(co, j - i);j++;}}return co;}}Dry Run ExampleInput:nums = [1,1,0,1]Execution:Window [i, j]Zeros zValid?Max length co[0,0] → [1]0Yes0[0,1] → [1,1]0Yes1[0,2] → [1,1,0]1Yes2[0,3] → [1,1,0,1]1Yes3Output:3Complexity AnalysisTime Complexity: O(n) → Each element is visited at most twice (i and j)Space Complexity: O(1) → Only counters and pointers usedEdge Cases ConsideredArray of all 1’s → must delete one → max length = n - 1Array of all 0’s → return 0Single element arrays → return 0 (because deletion required)Zeros at the start/end of array → handled by sliding windowSliding Window Pattern ImportanceThis problem is a great example of sliding window with limited violations:Maintain a window satisfying a constraint (at most one zero)Expand/shrink dynamicallyCompute max length without scanning all subarraysIt’s directly related to problems like:Max consecutive ones with k flipsLongest substring with at most k distinct charactersSubarray problems with limited replacementsConclusionBy tracking zeros with a sliding window, we efficiently find the longest subarray of 1’s after deleting one element in O(n) time.This pattern is reusable in many binary array and string problems, making it a must-know technique for coding interviews.

SlidingWindowBinaryArrayLeetCodeMedium

LeetCode 735: Asteroid Collision — Java Solution Explained

IntroductionIf you have been building your stack skills through problems like Valid Parentheses, Next Greater Element, and Backspace String Compare, then LeetCode 735 Asteroid Collision is the problem where everything comes together. It is one of the most satisfying Medium problems on LeetCode because it feels like a real simulation — you are literally modelling asteroids flying through space and crashing into each other.You can find the problem here — LeetCode 735 Asteroid Collision.This article breaks everything down in plain English so that anyone — beginner or experienced — can understand exactly what is happening and why the stack is the perfect tool for this problem.What Is the Problem Really Asking?You have a row of asteroids moving through space. Each asteroid has a size and a direction:Positive number → asteroid moving to the rightNegative number → asteroid moving to the leftAll asteroids move at the same speed. When a right-moving asteroid and a left-moving asteroid meet head-on, they collide:The smaller one explodesIf they are the same size, both explodeThe bigger one survives and keeps movingTwo asteroids moving in the same direction never meet, so they never collide.Return the final state of all surviving asteroids after every possible collision has happened.Real Life Analogy — Cars on a HighwayImagine a highway with cars driving in both directions. Cars going right are in one lane, cars going left are in another lane. Now imagine the lanes overlap at some point.A small car going right crashes into a big truck going left — the car gets destroyed, the truck keeps going. Two equally sized cars crash — both are destroyed. A massive truck going right demolishes everything coming from the left until it meets something bigger or nothing at all.That is exactly the asteroid problem. The stack helps us track which asteroids are still "alive" and moving right, waiting to potentially collide with the next left-moving asteroid that comes along.Why Stack Is the Perfect Data Structure HereThe key observation is this — only a right-moving asteroid followed by a left-moving asteroid can collide. A left-moving asteroid might destroy several right-moving ones in a chain before it either survives or gets destroyed itself.This chain reaction behavior — where the outcome of one collision immediately triggers the possibility of another — is exactly what a stack handles naturally. The stack holds right-moving asteroids that are still alive and waiting. When a left-moving asteroid arrives, it battles the top of the stack repeatedly until either it is destroyed or no more collisions are possible.All Possible Collision ScenariosBefore looking at code it is important to understand every case that can happen:Case 1 — Right-moving asteroid (ast[i] > 0) No collision possible immediately. Push it onto the stack and move on.Case 2 — Left-moving asteroid, stack is empty Nothing to collide with. Push it onto the stack.Case 3 — Left-moving asteroid, top of stack is also left-moving (negative) Two asteroids going the same direction never meet. Push it onto the stack.Case 4 — Left-moving asteroid meets right-moving asteroid (collision!) Three sub-cases:Stack top is bigger → left-moving asteroid explodes, stack top survivesStack top is smaller → stack top explodes, left-moving asteroid continues (loop again)Same size → both explodeThe Solution — Stack Simulationpublic int[] asteroidCollision(int[] ast) { Stack<Integer> st = new Stack<>(); for (int i = 0; i < ast.length; i++) { boolean survived = true; // assume current asteroid survives // collision only happens when stack top is positive // and current asteroid is negative while (!st.empty() && st.peek() > 0 && ast[i] < 0) { if (st.peek() > Math.abs(ast[i])) { // stack top is bigger — current asteroid explodes survived = false; break; } else if (st.peek() < Math.abs(ast[i])) { // current asteroid is bigger — stack top explodes // current asteroid keeps going, check next stack element st.pop(); } else { // equal size — both explode st.pop(); survived = false; break; } } if (survived) { st.push(ast[i]); } } // build result array from stack (stack gives reverse order) int[] ans = new int[st.size()]; for (int i = ans.length - 1; i >= 0; i--) { ans[i] = st.pop(); } return ans;}Step-by-Step Dry Run — asteroids = [10, 2, -5]Let us trace exactly what happens:Processing 10:Stack is empty, no collision possiblesurvived = true → push 10Stack: [10]Processing 2:Stack top is 10 (positive), current is 2 (positive) — same direction, no collisionsurvived = true → push 2Stack: [10, 2]Processing -5:Stack top is 2 (positive), current is -5 (negative) — collision!2 < 5 → stack top smaller, pop 2. survived stays trueStack: [10]Stack top is 10 (positive), current is -5 (negative) — collision again!10 > 5 → stack top bigger, current asteroid destroyed. survived = false, breakStack: [10]survived = false → do not push -5Final stack: [10] → output: [10] ✅Step-by-Step Dry Run — asteroids = [3, 5, -6, 2, -1, 4]Processing 3: stack empty → push. Stack: [3]Processing 5: both positive, same direction → push. Stack: [3, 5]Processing -6:Collision with 5: 5 < 6 → pop 5. Stack: [3]Collision with 3: 3 < 6 → pop 3. Stack: []Stack empty → survived = true → push -6Stack: [-6]Processing 2: stack top is -6 (negative), current is 2 (positive) — same direction check fails, no collision → push. Stack: [-6, 2]Processing -1:Collision with 2: 2 > 1 → stack top bigger, -1 explodes. survived = falseStack: [-6, 2]Processing 4: stack top is 2 (positive), current is 4 (positive) — same direction → push. Stack: [-6, 2, 4]Final stack: [-6, 2, 4] → output: [-6, 2, 4] ✅Understanding the survived FlagThe survived boolean flag is the most important design decision in this solution. It tracks whether the current asteroid makes it through all collisions.It starts as true — we assume the asteroid survives until proven otherwise. It only becomes false in two situations — when the stack top is bigger (current asteroid destroyed) or when both are equal size (mutual destruction). If survived is still true after the while loop, the asteroid either won all its battles or never had any — either way it gets pushed onto the stack.This flag eliminates the need for complicated nested conditions and makes the logic clean and readable.Building the Result ArrayOne important detail — when you pop everything from a stack to build an array, the order is reversed. The stack gives you elements from top to bottom (last to first). So we fill the result array from the end to the beginning using i = ans.length - 1 going down to 0. This preserves the original left-to-right order of surviving asteroids.Time and Space ComplexityTime Complexity: O(n) — each asteroid is pushed onto the stack at most once and popped at most once. Even though there is a while loop inside the for loop, each element participates in at most one push and one pop across the entire run. Total operations stay linear.Space Complexity: O(n) — in the worst case (all asteroids moving right, no collisions) all n asteroids sit on the stack simultaneously.Common Mistakes to AvoidForgetting that same-direction asteroids never collide The collision condition is specifically st.peek() > 0 && ast[i] < 0. Two positive asteroids, two negative asteroids, or a negative followed by a positive — none of these collide. Only right then left.Not using a loop for chain collisions A single left-moving asteroid can destroy multiple right-moving ones in sequence. If you only check the stack top once instead of looping, you will miss chain destructions like in the [3, 5, -6] example.Forgetting the survived flag and always pushing Without the flag, a destroyed asteroid still gets pushed onto the stack, giving wrong results.Wrong array reconstruction from stack Forgetting that stack order is reversed and filling the array from left to right gives a backwards answer. Always fill from the last index downward.How This Problem Differs From Previous Stack ProblemsEvery previous stack problem in this series had a simple push-or-pop decision per character. Asteroid Collision introduces something new — a while loop inside the for loop. This is because one incoming asteroid can trigger multiple consecutive pops (chain collisions). The stack is no longer just storing history — it is actively participating in a simulation where multiple stored elements can be affected by a single incoming element.This is the defining characteristic of harder stack problems and is exactly what appears in problems like Largest Rectangle in Histogram and Trapping Rain Water.FAQs — People Also AskQ1. Why is a Stack used to solve LeetCode 735 Asteroid Collision? Because right-moving asteroids wait on the stack until a left-moving asteroid arrives. The left-moving asteroid battles the top of the stack repeatedly — this LIFO chain reaction behavior is exactly what a stack handles naturally and efficiently.Q2. What is the time complexity of LeetCode 735? O(n) time because each asteroid is pushed and popped at most once regardless of how many chain collisions happen. Space complexity is O(n) for the stack in the worst case.Q3. When do two asteroids NOT collide in LeetCode 735? Two asteroids never collide when both move right (both positive), both move left (both negative), or when a left-moving asteroid comes before a right-moving one — they move away from each other in that case.Q4. Is LeetCode 735 asked in coding interviews? Yes, it is commonly asked at companies like Amazon, Google, and Microsoft as a Medium stack problem. It tests whether you can handle simulation problems with multiple conditional branches and chain reactions — skills that translate directly to real world system design thinking.Q5. What is the difference between LeetCode 735 and LeetCode 496 Next Greater Element? Both use a stack and involve comparing elements. In Next Greater Element, you search forward for something bigger. In Asteroid Collision, collisions happen between the current element and stack contents, and the current element might destroy multiple previous elements in a chain before settling. The collision logic in 735 is more complex.Similar LeetCode Problems to Practice Next496. Next Greater Element I — Easy — monotonic stack pattern739. Daily Temperatures — Medium — next greater with index distance1047. Remove All Adjacent Duplicates In String — Easy — chain removal with stack84. Largest Rectangle in Histogram — Hard — advanced stack simulation503. Next Greater Element II — Medium — circular array with monotonic stackConclusionLeetCode 735 Asteroid Collision is a wonderful problem that takes the stack simulation pattern to the next level. The key insight is recognizing that only right-then-left asteroid pairs can collide, that chain collisions require a while loop not just an if statement, and that the survived flag keeps the logic clean across all cases.Work through every dry run in this article carefully — especially the [3, 5, -6, 2, -1, 4] example — because seeing chain collisions play out step by step is what makes this pattern click permanently.Once this problem makes sense, you are genuinely ready for the harder stack problems that follow. Keep going!

LeetCodeJavaStackArrayMedium

Merge Sort Algorithm Explained | Java Implementation, Intuition & Complexity

IntroductionSorting is one of the most fundamental operations in computer science, and Merge Sort is among the most efficient and widely used sorting algorithms.It follows the Divide and Conquer approach, making it highly scalable and predictable even for large datasets.In this article, we will cover:Intuition behind Merge SortStep-by-step breakdownMultiple approachesJava implementation with commentsTime & space complexity analysis🔗 Problem LinkGeeksforGeeks: Merge SortProblem StatementGiven an array arr[] with starting index l and ending index r, sort the array using the Merge Sort algorithm.ExamplesExample 1Input:arr = [4, 1, 3, 9, 7]Output:[1, 3, 4, 7, 9]Example 2Input:arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]Output:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]Key InsightMerge Sort works by:Divide → Conquer → CombineDivide the array into two halvesRecursively sort each halfMerge both sorted halvesIntuition (Visual Understanding)For:[4, 1, 3, 9, 7]Step 1: Divide[4, 1, 3] [9, 7][4, 1] [3] [9] [7][4] [1]Step 2: Merge[4] [1] → [1, 4][1, 4] [3] → [1, 3, 4][9] [7] → [7, 9]Step 3: Final Merge[1, 3, 4] + [7, 9] → [1, 3, 4, 7, 9]Approach 1: Recursive Merge Sort (Top-Down)IdeaKeep dividing until single elements remainMerge sorted subarraysJava Codeclass Solution { // Function to merge two sorted halves void merge(int[] arr, int l, int mid, int h) { // Temporary array to store merged result int[] temp = new int[h - l + 1]; int i = l; // pointer for left half int j = mid + 1; // pointer for right half int k = 0; // pointer for temp array // Compare elements from both halves while (i <= mid && j <= h) { if (arr[i] <= arr[j]) { temp[k] = arr[i]; i++; } else { temp[k] = arr[j]; j++; } k++; } // Copy remaining elements from left half while (i <= mid) { temp[k] = arr[i]; i++; k++; } // Copy remaining elements from right half while (j <= h) { temp[k] = arr[j]; j++; k++; } // Copy sorted elements back to original array for (int m = 0; m < temp.length; m++) { arr[l + m] = temp[m]; } } // Recursive merge sort function void mergeSort(int arr[], int l, int h) { // Base case: single element if (l >= h) return; int mid = l + (h - l) / 2; // Sort left half mergeSort(arr, l, mid); // Sort right half mergeSort(arr, mid + 1, h); // Merge both halves merge(arr, l, mid, h); }}Approach 2: Iterative Merge Sort (Bottom-Up)IdeaStart with subarrays of size 1Merge pairsIncrease size graduallyCodeclass Solution { void merge(int[] arr, int l, int mid, int h) { int[] temp = new int[h - l + 1]; int i = l, j = mid + 1, k = 0; while (i <= mid && j <= h) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while (i <= mid) temp[k++] = arr[i++]; while (j <= h) temp[k++] = arr[j++]; for (int m = 0; m < temp.length; m++) { arr[l + m] = temp[m]; } } void mergeSort(int[] arr, int n) { for (int size = 1; size < n; size *= 2) { for (int l = 0; l < n - size; l += 2 * size) { int mid = l + size - 1; int h = Math.min(l + 2 * size - 1, n - 1); merge(arr, l, mid, h); } } }}Approach 3: Using Built-in Sorting (For Comparison)Arrays.sort(arr);👉 Internally uses optimized algorithms (TimSort in Java)Complexity AnalysisTime ComplexityCaseComplexityBestO(n log n)AverageO(n log n)WorstO(n log n)Space ComplexityO(n) (extra array for merging)Why Merge Sort is PowerfulStable sorting algorithmWorks efficiently on large datasetsPredictable performanceUsed in external sorting (large files)❌ Why Not Use Bubble/Selection Sort?AlgorithmTime ComplexityBubble SortO(n²)Selection SortO(n²)Merge SortO(n log n) ✅Key TakeawaysMerge Sort uses divide and conquerRecursion splits problem into smaller partsMerging is the key stepAlways O(n log n), regardless of inputWhen to Use Merge SortLarge datasetsLinked lists (very efficient)Stable sorting requiredExternal sortingConclusionMerge Sort is one of the most reliable and efficient sorting algorithms. Understanding its recursive structure and merging process is essential for mastering advanced algorithms.Once you grasp the divide-and-conquer pattern, it becomes easier to solve many complex problems.Frequently Asked Questions (FAQs)1. Is Merge Sort stable?Yes, it maintains the relative order of equal elements.2. Why is extra space required?Because we use a temporary array during merging.3. Can it be done in-place?Not efficiently; standard merge sort requires extra space.

GeekfOfGeeksMediumSortingMerge SortJava

Find First and Last Position in Sorted Array – From Brute Force to Binary Search (LeetCode 34)

Problem LinkLeetCode 34 – Find First and Last Position of Element in Sorted Array 👉 https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/📌 Problem OverviewYou are given a sorted array (non-decreasing order) and a target value.Your task:Return the starting and ending index of the target.If target does not exist → return [-1, -1]Required Time Complexity: O(log n)Example 1Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]Example 2Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]🧠 My First Intuition – Brute Force (O(n))When I first saw this problem, my thinking was simple:"Since the array is sorted, I just need to find the first occurrence and the last occurrence."So I used two loops:One loop from left → to find first occurrenceOne loop from right → to find last occurrenceHere is my submitted solution:class Solution { public int[] searchRange(int[] nums, int t) { int arr[] = new int[2]; arr[0] = -1; arr[1] = -1; for(int i = nums.length-1;i >=0 ;i--){ if(nums[i] == t){ arr[1] = i; break; } } for(int i = 0;i <nums.length ;i++){ if(nums[i] == t){ arr[0] = i; break; } } return arr; }}✅ Why This WorksSince the array is sorted, occurrences of the same number are grouped together.First loop (reverse) finds last occurrence.Second loop (forward) finds first occurrence.❌ Problem with This ApproachTime Complexity = O(n)Worst case:Target is not presentWe scan entire array twiceBut the problem clearly states:You must write an algorithm with O(log n) runtime complexity.That means: We must use Binary Search.🚀 Optimized Approach – Binary Search (O(log n))💡 Key IntuitionIf the array is sorted:We can use Binary Search to find the first occurrenceWe can use Binary Search again to find the last occurrenceInstead of stopping when we find the target:For first occurrence → continue searching leftFor last occurrence → continue searching right🧠 Idea Breakdown1️⃣ Find First OccurrenceWhen we find target at mid:Store indexMove left → high = mid - 1Because there might be another occurrence before it2️⃣ Find Last OccurrenceWhen we find target at mid:Store indexMove right → low = mid + 1Because there might be another occurrence after it💻 Optimized Code (Binary Search Approach)class Solution { public int[] searchRange(int[] nums, int target) { int[] result = new int[2]; result[0] = findFirst(nums, target); result[1] = findLast(nums, target); return result; } private int findFirst(int[] nums, int target) { int low = 0, high = nums.length - 1; int index = -1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] == target) { index = mid; high = mid - 1; // move left } else if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return index; } private int findLast(int[] nums, int target) { int low = 0, high = nums.length - 1; int index = -1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] == target) { index = mid; low = mid + 1; // move right } else if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return index; }}🔍 Why This WorksBinary Search normally stops when target is found.Here, we modify it slightly:Keep searching even after finding target.Narrow the search space toward the boundary we want.This guarantees:First occurrence → leftmost indexLast occurrence → rightmost index⏱ Complexity AnalysisBrute Force ApproachTime: O(n)Space: O(1)Binary Search ApproachTime: O(log n)Space: O(1)This satisfies the problem constraint.🎯 Key Learning from This ProblemThis problem teaches an important pattern:When array is sorted and you need boundaries → Think Binary Search.It is not just about finding the element.It is about finding:First occurrence (Lower Bound)Last occurrence (Upper Bound)This pattern appears in many interview problems.📚 Similar Problems to Practicehttps://leetcode.com/problems/binary-search/https://leetcode.com/problems/search-insert-position/https://leetcode.com/problems/search-in-rotated-sorted-array/https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/https://leetcode.com/problems/sqrtx/🏁 Final ThoughtsMy journey solving this problem:First thought → Use two loops (works but O(n))Then realized constraint → Must be O(log n)Optimized using two Binary SearchesThis is how problem solving improves:Start with correct solution.Then optimize.Then recognize patterns.LeetCode 34 is one of the most important Binary Search boundary problems.If you master this, you unlock an entire category of advanced Binary Search questions.

Binary SearchLeetCodeMedium

LeetCode 122 — Best Time to Buy and Sell Stock II | Every Approach Explained

🚀 Try This Problem First!Before reading the solution, attempt it yourself on LeetCode — you'll retain the concept far better.🔗 Problem Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/Understanding the ProblemYou are given an array prices where prices[i] is the stock price on day i. Unlike the classic version, here you can make as many transactions as you want — but you can only hold one share at a time. You may buy and sell on the same day.Goal: Return the maximum total profit achievable.Key Rules:You can buy and sell multiple times.You cannot hold more than one share at a time — you must sell before buying again.If no profit is possible, return 0.Constraints:1 ≤ prices.length ≤ 3 × 10⁴0 ≤ prices[i] ≤ 10⁴How This Differs From LeetCode 121 #In LeetCode 121, you were limited to exactly one buy-sell transaction. Here, the restriction is lifted — you can participate in as many transactions as you want. This fundamentally changes the strategy. Instead of hunting for the single best pair, you want to capture every profitable price movement in the array.The Core InsightLook at the price chart mentally. Every time the price goes up from one day to the next, that's money on the table. The question is — how do you collect all of it?The answer is surprisingly simple: add every single upward price difference to your profit. If prices go up three days in a row from 1 → 3 → 5 → 8, you collect (3-1) + (5-3) + (8-5) = 7, which is exactly the same as buying at 1 and selling at 8. You never miss a gain.This is the foundation of all approaches below.Approach 1 — Simple Greedy (Collect Every Upward Move)Intuition: Every time prices[i] > prices[i-1], add the difference to profit. You are essentially buying at every valley and selling at every peak, collecting each individual daily gain without explicitly tracking buy/sell days.Why it works: The total gain from buying at day 0 and selling at day N is mathematically equal to the sum of all positive daily differences in between. You never lose anything by collecting gains day by day.Example: prices = [1, 2, 3, 4, 5] Daily gains: (2-1) + (3-2) + (4-3) + (5-4) = 1+1+1+1 = 4 Same as buying at 1 and selling at 5 directly.class Solution {public int maxProfit(int[] prices) {int maxProfit = 0;for (int i = 1; i < prices.length; i++) {if (prices[i] > prices[i - 1]) {maxProfit += prices[i] - prices[i - 1];}}return maxProfit;}}Time Complexity: O(N) — single pass through the array. Space Complexity: O(1) — no extra space used.This is the cleanest and most recommended solution for this problem.Approach 2 — Peak Valley ApproachIntuition: Instead of collecting every daily gain, explicitly find every valley (local minimum) to buy at and every peak (local maximum) to sell at. You buy when price stops falling and sell when price stops rising.How it works: Scan through the array. When you find a valley (prices[i] ≤ prices[i+1]), that is your buy point. Then keep going until you find a peak (prices[i] ≥ prices[i+1]) — that is your sell point. Add the peak minus valley to profit. Repeat.Example: prices = [7, 1, 5, 3, 6, 4]Valley at index 1 (price = 1), Peak at index 2 (price = 5) → profit += 4 Valley at index 3 (price = 3), Peak at index 4 (price = 6) → profit += 3 Total = 7 ✅class Solution {public int maxProfit(int[] prices) {int i = 0;int maxProfit = 0;int valley, peak;while (i < prices.length - 1) {while (i < prices.length - 1 && prices[i] >= prices[i + 1]) {i++;}valley = prices[i];while (i < prices.length - 1 && prices[i] <= prices[i + 1]) {i++;}peak = prices[i];maxProfit += peak - valley;}return maxProfit;}}Time Complexity: O(N) — each element is visited at most twice. Space Complexity: O(1) — no extra space used.This approach is more explicit and easier to visualize on a graph, though the code is slightly more involved than Approach 1.Approach 3 — Two PointerIntuition: Use two pointers i (buy day) and j (sell day). Move j forward one step at a time. Whenever prices[j] > prices[i], you have a profitable window — add the profit and immediately move i to j (simulate selling and rebuying at the same price on the same day). Whenever prices[j] < prices[i], just move i to j since a cheaper buy day has been found.Why moving i to j after every profitable sale works: Selling at j and immediately rebuying at j costs nothing (profit of 0 for that rebuy). But it positions i at the latest price so you can catch the next upward movement. This correctly simulates collecting every upward segment.Example: prices = [7, 1, 5, 3, 6, 4]i=0, j=1 → 7 > 1, move i to 1. j=2. i=1, j=2 → 1 < 5, profit += 4, move i to 2. j=3. i=2, j=3 → 5 > 3, move i to 3. j=4. i=3, j=4 → 3 < 6, profit += 3, move i to 4. j=5. i=4, j=5 → 6 > 4, move i to 5. j=6. Loop ends. Total profit = 7 ✅class Solution {public int maxProfit(int[] prices) {int i = 0;int j = 1;int maxProfit = 0;while (i < j && j < prices.length) {if (prices[i] > prices[j]) {i = j;} else {maxProfit += prices[j] - prices[i];i = j;}j++;}return maxProfit;}}Time Complexity: O(N) — j traverses the array exactly once. Space Complexity: O(1) — only three integer variables.This approach is functionally identical to Approach 1 — both collect every upward daily movement. The two pointer framing makes the buy/sell simulation more explicit.Approach 4 — Dynamic ProgrammingIntuition: At any point in time, you are in one of two states — either you hold a stock or you do not hold a stock. Define two DP values updated each day:hold = maximum profit if you are currently holding a stock at the end of this day.cash = maximum profit if you are not holding any stock at the end of this day.Transitions:To hold on day i: either you already held yesterday, or you buy today. hold = max(hold, cash - prices[i])To have cash on day i: either you already had cash yesterday, or you sell today. cash = max(cash, hold + prices[i])Initialization:hold = -prices[0] (you bought on day 0)cash = 0 (you did nothing on day 0)class Solution {public int maxProfit(int[] prices) {int hold = -prices[0];int cash = 0;for (int i = 1; i < prices.length; i++) {hold = Math.max(hold, cash - prices[i]);cash = Math.max(cash, hold + prices[i]);}return cash;}}Time Complexity: O(N) — single pass. Space Complexity: O(1) — only two variables maintained at each step.This approach is the most powerful because it extends naturally to harder variants of this problem — like LeetCode 309 (with cooldown) and LeetCode 714 (with transaction fee) — where greedy no longer works and you need explicit state tracking.Dry Run — All Approaches on Example 1Input: prices = [7, 1, 5, 3, 6, 4], Expected Output: 7Approach 1 (Simple Greedy): Day 1→2: 1 - 7 = -6, skip. Day 2→3: 5 - 1 = 4, add. profit = 4. Day 3→4: 3 - 5 = -2, skip. Day 4→5: 6 - 3 = 3, add. profit = 7. Day 5→6: 4 - 6 = -2, skip. Result = 7 ✅Approach 4 (DP): Start: hold = -7, cash = 0. Day 1 (price=1): hold = max(-7, 0-1) = -1. cash = max(0, -1+1) = 0. Day 2 (price=5): hold = max(-1, 0-5) = -1. cash = max(0, -1+5) = 4. Day 3 (price=3): hold = max(-1, 4-3) = 1. cash = max(4, 1+3) = 4. Day 4 (price=6): hold = max(1, 4-6) = 1. cash = max(4, 1+6) = 7. Day 5 (price=4): hold = max(1, 7-4) = 3. cash = max(7, 3+4) = 7. Result = 7 ✅Comparison of All ApproachesApproach 1 — Simple Greedy Code simplicity: Simplest possible. Best for interviews — clean and readable. Does not extend to constrained variants.Approach 2 — Peak Valley Code simplicity: Moderate. Best for visual/conceptual understanding. Slightly verbose but maps directly to a chart.Approach 3 — Two Pointer Code simplicity: Simple. Explicit simulation of buy/sell actions. Functionally identical to Approach 1.Approach 4 — Dynamic Programming Code simplicity: Moderate. Most powerful — extends to cooldown, fee, and k-transaction variants. Worth mastering for the full stock problem series.Common Mistakes to AvoidThinking you need to find exact buy/sell days: The problem only asks for maximum profit — you do not need to output which days you traded. This frees you to use the simple greedy sum approach.Trying to find the global minimum and maximum: Unlike LeetCode 121, the single best buy-sell pair is not always optimal here. You need to capture multiple smaller movements, not one big one.Holding more than one share: You cannot buy twice in a row without selling in between. In Approach 3, moving i = j after every transaction ensures you always sell before the next buy.Not handling a flat or decreasing array: If prices never go up, all approaches correctly return 0 — the greedy sum adds nothing, peak-valley finds no valid pairs, and DP's cash stays at 0.Complexity SummaryAll four approaches run in O(N) time and O(1) space. The difference between them is conceptual clarity and extensibility, not raw performance.The Full Stock Problem Series on LeetCodeThis problem is part of a six-problem series. Understanding them in order builds intuition progressively:LeetCode 121 — One transaction only. Two pointer / min tracking greedy. [ Blog is also avaliable on this - Read Now]LeetCode 123 — At most 2 transactions. DP with explicit state for two transactions. [ Blog is also avaliable on this - Read Now]LeetCode 188 — At most k transactions. Generalized DP.LeetCode 309 — Unlimited transactions with cooldown after selling. DP with three states.LeetCode 714 — Unlimited transactions with a fee per transaction. DP with adjusted transitions.Each problem adds one constraint on top of the previous. If you understand the DP state machine from Approach 4 deeply, every problem in this series becomes a small modification of the same framework.Key Takeaways✅ When transactions are unlimited, collect every upward daily price movement — that is the global optimum.✅ The sum of all positive daily differences equals the sum of all peak-valley differences. Both are provably optimal.✅ The two pointer approach explicitly simulates buy and sell events — moving i = j after a sale means selling and immediately rebuying at the same price to stay positioned for the next gain.✅ The DP approach with hold and cash states is the most versatile — it is the foundation for every harder variant in the stock series.✅ Always initialize maxProfit = 0 so that the no-profit case (prices only falling) is handled correctly without extra conditions.Happy Coding! Once you have this problem locked down, the rest of the stock series will feel like natural extensions rather than new problems entirely. 🚀

LeetCodeGreedyTwo PointersDynamic ProgrammingMediumJavaArrays

LeetCode 1283 — Find the Smallest Divisor Given a Threshold | Binary Search on Answer Explained

🚀 Try This Problem First!Before reading the solution, attempt it yourself on LeetCode — you'll retain the concept far better.🔗 Problem Link: https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/Understanding the ProblemYou are given an array of integers nums and an integer threshold. You must choose a positive integer divisor, divide every element of the array by it (rounding up to the nearest integer), sum all the results, and make sure that sum is ≤ threshold.Goal: Find the smallest possible divisor that keeps the sum within the threshold.Important detail — Ceiling Division: Every division rounds up, not down. So 7 ÷ 3 = 3 (not 2), and 10 ÷ 2 = 5.Constraints:1 ≤ nums.length ≤ 5 × 10⁴1 ≤ nums[i] ≤ 10⁶nums.length ≤ threshold ≤ 10⁶Two Key Observations (Before Writing a Single Line of Code)Minimum possible divisor: The divisor must be at least 1. Dividing by anything less than 1 isn't a positive integer. So:low = 1Maximum possible divisor: If divisor = max(nums), then every element divided by it gives at most 1 (due to ceiling), so the sum equals nums.length, which is always ≤ threshold (guaranteed by constraints). So:high = max(nums)Our answer lies in the range [1, max(nums)]. This is the search space for Binary Search.Intuition — Why Binary Search?Ask yourself: what happens as the divisor increases?As divisor gets larger, each divided value gets smaller (or stays the same), so the total sum decreases or stays the same. This is a monotonic relationship — the green flag for Binary Search on the Answer.Instead of trying every divisor from 1 to max(nums), we binary search over divisor values. For each candidate mid, we ask:"Does dividing all elements by mid (ceiling) give a sum ≤ threshold?"This feasibility check runs in O(N), making the whole approach O(N log(max(nums))).The Feasibility Check — Ceiling Sum SimulationGiven a divisor mid, compute the sum of ⌈arr[i] / mid⌉ for all elements. If the total sum ≤ threshold, then mid is a valid divisor.In Java, ceiling division of integers is done as:Math.ceil((double) arr[i] / mid)Binary Search StrategyIf canDivide(mid) is true → mid might be the answer, but try smaller. Set ans = mid, high = mid - 1.If canDivide(mid) is false → divisor is too small, increase it. Set low = mid + 1.Dry Run — Example 1 (Step by Step)Input: nums = [1, 2, 5, 9], threshold = 6We start with low = 1 and high = 9 (max element in array).Iteration 1: mid = 1 + (9 - 1) / 2 = 5Compute ceiling sum with divisor 5: ⌈1/5⌉ + ⌈2/5⌉ + ⌈5/5⌉ + ⌈9/5⌉ = 1 + 1 + 1 + 2 = 55 ≤ 6 → ✅ Valid. Record ans = 5, search smaller → high = 4.Iteration 2: mid = 1 + (4 - 1) / 2 = 2Compute ceiling sum with divisor 2: ⌈1/2⌉ + ⌈2/2⌉ + ⌈5/2⌉ + ⌈9/2⌉ = 1 + 1 + 3 + 5 = 1010 > 6 → ❌ Too large. Increase divisor → low = 3.Iteration 3: mid = 3 + (4 - 3) / 2 = 3Compute ceiling sum with divisor 3: ⌈1/3⌉ + ⌈2/3⌉ + ⌈5/3⌉ + ⌈9/3⌉ = 1 + 1 + 2 + 3 = 77 > 6 → ❌ Too large. Increase divisor → low = 4.Iteration 4: mid = 4 + (4 - 4) / 2 = 4Compute ceiling sum with divisor 4: ⌈1/4⌉ + ⌈2/4⌉ + ⌈5/4⌉ + ⌈9/4⌉ = 1 + 1 + 2 + 3 = 77 > 6 → ❌ Too large. Increase divisor → low = 5.Loop ends: low (5) > high (4). Binary search terminates.Output: ans = 5 ✅The Code Implementationclass Solution {/*** Feasibility Check (Helper Function)** Given a divisor 'mid', this function computes the ceiling sum of* all elements divided by 'mid' and checks if it is within threshold.** @param mid - candidate divisor to test* @param arr - input array* @param thresh - the allowed threshold for the sum* @return true if the ceiling division sum <= threshold, false otherwise*/public boolean canDivide(int mid, int[] arr, int thresh) {int sumOfDiv = 0;for (int i = 0; i < arr.length; i++) {// Ceiling division: Math.ceil(arr[i] / mid)// Cast to double to avoid integer division truncationsumOfDiv += Math.ceil((double) arr[i] / mid);}// If total sum is within threshold, this divisor is validreturn sumOfDiv <= thresh;}/*** Main Function — Binary Search on the Answer** Search range: [1, max(nums)]* - low = 1 → smallest valid positive divisor* - high = max(nums) → guarantees every ceil(num/divisor) = 1,* so sum = nums.length <= threshold (always valid)** @param nums - input array* @param threshold - maximum allowed sum after ceiling division* @return smallest divisor such that the ceiling division sum <= threshold*/public int smallestDivisor(int[] nums, int threshold) {int min = 1; // Lower bound: divisor starts at 1int max = Integer.MIN_VALUE; // Will become max(nums)int ans = 1;// Find the upper bound of binary search (max element)for (int a : nums) {max = Math.max(max, a);}// Binary Search over the divisor spacewhile (min <= max) {int mid = min + (max - min) / 2; // Safe midpoint, avoids overflowif (canDivide(mid, nums, threshold)) {// mid is valid — record it and try a smaller divisorans = mid;max = mid - 1;} else {// mid is too small — the sum exceeded threshold, go highermin = mid + 1;}}return ans; // Smallest valid divisor}}Code Walkthrough — Step by StepSetting bounds: We iterate through nums once to find max — this becomes our upper bound high. The lower bound low = 1 because divisors must be positive integers.Binary Search loop: We pick mid = min + (max - min) / 2 as the candidate divisor. We check if using mid as the divisor keeps the ceiling sum ≤ threshold.Feasibility helper (canDivide): For each element, we compute Math.ceil((double) arr[i] / mid) and accumulate the total. The cast to double is critical — without it, Java performs integer division (which truncates, not rounds up).Narrowing the search: If the sum is within threshold → record ans = mid, try smaller (max = mid - 1). If the sum exceeds threshold → divisor is too small, increase it (min = mid + 1).A Critical Bug to Watch Out For — The return min vs return ans TrapIn your original code, the final line was return min instead of return ans. This is a subtle bug. After the loop ends, min has overshot past the answer (it's now ans + 1). Always store the answer in a dedicated variable ans and return that. Using return min would return the wrong result in most cases.Common Mistakes to AvoidWrong lower bound: Setting low = min(nums) instead of low = 1 seems intuitive but is wrong. A divisor smaller than the minimum element is still valid — for example, dividing [5, 9] by 3 gives ⌈5/3⌉ + ⌈9/3⌉ = 2 + 3 = 5, which could be within threshold.Forgetting ceiling division: Using arr[i] / mid (integer division, which truncates) instead of Math.ceil((double) arr[i] / mid) is wrong. The problem explicitly states results are rounded up.Returning min instead of ans: After the binary search loop ends, min > max, meaning min has already gone past the valid answer. Always return the stored ans.Integer overflow in midpoint: Always use mid = min + (max - min) / 2 instead of (min + max) / 2. When both values are large (up to 10⁶), their sum can overflow an int.Complexity AnalysisTime Complexity: O(N × log(max(nums)))Binary search runs over [1, max(nums)] → at most log₂(10⁶) ≈ 20 iterations.Each iteration calls canDivide which is O(N).Total: O(N log M) where M = max(nums).Space Complexity: O(1) No extra data structures — only a few integer variables are used throughout.How This Relates to LeetCode 1011This problem and LeetCode 1011 (Ship Packages Within D Days) are almost identical in structure:🔗 LeetCode 1011 #Search space: [max(weights), sum(weights)]Feasibility check: Can we ship in ≤ D days?Monotonic property: More capacity → fewer daysGoal: Minimize capacityLeetCode 1283Search space: [1, max(nums)]Feasibility check: Is ceiling sum ≤ threshold?Monotonic property: Larger divisor → smaller sumGoal: Minimize divisorOnce you deeply understand one, the other takes minutes to solve.Similar Problems (Same Pattern — Binary Search on Answer)LeetCode 875 — Koko Eating Bananas [ Blog is also avaliable on this - Read Now ]LeetCode 1011 — Capacity To Ship Packages Within D Days [ Blog is also avaliable on this - Read Now ]LeetCode 410 — Split Array Largest SumLeetCode 2064 — Minimized Maximum of Products Distributed to Any StoreAll follow the same template: identify a monotonic answer space, write an O(N) feasibility check, and binary search over it.Key Takeaways✅ When the problem asks "find the minimum value such that a condition holds" — think Binary Search on the Answer.✅ The lower bound is the most constrained valid value (1 here, since divisors must be positive).✅ The upper bound is the least constrained valid value (max element, guarantees sum = length ≤ threshold).✅ Ceiling division in Java requires casting to double: Math.ceil((double) a / b).✅ Always store the answer in a separate ans variable — never return min or max directly after a binary search loop.Happy Coding! Smash that upvote if this helped you crack the pattern. 🚀

LeetCodeBinary SearchMediumJavaBinary Search on AnswerArraysCeiling Division

LeetCode 121 — Best Time to Buy and Sell Stock I | Two Pointer / Sliding Window Explained

🚀 Try This Problem First!Before reading the solution, attempt it yourself on LeetCode — you'll retain the concept far better.🔗 Problem Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/Understanding the ProblemYou are given an array prices where prices[i] is the stock price on day i. You can buy on one day and sell on a later day. You want to maximize your profit.Goal: Return the maximum profit possible. If no profit can be made, return 0.Key Rules:You must buy before you sell — no going back in time.You can only make one transaction (one buy, one sell).If prices only go down, profit is impossible — return 0.Constraints:1 ≤ prices.length ≤ 10⁵0 ≤ prices[i] ≤ 10⁴Understanding the Problem With a Real-World AnalogyImagine you're watching a stock ticker for a week. You want to pick the single best day to buy and a later day to sell. You can't predict the future — you just have historical prices. The question is: looking back at all the prices, what was the best single buy-sell pair you could have chosen?Key Observation (Before Writing a Single Line of Code)The profit on any given pair of days is:profit = prices[sell_day] - prices[buy_day]To maximize profit, for every potential sell day, we want the lowest possible buy price seen so far to the left of it. This is the core insight that drives the efficient solution.If at any point the current price is lower than our tracked minimum, there is no point keeping the old minimum — the new one is strictly better for any future sell day.Intuition — The Two Pointer ApproachWe use two pointers i (buy pointer) and j (sell pointer), both starting at the beginning with i = 0 and j = 1.At every step we ask: is prices[j] greater than prices[i]?If yes → this is a profitable pair. Compute the profit and update the maximum if it's better.If no → prices[j] is cheaper than prices[i]. There's no reason to keep i where it is — any future sell day would be better served by buying at j instead. So we move i to j.Either way, j always moves forward by 1 until it reaches the end of the array.Why Moving i to j is CorrectThis is the most important conceptual point. When prices[j] < prices[i], you might wonder — why not just skip j and move on? Why move i?Because for any future day k > j, the profit buying at j is:prices[k] - prices[j]And the profit buying at i is:prices[k] - prices[i]Since prices[j] < prices[i], buying at j will always give a higher or equal profit for the same sell day k. So we update i = j — there is no scenario where keeping the old i is better.Dry Run — Example 1 (Step by Step)Input: prices = [7, 1, 5, 3, 6, 4]We start with i = 0, j = 1, maxP = 0.Step 1: i = 0, j = 1 → prices[i] = 7, prices[j] = 17 > 1 → prices[j] is cheaper. Move i to j. i = 1, j moves to 2. maxP = 0.Step 2: i = 1, j = 2 → prices[i] = 1, prices[j] = 51 < 5 → Profitable! profit = 5 - 1 = 4. 4 > 0 → update maxP = 4. j moves to 3.Step 3: i = 1, j = 3 → prices[i] = 1, prices[j] = 31 < 3 → Profitable! profit = 3 - 1 = 2. 2 < 4 → maxP stays 4. j moves to 4.Step 4: i = 1, j = 4 → prices[i] = 1, prices[j] = 61 < 6 → Profitable! profit = 6 - 1 = 5. 5 > 4 → update maxP = 5. j moves to 5.Step 5: i = 1, j = 5 → prices[i] = 1, prices[j] = 41 < 4 → Profitable! profit = 4 - 1 = 3. 3 < 5 → maxP stays 5. j moves to 6. j = 6 = prices.length → loop ends.Output: maxP = 5 ✅ (Buy at day 2 price=1, sell at day 5 price=6)Dry Run — Example 2 (Step by Step)Input: prices = [7, 6, 4, 3, 1]We start with i = 0, j = 1, maxP = 0.Step 1: i = 0, j = 1 → prices[i] = 7, prices[j] = 67 > 6 → Move i to j. i = 1, j moves to 2. maxP = 0.Step 2: i = 1, j = 2 → prices[i] = 6, prices[j] = 46 > 4 → Move i to j. i = 2, j moves to 3. maxP = 0.Step 3: i = 2, j = 3 → prices[i] = 4, prices[j] = 34 > 3 → Move i to j. i = 3, j moves to 4. maxP = 0.Step 4: i = 3, j = 4 → prices[i] = 3, prices[j] = 13 > 1 → Move i to j. i = 4, j moves to 5. j = 5 = prices.length → loop ends.Output: maxP = 0 ✅ (Prices only went down, no profitable transaction exists)The Code — Implementationclass Solution {public int maxProfit(int[] prices) {int i = 0; // Buy pointer — points to the current minimum price dayint j = 1; // Sell pointer — scans forward through the arrayint maxP = 0; // Tracks the maximum profit seen so far// j scans from day 1 to the end of the arraywhile (i < j && j < prices.length) {if (prices[i] > prices[j]) {// prices[j] is cheaper than current buy price// Move buy pointer to j — buying here is strictly better// for any future sell dayi = j;} else {// prices[j] > prices[i] — this is a profitable pair// Calculate profit and update maxP if it's the best so farint profit = prices[j] - prices[i];if (profit > maxP) {maxP = profit;}}// Always move the sell pointer forwardj++;}// If no profitable transaction was found, maxP remains 0return maxP;}}Code Walkthrough — Step by StepInitialization: i = 0 acts as our buy day pointer (always pointing to the lowest price seen so far). j = 1 is our sell day pointer scanning forward. maxP = 0 is our answer — defaulting to 0 handles the case where no profit is possible.The loop condition: i < j ensures we never sell before buying. j < prices.length ensures we don't go out of bounds.When prices[i] > prices[j]: The current sell day price is cheaper than our buy day. We update i = j, because buying at j dominates buying at i for all future sell days.When prices[j] >= prices[i]: We have a potential profit. We compute it and update maxP if it beats the current best.j always increments: Regardless of which branch we take, j++ moves the sell pointer forward every iteration — this is what drives the loop to completion.Common Mistakes to AvoidNot returning 0 for no-profit cases: If prices are strictly decreasing, maxP never gets updated and stays 0. The initialization maxP = 0 handles this correctly — never initialize it to a negative number.Using a nested loop (brute force): A common first instinct is two nested loops checking every pair. That is O(N²) and will TLE on large inputs. The two pointer approach solves it in O(N).Thinking you need to sort: Sorting destroys the order of days, which is fundamental to the problem. Never sort the prices array here.Moving i forward by 1 instead of to j: When prices[j] < prices[i], some people write i++ instead of i = j. This is wrong — you might miss the new minimum entirely and waste iterations.Complexity AnalysisTime Complexity: O(N) The j pointer traverses the array exactly once from index 1 to the end. The i pointer only moves forward and never exceeds j. So the entire algorithm is a single linear pass — O(N).Space Complexity: O(1) No extra arrays, maps, or stacks are used. Only three integer variables — i, j, and maxP.Alternative Way to Think About It (Min Tracking)Some people write this problem using a minPrice variable instead of two pointers. Both approaches are equivalent — the two pointer framing is slightly more intuitive visually, but here is the min-tracking version for reference:int minPrice = Integer.MAX_VALUE;int maxProfit = 0;for (int price : prices) {if (price < minPrice) {minPrice = price;} else if (price - minPrice > maxProfit) {maxProfit = price - minPrice;}}return maxProfit;The logic is the same — always track the cheapest buy day seen so far, and for each day compute what profit would look like if you sold today.Similar Problems (Build on This Foundation)LeetCode 122 — Best Time to Buy and Sell Stock II (multiple transactions allowed) [ Blog is also avaliable on this - Read Now ]LeetCode 123 — Best Time to Buy and Sell Stock III (at most 2 transactions) [ Blog is also avaliable on this - Read Now ]LeetCode 188 — Best Time to Buy and Sell Stock IV (at most k transactions)LeetCode 309 — Best Time to Buy and Sell Stock with CooldownLeetCode 714 — Best Time to Buy and Sell Stock with Transaction FeeLeetCode 121 is the foundation. Master this one deeply before moving to the others — they all build on the same core idea.Key Takeaways✅ For every potential sell day, the best buy day is always the minimum price seen to its left — this drives the whole approach.✅ When the sell pointer finds a cheaper price than the buy pointer, always move the buy pointer there — it strictly dominates the old buy day for all future sells.✅ Initialize maxP = 0 so that no-profit scenarios (prices only going down) are handled automatically.✅ The two pointer approach solves this in a single linear pass — O(N) time and O(1) space.✅ j always increments every iteration — i only moves when a cheaper price is found.Happy Coding! If this clicked for you, the entire Stock series on LeetCode will feel much more approachable.

LeetCodeTwo PointersEasyJavaDSA

Find All Duplicates in an Array

LeetCode Problem 448 – Find All Numbers Disappeared in an ArrayProblem Link: LinkProblem StatementYou are given an array nums of length n, where each element nums[i] lies in the range [1, n]. Your task is to return all numbers in the range [1, n] that do not appear in the array.Example 1Inputnums = [4, 3, 2, 7, 8, 2, 3, 1]Output[5, 6]Example 2Inputnums = [1, 1]Output[2]Constraintsn == nums.length1 ≤ n ≤ 10⁵1 ≤ nums[i] ≤ nApproachThe goal is to identify numbers within the range 1 to n that are missing from the given array.One straightforward way to solve this problem is by using a HashMap to track the presence of each number:Traverse the array and store each element in a HashMap.Iterate through the range 1 to n.For each number, check whether it exists in the HashMap.If a number is not present, add it to the result list.This approach ensures that:Each element is processed only once.Lookup operations are efficient.Time and Space ComplexityTime Complexity: O(n)Space Complexity: O(n) (due to the HashMap)Solution Code (Java)public List<Integer> findDisappearedNumbers(int[] nums) { HashMap<Integer, Integer> map = new HashMap<>(); List<Integer> result = new ArrayList<>(); // Store all elements in the HashMap for (int num : nums) { map.put(num, 0); } // Check for missing numbers in the range [1, n] for (int i = 1; i <= nums.length; i++) { if (!map.containsKey(i)) { result.add(i); } } return result;}Final NotesWhile this solution is simple and easy to understand, it uses additional space.LeetCode also offers a constant space solution by modifying the input array in-place, which is worth exploring for optimization.

LeetCodeMediumHashMap

Equilibrium Point

GeeksforGeeks ProblemLink of the Problem to try -: LinkGiven an array of integers arr[], the task is to find the first equilibrium point in the array.The equilibrium point in an array is an index (0-based indexing) such that the sum of all elements before that index is the same as the sum of elements after it. Return -1 if no such point exists.Examples:Input: arr[] = [1, 2, 0, 3]Output: 2Explanation: The sum of left of index 2 is 1 + 2 = 3 and sum on right of index 2 is 3.Input: arr[] = [1, 1, 1, 1]Output: -1Explanation: There is no equilibrium index in the array.Input: arr[] = [-7, 1, 5, 2, -4, 3, 0]Output: 3Explanation: The sum of left of index 3 is -7 + 1 + 5 = -1 and sum on right of index 3 is -4 + 3 + 0 = -1.Constraints:3 <= arr.size() <= 105-104 <= arr[i] <= 104Solution:Solving the Equilibrium Index ProblemThe core logic of this problem is finding the Prefix Sum and Suffix Sum. The goal is to identify the specific index where the sum of elements on the left equals the sum of elements on the right.For beginners, this problem can feel difficult because it isn't immediately obvious how to "balance" the two sides of an array. Understanding these two concepts makes the solution simple:Prefix Sum: The cumulative sum of elements from left to right. We store the total sum at each index as we move forward.Suffix Sum: The cumulative sum of elements from right to left. We store the total sum at each index as we move backward.By comparing these two sums, you can easily find the Equilibrium Point where the two halves of the array are equal.Code:class Solution {// Function to find equilibrium point in the array.public static int findEquilibrium(int arr[]) {// code hereint prefix[] = new int[arr.length];int suffix[] = new int[arr.length];int presum=0;for(int i=0;i<arr.length;i++){presum+=arr[i];prefix[i] = presum;}int suffsum=0;for(int i=arr.length-1;i>=0;i--){suffsum+=arr[i];suffix[i] = suffsum;}for(int i=0;i<suffix.length;i++){if(suffix[i] == prefix[i]){return i;}}return -1;}}

GeeksforGeeksPrefix SumEasy