Search Blogs

Showing results for "LeetCode Medium"

Found 30 results

Majority Element II

LeetCode Problem 229Link of the Problem to try -: LinkGiven an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. Example 1:Input: nums = [3,2,3]Output: [3]Example 2:Input: nums = [1]Output: [1]Example 3:Input: nums = [1,2]Output: [1,2] Constraints:1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109Solution:According to question says we have to create ArrayList in which we have to return those elements whose frequency count is more than array's length divided by 3 and we have to return it simply this is it.And personally if I say this is a very easy question as there you don't need to think very much you can simply create a HashMap in which you maintain frequency of each element and then simply run a for each loop and iterate over the keys by keySet method of HashMap and then get value of each key and check is it greater than array.length/3 or not if it is then simply add in the ArrayList and here you got your ans.Code: public List<Integer> majorityElement(int[] nums) { HashMap<Integer, Integer> mp = new HashMap<>(); List<Integer> lis = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { mp.put(nums[i], mp.getOrDefault(nums[i], 0) + 1); } for (int i : mp.keySet()) { if (mp.get(i) > nums.length / 3) { lis.add(i); } } return lis; }

LeetCodeMediumHashMap

Maximum Product Subarray

LeetCode Problem 152Link of the Problem to try -: LinkGiven an integer array nums, find a subarray that has the largest product, and return the product.The test cases are generated so that the answer will fit in a 32-bit integer.Note that the product of an array with a single element is the value of that element.Example 1:Input: nums = [2,3,-2,4]Output: 6Explanation: [2,3] has the largest product 6.Example 2:Input: nums = [-2,0,-1]Output: 0Explanation: The result cannot be 2, because [-2,-1] is not a subarray.Constraints:1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10The product of any subarray of nums is guaranteed to fit in a 32-bit integer.Solution:Approach(1)In this approach we have to just multiply all the elements of our array from left to right and right to left also we have to ensure that whenever our multiplication goes to negative it must be reset to 1 so that when next element multiply it not be negative or zero as well due to this approach we will traverse the whole array one time and that's why it's time complexity is O(n).Solution Code:public int maxProduct(int[] nums) {int max =Integer.MIN_VALUE;int l =1;int r =1;int rev = nums.length-1;for(int i =0;i <nums.length;i++){if(l ==0) l =1;if(r ==0) r =1;l*=nums[i];r*=nums[rev];rev--;max = Math.max(max,Math.max(l,r));}return max;}Approach(2)In this approach we will create two variables like currmin and currmax these two variales will be store the maximum multiplied value and the minimum multiply value just the thing we have to handle is that whenever we got a negative value in the arrya we have to interchange the value of both variables because if we got a negative value then if that value multiply by the currmax variable then make it's value minimum as (+ x - = -) that's why we have to interchange the values of both variables.here is the approach code:public int maxProduct(int[] nums) {int maxi = nums[0];int currmax =nums[0];int currmin= nums[0];for(int i=1;i <nums.length;i++){if(nums[i] <0){int temp = currmax;currmax = currmin;currmin = temp;}currmax = Math.max(nums[i],nums[i] *currmax);currmin = Math.min(nums[i],nums[i] *currmin);maxi = Math.max(maxi,currmax);}return maxi;}

LeetcodeMediumArray

Maximum Absolute Sum of Any Subarray

LeetCode Problem 1749Link of the Problem to try -: LinkYou are given an integer array nums. The absolute sum of a subarray [numsl, numsl+1, ..., numsr-1, numsr] is abs(numsl + numsl+1 + ... + numsr-1 + numsr).Return the maximum absolute sum of any (possibly empty) subarray of nums.Note that abs(x) is defined as follows:If x is a negative integer, then abs(x) = -x.If x is a non-negative integer, then abs(x) = x.Example 1:Input: nums = [1,-3,2,3,-4]Output: 5Explanation: The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.Example 2:Input: nums = [2,-5,1,-4,3,-2]Output: 8Explanation: The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.Constraints:1 <= nums.length <= 105-104 <= nums[i] <= 104My ThinkingSo, in this question what exactly we have to do what actual logic behind it to solve this question is that like you need to first find out the maximum sum of sub array via kadane's algorithm also find the minimum sum of subarray and then compare both numbers ignore the negative signs of it and then return the maximum number that is what the question want and we have to solve in it.Kadane's AlgorithmThis algorithm is highly efficient, solving the problem in a single pass with a time complexity of O(n), not O(1) constant time, as the algorithm must iterate through all n elements of the input array.The core principle is based on the idea that any negative prefix sum acts as a 'debt' that subsequent positive numbers must overcome. The strategy is to always pursue the maximum sum. If the running sum becomes negative at any point, it is reset to zero, effectively 'discarding' the previous negative sequence, and the search for a new maximum sum begins with the next element.Here is a video for more better understandingSolution:Here is the solution for this quesiton in java by Kadane's Algorithmpublic int maxAbsoluteSum(int[] nums) {int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;int maxSum=0;int minSum=0;for(int i =0 ; i< nums.length;i++){maxSum = Math.max(maxSum+nums[i],nums[i]);max = Math.max(max,maxSum);minSum = Math.min(minSum+nums[i],nums[i]);min = Math.min(min,minSum);}return Math.max(max,Math.abs(min));}

leetcodemediumkadane algorithm

Maximum Subarray

LeetCode Problem 53Link of the Problem to try -: LinkGiven an integer array nums, find the subarray with the largest sum, and return its sum.Example 1:Input: nums = [-2,1,-3,4,-1,2,1,-5,4]Output: 6Explanation: The subarray [4,-1,2,1] has the largest sum 6.Example 2:Input: nums = [1]Output: 1Explanation: The subarray [1] has the largest sum 1.Example 3:Input: nums = [5,4,-1,7,8]Output: 23Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.Constraints:1 <= nums.length <= 105-104 <= nums[i] <= 104Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.My Approach -: I successfully addressed this problem by implementing nested loops to generate the required subarrays. My approach effectively handles the subarray creation logic as specified. Please find the implementation code below.int ans=0;for(int i=0;i<nums.length;i++){int sum =0;for(int j =i;j<nums.length;j++){sum += nums[j];ans = Math.max(sum,ans);}}return ans;Although this solution passed local tests, it encountered a 'Time Limit Exceeded' (TLE) error on LeetCode due to the constraints of the problem. While the nested loop approach is logically sound, further optimization is required to improve its time complexity for larger test cases.Optimized Algorithm (Kadane's Algorithm)This algorithm is highly efficient, solving the problem in a single pass with a time complexity of O(n), not O(1) constant time, as the algorithm must iterate through all n elements of the input array.The core principle is based on the idea that any negative prefix sum acts as a 'debt' that subsequent positive numbers must overcome. The strategy is to always pursue the maximum sum. If the running sum becomes negative at any point, it is reset to zero, effectively 'discarding' the previous negative sequence, and the search for a new maximum sum begins with the next element.Here is a video for more better understandingMy Understanding Steps to solve this QuestionTo solve this problem efficiently in (O(n)) time, I implemented the following steps:Initialization: Define two integer variables: currentSum (initialized to 0) and maxSum (initialized to Integer.MIN_VALUE). currentSum tracks the running total, while maxSum stores the overall maximum subarray sum found so far.Iteration: Traverse the array using a single for loop.Update Running Sum: At each element, add its value to currentSum.Update Maximum: Compare currentSum with maxSum. If currentSum is greater, update maxSum with this new value.Reset Negative Sums: If currentSum drops below zero, reset it to 0. This effectively "discards" a negative prefix that would otherwise reduce the sum of subsequent subarrays.Return Result: After the loop completes, return maxSum as the final result.Here is the Code:int sum = 0;int max = Integer.MIN_VALUE;for(int i=0;i <nums.length;i++){sum +=nums[i];max =Math.max(sum,max);if(sum < 0){sum =0;}}return max;(Note this same solution can also write in another way as well)Here is another way to write this same solution:int sum = 0;int max = Integer.MIN_VALUE;for(int i=0;i <nums.length;i++){// sum +=nums[i];sum = Math.max(sum+nums[i],nums[i]); // Here we are ensuring that sum will alwaays be grestest in all time so that it will not be negative or smaller ass previously we directly putting value in it.max =Math.max(sum,max);// if(sum < 0){ We don't need this as we already ensure that sum will never be negative and always a positive number// sum =0;// }}return max;

LeetCodeArrayMedium

Sort Colors

LeetCode Problem 75 Link of the Problem to try -: LinkProblem Statement :- Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.Example 1:Input: nums = [2,0,2,1,1,0]Output: [0,0,1,1,2,2]Example 2:Input: nums = [2,0,1]Output: [0,1,2]You must solve this problem without using the library's sort function.My Approach (1)I have solved this question via my approach by counting frequency of each element like 0,1 and 2 as I avoid to use nested loops but i used for loops multiple times but as loops are used in a constant space of time that's why they did not increases the time complexity that's why my solution time complexity is O(n) even though I need to traverse array multiple time.Here is the Approach:int zeroCounter= 0;int oneCounter = 0;int twoCounter=0;int counter =0;for(int i =0; i< nums.length; i++){if(nums[i] == 0){zeroCounter++;}else if(nums[i] == 1){oneCounter++;}else{twoCounter++;}}for(int i=0; i<zeroCounter;i++){nums[i] = 0;counter++;}for(int i=0; i<oneCounter;i++){nums[counter] = 1;counter++;}for(int i=0; i<twoCounter;i++){nums[counter] = 2;counter++;}My Approach (2)This approach uses a algorithm called DNF (Dutch National Flag) Algorithm in this algorithm we have to focus on two elements out of three and make sure those two element are on the correct place as the last one came automatically to the correct position even though my approach(1) is uses loops multiple time but this approach is also take O(n) time complexity but uses loop one time that's why this approach is far cleaner than approach (1).int low =0;int high= nums.length-1;int curr =0;while(curr <= high){if(nums[curr] == 0){int temp = nums[low];nums[low] = nums[curr];nums[curr] = temp;low++;curr++;}else if( nums[curr] == 1){curr++;}else{int temp = nums[curr];nums[curr] = nums[high];nums[high] = temp;high--;}}

LeetCodeMediumTwo PointerDutchman Flag Algorithm

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

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

Single Number III

LeetCode Problem 260Link of the Problem to try -: LinkGiven an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.You must write an algorithm that runs in linear runtime complexity and uses only constant extra space. Example 1:Input: nums = [1,2,1,3,2,5]Output: [3,5]Explanation: [5, 3] is also a valid answer.Example 2:Input: nums = [-1,0]Output: [-1,0]Example 3:Input: nums = [0,1]Output: [1,0] Constraints:2 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1Each integer in nums will appear twice, only two integers will appear once.Solution:It is a very easy question if we only know about HashMap because it is clearly telling us about to create frequency and to return that number whose frequency is exactly 1 so that's why in this question not a very different or bug thing is there that we have to think about very much.Code: HashMap<Integer,Integer> mp = new HashMap<>(); int ans[] =new int[2]; for(int i=0;i<nums.length;i++){ mp.put(nums[i],mp.getOrDefault(nums[i],0)+1); } int co =0; for(int a:mp.keySet()){ if(mp.get(a) == 1){ ans[co] = a; co++; } } return ans;

LeetCodeMediumHashMapArray

Contains Duplicate

LeetCode Problem 217Link of the Problem to try -: LinkGiven an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.Example 1:Input: nums = [1,2,3,1]Output: trueExplanation:The element 1 occurs at the indices 0 and 3.Example 2:Input: nums = [1,2,3,4]Output: falseExplanation:All elements are distinct.Example 3:Input: nums = [1,1,1,3,3,4,3,2,4,2]Output: trueConstraints:1 <= nums.length <= 105-109 <= nums[i] <= 109Solution:1. The HashMap ApproachUsing a HashMap is a highly effective way to track occurrences. Although we are only checking for the existence of a value, the HashMap logic allows us to store the element as a "Key" and its frequency as a "Value."Logic:Iterate through the nums array.Before inserting an element, check if the HashMap already contains that key.If it exists, you've found your duplicate—return true.Otherwise, put the value into the map and continue.Code:public boolean containsDuplicate(int[] nums) {HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {// Check if the current number is already a key in our mapif (map.containsKey(nums[i])) {return true;}// Map the number to its count (1)map.put(nums[i], 1);}return false;}2. The HashSet Approach (Optimized for Storage)While similar to the HashMap, the HashSet is often more appropriate for this specific problem because we only care if a number exists, not how many times it appears or what its index is.Logic:We initialize an empty HashSet.As we loop through the array, we check ms.contains(nums[i]).If the set already has the number, it's a duplicate.This approach is preferred over HashMap for this problem because it uses less memory and has cleaner syntax.Code:public boolean containsDuplicate(int[] nums) {HashSet<Integer> ms = new HashSet<>();for (int i = 0; i < nums.length; i++) {if (ms.contains(nums[i])) {return true;}ms.add(nums[i]);}return false;}3. The Sorting & Two-Pointer ApproachIf you want to avoid using extra memory (like a Set or Map), you can use the Two-Pointer method combined with Sorting.Logic:First, we sort the array. This ensures that any duplicate values are placed next to each other.We use two pointers: j (the previous element) and i (the current element).By moving these pointers across the array, we compare the values. If nums[i] == nums[j], a duplicate exists.Code:public boolean containsDuplicate(int[] nums) {// Step 1: Sort the arrayArrays.sort(nums);// Step 2: Use two pointers to compare adjacent elementsint j = 0;for (int i = 1; i < nums.length; i++) {if (nums[i] == nums[j]) {return true; // Duplicate found}j++; // Move the previous pointer forward}return false;}Performance SummaryApproachTime ComplexitySpace ComplexityRecommendationHashSetO(n)O(n)Best Overall – Fastest performance.HashMapO(n)O(n)Good, but HashSet is cleaner for this use case.Two PointerO(n \log n)O(1)Best for Memory – Use if space is limited.Final ThoughtsChoosing the right approach depends on whether you want to prioritize speed (HashSet) or memory efficiency (Two-Pointer). For most coding interviews, the HashSet solution is the "Gold Standard" due to its linear time complexity.

LeetCodeEasyHashMap

LeetCode 2390: Removing Stars From a String — Java Solution With All Approaches Explained

Introduction: What Is LeetCode 2390 Removing Stars From a String?If you are preparing for coding interviews at companies like Google, Amazon, or Microsoft, LeetCode 2390 Removing Stars From a String is a must-solve problem. It tests your understanding of the stack data structure and string manipulation — two of the most frequently tested topics in technical interviews.In this article, we will cover:What the problem is asking in plain English3 different Java approaches (Brute Force, Stack, StringBuilder)Step-by-step dry run with examplesTime and space complexity for each approachCommon mistakes to avoidFAQs that appear in Google's People Also AskLet's dive in!Problem Statement SummaryYou are given a string s containing lowercase letters and stars *. In one operation:Choose any * in the stringRemove the * itself AND the closest non-star character to its leftRepeat until all stars are removed and return the final string.Example:Input: s = "leet**cod*e"Output: "lecoe"Real Life Analogy — Think of It as a Backspace KeyImagine you are typing on a keyboard. Every * acts as your backspace key — it deletes itself and the character just before it.You type "leet" and press backspace twice:Backspace 1 → deletes t → "lee"Backspace 2 → deletes e → "le"That is exactly what this problem simulates! Once you see it this way, the solution becomes very obvious.Approach 1: Brute Force Simulation (Beginner Friendly)IdeaDirectly simulate the process the problem describes:Scan the string from left to rightFind the first *Remove it and the character just before itRepeat until no stars remainJava Codepublic String removeStars(String s) {StringBuilder sb = new StringBuilder(s);int i = 0;while (i < sb.length()) {if (sb.charAt(i) == '*') {sb.deleteCharAt(i); // remove the starif (i > 0) {sb.deleteCharAt(i - 1); // remove closest left characteri--;}} else {i++;}}return sb.toString();}Time and Space ComplexityComplexityValueReasonTimeO(n²)Each deletion shifts all remaining charactersSpaceO(n)StringBuilder storage⚠️ Important WarningThis problem has n up to 100,000. Brute force will get Time Limit Exceeded (TLE) on LeetCode. Use this only to understand the concept, never in production or interviews.Approach 2: Stack Based Solution (Interview Favorite)IdeaA stack is the perfect data structure here because:We always remove the most recently added letter when a * appearsThat is the definition of Last In First Out (LIFO) — exactly what a stack doesAlgorithm:Letter → push onto stack* → pop from stack (removes closest left character)At the end, build result from stack contentsJava Codepublic String removeStars(String s) {Stack<Character> st = new Stack<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '*') {if (!st.empty()) {st.pop();}} else {st.push(c);}}StringBuilder sb = new StringBuilder();while (!st.empty()) {sb.append(st.pop());}return sb.reverse().toString();}Step-by-Step Dry Run — "leet**cod*e"StepCharacterActionStack State1lpush[l]2epush[l,e]3epush[l,e,e]4tpush[l,e,e,t]5*pop t[l,e,e]6*pop e[l,e]7cpush[l,e,c]8opush[l,e,c,o]9dpush[l,e,c,o,d]10*pop d[l,e,c,o]11epush[l,e,c,o,e]✅ Final Answer: "lecoe"Time and Space ComplexityComplexityValueReasonTimeO(n)Single pass through the stringSpaceO(n)Stack holds up to n charactersApproach 3: StringBuilder as Stack (Optimal Solution) ✅IdeaThis is the best and most optimized approach. A StringBuilder can act as a stack:append(c) → works like pushdeleteCharAt(sb.length() - 1) → works like popNo reverse needed at the end unlike the Stack approachJava Codepublic String removeStars(String s) {StringBuilder sb = new StringBuilder();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '*') {if (sb.length() > 0) {sb.deleteCharAt(sb.length() - 1);}} else {sb.append(c);}}return sb.toString();}Step-by-Step Dry Run — "erase*****"StepCharacterActionStringBuilder1eappend"e"2rappend"er"3aappend"era"4sappend"eras"5eappend"erase"6*delete last"eras"7*delete last"era"8*delete last"er"9*delete last"e"10*delete last""✅ Final Answer: ""Why StringBuilder Beats Stack in JavaFactorStack<Character>StringBuilderMemoryBoxes char → Character objectWorks on primitives directlyReverse neededYesNoCode lengthMore verboseCleaner and shorterPerformanceSlightly slowerFasterTime and Space ComplexityComplexityValueReasonTimeO(n)One pass, each character processed onceSpaceO(n)StringBuilder storageAll Approaches Comparison TableApproachTimeSpacePasses LeetCode?Best ForBrute ForceO(n²)O(n)❌ TLEUnderstanding conceptStackO(n)O(n)✅ YesInterview explanationStringBuilderO(n)O(n)✅ YesBest solutionHow This Relates to LeetCode 3174 Clear DigitsIf you have already solved LeetCode 3174 Clear Digits, you will notice this problem is nearly identical:Feature3174 Clear Digits2390 Removing StarsTriggerDigit 0-9Star *RemovesClosest left non-digitClosest left non-starDifficultyEasyMediumBest approachStringBuilderStringBuilderThe exact same solution pattern works for both. This is why learning patterns matters more than memorizing individual solutions!Common Mistakes to Avoid1. Not checking sb.length() > 0 before deleting Even though the problem guarantees valid input, always add this guard. It shows clean, defensive coding in interviews.2. Forgetting to reverse when using Stack Stack gives you characters in reverse order. If you forget .reverse(), your answer will be backwards.3. Using Brute Force for large inputs With n up to 100,000, O(n²) will time out. Always use the O(n) approach.FAQs — People Also AskQ1. What data structure is best for LeetCode 2390? A Stack or StringBuilder used as a stack is the best data structure. Both give O(n) time complexity. StringBuilder is slightly more optimal in Java because it avoids object boxing overhead.Q2. Why does a star remove the closest left character? Because the problem defines it that way — think of * as a backspace key on a keyboard. It always deletes the character immediately before the cursor position.Q3. What is the time complexity of LeetCode 2390? The optimal solution runs in O(n) time and O(n) space, where n is the length of the input string.Q4. Is LeetCode 2390 asked in Google interviews? Yes, this type of stack simulation problem is commonly asked at Google, Amazon, Microsoft, and Meta interviews as it tests understanding of LIFO operations and string manipulation.Q5. What is the difference between LeetCode 2390 and LeetCode 844? Both use the same backspace simulation pattern. In 844 Backspace String Compare, # is the backspace character and you compare two strings. In 2390, * is the backspace and you return the final string.Similar LeetCode Problems to Practice NextProblemDifficultyPattern844. Backspace String CompareEasyStack simulation1047. Remove All Adjacent Duplicates In StringEasyStack simulation3174. Clear DigitsEasyStack simulation20. Valid ParenthesesEasyClassic stack735. Asteroid CollisionMediumStack simulationConclusionLeetCode 2390 Removing Stars From a String is a classic stack simulation problem that every developer preparing for coding interviews should master. The key insight is recognizing that * behaves exactly like a backspace key, which makes a stack or StringBuilder the perfect tool.Quick Recap:Brute force works conceptually but TLEs on large inputsStack solution is clean and great for explaining in interviewsStringBuilder solution is the most optimal in Java — no boxing, no reversal

StringStackMediumLeetCode

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

LeetCode 143 Reorder List - Java Solution Explained

IntroductionLeetCode 143 Reorder List is one of those problems that looks simple when you read it but immediately makes you wonder — where do I even start? There is no single trick that solves it. Instead it combines three separate linked list techniques into one clean solution. Mastering this problem means you have genuinely understood linked lists at an intermediate level.You can find the problem here — LeetCode 143 Reorder List.This article walks through everything — what the problem wants, the intuition behind each step, all three techniques used, a detailed dry run, complexity analysis, and common mistakes beginners make.What Is the Problem Really Asking?You have a linked list: L0 → L1 → L2 → ... → LnYou need to reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...In plain English — take one node from the front, then one from the back, then one from the front, then one from the back, and keep alternating until all nodes are used.Example:Input: 1 → 2 → 3 → 4 → 5Output: 1 → 5 → 2 → 4 → 3Node 1 from front, Node 5 from back, Node 2 from front, Node 4 from back, Node 3 stays in middle.Real Life Analogy — Dealing Cards From Both EndsImagine you have a deck of cards laid out in a line face up: 1, 2, 3, 4, 5. Now you deal them by alternately picking from the left end and the right end of the line:Pick 1 from left → placePick 5 from right → place after 1Pick 2 from left → place after 5Pick 4 from right → place after 2Pick 3 (only one left) → place after 4Result: 1, 5, 2, 4, 3That is exactly what the problem wants. The challenge is doing this efficiently on a singly linked list where you cannot just index from the back.Why This Problem Is Hard for BeginnersIn an array you can just use two pointers — one at the start and one at the end — and swap/interleave easily. But a singly linked list only goes forward. You cannot go backwards. You cannot easily access the last element.This is why the problem requires a three-step approach that cleverly works around the limitations of a singly linked list.The Three Step ApproachEvery experienced developer solves this problem in exactly three steps:Step 1 — Find the middle of the linked list using the Fast & Slow Pointer techniqueStep 2 — Reverse the second half of the linked listStep 3 — Merge the two halves by alternating nodes from eachLet us understand each step deeply before looking at code.Step 1: Finding the Middle — Fast & Slow PointerThe Fast & Slow Pointer technique (also called Floyd's algorithm) uses two pointers moving at different speeds through the list:slow moves one step at a timefast moves two steps at a timeWhen fast reaches the end, slow is exactly at the middle. This works because fast covers twice the distance of slow in the same number of steps.ListNode fast = head;ListNode slow = head;while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next;}// slow is now at the middleFor 1 → 2 → 3 → 4 → 5:Start: slow=1, fast=1Step 1: slow=2, fast=3Step 2: slow=3, fast=5 (fast.next is null, stop)Middle is node 3For 1 → 2 → 3 → 4:Start: slow=1, fast=1Step 1: slow=2, fast=3Step 2: fast.next.next is null, stopslow=2, middle is node 2After finding the middle, we cut the list in two by setting slow.next = null. This disconnects the first half from the second half.Step 2: Reversing the Second HalfOnce we have the second half starting from slow.next, we reverse it. After reversal, what was the last node becomes the first — giving us easy access to the back elements of the original list.public ListNode reverse(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode next = curr.next; // save next curr.next = prev; // reverse the link prev = curr; // move prev forward curr = next; // move curr forward } return prev; // prev is the new head}For second half 3 → 4 → 5 (from the first example):Reverse → 5 → 4 → 3Now we have:First half: 1 → 2 → 3 (but 3 is the end since we cut at slow)Wait — actually after cutting at slow=3: first half is 1 → 2 → 3, second half reversed is 5 → 4Let us be precise. For 1 → 2 → 3 → 4 → 5, slow stops at 3. slow.next = null cuts to give:First half: 1 → 2 → 3 → nullSecond half before reverse: 4 → 5Second half after reverse: 5 → 4Step 3: Merging Two HalvesNow we have two lists and we merge them by alternately taking one node from each:Take from first half, take from second half, take from first half, take from second half...ListNode orig = head; // pointer for first halfListNode newhead = second; // pointer for reversed second halfwhile (newhead != null) { ListNode temp1 = orig.next; // save next of first half ListNode temp2 = newhead.next; // save next of second half orig.next = newhead; // first → second newhead.next = temp1; // second → next of first orig = temp1; // advance first half pointer newhead = temp2; // advance second half pointer}Why do we loop on newhead != null and not orig != null? Because the second half is always equal to or shorter than the first half (we cut at middle). Once the second half is exhausted, the remaining first half nodes are already in the correct position.Complete Solutionclass Solution { public ListNode reverse(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } public void reorderList(ListNode head) { // Step 1: Find middle using fast & slow pointer ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } // Step 2: Reverse second half ListNode newhead = reverse(slow.next); slow.next = null; // cut the list into two halves // Step 3: Merge two halves alternately ListNode orig = head; while (newhead != null) { ListNode temp1 = orig.next; ListNode temp2 = newhead.next; orig.next = newhead; newhead.next = temp1; orig = temp1; newhead = temp2; } }}Complete Dry Run — head = [1, 2, 3, 4, 5]Step 1: Find MiddleList: 1 → 2 → 3 → 4 → 5Initial: slow=1, fast=1Iteration 1: slow=2, fast=3Iteration 2: fast.next=4, fast.next.next=5 → slow=3, fast=5fast.next is null → stopslow is at node 3Step 2: Cut and ReverseCut: slow.next = nullFirst half: 1 → 2 → 3 → nullSecond half: 4 → 5Reverse second half 4 → 5:prev=null, curr=4 → next=5, 4.next=null, prev=4, curr=5prev=4, curr=5 → next=null, 5.next=4, prev=5, curr=nullReturn prev=5Reversed second half: 5 → 4 → nullStep 3: Mergeorig=1, newhead=5Iteration 1:temp1 = orig.next = 2temp2 = newhead.next = 4orig.next = newhead → 1.next = 5newhead.next = temp1 → 5.next = 2orig = temp1 = 2newhead = temp2 = 4List so far: 1 → 5 → 2 → 3Iteration 2:temp1 = orig.next = 3temp2 = newhead.next = nullorig.next = newhead → 2.next = 4newhead.next = temp1 → 4.next = 3orig = temp1 = 3newhead = temp2 = nullList so far: 1 → 5 → 2 → 4 → 3newhead is null → loop endsFinal result: 1 → 5 → 2 → 4 → 3 ✅Dry Run — head = [1, 2, 3, 4]Step 1: Find MiddleInitial: slow=1, fast=1Iteration 1: slow=2, fast=3fast.next=4, fast.next.next=null → stopslow is at node 2Step 2: Cut and ReverseFirst half: 1 → 2 → nullSecond half: 3 → 4Reversed: 4 → 3 → nullStep 3: Mergeorig=1, newhead=4Iteration 1:temp1=2, temp2=31.next=4, 4.next=2orig=2, newhead=3List: 1 → 4 → 2 → 3Iteration 2:temp1=null (2.next was originally 3 but we cut at slow=2, so 2.next = null... wait)Actually after cutting at slow=2, first half is 1 → 2 → null, so orig when it becomes 2, orig.next = null.temp1 = orig.next = nulltemp2 = newhead.next = null2.next = 3, 3.next = nullorig = null, newhead = nullnewhead is null → stopFinal result: 1 → 4 → 2 → 3 ✅Why slow.next = null Must Come After Saving newheadThis is a subtle but critical ordering detail in the code. Look at this sequence:ListNode newhead = reverse(slow.next); // save reversed second half FIRSTslow.next = null; // THEN cut the listIf you cut first (slow.next = null) and then try to reverse, you lose the reference to the second half entirely because slow.next is already null. Always save the second half reference before cutting.Time and Space ComplexityTime Complexity: O(n) — each of the three steps (find middle, reverse, merge) makes a single pass through the list. Total is 3 passes = O(3n) = O(n).Space Complexity: O(1) — everything is done by rearranging pointers in place. No extra arrays, no recursion stack, no additional data structures. Just a handful of pointer variables.This is the optimal solution — linear time and constant space.Alternative Approach — Using ArrayList (Simpler but O(n) Space)If you find the three-step approach hard to implement under interview pressure, here is a simpler approach using extra space:public void reorderList(ListNode head) { // store all nodes in ArrayList for random access List<ListNode> nodes = new ArrayList<>(); ListNode curr = head; while (curr != null) { nodes.add(curr); curr = curr.next; } int left = 0; int right = nodes.size() - 1; while (left < right) { nodes.get(left).next = nodes.get(right); left++; if (left == right) break; // odd number of nodes nodes.get(right).next = nodes.get(left); right--; } nodes.get(left).next = null; // terminate the list}This is much easier to understand and code. Store all nodes in an ArrayList, use two pointers from both ends, and wire up the next pointers.Time Complexity: O(n) Space Complexity: O(n) — ArrayList stores all nodesThis is acceptable in most interviews. Mention the O(1) space approach as the optimal solution if asked.Common Mistakes to AvoidNot cutting the list before merging If you do not set slow.next = null after finding the middle, the first half still points into the second half. During merging, this creates cycles and infinite loops. Always cut before merging.Wrong loop condition for finding the middle The condition fast.next != null && fast.next.next != null ensures fast does not go out of bounds when jumping two steps. Using just fast != null && fast.next != null moves slow one step too far for even-length lists.Looping on orig instead of newhead The merge loop should run while newhead != null, not while orig != null. The second half is always shorter or equal to the first half. Once the second half is done, the remaining first half is already correctly placed.Forgetting to save both temp pointers before rewiring In the merge step, you must save both orig.next and newhead.next before changing any pointers. Changing orig.next first and then trying to access orig.next to save it gives you the wrong node.How This Problem Combines Multiple PatternsThis problem is special because it does not rely on a single technique. It is a combination of three fundamental linked list operations:Fast & Slow Pointer — you saw this concept in problems like finding the middle of a list and detecting cycles (LeetCode 141, 142).Reverse a Linked List — the most fundamental linked list operation, appears in LeetCode 206 and as a subtask in dozens of problems.Merge Two Lists — similar to merging two sorted lists (LeetCode 21) but here order is not sorted, it is alternating.Solving this problem proves you are comfortable with all three patterns individually and can combine them when needed.FAQs — People Also AskQ1. What is the most efficient approach for LeetCode 143 Reorder List? The three-step approach — find middle with fast/slow pointer, reverse second half, merge alternately — runs in O(n) time and O(1) space. It is the optimal solution. The ArrayList approach is O(n) time and O(n) space but simpler to code.Q2. Why use fast and slow pointer to find the middle? Because a singly linked list has no way to access elements by index. You cannot just do list[length/2]. The fast and slow pointer technique finds the middle in a single pass without knowing the length beforehand.Q3. Why reverse the second half instead of the first half? The problem wants front-to-back alternation. If you reverse the second half, its first node is the original last node — exactly what you need to interleave with the front of the first half. Reversing the first half would give the wrong order.Q4. What is the time complexity of LeetCode 143? O(n) time for three linear passes (find middle, reverse, merge). O(1) space since all operations are in-place pointer manipulations with no extra data structures.Q5. Is LeetCode 143 asked in coding interviews? Yes, frequently at companies like Amazon, Google, Facebook, and Microsoft. It is considered a benchmark problem for linked list mastery because it requires combining three separate techniques cleanly under pressure.Similar LeetCode Problems to Practice Next206. Reverse Linked List — Easy — foundation for step 2 of this problem876. Middle of the Linked List — Easy — fast & slow pointer isolated21. Merge Two Sorted Lists — Easy — merging technique foundation234. Palindrome Linked List — Easy — also uses find middle + reverse second half148. Sort List — Medium — merge sort on linked list, uses same split techniqueConclusionLeetCode 143 Reorder List is one of the best Medium linked list problems because it forces you to think in multiple steps and combine techniques rather than apply a single pattern. The fast/slow pointer finds the middle efficiently without knowing the length. Reversing the second half turns the "cannot go backwards" limitation of singly linked lists into a non-issue. And the alternating merge weaves everything together cleanly.Work through the dry runs carefully — especially the pointer saving step in the merge. Once you see why each step is necessary and how they connect, this problem will always feel approachable no matter when it shows up in an interview.

LeetCodeJavaLinked ListTwo PointerFast Slow PointerMedium

Count Subarrays of Size K with Average ≥ Threshold — Sliding Window Solution (LeetCode 1343)

IntroductionLeetCode 1343: Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold is another excellent problem to practice the sliding window technique.The goal is not just to compute values but to count how many subarrays satisfy a given condition efficiently.You are given:An integer array arrAn integer k representing subarray sizeA threshold valueYou must return the number of subarrays of size k whose average is greater than or equal to the threshold.If you'd like to try solving the problem first, you can attempt it here:👉 Try the problem on LeetCode:https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/Problem UnderstandingA direct approach would calculate the average for every subarray of size k. However, recomputing sums repeatedly leads to unnecessary work.To optimize, we use a sliding window, allowing us to reuse previous computations and move efficiently across the array.Key Idea: Sliding Window OptimizationInstead of calculating sums repeatedly:Maintain the sum of the current window.Slide the window by:Adding the next elementRemoving the element leaving the windowCheck if the average satisfies the threshold.Count valid windows.This ensures each element is processed only once.ApproachMaintain two pointers to represent the window.Add elements until window size reaches k.Check if average meets the threshold.Move the window forward.Count valid subarrays.An important optimization: instead of computing average each time, we can compare the sum with threshold * k. However, your current implementation using division also works correctly.Implementation (Java)class Solution { public int numOfSubarrays(int[] arr, int k, int t) { int curr = 0; int i = 0; int j = 0; int co = 0; while (j < arr.length) { curr += arr[j]; if (j - i + 1 < k) { j++; } else { if (j - i + 1 == k) { if (curr / k >= t) { co++; } curr -= arr[i]; i++; j++; } } } return co; }}Dry Run ExampleInput:arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4Valid subarrays:[2,5,5] → avg = 4[5,5,5] → avg = 5[5,5,8] → avg = 6Total valid subarrays = 3Complexity AnalysisTime Complexity: O(n)Each element enters and leaves the window once.Space Complexity: O(1)Only constant extra variables are used.Edge Cases ConsideredThreshold equals zeroMinimum array lengthLarge array sizesNon-integer averagesAll elements smaller than thresholdSliding Window Pattern ImportanceThis problem reinforces the sliding window pattern, which appears frequently in:Fixed-size window problemsMaximum or minimum subarray problemsCounting valid segmentsString window problemsMastering this pattern helps solve many interview questions efficiently.ConclusionThis problem is a strong example of turning a potentially expensive brute-force approach into an efficient linear solution using sliding window.Once you recognize this pattern, many array and string problems become significantly easier to solve.

LeetCodeSliding WindowMedium

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

Longest Repeating Character Replacement – Sliding Window Explained (LeetCode 424)

🔗 Problem LinkLeetCode 424 – Longest Repeating Character Replacement👉 https://leetcode.com/problems/longest-repeating-character-replacement/IntroductionWhen I first looked at this problem, it didn’t immediately feel like a typical sliding window question. It talks about replacing characters, not finding substrings directly.But the moment you carefully read:"Return the length of the longest substring containing the same letter after at most k replacements."That’s when the pattern becomes clear.This is a variable-size sliding window problem where we try to maintain a valid window under a certain condition.In this blog, I’ll explain:The intuition behind the problemWhy sliding window worksThe key tricky conditionStep-by-step explanation of the codeTime and space complexity📌 Problem UnderstandingWe are allowed to:Pick any character in the stringReplace it with any uppercase letterPerform at most k replacementsWe need to find the maximum length substring that can become all the same character after at most k changes.🧠 Key ObservationIn any window (substring):To make all characters the same, we need to:Keep the most frequent characterReplace all other charactersSo the number of replacements required is:Window Size - Maximum Frequency Character in that WindowIf that value is ≤ k, then the window is valid.This is the most important insight in the entire problem.🚀 Why Sliding Window?We are asked for:Longest substringUnder a constraintWith dynamic window expansionThat is a clear sign of the sliding window pattern.We use:i → left pointerj → right pointerHashMap → to track character frequencies💻 Your Codeclass Solution {public int characterReplacement(String s, int k) {HashMap<Character,Integer> mp = new HashMap<>();int i= 0;int j =0;int co =0;while(j < s.length()){mp.put(s.charAt(j),mp.getOrDefault(s.charAt(j),0)+1);int maxfreq = 0;for(int a : mp.values()){maxfreq = Math.max(maxfreq,a);}while((j - i +1)-maxfreq > k){ // Tricky partmp.put(s.charAt(i),mp.get(s.charAt(i))-1);if(mp.get(s.charAt(i)) == 0){mp.remove(s.charAt(i));}i++;}co = Math.max(co,j-i+1);j++;}return co;}}🔍 Step-by-Step Explanation1️⃣ Expanding the Windowmp.put(s.charAt(j), mp.getOrDefault(s.charAt(j), 0) + 1);We add the current character into the frequency map.2️⃣ Finding Maximum Frequencyint maxfreq = 0;for(int a : mp.values()){maxfreq = Math.max(maxfreq,a);}We calculate the highest frequency character inside the window.Why?Because that is the character we will keep.All others will be replaced.3️⃣ The Most Important Condition (Tricky Part)while((j - i +1)-maxfreq > k)Let’s break this:j - i + 1 → Window sizemaxfreq → Count of most frequent characterwindowSize - maxfreq → Replacements neededIf replacements needed > k → window is invalidSo we shrink from left.4️⃣ Shrinking the Windowmp.put(s.charAt(i), mp.get(s.charAt(i)) - 1);if(mp.get(s.charAt(i)) == 0){mp.remove(s.charAt(i));}i++;We remove left character and move i forward.5️⃣ Updating Maximum Lengthco = Math.max(co, j - i + 1);We update our answer whenever the window is valid.🎯 Why This WorksWe always maintain:(window size - most frequent character count) <= kThat guarantees:We can convert the entire window into one repeating character using at most k replacements.⏱ Time and Space ComplexityTime Complexity: O(26 * n) ≈ O(n)For each character, we scan at most 26 letters.Since there are only uppercase letters, this is effectively linear.Space Complexity: O(26)At most 26 uppercase characters stored.🔥 Important Optimization InsightYour solution recalculates maxfreq every time using a loop.A common optimization is:Maintain a global maxfreqUpdate only when expanding windowDo not recalculate during shrinkingThat reduces unnecessary scanning.But your solution is completely correct and efficient.🏁 Final ThoughtsThis problem teaches:Sliding Window with conditionFrequency trackingWindow validation logicThinking in terms of "how many changes needed"The key formula to remember:window size - max frequency <= kIf you truly understand this condition, you unlock many similar problems like:Longest Substring with K ReplacementsMax Consecutive Ones IIIFruit Into Baskets

Sliding WindowLeetCodeTwo PointersHashMapMedium

Fruit Into Baskets – Sliding Window with Two Types

IntroductionLeetCode 904: Fruit Into Baskets is a classic sliding window problem that tests your ability to track a limited number of distinct elements in a subarray.The problem can be rephrased as:Find the longest subarray containing at most 2 distinct types of elements.This is a great example of using HashMap + sliding window to efficiently track counts of elements while expanding and shrinking the window.If you’d like to try solving the problem first, you can attempt it here:Try the problem on LeetCode:https://leetcode.com/problems/fruit-into-baskets/Problem UnderstandingYou are given:An array fruits where fruits[i] represents the type of fruit from tree iTwo baskets, each can hold only one type of fruitRules:Start at any tree and move only to the rightPick exactly one fruit from each tree while movingStop when a tree’s fruit cannot fit in your basketsGoal: Return the maximum number of fruits you can pick.Examples:Input: fruits = [1,2,1]Output: 3Explanation: Pick all fruits [1,2,1].Input: fruits = [0,1,2,2]Output: 3Explanation: Best subarray [1,2,2].Input: fruits = [1,2,3,2,2]Output: 4Explanation: Best subarray [2,3,2,2].A naive approach would check all subarrays, count distinct fruits, and pick the max →Time Complexity: O(n²) → too slow for fruits.length up to 10⁵Key Idea: Sliding Window with At Most Two TypesInstead of brute-force:Track the number of each fruit type in the current window using a HashMapUse two pointers i and j for the windowExpand j by adding fruits[j] to the mapIf the number of distinct types mp.size() exceeds 2:Shrink the window from the left (i) until mp.size() <= 2The window length j - i + 1 gives the max fruits collected so farIntuition:Only two baskets → window can contain at most 2 distinct fruitsThe sliding window efficiently finds the longest subarray with ≤ 2 distinct elementsApproach (Step-by-Step)Initialize i = 0, j = 0 for window pointersInitialize HashMap mp to store fruit countsInitialize co = 0 → maximum fruits collectedIterate j over fruits:Add fruits[j] to the mapCheck mp.size():If ≤ 2 → update co = max(co, j - i + 1)If > 2 → shrink window from i until mp.size() <= 2Continue expanding the windowReturn co as the maximum fruits collectedOptimization:HashMap keeps track of counts → no need to scan subarray repeatedlySliding window ensures linear traversalImplementation (Java)class Solution {public int totalFruit(int[] nums) {HashMap<Integer,Integer> mp = new HashMap<>();int i = 0, j = 0; // window pointersint co = 0; // max fruits collectedwhile (j < nums.length) {// Add current fruit to mapmp.put(nums[j], mp.getOrDefault(nums[j], 0) + 1);if (mp.size() <= 2) {co = Math.max(co, j - i + 1); // valid windowj++;} else {// Shrink window until at most 2 types of fruitswhile (mp.size() > 2) {mp.put(nums[i], mp.get(nums[i]) - 1);if (mp.get(nums[i]) == 0) {mp.remove(nums[i]);}i++;}co = Math.max(co, j - i + 1);j++;}}return co;}}Dry Run ExampleInput:fruits = [1,2,3,2,2]Execution:Window [i, j]Fruit counts mpDistinct TypesValid?Max co[0,0] → [1]{1:1}1Yes1[0,1] → [1,2]{1:1,2:1}2Yes2[0,2] → [1,2,3]{1:1,2:1,3:1}3No → shrink2[1,2] → [2,3]{2:1,3:1}2Yes2[1,3] → [2,3,2]{2:2,3:1}2Yes3[1,4] → [2,3,2,2]{2:3,3:1}2Yes4Output:4Complexity AnalysisTime Complexity: O(n) → Each element is added and removed at most onceSpace Complexity: O(1) → HashMap stores at most 2 types of fruitsEdge Cases ConsideredArray with ≤ 2 types → entire array can be pickedArray with all same type → window length = array lengthZeros or non-continuous fruit types → handled by sliding windowLarge arrays up to 10⁵ elements → O(n) solution works efficientlySliding Window Pattern ImportanceThis problem demonstrates the sliding window + frequency map pattern:Track limited number of distinct elementsExpand/shrink window dynamicallyEfficiently compute max subarray length with constraintsIt’s directly related to problems like:Max consecutive ones with flipsLongest substring with k distinct charactersFruit collection / subarray problems with type limitsConclusionBy tracking fruit counts with a HashMap in a sliding window, we efficiently find the maximum fruits collectible in O(n) time.Mastering this pattern allows solving many array and string problems with constraints on distinct elements in a linear and elegant way.

SlidingWindowHashMapLeetCodeMedium

Length of Longest Subarray With At Most K Frequency – Sliding Window Approach

IntroductionLeetCode 2958: Length of Longest Subarray With at Most K Frequency is an excellent problem to understand how sliding window with frequency counting works in arrays with duplicates.The problem asks us to find the longest contiguous subarray such that no element occurs more than K times.If you’d like to try solving the problem first, you can attempt it here:Try the problem on LeetCode:https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-frequency/Problem UnderstandingYou are given:An integer array numsAn integer kA good subarray is defined as a subarray where the frequency of each element is ≤ k.Goal: Return the length of the longest good subarray.Examples:Input: nums = [1,2,3,1,2,3,1,2], k = 2Output: 6Explanation: Longest good subarray = [1,2,3,1,2,3]Input: nums = [1,2,1,2,1,2,1,2], k = 1Output: 2Explanation: Longest good subarray = [1,2]Input: nums = [5,5,5,5,5,5,5], k = 4Output: 4Explanation: Longest good subarray = [5,5,5,5]A naive approach would check all subarrays and count frequencies →Time Complexity: O(n²) → too slow for nums.length up to 10⁵Key Idea: Sliding Window with Frequency MapInstead of brute-force:Use a sliding window [i, j] to track the current subarrayUse a HashMap mp to store the frequency of each element in the windowExpand j by adding nums[j] to the mapIf mp.get(nums[j]) > k, shrink the window from the left (i) until mp.get(nums[j]) <= kAt each step, update the maximum length of the valid windowIntuition:We allow each element to appear at most K timesBy shrinking the window whenever a frequency exceeds k, we always maintain a valid subarraySliding window ensures linear traversalApproach (Step-by-Step)Initialize i = 0, j = 0 → window pointersInitialize co = 0 → maximum lengthInitialize HashMap mp to store frequencies of elements in the windowIterate j from 0 to nums.length - 1:Increment frequency of nums[j] in mpWhile mp.get(nums[j]) > k:Shrink window from the left by decrementing mp[nums[i]] and incrementing iUpdate co = max(co, j - i + 1)Return co as the length of the longest good subarrayImplementation (Java)class Solution {public int maxSubarrayLength(int[] nums, int k) {int i = 0, j = 0; // window pointersint co = 0; // max length of good subarrayHashMap<Integer, Integer> mp = new HashMap<>(); // frequency mapwhile (j < nums.length) {mp.put(nums[j], mp.getOrDefault(nums[j], 0) + 1);// Shrink window until all frequencies <= kwhile (mp.get(nums[j]) > k) {mp.put(nums[i], mp.get(nums[i]) - 1);i++;}co = Math.max(co, j - i + 1);j++;}return co;}}Dry Run ExampleInput:nums = [1,2,3,1,2,3,1,2], k = 2Execution:Window [i, j]Frequency Map mpValid?Max length co[0,0] → [1]{1:1}Yes1[0,1] → [1,2]{1:1,2:1}Yes2[0,2] → [1,2,3]{1:1,2:1,3:1}Yes3[0,3] → [1,2,3,1]{1:2,2:1,3:1}Yes4[0,4] → [1,2,3,1,2]{1:2,2:2,3:1}Yes5[0,5] → [1,2,3,1,2,3]{1:2,2:2,3:2}Yes6[0,6] → [1,2,3,1,2,3,1]{1:3,2:2,3:2}No → shrink6Output:6Complexity AnalysisTime Complexity: O(n) → Each element enters and leaves the window at most onceSpace Complexity: O(n) → HashMap stores frequencies of elements in the window (worst-case all distinct)Edge Cases ConsideredAll elements occur ≤ k → entire array is validAll elements occur > k → max subarray length = kSingle-element arrays → return 1 if k ≥ 1Large arrays up to 10⁵ elements → O(n) solution works efficientlySliding Window Pattern ImportanceThis problem demonstrates sliding window with frequency map, useful for:Subarrays with frequency constraintsLongest subarray with limited duplicatesSimilar to "max consecutive ones with flips" and "fruit into baskets"By mastering this approach, you can efficiently solve many array and subarray problems with constraints.ConclusionUsing HashMap + sliding window, we reduce a naive O(n²) approach to O(n) while keeping the solution intuitive and easy to implement.Understanding this pattern allows solving complex frequency-constrained subarray problems efficiently in interviews.

SlidingWindowHashMapLeetCodeMedium

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

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 402: Remove K Digits — Java Solution Explained

IntroductionLeetCode 402 Remove K Digits is one of those problems where the brute force solution feels obvious but completely falls apart at scale — and the optimal solution requires a genuinely clever insight that, once you see it, feels like magic.This problem sits at the intersection of two powerful techniques — Greedy thinking and Monotonic Stack. If you have already solved Next Greater Element and Asteroid Collision, you have all the building blocks you need. This is where those patterns level up.You can find the problem here — LeetCode 402 Remove K Digits.What Is the Problem Really Asking?You are given a number as a string and an integer k. Remove exactly k digits from the number such that the resulting number is as small as possible. Return it as a string without leading zeros.Example:num = "1432219", k = 3We want to remove 3 digits to make the number as small as possibleRemove 4, 3, 2 → remaining is "1219"Output: "1219"Simple goal — smallest possible number after exactly k removals.Real Life Analogy — Choosing the Best Price TagImagine you are reading a price tag digit by digit from left to right. Every time you see a digit that is bigger than the next one coming, you have a chance to remove it and make the price smaller. You have a limited number of removals — use them wisely on the biggest offenders from the left side, because leftmost digits have the most impact on the overall value.Removing a 9 from the front of a number shrinks it far more than removing a 9 from the end. This left-to-right priority with greedy removal is the entire insight of this problem.The Core Greedy InsightHere is the key question — which digit should we remove first to make the number as small as possible?Think about it this way. In the number "1432219", which digit is hurting us the most? It is 4 — because it is large and sits early in the number. After removing 4 we get "132219". Now 3 is the biggest early offender. And so on.More precisely — whenever you see a digit that is greater than the digit immediately after it, removing it makes the number smaller. This is because a larger digit sitting before a smaller digit inflates the overall value.This is the Greedy rule: scan left to right, and whenever the current digit on the stack is greater than the incoming digit, remove it (if we still have removals left).A Monotonic Increasing Stack enforces exactly this — it keeps digits in non-decreasing order, automatically kicking out any digit that is larger than what comes next.The Solution — Monotonic Stackpublic String removeKdigits(String num, int k) { Stack<Character> st = new Stack<>(); // build monotonic increasing stack for (int i = 0; i < num.length(); i++) { // while stack top is greater than current digit and we still have removals while (!st.empty() && k != 0 && st.peek() > num.charAt(i)) { st.pop(); // remove the larger digit — greedy choice k--; } st.push(num.charAt(i)); } // if k removals still remaining, remove from the end (largest digits are at top) while (k != 0) { st.pop(); k--; } // build result string from stack StringBuilder sb = new StringBuilder(); while (!st.empty()) { sb.append(st.pop()); } sb.reverse(); // stack gives reverse order // remove leading zeros while (sb.length() > 0 && sb.charAt(0) == '0') { sb.deleteCharAt(0); } // if nothing left, return "0" return sb.length() == 0 ? "0" : sb.toString();}Step-by-Step Dry Run — num = "1432219", k = 3Processing 1: Stack empty → push. Stack: [1]Processing 4: Stack top 1 < 4 → no pop. Push 4. Stack: [1, 4]Processing 3: Stack top 4 > 3 and k=3 → pop 4, k=2. Stack: [1] Stack top 1 < 3 → stop. Push 3. Stack: [1, 3]Processing 2: Stack top 3 > 2 and k=2 → pop 3, k=1. Stack: [1] Stack top 1 < 2 → stop. Push 2. Stack: [1, 2]Processing 2: Stack top 2 == 2 → not greater, stop. Push 2. Stack: [1, 2, 2]Processing 1: Stack top 2 > 1 and k=1 → pop 2, k=0. Stack: [1, 2] k=0, stop. Push 1. Stack: [1, 2, 1]Processing 9: k=0, no more removals. Push 9. Stack: [1, 2, 1, 9]k is now 0, skip the cleanup loop.Build result: pop all → "9121" → reverse → "1219" No leading zeros. Return "1219" ✅Step-by-Step Dry Run — num = "10200", k = 1Processing 1: stack empty → push. Stack: [1]Processing 0: Stack top 1 > 0 and k=1 → pop 1, k=0. Stack: [] Push 0. Stack: [0]Processing 2: k=0, no removals. Push. Stack: [0, 2]Processing 0: k=0. Push. Stack: [0, 2, 0]Processing 0: k=0. Push. Stack: [0, 2, 0, 0]k=0, skip cleanup.Build result: "0020" → reverse → "0200" Remove leading zero → "200" Return "200" ✅Step-by-Step Dry Run — num = "10", k = 2Processing 1: push. Stack: [1]Processing 0: Stack top 1 > 0 and k=2 → pop 1, k=1. Stack: [] Push 0. Stack: [0]k=1 remaining → cleanup loop → pop 0, k=0. Stack: []Build result: empty string. Remove leading zeros: nothing to remove. Length is 0 → return "0" ✅The Three Tricky Cases You Must HandleCase 1 — k is not fully used after the loop This happens with a non-decreasing number like "12345" with k=2. No element ever gets popped during the loop because no digit is greater than the next one. The stack ends up as [1,2,3,4,5] with k still = 2. The solution is to pop from the top of the stack — which holds the largest digits — until k hits 0.Case 2 — Leading zeros After removing digits, the remaining number might start with zeros. "10200" becomes "0200" after removing 1. We strip leading zeros with a while loop. But we must be careful not to strip the only zero — that is why we check length > 0 before each removal.Case 3 — Empty result If all digits are removed (like "10" with k=2), the StringBuilder ends up empty. We return "0" because an empty number is represented as zero.Why Remaining k Gets Removed From the EndAfter the main loop, if k is still greater than 0, why do we remove from the top of the stack (which corresponds to the end of the number)?Because the stack at this point holds a non-decreasing sequence. In a non-decreasing sequence, the largest values are at the end. Removing from the end removes the largest remaining digits — which is exactly the greedy choice to minimize the number.For example in "12345" with k=2: the stack is [1,2,3,4,5]. Pop top twice → remove 5 and 4 → [1,2,3] → result is "123". Correct!Time and Space ComplexityTime Complexity: O(n) — each digit is pushed onto the stack exactly once and popped at most once. Even with the while loop inside the for loop, total push and pop operations across the entire run never exceed 2n. The leading zero removal is also O(n) in the worst case. Overall stays linear.Space Complexity: O(n) — the stack holds at most n digits in the worst case when no removals happen during the main loop.Common Mistakes to AvoidNot handling remaining k after the loop This is the most common mistake. If the number is already non-decreasing, the loop never pops anything. Forgetting the cleanup loop gives the wrong answer for inputs like "12345" with k=2.Not removing leading zeros After removals, the result might start with zeros. "0200" should be returned as "200". Skipping this step gives wrong output.Returning empty string instead of "0" When all digits are removed, return "0" not "". An empty string is not a valid number representation.Using >= instead of > in the pop condition If you pop on equal digits too, you remove more than necessary and might get wrong results. Only pop when strictly greater — equal digits in sequence are fine to keep.How This Connects to the Monotonic Stack SeriesLooking at the stack problems you have been solving:496 Next Greater Element — monotonic decreasing stack, find first bigger to the right 735 Asteroid Collision — stack simulation, chain reactions 402 Remove K Digits — monotonic increasing stack, greedy removal for minimum numberThe direction of the monotonic stack flips based on what you are optimizing. For "next greater" you keep a decreasing stack. For "smallest number" you keep an increasing stack. Recognizing which direction to go is the skill that connects all these problems.FAQs — People Also AskQ1. Why does a Monotonic Stack give the smallest number in LeetCode 402? A monotonic increasing stack ensures that at every point, the digits we have kept so far are in the smallest possible order. Whenever a smaller digit arrives and the stack top is larger, removing that larger digit can only make the number smaller — this greedy choice is always optimal.Q2. What happens if k is not fully used after the main loop in LeetCode 402? The number is already in non-decreasing order so no removals happened during the loop. The remaining removals should be made from the end of the number (top of stack) since those are the largest values in a non-decreasing sequence.Q3. How are leading zeros handled in LeetCode 402? After building the result string, strip any leading zeros with a while loop. If stripping leaves an empty string, return "0" because the empty case represents zero.Q4. What is the time complexity of LeetCode 402? O(n) time because each digit is pushed and popped at most once across the entire algorithm. Space complexity is O(n) for the stack.Q5. Is LeetCode 402 asked in coding interviews? Yes, it is frequently asked at companies like Google, Amazon, and Microsoft. It tests greedy thinking combined with monotonic stack — two patterns that interviewers love because they require genuine insight rather than memorization.Similar LeetCode Problems to Practice Next496. Next Greater Element I — Easy — monotonic decreasing stack739. Daily Temperatures — Medium — next greater with distances316. Remove Duplicate Letters — Medium — similar greedy stack with constraints1081. Smallest Subsequence of Distinct Characters — Medium — same approach as 31684. Largest Rectangle in Histogram — Hard — advanced monotonic stackConclusionLeetCode 402 Remove K Digits is a beautiful problem that rewards clear thinking. The greedy insight — always remove a digit when a smaller digit comes after it — naturally leads to the monotonic stack solution. The three edge cases (remaining k, leading zeros, empty result) are what separate a buggy solution from a clean, accepted one.Work through all three dry runs carefully. Once you see how the stack stays increasing and how each pop directly corresponds to a greedy removal decision, this pattern will click permanently and carry you through harder stack problems ahead.

LeetCodeJavaStackMonotonic StackGreedyStringMedium

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

Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

IntroductionThe Subsets problem (LeetCode 78) is one of the most fundamental and frequently asked questions in coding interviews. It introduces the concept of generating a power set, which is a core idea in recursion, backtracking, and combinatorics.Mastering this problem helps in solving a wide range of advanced problems like combinations, permutations, and decision-based recursion.In this article, we will explore:Intuition behind subsetsRecursive (backtracking) approachIterative (loop-based) approachBit manipulation approachTime and space complexity analysisProblem StatementGiven an integer array nums of unique elements, return all possible subsets (the power set).Key PointsEach element can either be included or excludedNo duplicate subsetsReturn subsets in any orderExamplesExample 1Input:nums = [1, 2, 3]Output:[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Example 2Input:nums = [0]Output:[[], [0]]Key InsightFor each element, there are two choices:Include it OR Exclude itSo total subsets:2^nThis makes it a binary decision tree problem, very similar to:Permutation with SpacesBinary choices recursionBacktracking problemsApproach 1: Recursion + Backtracking (Most Important)IntuitionAt each index:Skip the elementInclude the elementBuild subsets step by step and backtrack.Java Code (With Explanation)import java.util.*;class Solution { List<List<Integer>> liss = new ArrayList<>(); void solve(int[] an, int ind, List<Integer> lis) { // Base case: reached end → one subset formed if (ind == an.length) { liss.add(new ArrayList<>(lis)); // store copy return; } // Choice 1: Do NOT include current element solve(an, ind + 1, lis); // Choice 2: Include current element lis.add(an[ind]); solve(an, ind + 1, lis); // Backtrack: remove last added element lis.remove(lis.size() - 1); } public List<List<Integer>> subsets(int[] nums) { List<Integer> lis = new ArrayList<>(); solve(nums, 0, lis); return liss; }}Dry Run (nums = [1,2])Start: [] → skip 1 → [] → skip 2 → [] → take 2 → [2] → take 1 → [1] → skip 2 → [1] → take 2 → [1,2]Final Output:[], [2], [1], [1,2]Approach 2: Iterative (Loop-Based)IntuitionStart with an empty subset:[ [] ]For each element:Add it to all existing subsetsCodeimport java.util.*;class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); result.add(new ArrayList<>()); for (int num : nums) { int size = result.size(); for (int i = 0; i < size; i++) { List<Integer> temp = new ArrayList<>(result.get(i)); temp.add(num); result.add(temp); } } return result; }}How It WorksFor [1,2,3]:Start: [[]]Add 1 → [[], [1]]Add 2 → [[], [1], [2], [1,2]]Add 3 → [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Approach 3: Bit ManipulationIntuitionEach subset can be represented using a binary number:For n = 3:000 → []001 → [1]010 → [2]011 → [1,2]...Codeimport java.util.*;class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); int n = nums.length; int total = 1 << n; // 2^n for (int i = 0; i < total; i++) { List<Integer> subset = new ArrayList<>(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { subset.add(nums[j]); } } result.add(subset); } return result; }}Complexity AnalysisApproachTime ComplexitySpace ComplexityRecursionO(2^n)O(n) stackIterativeO(2^n)O(2^n)Bit ManipulationO(2^n)O(2^n)Why All Approaches Are O(2ⁿ)Because:Total subsets = 2ⁿEach subset takes up to O(n) to constructWhen to Use Which ApproachRecursion / Backtracking → Best for interviews (easy to explain)Iterative → Clean and beginner-friendlyBit Manipulation → Best for optimization & advanced understandingKey TakeawaysSubsets = power set problemEvery element → 2 choicesThink in terms of decision treesBacktracking = build + undo (add/remove)Common Interview VariationsSubsets with duplicatesCombination sumPermutationsK-sized subsetsConclusionThe Subsets problem is a foundational DSA concept that appears across many interview questions. Understanding all approaches—especially recursion and iterative expansion—gives a strong base for solving complex backtracking problems.If you master this pattern, you unlock a whole category of problems in recursion and combinatorics.Frequently Asked Questions (FAQs)1. Why are there 2ⁿ subsets?Because each element has 2 choices: include or exclude.2. Which approach is best for interviews?Recursion + backtracking is the most preferred.3. Is bit manipulation important?Yes, it helps in optimizing and understanding binary patterns.

LeetCodeMediumJavaRecursionBacktracking

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

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

LeetCode 682 Baseball Game - Java Solution Explained

IntroductionLeetCode 682 Baseball Game is one of the cleanest and most beginner-friendly stack simulation problems on LeetCode. It does not require any fancy algorithm or deep insight — it purely tests whether you can carefully read the rules and simulate them faithfully using the right data structure.But do not let "Easy" fool you. This problem is a great place to practice thinking about which data structure fits best and why. We will solve it three different ways — Stack, ArrayList, and Deque — so you can see the tradeoffs and pick the one that makes most sense to you.You can find the problem here — LeetCode 682 Baseball Game.What Is the Problem Really Asking?You are keeping score for a baseball game with four special rules. You process a list of operations one by one and maintain a record of scores. At the end, return the total sum of all scores in the record.The four operations are:A number (like "5" or "-2") — just add that number as a new score to the record."C" — the last score was invalid, remove it from the record."D" — add a new score that is double the most recent score."+" — add a new score that is the sum of the two most recent scores.That is it. Four rules, simulate them in order, sum up what is left.Real Life Analogy — A Scoreboard With CorrectionsImagine a scoreboard operator at a sports event. They write scores on a whiteboard as the game progresses:A player scores 5 points → write 5Another player scores 2 → write 2Referee says last score was invalid → erase the last number (C)Special bonus rule kicks in → double the last valid score (D)Two scores combine → add the last two scores as one entry (+)At the end, add up everything on the whiteboard. The stack is your whiteboard — you write on top and erase from the top.Why Stack Is the Natural FitAll four operations only ever look at or modify the most recently added scores. C removes the last one. D doubles the last one. + uses the last two. This "most recent first" access pattern is the definition of LIFO — Last In First Out — which is exactly what a Stack provides.Any time a problem says "the previous score" or "the last two scores," your brain should immediately think Stack.Approach 1: Stack (Your Solution) ✅The IdeaUse a Stack of integers. For each operation:Number → parse and pushC → pop the topD → peek the top, push doubled value+ → pop top two, push both back, push their sumpublic int calPoints(String[] operations) { Stack<Integer> st = new Stack<>(); for (int i = 0; i < operations.length; i++) { String op = operations[i]; if (op.equals("C")) { st.pop(); // remove last score } else if (op.equals("D")) { st.push(st.peek() * 2); // double of last score } else if (op.equals("+")) { int prev1 = st.pop(); // most recent score int prev2 = st.pop(); // second most recent score int sum = prev1 + prev2; st.push(prev2); // put them back st.push(prev1); st.push(sum); // push the new score } else { st.push(Integer.parseInt(op)); // regular number } } // sum all remaining scores int total = 0; while (!st.empty()) { total += st.pop(); } return total;}One small improvement over your original solution — using op.equals("C") instead of op.charAt(0) == 'C'. This is cleaner and handles edge cases better since negative numbers like "-2" also start with - not a digit, so charAt(0) comparisons can get tricky. Using equals is always safer for string operations.Why the + Operation Needs Pop-Push-PopThe trickiest part is the + operation. You need the two most recent scores. Stack only lets you see the top. So you pop the first, then the second, compute the sum, then push both back before pushing the sum. This restores the record correctly — the previous two scores stay, and the new sum score is added on top.Detailed Dry Run — ops = ["5","2","C","D","+"]Let us trace every step carefully:"5" → number, parse and push Stack: [5]"2" → number, parse and push Stack: [5, 2]"C" → remove last score, pop Stack: [5]"D" → double last score, peek=5, push 10 Stack: [5, 10]"+" → sum of last two:pop prev1 = 10pop prev2 = 5sum = 15push prev2=5, push prev1=10, push sum=15 Stack: [5, 10, 15]Sum all: 5 + 10 + 15 = 30 ✅Detailed Dry Run — ops = ["5","-2","4","C","D","9","+","+"]"5" → push 5. Stack: [5]"-2" → push -2. Stack: [5, -2]"4" → push 4. Stack: [5, -2, 4]"C" → pop 4. Stack: [5, -2]"D" → peek=-2, push -4. Stack: [5, -2, -4]"9" → push 9. Stack: [5, -2, -4, 9]"+" → prev1=9, prev2=-4, sum=5. Push -4, 9, 5. Stack: [5, -2, -4, 9, 5]"+" → prev1=5, prev2=9, sum=14. Push 9, 5, 14. Stack: [5, -2, -4, 9, 5, 14]Sum: 5 + (-2) + (-4) + 9 + 5 + 14 = 27 ✅Approach 2: ArrayList (Most Readable)The IdeaArrayList gives you index-based access which makes the + operation much cleaner — no need to pop and push back. Just access the last two elements directly using size()-1 and size()-2.public int calPoints(String[] operations) { ArrayList<Integer> record = new ArrayList<>(); for (String op : operations) { int n = record.size(); if (op.equals("C")) { record.remove(n - 1); // remove last element } else if (op.equals("D")) { record.add(record.get(n - 1) * 2); // double last } else if (op.equals("+")) { // sum of last two — no need to remove and re-add! record.add(record.get(n - 1) + record.get(n - 2)); } else { record.add(Integer.parseInt(op)); } } int total = 0; for (int score : record) { total += score; } return total;}See how the + operation becomes a single line with ArrayList? record.get(n-1) + record.get(n-2) directly accesses the last two elements without any pop-push gymnastics.Dry Run — ops = ["5","2","C","D","+"]"5" → add 5. List: [5]"2" → add 2. List: [5, 2]"C" → remove last. List: [5]"D" → 5×2=10, add 10. List: [5, 10]"+" → get(0)+get(1) = 5+10=15, add 15. List: [5, 10, 15]Sum: 30 ✅Time Complexity: O(n) — single pass through operations Space Complexity: O(n) — ArrayList stores at most n scoresThe one tradeoff — remove(n-1) on an ArrayList is O(1) for the last element (no shifting needed). And get() is O(1). So this is fully O(n) overall and arguably the cleanest solution to read and understand.Approach 3: Deque (ArrayDeque — Fastest in Java)The IdeaArrayDeque is faster than Stack in Java because Stack is synchronized (thread-safe overhead) and ArrayDeque is not. For single-threaded LeetCode problems, ArrayDeque is always the better choice over Stack.public int calPoints(String[] operations) { Deque<Integer> deque = new ArrayDeque<>(); for (String op : operations) { if (op.equals("C")) { deque.pollLast(); // remove last } else if (op.equals("D")) { deque.offerLast(deque.peekLast() * 2); // double last } else if (op.equals("+")) { int prev1 = deque.pollLast(); int prev2 = deque.pollLast(); int sum = prev1 + prev2; deque.offerLast(prev2); // restore deque.offerLast(prev1); // restore deque.offerLast(sum); // new score } else { deque.offerLast(Integer.parseInt(op)); } } int total = 0; for (int score : deque) { total += score; } return total;}The logic is identical to the Stack approach. The only difference is the method names — offerLast instead of push, pollLast instead of pop, peekLast instead of peek.Time Complexity: O(n) Space Complexity: O(n)For iterating a Deque to sum, you can use a for-each loop directly — no need to pop everything out like with Stack.Approach ComparisonApproachTimeSpaceBest ForStackO(n)O(n)Classic interview answer, clear LIFO intentArrayListO(n)O(n)Cleanest code, easiest to readArrayDequeO(n)O(n)Best performance, preferred in productionAll three approaches have identical time and space complexity. The difference is purely in code style and readability. In an interview, any of these is perfectly acceptable. Mention that ArrayDeque is preferred over Stack in Java for performance if you want to impress.Why op.equals() Is Better Than op.charAt(0)Your original solution uses operations[i].charAt(0) == 'C' to check operations. This works but has a subtle risk — the + character check with charAt(0) is fine, but imagine if a future test had a number starting with C or D (it will not in this problem but defensive coding is a good habit). More importantly, "-2".charAt(0) is '-' which is fine, but using equals is semantically clearer — you are comparing the whole string, not just the first character. This shows cleaner coding habits in interviews.Edge Cases to KnowNegative numbers like "-2" Integer.parseInt("-2") handles negatives perfectly. The D operation on -2 gives -4. The + operation works correctly with negatives too. No special handling needed."C" after a "+" that added a score The problem guarantees C always has at least one score to remove. So after + adds a score, a C removes just that one new score — the previous two scores that + used remain intact. This is correct behavior and our solution handles it automatically.All scores removed If all operations are numbers followed by C operations removing every score, the stack ends up empty and the sum is 0. Our while loop handles this correctly — it simply never executes and returns 0.Only one operation A single number like ["5"] → push 5, sum is 5. Works fine.Common Mistakes to AvoidIn the + operation, forgetting to push both numbers back When you pop prev1 and prev2 to compute the sum, you must push them back onto the stack before pushing the sum. If you only push the sum without restoring prev1 and prev2, those scores disappear from the record permanently — which is wrong. The + operation only adds a new score, it does not remove the previous ones.Using charAt(0) comparison for detecting numbers Negative numbers start with -, not a digit. If you check charAt(0) >= '0' && charAt(0) <= '9' to detect numbers, you will miss negatives. The safest approach is to check for C, D, and + explicitly using equals, and fall through to the else for everything else (which covers both positive and negative numbers).Calling st.peek() or st.pop() without checking empty The problem guarantees valid operations — C always has something to remove, + always has two previous scores, D always has one. But in real code and defensive interview solutions, adding empty checks shows good habits even when the constraints guarantee safety.FAQs — People Also AskQ1. Why is Stack a good choice for LeetCode 682 Baseball Game? Because all four operations only access the most recently added scores — the last score for C and D, the last two for +. This "most recent first" access pattern is exactly what LIFO (Last In First Out) provides. Stack's push, pop, and peek all run in O(1) making it perfectly efficient.Q2. What is the time complexity of LeetCode 682? O(n) time where n is the number of operations. Each operation performs a constant number of stack operations (at most 3 pushes/pops for the + case). Space complexity is O(n) for storing scores.Q3. Why does the + operation need to pop and push back in the Stack approach? Stack only gives direct access to the top element. To get the second most recent score, you must pop the first one, peek/pop the second, then push the first one back. The ArrayList approach avoids this by using index-based access directly.Q4. What is the difference between Stack and ArrayDeque in Java for this problem? Both work correctly. ArrayDeque is faster because Stack is a legacy class that extends Vector and is synchronized (thread-safe), adding unnecessary overhead for single-threaded use. ArrayDeque has no synchronization overhead. For LeetCode and interviews, either is acceptable but ArrayDeque is technically better.Q5. Is LeetCode 682 asked in coding interviews? It appears occasionally as a warmup or screening problem. Its main value is testing whether you can carefully simulate rules without making logical errors — a skill that matters in systems programming, game development, and any domain with complex state management.Similar LeetCode Problems to Practice Next71. Simplify Path — Medium — stack simulation with path operations1047. Remove All Adjacent Duplicates In String — Easy — stack simulation735. Asteroid Collision — Medium — stack simulation with conditions150. Evaluate Reverse Polish Notation — Medium — stack with arithmetic operations, very similar pattern227. Basic Calculator II — Medium — stack with operator precedenceConclusionLeetCode 682 Baseball Game is a perfect problem to build confidence with stack simulation. The four operations are clearly defined, the rules are unambiguous, and the stack maps naturally to every operation. Once you understand why pop-push-back is needed for + in the stack approach and how ArrayList simplifies that with index access, you have genuinely understood the tradeoffs between these data structures.If you are newer to stacks, start with the ArrayList solution for clarity. Once that clicks, rewrite it with Stack to understand the LIFO mechanics. Then try ArrayDeque to understand why it is preferred in modern Java code.

LeetCodeJavaStackArrayListDequeEasy

LeetCode 22 Generate Parentheses | Backtracking Java Solution Explained

IntroductionThe Generate Parentheses problem is one of the most important and frequently asked backtracking questions in coding interviews.At first glance, it may look like a simple string generation problem—but the real challenge is to generate only valid (well-formed) parentheses combinations.This problem is a perfect example of:Constraint-based recursionBacktracking with conditionsDecision tree pruningIn this article, we’ll break down the intuition, understand the constraints, and implement a clean and efficient solution.🔗 Problem LinkLeetCode: Generate ParenthesesProblem StatementGiven n pairs of parentheses:👉 Generate all combinations of well-formed parenthesesExamplesExample 1Input:n = 3Output:["((()))","(()())","(())()","()(())","()()()"]Example 2Input:n = 1Output:["()"]Key InsightWe are not generating all possible strings—we are generating only valid parentheses.Rules of Valid ParenthesesNumber of ( must equal number of )At any point:closing brackets should never exceed opening bracketsIntuition (Decision Making)At every step, we have two choices:Add "(" OR Add ")"But we cannot always take both choices.Valid ConditionsWhen can we add "("?If open > 0When can we add ")"?If close > open👉 This ensures the string always remains valid.Decision Tree (n = 3)👉 You can add your tree diagram here for better visualization.Conceptual FlowStart: ""→ "(" → "(("→ "(((" → "((()"→ ...Invalid paths like ")(" are never explored because of constraints.Approach: Backtracking with ConstraintsIdeaKeep track of:Remaining open bracketsRemaining close bracketsBuild string step by stepOnly take valid decisionsJava Codeimport java.util.*;class Solution {// List to store all valid combinationsList<String> lis = new ArrayList<>();public void solve(int open, int close, String curr) {// Base case: no brackets leftif (open == 0 && close == 0) {lis.add(curr); // valid combinationreturn;}// Choice 1: Add opening bracket "("// Allowed only if we still have opening brackets leftif (open > 0) {solve(open - 1, close, curr + "(");}// Choice 2: Add closing bracket ")"// Allowed only if closing brackets > opening bracketsif (open < close) {solve(open, close - 1, curr + ")");}}public List<String> generateParenthesis(int n) {solve(n, n, ""); // start recursionreturn lis;}}Step-by-Step Execution (n = 2)Start: ""→ "("→ "(("→ "(())"→ "()"→ "()()"Complexity AnalysisTime Complexity: O(4ⁿ / √n) (Catalan Number)Space Complexity: O(n) recursion stackWhy Catalan Number?The number of valid parentheses combinations is:Cn = (1 / (n+1)) * (2n choose n)Why This Approach WorksIt avoids invalid combinations earlyUses constraints to prune recursion treeGenerates only valid resultsEfficient compared to brute force❌ Naive Approach (Why It Fails)Generate all combinations of ( and ):Total combinations = 2^(2n)Then filter valid ones👉 Very inefficient → TLEKey TakeawaysThis is a constraint-based recursion problemAlways:Add "(" if availableAdd ")" only if validBacktracking avoids invalid pathsImportant pattern for interviewsCommon Interview VariationsValid parentheses checkingLongest valid parenthesesRemove invalid parenthesesBalanced expressionsConclusionThe Generate Parentheses problem is a must-know backtracking problem. It teaches how to apply constraints during recursion to efficiently generate valid combinations.Once mastered, this pattern becomes extremely useful in solving many advanced recursion problems.Frequently Asked Questions (FAQs)1. Why can’t we add ")" anytime?Because it may create invalid sequences like ")(".2. What is the key trick?Ensure:close > open3. Is recursion the best approach?Yes, it is the most intuitive and efficient method.

MediumLeetCodeJavaRecursion

LeetCode 1047: Remove All Adjacent Duplicates In String — Java Solution With All Approaches Explained

Introduction: What Is LeetCode 1047 Remove All Adjacent Duplicates In String?If you are grinding LeetCode for coding interviews at companies like Google, Amazon, or Microsoft, LeetCode 1047 Remove All Adjacent Duplicates In String is a problem you cannot skip. It is one of the most elegant examples of the stack simulation pattern and appears frequently as a warmup or follow-up question in technical rounds.In this article we will cover everything you need — plain English explanation, real life analogy, 3 Java approaches with dry runs, complexity analysis, common mistakes, FAQs, and similar problems to practice next.Here is the problem link-: Leetcode 1047 What Is the Problem Really Asking?You are given a string. Keep scanning it and whenever you find two same letters sitting next to each other, remove both of them. After removing, the letters around them might now become adjacent and form a new pair — so you keep doing this until no more adjacent duplicates exist.Example walkthrough for "abbaca":"abbaca" → bb are adjacent duplicates → remove → "aaca""aaca" → aa are adjacent duplicates → remove → "ca""ca" → no adjacent duplicates → done!✅ Output: "ca"Real Life Analogy — Think of Popping BubblesImagine a row of colored bubbles. Whenever two bubbles of the same color are next to each other, they pop and disappear. After they pop, the bubbles on either side might now touch each other — and if they are the same color, they pop too! You keep going until no two same-colored bubbles are touching.That chain reaction is exactly what this problem simulates. And the best tool to handle that chain reaction? A stack.Approach 1: Brute Force (Beginner Friendly)The IdeaScan the string repeatedly. Every time you find two adjacent equal characters, remove them. Keep doing this until a full pass finds nothing to remove.public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(s); boolean found = true; while (found) { found = false; for (int i = 0; i < sb.length() - 1; i++) { if (sb.charAt(i) == sb.charAt(i + 1)) { sb.deleteCharAt(i); sb.deleteCharAt(i); found = true; break; } } } return sb.toString();}This is easy to understand but very slow. For each pair found, you restart the entire scan. With n up to 100,000, this will get Time Limit Exceeded on LeetCode. Use it only to build intuition.Time Complexity: O(n²) — repeated passes over the string Space Complexity: O(n) — StringBuilder storageApproach 2: Stack Based Solution (Classic Interview Approach)The IdeaA stack is perfect here because of one key observation — when you remove a pair, the character that was before the pair is now adjacent to the character after the pair. That is a Last In First Out situation, which is exactly what a stack handles naturally.Algorithm:If the current character matches the top of the stack → pop (they cancel each other)Otherwise → push the current character onto the stackAt the end, the stack contains your final answerpublic String removeDuplicates(String s) { Stack<Character> st = new Stack<>(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (!st.empty() && c == st.peek()) { st.pop(); // adjacent duplicate found, cancel both } else { st.push(c); } } while (!st.empty()) { sb.append(st.pop()); } return sb.reverse().toString();}Dry Run — "abbaca"We go character by character and check against the top of the stack:a → stack empty, push → stack: [a]b → top is a, not equal, push → stack: [a, b]b → top is b, equal! pop → stack: [a]a → top is a, equal! pop → stack: []c → stack empty, push → stack: [c]a → top is c, not equal, push → stack: [c, a]Stack remaining: [c, a] → reverse → ✅ "ca"Notice how after removing bb, the two as automatically become adjacent and get caught — the stack handles this chain reaction naturally without any extra logic!Time Complexity: O(n) — single pass through the string Space Complexity: O(n) — stack holds up to n charactersApproach 3: StringBuilder as Stack (Optimal Solution) ✅The IdeaThis is your own solution and the best one! Instead of using a separate Stack<Character>, we use StringBuilder itself as a stack:sb.append(c) acts as pushsb.deleteCharAt(sb.length() - 1) acts as popsb.charAt(sb.length() - 1) acts as peekNo extra data structure, no boxing of char into Character objects, and no reversal needed at the end. Clean, fast, and minimal.public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (sb.length() != 0 && c == sb.charAt(sb.length() - 1)) { sb.deleteCharAt(sb.length() - 1); // adjacent duplicate, remove both } else { sb.append(c); } } return sb.toString();}Dry Run — "azxxzy"a → sb empty, append → "a"z → last char is a, not equal, append → "az"x → last char is z, not equal, append → "azx"x → last char is x, equal! delete → "az"z → last char is z, equal! delete → "a"y → last char is a, not equal, append → "ay"✅ Final Answer: "ay"Again, notice the chain reaction — after xx was removed, z and z became adjacent and got removed too. The StringBuilder handles this perfectly in a single pass!Time Complexity: O(n) — one pass, every character processed exactly once Space Complexity: O(n) — StringBuilder storageWhy StringBuilder Beats Stack in JavaWhen you use Stack<Character> in Java, every char primitive gets auto-boxed into a Character object. That means extra memory allocation for every single character. With StringBuilder, you work directly on the underlying char array — faster and leaner. Plus you skip the reversal step entirely.For an interview, the Stack approach is great for explaining your thought process clearly. But for the final submitted solution, StringBuilder is the way to go.Common Mistakes to AvoidNot checking sb.length() != 0 before peeking If the StringBuilder is empty and you call sb.charAt(sb.length() - 1), you will get a StringIndexOutOfBoundsException. Always guard this check — even if the problem guarantees valid input, it shows clean coding habits.Thinking you need multiple passes Many beginners think you need to scan the string multiple times because of chain reactions. The stack handles chain reactions automatically in a single pass. Trust the process!Forgetting to reverse when using Stack Since a stack gives you characters in reverse order when you pop them, you must call .reverse() at the end. With StringBuilder you do not need this.How This Fits Into the Stack Simulation PatternBy now you might be noticing a theme across multiple problems:LeetCode 3174 Clear Digits — digit acts as backspace, deletes closest left non-digit LeetCode 2390 Removing Stars — star acts as backspace, deletes closest left non-star LeetCode 1047 Remove Adjacent Duplicates — character cancels itself if it matches the top of stackAll three use the exact same StringBuilder-as-stack pattern. The only difference is the condition that triggers a deletion. This is why pattern recognition is the real skill — once you internalize this pattern, you can solve a whole family of problems in minutes.FAQs — People Also AskQ1. What is the best approach for LeetCode 1047 in Java? The StringBuilder approach is the best. It runs in O(n) time, uses O(n) space, requires no extra data structure, and avoids the reversal step needed with a Stack.Q2. Why does a stack work for removing adjacent duplicates? Because whenever you remove a pair, the characters around them become the new neighbors. A stack naturally keeps track of the most recently seen character, so it catches these chain reactions without any extra logic.Q3. What is the time complexity of LeetCode 1047? The optimal solution runs in O(n) time and O(n) space, where n is the length of the input string.Q4. Is LeetCode 1047 asked in coding interviews? Yes, it is commonly asked as a warmup problem or follow-up at companies like Google, Amazon, and Adobe. It tests your understanding of stack-based string manipulation.Q5. What is the difference between LeetCode 1047 and LeetCode 1209? LeetCode 1047 removes pairs of adjacent duplicates. LeetCode 1209 is the harder version — it removes groups of k adjacent duplicates, requiring you to store counts alongside characters in the stack.Similar LeetCode Problems to Practice Next2390. Removing Stars From a String — Medium — star as backspace3174. Clear Digits — Easy — digit as backspace844. Backspace String Compare — Easy — compare two strings after backspaces1209. Remove All Adjacent Duplicates in String II — Medium — harder version with k duplicates735. Asteroid Collision — Medium — stack simulation with collision logicConclusionLeetCode 1047 Remove All Adjacent Duplicates In String is a beautiful problem that teaches you one of the most powerful and reusable patterns in DSA — stack simulation. The moment you spot that a removal can cause a chain reaction of more removals, you know a stack is your best friend.The StringBuilder solution is clean, optimal, and interview-ready. Master it, understand why it works, and you will be able to tackle the entire family of stack simulation problems with confidence.Found this helpful? Share it with friends preparing for coding interviews

LeetCodeJavaStackStringEasy

LeetCode 844: Backspace String Compare — Java Solution With All Approaches Explained

IntroductionLeetCode 844 Backspace String Compare is a fantastic problem that shows up frequently in coding interviews. It combines string manipulation, stack simulation, and even has a follow-up that challenges you to solve it in O(1) space — which is what separates a good candidate from a great one.Here is the Link of Question -: LeetCode 844In this article we cover a plain English explanation, real life analogy, 3 Java approaches including the O(1) space two pointer solution, dry runs, complexity analysis, common mistakes, and FAQs.What Is the Problem Really Asking?You are given two strings s and t. Both contain lowercase letters and # characters. Think of # as the backspace key on your keyboard — it deletes the character just before it. If there is nothing to delete, it does nothing.Process both strings through these backspace operations and check if the resulting strings are equal. Return true if equal, false otherwise.Quick Example:s = "ab#c" → # deletes b → becomes "ac"t = "ad#c" → # deletes d → becomes "ac"Both equal "ac" → return true ✅Real Life Analogy — The Keyboard TypoYou are typing a message. You type "ab", realize you made a typo, hit backspace, and type "c". Your friend types "ad", hits backspace, and types "c". Even though you both typed differently, the final message on screen is the same — "ac".That is exactly what this problem is about. Two people typing differently but ending up with the same result.Approach 1: StringBuilder as Stack (Optimal & Clean) ✅The IdeaThis is your own solution and the best O(n) approach. Process each string independently using a StringBuilder as a stack:Letter → append to StringBuilder (push)# → delete last character if StringBuilder is not empty (pop)Then simply compare the two resulting StringBuilders.public boolean backspaceCompare(String s, String t) { return process(s).equals(process(t));}private String process(String str) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (c == '#') { if (sb.length() > 0) { sb.deleteCharAt(sb.length() - 1); } } else { sb.append(c); } } return sb.toString();}Notice how extracting a process() helper method makes the code cleaner and avoids repeating the same loop twice — a great habit to show in interviews!Dry Run — s = "ab##", t = "c#d#"Processing s = "ab##":a → append → "a"b → append → "ab"# → delete last → "a"# → delete last → ""Processing t = "c#d#":c → append → "c"# → delete last → ""d → append → "d"# → delete last → ""Both result in "" → return true ✅Time Complexity: O(n + m) — where n and m are lengths of s and t Space Complexity: O(n + m) — two StringBuilders storing processed stringsApproach 2: Stack Based Solution (Interview Classic)The IdeaSame logic as above but using explicit Stack<Character> objects. Great for explaining your thought process clearly in an interview even though StringBuilder is cleaner.public boolean backspaceCompare(String s, String t) { return processStack(s).equals(processStack(t));}private String processStack(String str) { Stack<Character> st = new Stack<>(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (c == '#') { if (!st.empty()) { st.pop(); } } else { st.push(c); } } StringBuilder sb = new StringBuilder(); while (!st.empty()) { sb.append(st.pop()); } return sb.reverse().toString();}Dry Run — s = "a#c", t = "b"Processing s = "a#c":a → push → stack: [a]# → pop → stack: []c → push → stack: [c]Result: "c"Processing t = "b":b → push → stack: [b]Result: "b""c" does not equal "b" → return false ✅Time Complexity: O(n + m) Space Complexity: O(n + m)Approach 3: Two Pointer — O(1) Space (Follow-Up Solution) 🔥This is the follow-up the problem asks about — can you solve it in O(n) time and O(1) space? This means no extra StringBuilder or Stack allowed.The IdeaInstead of building processed strings, traverse both strings from right to left simultaneously. Keep a count of pending backspaces. Skip characters that would be deleted and compare characters that survive.Why right to left? Because # affects characters to its left, so processing from the end lets us know upfront how many characters to skip.public boolean backspaceCompare(String s, String t) { int i = s.length() - 1; int j = t.length() - 1; int skipS = 0, skipT = 0; while (i >= 0 || j >= 0) { // Find next valid character in s while (i >= 0) { if (s.charAt(i) == '#') { skipS++; i--; } else if (skipS > 0) { skipS--; i--; } else { break; } } // Find next valid character in t while (j >= 0) { if (t.charAt(j) == '#') { skipT++; j--; } else if (skipT > 0) { skipT--; j--; } else { break; } } // Compare the valid characters if (i >= 0 && j >= 0) { if (s.charAt(i) != t.charAt(j)) { return false; } } else if (i >= 0 || j >= 0) { return false; // one string still has chars, other doesn't } i--; j--; } return true;}Dry Run — s = "ab#c", t = "ad#c"Starting from the right end of both strings:Round 1:s[3] = 'c' → valid, no skips → stopt[3] = 'c' → valid, no skips → stopCompare 'c' == 'c' ✅ → move both pointers leftRound 2:s[2] = '#' → skipS = 1, move lefts[1] = 'b' → skipS > 0, skipS = 0, move lefts[0] = 'a' → valid, stopt[2] = '#' → skipT = 1, move leftt[1] = 'd' → skipT > 0, skipT = 0, move leftt[0] = 'a' → valid, stopCompare 'a' == 'a' ✅ → move both pointers leftBoth pointers exhausted → return true ✅Time Complexity: O(n + m) — each character visited at most once Space Complexity: O(1) — only pointer and counter variables, no extra storage!Approach ComparisonThe StringBuilder approach is the easiest to write and explain. The Stack approach is slightly more verbose but shows clear intent. The Two Pointer approach is the hardest to code but the most impressive — it solves the follow-up and uses zero extra space.In an interview, start with the StringBuilder solution, explain it clearly, then mention the Two Pointer approach as the O(1) space optimization if asked.How This Fits the Stack Simulation PatternYou have now seen this same pattern across four problems:3174 Clear Digits — digit deletes closest left non-digit 2390 Removing Stars — star deletes closest left non-star 1047 Remove Adjacent Duplicates — character cancels matching top of stack 844 Backspace String Compare — # deletes closest left character, then compare two stringsAll four use the same StringBuilder-as-stack core. The only differences are the trigger character and what you do with the result. This is the power of pattern recognition in DSA.Common Mistakes to AvoidNot handling backspace on empty string When # appears but the StringBuilder is already empty, do nothing. Always guard with sb.length() > 0 before calling deleteCharAt. The problem explicitly states backspace on empty text keeps it empty.Using Stack and forgetting to handle # when stack is empty In the Stack approach, only pop if the stack is not empty. Pushing # onto the stack when it is empty is a common bug that gives wrong answers.In Two Pointer, comparing before both pointers find valid characters Make sure both inner while loops fully complete before comparing. Comparing too early is the most common mistake in the O(1) space solution.FAQs — People Also AskQ1. What is the best approach for LeetCode 844 in Java? For most interviews, the StringBuilder approach is the best — clean, readable, and O(n) time. If the interviewer asks for O(1) space, switch to the Two Pointer approach traversing from right to left.Q2. How does the O(1) space solution work for LeetCode 844? It uses two pointers starting from the end of both strings, keeping a skip counter to track pending backspaces. Characters that would be deleted are skipped, and only surviving characters are compared.Q3. What is the time complexity of LeetCode 844? All three approaches run in O(n + m) time where n and m are the lengths of the two strings. The Two Pointer approach achieves this with O(1) space instead of O(n + m).Q4. Why traverse from right to left in the Two Pointer approach? Because # affects characters to its left. Scanning from the right lets you know upfront how many characters to skip before you reach them, avoiding the need to store anything.Q5. Is LeetCode 844 asked in Google interviews? Yes, it is commonly used as a warmup or screening problem. The follow-up O(1) space solution is what makes it interesting for senior-level interviews.Similar LeetCode Problems to Practice Next1047. Remove All Adjacent Duplicates In String — Easy — same stack pattern2390. Removing Stars From a String — Medium — star as backspace3174. Clear Digits — Easy — digit as backspace1209. Remove All Adjacent Duplicates in String II — Medium — k adjacent duplicates678. Valid Parenthesis String — Medium — stack with wildcardsConclusionLeetCode 844 Backspace String Compare is a well-rounded problem that tests string manipulation, stack simulation, and space optimization all in one. The StringBuilder solution is your go-to for interviews. But always be ready to explain the Two Pointer O(1) space follow-up — that is what shows real depth of understanding.Check out these problems alongside 1047, 2390, and 3174 and you will have the entire stack simulation pattern locked down for any coding interview.

StringStackTwo PointerString Builder

LeetCode 3761 Minimum Absolute Distance Between Mirror Pairs | Java HashMap Solution

IntroductionSome problems look simple at first—but hide a clever trick inside.LeetCode 3761 – Minimum Absolute Distance Between Mirror Pairs is one such problem. It combines:Number manipulation (digit reversal)HashingEfficient searchingIf approached naively, this problem can easily lead to O(n²) time complexity—which is not feasible for large inputs.In this article, we will walk through:Problem intuitionNaive approach (and why it fails)Optimized HashMap solutionStep-by-step explanationClean Java code with comments🔗 Problem LinkLeetCode: Minimum Absolute Distance Between Mirror PairsTo gain a deeper understanding of the problem, it is highly recommended that you review this similar problem Closest Equal Element Queries here is the link of the article. Both cases follow a nearly identical pattern, and studying the initial example will provide valuable context for the current task.Problem StatementYou are given an integer array nums.A mirror pair (i, j) satisfies:0 ≤ i < j < nums.lengthreverse(nums[i]) == nums[j]👉 Your task is to find:The minimum absolute distance between such pairsIf no mirror pair exists, return -1.ExamplesExample 1Input:nums = [12, 21, 45, 33, 54]Output:1Explanation:(0,1) → reverse(12) = 21 → distance = 1(2,4) → reverse(45) = 54 → distance = 2✔ Minimum = 1Example 2Input:nums = [120, 21]Output:1Example 3Input:nums = [21, 120]Output:-1Key InsightThe core idea is:Instead of checking every pair,store reversed values and match on the fly.❌ Naive Approach (Brute Force)IdeaCheck all pairs (i, j)Reverse nums[i]Compare with nums[j]ComplexityTime: O(n²) ❌Space: O(1)ProblemWith n ≤ 100000, this approach will definitely cause TLE.✅ Optimized Approach (HashMap)IntuitionWhile iterating through the array:Reverse the current numberCheck if this number was already seen as a reversed valueIf yes → we found a mirror pairKey TrickInstead of storing original numbers:👉 Store reversed values as keysThis allows instant lookup.Java Code (With Detailed Comments)import java.util.*;class Solution {// Function to reverse digits of a numberpublic int reverse(int m) {int rev = 0;while (m != 0) {int dig = m % 10; // extract last digitm = m / 10; // remove last digitrev = rev * 10 + dig; // build reversed number}return rev;}public int minMirrorPairDistance(int[] nums) {// Map to store reversed values and their indicesHashMap<Integer, Integer> mp = new HashMap<>();int min = Integer.MAX_VALUE;for (int i = 0; i < nums.length; i++) {// Check if current number exists in map// Meaning: some previous number had reverse equal to thisif (mp.containsKey(nums[i])) {// Calculate distanceint prevIndex = mp.get(nums[i]);min = Math.min(min, Math.abs(i - prevIndex));}// Reverse current numberint revVal = reverse(nums[i]);// Store reversed value with indexmp.put(revVal, i);}// If no pair found, return -1return min == Integer.MAX_VALUE ? -1 : min;}}Step-by-Step Dry RunInput:nums = [12, 21, 45, 33, 54]Execution:IndexValueReverseMap CheckAction01221not foundstore (21 → 0)12112founddistance = 124554not foundstore (54 → 2)33333not foundstore (33 → 3)45445founddistance = 2👉 Minimum = 1Complexity AnalysisTime ComplexityReversing number → O(digits) ≈ O(log n)Loop → O(n)👉 Overall: O(n)Space ComplexityHashMap stores at most n elements👉 O(n)Why This Approach WorksAvoids unnecessary pair comparisonsUses hashing for constant-time lookupProcesses array in a single passKey TakeawaysAlways think of hashing when matching conditions existReversing numbers can convert the problem into a lookup problemAvoid brute force when constraints are largeThis is a classic “store & check” patternCommon Interview PatternThis problem is similar to:Two Sum (hashing)Reverse pairsMatching transformationsConclusionThe Minimum Absolute Distance Between Mirror Pairs problem is a great example of how a simple optimization (using a HashMap) can reduce complexity from O(n²) → O(n).Understanding this pattern will help you solve many similar problems involving:TransformationsMatching conditionsEfficient lookupsFrequently Asked Questions (FAQs)1. Why store reversed value instead of original?Because we want to quickly check if a number matches the reverse of a previous number.2. What if multiple same reversed values exist?The map stores the latest index, ensuring minimum distance is considered.3. Can this be solved without HashMap?Yes, but it will result in inefficient O(n²) time.

LeetCodeArrayJavaMediumHashMap

LeetCode 784 Letter Case Permutation | Recursion & Backtracking Java Solution

IntroductionThe Letter Case Permutation problem is a classic example of recursion and backtracking, often asked in coding interviews and frequently searched by learners preparing for platforms like LeetCode.This problem helps in understanding:Decision-making at each stepRecursive branchingString manipulationIn this article, we’ll break down the intuition, visualize the decision process using your decision tree, and implement an efficient Java solution.🔗 Problem LinkLeetCode: Letter Case PermutationProblem StatementGiven a string s, you can transform each alphabet character into:LowercaseUppercaseDigits remain unchanged.👉 Return all possible strings formed by these transformations.ExamplesExample 1Input:s = "a1b2"Output:["a1b2","a1B2","A1b2","A1B2"]Example 2Input:s = "3z4"Output:["3z4","3Z4"]Key InsightAt each character:If it's a digit → only one choiceIf it's a letter → two choices:lowercase OR uppercaseSo total combinations:2^(number of letters)Intuition (Using Your Decision Tree)For input: "a1b2"Start from index 0: "" / \ "a" "A" | | "a1" "A1" / \ / \ "a1b" "a1B" "A1b" "A1B" | | | | "a1b2" "a1B2" "A1b2" "A1B2"Understanding the TreeAt 'a' → branch into 'a' and 'A''1' → no branching (digit)'b' → again branching'2' → no branching📌 Leaf nodes = final answersApproach: Recursion + BacktrackingIdeaTraverse the string character by characterIf digit → move forwardIf letter → branch into:lowercaseuppercaseJava Codeimport java.util.*;class Solution { // List to store all results List<String> lis = new ArrayList<>(); public void solve(String s, int ind, String ans) { // Base case: reached end of string if (ind == s.length()) { lis.add(ans); // store generated string return; } char ch = s.charAt(ind); // If character is a digit → only one option if (ch >= '0' && ch <= '9') { solve(s, ind + 1, ans + ch); } else { // Choice 1: convert to lowercase solve(s, ind + 1, ans + Character.toLowerCase(ch)); // Choice 2: convert to uppercase solve(s, ind + 1, ans + Character.toUpperCase(ch)); } } public List<String> letterCasePermutation(String s) { solve(s, 0, ""); // start recursion return lis; }}Step-by-Step ExecutionFor "a1b2":Start → ""'a' → "a", "A"'1' → "a1", "A1"'b' → "a1b", "a1B", "A1b", "A1B"'2' → final stringsComplexity AnalysisTime Complexity: O(2^n)(n = number of letters)Space Complexity: O(2^n)(for storing results)Why This Approach WorksRecursion explores all possibilitiesEach letter creates a branching pointDigits pass through unchangedBacktracking ensures all combinations are generatedKey TakeawaysThis is a binary decision recursion problemLetters → 2 choicesDigits → 1 choiceDecision tree directly maps to recursionPattern similar to:SubsetsPermutations with conditionsWhen This Problem Is AskedCommon in:Coding interviewsRecursion/backtracking roundsString manipulation problemsConclusionThe Letter Case Permutation problem is a perfect example of how recursion can be used to explore all possible combinations efficiently.Once the decision tree is clear, the implementation becomes straightforward. This pattern is widely used in many advanced problems, making it essential to master.Frequently Asked Questions (FAQs)1. Why don’t digits create branches?Because they have only one valid form.2. What is the main concept used?Recursion with decision-making (backtracking).3. Can this be solved iteratively?Yes, using BFS or iterative expansion, but recursion is more intuitive.

LeetCodeMediumJavaRecursion