Search Blogs

Showing results for "Array Problems"

Found 50 results

LeetCode 1752: Check if Array Is Sorted and Rotated – Java Solution Explained

IntroductionLeetCode 1752 – Check if Array Is Sorted and Rotated is a classic array observation problem that tests your understanding of:Sorted arraysRotation logicCircular traversalEdge case handlingPattern recognitionAt first, many developers overcomplicate this problem by trying to actually rotate arrays and compare them. However, the problem can be solved using a very elegant observation.This problem is commonly asked in coding interviews because it evaluates:Logical thinkingArray traversal skillsOptimization abilityUnderstanding of rotated arraysProblem Link🔗 https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/Problem StatementGiven an array:numsReturn:trueif the array was originally sorted in non-decreasing order and then rotated some number of times.Otherwise return:falseDuplicates are allowed.Understanding RotationSuppose the original sorted array is:[1,2,3,4,5]After rotation:[3,4,5,1,2]The array is still almost sorted except for one “breaking point”.Key ObservationA sorted rotated array can have:At most one decreasing pairExample:[3,4,5,1,2]Breaking point:5 > 1Only once.Invalid Example[2,1,3,4]Breaking points:2 > 1and circularly:4 > 2Two breaking points.So answer is:falseBrute Force ApproachIntuitionTry all possible rotations.For every rotation:Rotate arrayCheck if sortedIf any rotation works → return trueBrute Force AlgorithmFor every rotation count:Create rotated arrayVerify sorted orderIf sorted:return trueElse:return falseBrute Force ComplexityTime ComplexityO(N²)because each rotation requires traversal.Space ComplexityO(N)This solution:Finds rotation pointSorts arrayRotates sorted arrayCompares with originalThis is a valid simulation-based approach.Java Solutionclass Solution { public boolean check(int[] nums) { int[] arr = new int[nums.length]; int o = 0; int mini = Integer.MIN_VALUE; int temp = 0; int maxnumind = 0; for(int a : nums) { arr[o] = a; temp = mini; mini = Math.max(mini, a); if(mini != temp) { maxnumind = o; } o++; } for(int i = 0; i < nums.length - 1; i++) { if(nums[i] > nums[i + 1]) { maxnumind = i; } } int ro = nums.length - maxnumind - 1; Arrays.sort(nums); int[] rotarr = new int[nums.length]; for(int i = 0; i < nums.length; i++) { rotarr[i] = nums[(i + ro) % nums.length]; } for(int i = 0; i < arr.length; i++) { if(rotarr[i] != arr[i]) { return false; } } return true; }}Optimized Approach (Best Solution)We do not need:SortingExtra arraysRotation simulationWe only count:decreasing pairsOptimized IntuitionFor a valid rotated sorted array:nums[i] > nums[i+1]can happen only once.Also check circular condition:last element > first elementOptimized Java Solutionclass Solution { public boolean check(int[] nums) { int count = 0; for(int i = 0; i < nums.length; i++) { if(nums[i] > nums[(i + 1) % nums.length]) { count++; } } return count <= 1; }}Why This WorksIf array is sorted and rotated:Sequence increases normallyOnly one position breaks orderIf more than one break exists:Not a rotated sorted arrayDry RunInputnums = [3,4,5,1,2]Step 1Compare adjacent elements:3 < 44 < 55 > 1 ← breaking point1 < 22 < 3 (circular)Breaking points:1Valid.Return:trueAnother Dry RunInputnums = [2,1,3,4]Comparisons:2 > 1 ← break1 < 33 < 44 > 2 ← circular breakBreaking points:2Invalid.Return:falseTime Complexity AnalysisTime ComplexityO(N log N)because of sorting.Space ComplexityO(N)extra arrays used.Optimized ApproachTime ComplexityO(N)single traversal.Space ComplexityO(1)Comparison of ApproachesApproachTime ComplexitySpace ComplexityRotation SimulationO(N log N)O(N)Decreasing Pair CountO(N)O(1)Interview ExplanationIn interviews, explain:A sorted rotated array can contain only one position where the order decreases. By counting such breaking points including circular comparison, we can determine validity in linear time.This demonstrates:Pattern recognitionCircular traversal understandingOptimization thinkingCommon Mistakes1. Forgetting Circular CheckAlways compare:nums[n-1] > nums[0]using modulo.2. Actually Rotating ArraysUnnecessary and inefficient.3. Using Strictly Increasing LogicDuplicates are allowed.So:1,1,2,2is valid.FAQsQ1. Why use modulo?To compare:last element with first elementcircularly.Q2. Why is only one break allowed?Because rotation shifts sorted order only once.Q3. Is sorting required?No.Observation-based traversal is enough.Q4. Is this problem important for interviews?Yes.It tests:Array logicRotationsOptimizationObservation skillsRelated ProblemsAfter mastering this problem, practice:Search in Rotated Sorted ArrayFind Minimum in Rotated Sorted ArrayFind Minimum in Rotated Sorted Array IIConclusionLeetCode 1752 is an excellent observation-based array problem.It teaches:Rotated array logicCircular traversalOptimization techniquesPattern recognitionThe key insight is:A sorted rotated array can have at most one decreasing point.Once you understand this observation, the optimized solution becomes extremely clean and efficient.

LeetCodeJavaArrayRotation ProblemsSortingEasy

LeetCode 2657: Find the Prefix Common Array of Two Arrays – Java Hashing Solution Explained

IntroductionLeetCode 2657 – Find the Prefix Common Array of Two Arrays is an interesting prefix and hashing problem that tests your understanding of:Prefix processingHashingFrequency countingSet operationsArray traversalAt first glance, the problem may look confusing because of the term:Prefix Common ArrayBut once you understand the meaning of prefixes and common elements, the problem becomes straightforward.This problem is useful for improving:Prefix-based thinkingHashing intuitionOptimization skillsInterview problem-solving abilityProblem Link🔗 Find the prefix Common Array of Two ArraysProblem StatementYou are given two permutations:A and BBoth arrays contain numbers:1 to nexactly once.You need to create an array:Cwhere:C[i]represents:Count of numbers present in both arrays from index 0 to i.Understanding Prefix Common ArraySuppose:A = [1,3,2,4]B = [3,1,2,4]Prefix at Index 0A Prefix = [1]B Prefix = [3]Common numbers:NoneSo:C[0] = 0Prefix at Index 1A Prefix = [1,3]B Prefix = [3,1]Common numbers:1, 3So:C[1] = 2Final Output[0,2,3,4]Key ObservationBoth arrays are permutations.This means:Every number appears exactly once.Once a number appears in both prefixes, it remains common forever.This simplifies the logic significantly.Brute Force ApproachIntuitionFor every index:Build prefixesCompare elementsCount common numbersBrute Force AlgorithmFor each index:Traverse all previous elementsCheck whether numbers exist in both prefixesCount matchesBrute Force ComplexityTime ComplexityO(N²)because for every index we may scan previous elements.Space ComplexityO(N)Understanding ApproachThis approach uses:HashMapPrefix trackingCounting common valuesThe idea is:Store prefix elements from BTraverse A prefixCount matching numbersThis works because prefixes gradually expand.Java Solutionclass Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int j = 0; int[] ans = new int[A.length]; HashMap<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < A.length; i++) { map.put(B[i], i); int counter = 0; int c = 0; for(int a : map.keySet()) { if(map.containsKey(A[c])) { counter++; } c++; } ans[j] = counter; j++; } return ans; }}Better Optimized ApproachWe can solve this more cleanly using:HashSetor frequency counting.Optimized IntuitionAt every index:Add A[i]Add B[i]Track which numbers appearedIf a number appears in both arrays, increase common countBest Optimized Approach Using Frequency ArrayBecause values are from:1 to nwe can use a frequency array.Optimized Java Solutionclass Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int n = A.length; int[] ans = new int[n]; int[] freq = new int[n + 1]; int common = 0; for(int i = 0; i < n; i++) { freq[A[i]]++; if(freq[A[i]] == 2) common++; freq[B[i]]++; if(freq[B[i]] == 2) common++; ans[i] = common; } return ans; }}Why Does This Work?Every number appears once in A and once in B.So:First appearance → frequency becomes 1Second appearance → frequency becomes 2When frequency becomes:2it means the number has appeared in both prefixes.So we increase:commonDry RunInputA = [1,3,2,4]B = [3,1,2,4]Step 1Index:0Add:1 and 3Frequencies:1 → 13 → 1No common elements.ans[0] = 0Step 2Add:3 and 1Frequencies:1 → 23 → 2Two common elements found.ans[1] = 2Step 3Add:2 and 2Frequency:2 → 2Common becomes:3ans[2] = 3Step 4Add:4 and 4Frequency:4 → 2Common becomes:4ans[3] = 4Final Output[0,2,3,4]Time Complexity AnalysisTime ComplexityO(N²)Nested traversal inside loop.Space ComplexityO(N)Optimized Frequency ApproachTime ComplexityO(N)Single traversal.Space ComplexityO(N)Frequency array.HashMap vs Frequency ArrayApproachTime ComplexitySpace ComplexityHashMapO(N²)O(N)Frequency ArrayO(N)O(N)Interview ExplanationIn interviews, explain:Since both arrays are permutations, every number appears exactly twice overall — once in A and once in B. Using frequency counting, whenever a number’s frequency becomes 2, it means it has appeared in both prefixes.This demonstrates:Prefix understandingOptimization thinkingHashing skillsCommon Mistakes1. Recalculating Common Elements Every TimeThis causes:O(N²)complexity.2. Forgetting Arrays Are PermutationsThis special condition allows frequency optimization.3. Incorrect Prefix LogicRemember:Prefix means elements from 0 to i.FAQsQ1. Why is this called Prefix Common Array?Because:C[i]stores common elements between prefixes ending at index:iQ2. Why does frequency 2 mean common?Because every number appears once in each array.Q3. Which approach is best?Frequency array approach is the most optimized.Q4. Is this problem important for interviews?Yes.It tests:Prefix logicHashingOptimizationArray traversalRelated ProblemsAfter mastering this problem, practice:Intersection of Two ArraysIntersection of Two Arrays IIContains DuplicateSubarray Sum Equals KPrefix SumFind the Difference of Two ArraysConclusionLeetCode 2657 is an excellent prefix and hashing problem.It teaches:Prefix processingFrequency countingOptimization techniquesHashing fundamentalsThe key insight is:A number becomes common exactly when its frequency becomes 2.Once you understand this observation, the optimized solution becomes very simple and efficient.

LeetCodePrefix Common ArrayJavaHashMapHashSetArrayPrefixArrayMedium

LeetCode 154: Find Minimum in Rotated Sorted Array II – Java Binary Search Solution Explained

IntroductionLeetCode 154 – Find Minimum in Rotated Sorted Array II is a classic binary search interview problem.This problem is an advanced version of:Find Minimum in Rotated Sorted ArrayThe major difference is:The array may contain duplicates.That small change makes the problem much harder because duplicates can break normal binary search logic.This problem teaches:Modified binary searchRotated array conceptsHandling duplicatesEdge case optimizationInterview problem-solving techniquesProblem Link🔗 ProblemLeetCode 154: Find Minimum in Rotated Sorted Array IIOfficial Problem: LeetCode Problem LinkProblem StatementAn ascending sorted array is rotated between 1 and n times.Example:[0,1,4,4,5,6,7]may become:[4,5,6,7,0,1,4]or[0,1,4,4,5,6,7]Given the rotated sorted array nums that may contain duplicates, return the minimum element.ExampleExample 1Input:nums = [1,3,5]Output:1Example 2Input:nums = [2,2,2,0,1]Output:0Understanding Rotated Sorted ArraysNormally a sorted array looks like:[1,2,3,4,5]After rotation:[4,5,1,2,3]The minimum element becomes the pivot point.Our goal is to efficiently find this pivot.Brute Force ApproachIntuitionTraverse the entire array and keep track of the smallest element.AlgorithmInitialize minimum as first element.Traverse the array.Update minimum whenever a smaller element appears.Return minimum.Java Code – Brute Forceclass Solution { public int findMin(int[] nums) { int min = nums[0]; for(int num : nums) { min = Math.min(min, num); } return min; }}Dry Run – Brute ForceInput:[2,2,2,0,1]Traversal:ElementMinimum2222220010Final answer:0Complexity Analysis – Brute ForceTime ComplexityO(N)Space ComplexityO(1)Can We Do Better?Yes.Since the array is sorted and rotated, we can use Binary Search.However, duplicates make the problem tricky.Binary Search IntuitionIn a rotated sorted array:One half is always sorted.The minimum lies in the unsorted half.Without duplicates, binary search becomes straightforward.But duplicates create ambiguity.Example:[2,2,2,0,2]If:nums[mid] == nums[right]we cannot determine which side contains the minimum.So we shrink the search space carefully.Key Binary Search ObservationsCase 1If:nums[mid]<nums[right]nums[mid] < nums[right]nums[mid]<nums[right]then the right half is sorted, and minimum may lie at mid or left side.Move:right = midCase 2If:nums[mid]>nums[right]nums[mid] > nums[right]nums[mid]>nums[right]then minimum lies in the right half.Move:left = mid + 1Case 3If:nums[mid]=nums[right]nums[mid] = nums[right]nums[mid]=nums[right]we cannot identify the correct side.Safely reduce search space:right--Optimized Binary Search ApproachStepsInitialize two pointers:leftrightFind middle element.Compare nums[mid] with nums[right].Narrow the search space accordingly.Continue until pointers meet.Java Binary Search Solutionclass Solution { public int findMin(int[] nums) { if(nums.length == 1) return nums[0]; int left = 0; int right = nums.length - 1; int min = Integer.MAX_VALUE; while(left <= right) { int mid = left + (right - left) / 2; if(nums[mid] < nums[right]) { right = mid; min = Math.min(min, nums[right]); } else if(nums[mid] > nums[right]) { min = Math.min(min, nums[right]); left = mid + 1; } else { right--; } min = Math.min(min, nums[mid]); } return min; }}Dry Run – Binary SearchInputnums = [2,2,2,0,1]Initial StateLeftRight04Iteration 1Midmid = 2Value:nums[mid] = 2nums[right] = 1Since:2>12 > 12>1Move:left = mid + 1Now:LeftRight34Iteration 2Midmid = 3Value:nums[mid] = 0nums[right] = 1Since:0<10 < 10<1Move:right = midNow:LeftRight33Final Answer0Time Complexity AnalysisAverage CaseO(log N)Worst CaseDue to duplicates:O(N)Why Worst Case Becomes O(N)Consider:[1,1,1,1,1]Every comparison becomes:nums[mid] == nums[right]We can only shrink by one element:right--This degrades binary search to linear complexity.Interview ExplanationIn interviews, explain:Duplicates destroy the ability to always determine the sorted half uniquely. When nums[mid] == nums[right], we cannot confidently eliminate one side, so we reduce the search space by one element.This is the key insight interviewers look for.Common Mistakes1. Using Standard Binary Search LogicStandard rotated-array logic fails with duplicates.2. Ignoring Duplicate CaseThis condition is essential:else { right--;}3. Infinite Loop ErrorsAlways update pointers carefully.Alternative Simpler Binary SearchA cleaner version:class Solution { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < nums[right]) { right = mid; } else if(nums[mid] > nums[right]) { left = mid + 1; } else { right--; } } return nums[left]; }}This is the most common interview solution.FAQsQ1. Why does binary search become O(N)?Duplicates prevent us from discarding half the search space confidently.Q2. Why compare with nums[right]?It helps identify whether the minimum lies on the left or right side.Q3. Is this problem important for interviews?Yes.It is a very popular advanced binary search interview problem.ConclusionLeetCode 154 is an excellent problem for mastering:Modified binary searchRotated sorted arraysDuplicate handlingSearch optimizationThe key challenge is handling:nums[mid]=nums[right]nums[mid] = nums[right]nums[mid]=nums[right]correctly.Once you understand this pattern, many advanced binary search interview problems become much easier.

HardBinary SearchRotated Sorted ArrayJavaLeetCode

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

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

LeetCodeBinary SearchRotated Sorted ArrayJavaMedium

LeetCode 2553: Separate the Digits in an Array – Java Solution Explained (2 Easy Approaches)

IntroductionIn coding interviews and competitive programming, many problems test how well you can manipulate numbers and arrays together. One such beginner-friendly problem is LeetCode 2553 – Separate the Digits in an Array.In this problem, we are given an integer array, and we need to separate every digit of every number while maintaining the original order.This problem is excellent for practicing:Array traversalDigit extractionReverse processingArrayList usage in JavaThinking about order preservationProblem Link🔗 ProblemLeetCode 2553: Separate the Digits in an ArrayProblem StatementGiven an array of positive integers nums, return an array containing all digits of each integer in the same order they appear.ExampleInput:nums = [13,25,83,77]Output:[1,3,2,5,8,3,7,7]IntuitionThe main challenge is:Extract digits from each numberPreserve the original left-to-right orderNormally, extracting digits using % 10 gives digits in reverse order.Example:83 → 3 → 8So we need a way to restore the correct order.Approach 1 – Using String ConversionIdeaConvert every number into a string and then traverse each character.This is the simplest and most beginner-friendly approach.AlgorithmTraverse every number in the array.Convert the number into a string.Traverse each character of the string.Convert character back to integer.Store digits into ArrayList.Convert ArrayList to array.Java Code – String Approachclass Solution { public int[] separateDigits(int[] nums) { ArrayList<Integer> list = new ArrayList<>(); for (int num : nums) { String str = String.valueOf(num); for (char ch : str.toCharArray()) { list.add(ch - '0'); } } int[] ans = new int[list.size()]; for (int i = 0; i < list.size(); i++) { ans[i] = list.get(i); } return ans; }}Dry Run (String Approach)Input:nums = [13,25]Step 113 → "13"Digits added:1, 3Step 225 → "25"Digits added:2, 5Final Array:[1,3,2,5]Time Complexity & Space ComplexityTime ComplexityO(N × D)Where:N = number of elementsD = number of digitsSpace ComplexityO(N × D)For storing digits.Approach 2 – Mathematical Digit Extraction (Optimal Without String)This is the approach you implemented in your code.Instead of converting numbers into strings, we extract digits mathematically using:digit = num % 10num = num / 10But digits come in reverse order.To fix this:Traverse the original array from back to frontStore extracted digitsReverse the final resultThis avoids string conversion completely.Intuition Behind Reverse TraversalSuppose:nums = [13,25]If we traverse from the end:25 → 5,213 → 3,1Stored list:[5,2,3,1]Now reverse the list:[1,3,2,5]Correct answer achieved.Java Code – Mathematical Approachclass Solution { public int[] separateDigits(int[] nums) { ArrayList<Integer> list = new ArrayList<>(); for (int i = nums.length - 1; i >= 0; i--) { if (nums[i] < 10) { list.add(nums[i]); } else { int val = nums[i]; while (val != 0) { int digit = val % 10; val = val / 10; list.add(digit); } } } int[] ans = new int[list.size()]; int k = 0; for (int i = list.size() - 1; i >= 0; i--) { ans[k++] = list.get(i); } return ans; }}Dry Run (Mathematical Approach)Input:nums = [13,25,83]Traverse from Back83Digits extracted:3, 8List:[3,8]25Digits extracted:5,2List:[3,8,5,2]13Digits extracted:3,1List:[3,8,5,2,3,1]Reverse Final List[1,3,2,5,8,3]Correct answer.Time Complexity Analysis & Space ComplexityTime ComplexityO(N × D)Because every digit is processed once.Space ComplexityO(N × D)For storing final digits.Which Approach is Better?ApproachAdvantagesDisadvantagesString ConversionEasy to understandUses extra string conversionMathematical ExtractionBetter DSA practiceSlightly harder logicInterview PerspectiveIn interviews:Beginners should first explain the string approach.Then discuss optimization using mathematical extraction.Interviewers like when candidates:Understand digit manipulationThink about order preservationCompare multiple approachesCommon Mistakes1. Forgetting Reverse OrderUsing % 10 extracts digits backward.Example:123 → 3,2,1You must reverse later.2. Not Handling Single Digit NumbersSingle digit numbers should directly be added.3. Character Conversion MistakeWrong:list.add(ch);Correct:list.add(ch - '0');Frequently Asked Questions (FAQs)Q1. Why do digits come in reverse order?Because % 10 always extracts the last digit first.Example:123 % 10 = 3Q2. Can we solve this without ArrayList?Yes, but ArrayList makes dynamic storage easier.Q3. Which approach is more optimal?Both have similar complexity.Mathematical extraction avoids string conversion and is preferred in interviews.Q4. Is this problem important for interviews?Yes. It teaches:Number manipulationOrder handlingArray traversalBasic optimization thinkingConclusionLeetCode 2553 is a simple yet valuable beginner problem for understanding:Digit extractionArray handlingReverse traversalOrder preservationYou learned two approaches:String Conversion ApproachMathematical Digit Extraction ApproachThe mathematical solution is especially useful because it strengthens core DSA concepts and improves problem-solving skills for interviews.If you're preparing for coding interviews in Java, this is a great problem to master before moving to harder digit manipulation questions.

ArrayEasyLeetcodeDigit ExtractionJava

Amazon OA: Find the Element Occurring Less Than K Times in a Sorted Array – Java Solution

IntroductionThis is a sorted array frequency problem that can appear in coding assessments and online assessments such as an Amazon OA.You are given a sorted array B of size N. Every distinct element occurs exactly K times except for one element, whose frequency is less than K.The task is to find that element.Because the array is sorted, all occurrences of the same element are located together. This allows us to process the array sequentially and keep track of the current element and its frequency.For example:B = [2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5]K = 3Here:2 → 3 times3 → 2 times4 → 3 times5 → 3 timesTherefore, the answer is:3because 3 occurs fewer than K = 3 times.QuestionYou are given a sorted array B of size N.Every element in the array occurs exactly K times except one element, which occurs fewer than K times.Find that element.It is guaranteed that there is exactly one element whose frequency is less than K.ConstraintsN <= 100000K >= 21 <= B[i] <= 10000000000Since B[i] can be as large as 10^10, a Java long should be used to safely store the array values.ExampleConsider:B = [2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5]K = 3Frequency table:Element Frequency2 33 24 35 3Only 3 occurs fewer than K times.Therefore:Output: 3Understanding the Sorted ArrayThe most important property of this problem is that the array is sorted.Because of that, identical elements always appear consecutively.For example:1 1 1 2 2 2 3 3 4 4 4We never have to search the entire array to count the occurrences of an element.We can simply scan from left to right.When the value changes, the frequency of the previous value is known.For example:1 1 1When we encounter 2, we know that:1 occurred 3 timesWe can compare this frequency with K.If it is less than K, then 1 is the required answer.Approach: Track the Current Element and Its FrequencyWe can maintain two variables:int cand;int count;where:cand represents the current element.count represents how many times that element has appeared so far.Initially:cand = arr[0];count = 1;Then we scan the remaining elements.There are three important situations.Case 1: Same ElementIf:cand == arr[i]then the current element is still being counted.So:count++;Case 2: Element Changes and Frequency Is KIf:cand != arr[i] && count == kthen the previous element occurred exactly K times.Therefore, we can start counting the new element:cand = arr[i];count = 1;Case 3: Element Changes and Frequency Is Less Than KIf:cand != arr[i] && count < kthen the previous element is the unique element whose frequency is less than K.So we can immediately stop.Java SolutionThe same logic can be implemented more cleanly as follows:class Main { public static void main(String[] args) { int[] arr = {1, 1, 2, 2, 2, 3, 3, 3}; int k = 3; int cand = arr[0]; int count = 1; for (int i = 1; i < arr.length; i++) { // Current element is still the same if (cand == arr[i]) { count++; } // Current element changed else { // Previous element occurred less than K times if (count < k) { break; } // Start counting the new element cand = arr[i]; count = 1; } } // The incomplete-frequency element may be the last element if (count < k) { System.out.println(cand); } }}Dry RunConsider:arr = [1, 1, 2, 2, 2, 3, 3, 3]k = 3Initially:cand = 1count = 1Now process the array.Step 1Current value:arr[1] = 1It is the same as cand.count = 2Step 2Current value:arr[2] = 2The value changed.Before moving to 2, we check the frequency of 1:count = 2k = 3Since:2 < 3we have found the answer.Therefore:Output: 1Another ExampleConsider:B = [2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5]K = 3We start with:cand = 2count = 1After processing the three 2s:cand = 2count = 3The next value is 3.Since:count == Kwe move to the next candidate:cand = 3count = 1After processing the second 3:cand = 3count = 2The next value is 4.Now:count < Kbecause:2 < 3Therefore:3is the required answer.Important Edge Case: Answer at the EndThere is one important case to handle.Suppose the incomplete element is the last element in the array.For example:arr = [1, 1, 1, 2, 2]K = 3When the loop finishes, there is no next element that causes the value to change.So the condition:if (cand != arr[i])will never execute for the final 2.We therefore need one final check after the loop:if (count < k) { System.out.println(cand);}This handles the case where the answer is at the end.Complexity AnalysisWe scan the array only once.For every element, we perform constant-time operations.Therefore:Time Complexity:O(N)Space Complexity:O(1)This is efficient enough for:N <= 100000and does not require an additional HashMap or frequency array.Why Does the Sorted Property Matter?Without the sorted property, the same element could appear at different positions.For example:2 3 2 4 3 2In that case, simply maintaining the frequency of the current consecutive value would not work.We would need another approach such as a HashMap.But because the input is sorted:2 2 2 3 3 4 4 4all occurrences of an element form one continuous block.That is what allows us to solve the problem with:O(N) timeO(1) extra spaceA Simpler AlternativeBecause the array is sorted, another straightforward solution is to count consecutive equal values.For example:class Main { public static void main(String[] args) { int[] arr = {2, 2, 2, 3, 3, 4, 4, 4}; int k = 3; int count = 1; for (int i = 1; i <= arr.length; i++) { if (i < arr.length && arr[i] == arr[i - 1]) { count++; } else { if (count < k) { System.out.println(arr[i - 1]); break; } count = 1; } } }}This version focuses directly on counting each consecutive group.The idea is:Read same values ↓Count them ↓Value changes ↓Check count < K ↓If yes → answer foundInterview TipWhen an interview or OA problem gives you a sorted array, always ask yourself:What does sorting allow me to avoid?Here, sorting means all equal values are adjacent.Instead of using:HashMapor sorting the array again, we can simply maintain a running frequency.The important pattern is:Current value+Consecutive frequency+Check when value changesThis pattern is useful in many array problems involving duplicate or repeated elements.ConclusionThis Amazon OA-style problem can be solved efficiently by taking advantage of the fact that the input array is sorted.Since equal elements appear consecutively, we only need to maintain:current elementcurrent frequencyWhenever the element changes, we check whether its frequency was less than K.The solution requires:Time: O(N)Space: O(1)The main takeaway is that the sorted property removes the need for additional frequency data structures and lets us find the unique incomplete-frequency element with a single linear scan.

Amazon OAAmazon Online AssessmentJavaArraysFrequency CountingSorted ArrayDSAArray Problems

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

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

LeetCodeEasyTwo PointerArrayJava

LeetCode 845: Longest Mountain in Array – Java Solution with Peak Expansion

IntroductionA mountain subarray is a contiguous portion of an array that first strictly increases and then strictly decreases.For example:[1, 4, 7, 3, 2] ↑ PeakThe array increases toward 7 and decreases after 7, making it a valid mountain of length 5.The goal is to find the longest mountain subarray in the given array.This problem is useful for understanding an important array pattern:Find a valid peak → expand around the peak → calculate the complete structure.The follow-up also asks for a solution using one pass and O(1) extra space, making it a good interview problem for learning how to optimize array traversal.Problem StatementProblem Link -: longest mountain subarrayGiven an integer array arr, return the length of the longest contiguous subarray that forms a mountain.A valid mountain must:Contain at least 3 elements.Strictly increase toward a peak.Strictly decrease after the peak.Have the peak somewhere between the first and last element.For example:[2, 1, 4, 7, 3, 2, 5]The longest mountain is:[1, 4, 7, 3, 2] ↑ peakTherefore:Answer = 5Understanding the PatternThe most important observation is that every valid mountain has a peak.A peak is an element satisfying:arr[i - 1] < arr[i] > arr[i + 1]For example:1 4 7 3 2 ↑ iAt index 2:4 < 77 > 3Therefore, 7 is a peak.Once a peak is found, the complete mountain can be discovered by expanding: peak ↓1 → 4 → 7 ← 3 ← 2 ←──── ────→The left side continues while values are increasing toward the peak.The right side continues while values are decreasing away from the peak.Approach: Expand Around Every PeakThe solution can be divided into three simple steps.Find every possible peakTraverse the array from index 1 to n - 2.For every index:arr[i - 1] < arr[i] && arr[i] > arr[i + 1]If this condition is true, i is a valid mountain peak.Expand toward the leftStarting from the peak, move left while:arr[left] > arr[left - 1]This finds how far the increasing portion extends.Expand toward the rightStarting from the peak, move right while:arr[right] > arr[right + 1]This finds how far the decreasing portion extends.The peak is counted from both sides, so:mountain length = leftLength + rightLength - 1Java SolutionThe following implementation follows the peak-expansion approach while keeping the extra space at O(1).class Solution { // Finds how far the mountain extends toward the left public int lef(int st, int[] arr) { int len = 1; // Keep moving left while the sequence is strictly increasing // toward the peak. while (st > 0 && arr[st] > arr[st - 1]) { len++; st--; } return len; } // Finds how far the mountain extends toward the right public int righ(int st, int[] arr) { int len = 1; // Keep moving right while the sequence is strictly decreasing // after the peak. while (st < arr.length - 1 && arr[st] > arr[st + 1]) { len++; st++; } return len; } public int longestMountain(int[] arr) { // A mountain must contain at least 3 elements. if (arr.length < 3) { return 0; } int ans = 0; // The first and last elements cannot be peaks, // so start from index 1 and stop at n - 2. for (int i = 1; i < arr.length - 1; i++) { // Check whether arr[i] is a valid peak. if (arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) { // Count the increasing part including the peak. int left = lef(i, arr); // Count the decreasing part including the peak. int right = righ(i, arr); // The peak is counted twice, so subtract 1. int mountainLength = left + right - 1; ans = Math.max(ans, mountainLength); } } return ans; }}Dry RunConsider:arr = [2, 1, 4, 7, 3, 2, 5]Start scanning from index 1.Index 12 1 4 ↑1 is not a peak because:2 < 1 ❌Move forward.Index 22 1 4 7 3 2 5 ↑For 4:1 < 4 > 7Not a peak.Index 32 1 4 7 3 2 5 ↑For 7:4 < 7 > 3So 7 is a valid peak.Expand leftStarting at 7:1 < 4 < 7The left side is:[1, 4, 7]Length:3Expand rightStarting at 7:7 > 3 > 2The right side is:[7, 3, 2]Length:3The peak 7 was counted twice:3 + 3 - 1 = 5Therefore:Longest mountain = 5Why the Peak Is Counted TwiceThis is an important detail in the implementation.Suppose the mountain is:1 4 7 3 2 ↑ peakThe left traversal counts:1 4 7The right traversal counts:7 3 2Adding them gives:3 + 3 = 6But the 7 belongs to both sections.Therefore:6 - 1 = 5Hence:left + right - 1Complexity AnalysisTime ComplexityThe overall complexity is:O(n)Although the implementation expands left and right whenever a peak is found, each increasing/decreasing section belongs to a particular mountain structure and the total traversal remains linear.Space ComplexityOnly a few integer variables are used:O(1)No auxiliary array, HashMap, HashSet, or other data structure is required.One-Pass OptimizationThe same problem can also be solved using a direct one-pass approach.Instead of explicitly expanding from every peak, maintain:the length of the current increasing sectionthe length of the current decreasing sectionWhen an increasing sequence changes into a decreasing sequence, a mountain has been formed.A compact implementation is:class Solution { public int longestMountain(int[] arr) { int n = arr.length; int ans = 0; int up = 0; int down = 0; for (int i = 1; i < n; i++) { // If the sequence starts increasing after a decrease, // begin tracking a new mountain. if (arr[i] > arr[i - 1]) { if (down > 0) { up = 0; down = 0; } up++; } // Continue the decreasing part of the mountain. else if (arr[i] < arr[i - 1] && up > 0) { down++; // A valid mountain requires both an increasing // and decreasing portion. ans = Math.max(ans, up + down + 1); } // Equal adjacent elements break a mountain completely. else { up = 0; down = 0; } } return ans; }}This approach directly satisfies the follow-up requirement:Time = O(n)Space = O(1)Common MistakesTreating a simple increasing sequence as a mountain1 2 3 4 5This is not a mountain because there is no decreasing portion.Treating a simple decreasing sequence as a mountain5 4 3 2 1This is also not a mountain because there is no increasing portion.Allowing equal elements1 3 3 2This is not a valid mountain because the increase must be strict.The conditions require:<>not:<=>=Forgetting the minimum lengthA mountain must contain at least three elements:increasing part + peak + decreasing partTherefore:[1, 2] → invalid[2, 1] → invalid[1, 2, 1] → validInterview TipThe key to this problem is not the code itself but recognizing the peak structure.Whenever a problem describes something like:increasing → peak → decreasinga useful first thought is:Can the middle element be treated as a peak and the structure be expanded from there?This transforms a complicated subarray condition into two simple directional scans.For interview optimization questions, it is also useful to recognize that the same structure can often be tracked using a few variables instead of repeatedly constructing subarrays.ConclusionThe Longest Mountain in Array problem demonstrates an important array technique: identifying a structural peak and analyzing the elements around it.The main ideas are:A mountain must have a valid peak.The left side must be strictly increasing.The right side must be strictly decreasing.Expanding from each peak provides an intuitive solution.The problem can also be optimized into a true one-pass O(n), O(1) solution.The most important pattern to remember is:Increasing → Peak → DecreasingOnce that pattern becomes familiar, similar problems involving peaks, valleys, increasing/decreasing runs, and subarray structures become significantly easier to recognize.

LeetCodeJavaArraysTwo PointersMedium

LeetCode 2161: Partition Array According to Given Pivot – Java Easy Stable Partition Solution

IntroductionLeetCode 2161 is a clean and important array manipulation problem that tests:Array traversalStable partitioningOrder preservationTwo-pass and three-pass approachesLogical grouping of elementsThe interesting part of this problem is that we are not only partitioning the array around a pivot, but we also need to preserve the relative order of elements.This makes the problem slightly different from classical partition algorithms like QuickSort partitioning.In this article, we will understand:The intuition behind stable partitioningWhy order preservation mattersStep-by-step explanationDry runTime and space complexityComplete optimized Java solutionProblem StatementTry this probelm here :- Partition ArrayYou are given:An integer array:numsAn integer:pivotYou must rearrange the array such that:All elements smaller than pivot come firstAll elements equal to pivot come nextAll elements greater than pivot come lastRelative ordering must remain preservedReturn the rearranged array.ExampleInputnums = [9,12,5,10,14,3,10]pivot = 10Output[9,5,3,10,10,12,14]ExplanationElements less than 109, 5, 3Elements equal to 1010, 10Elements greater than 1012, 14All relative orderings are preserved.Key ObservationWe do NOT need sorting.We only need grouping while maintaining original order.This is called:Stable PartitioningApproachWe create a new array and fill it in 3 phases:Phase 1Insert all elements:< pivotPhase 2Insert all elements:== pivotPhase 3Insert all elements:> pivotThis naturally preserves relative ordering because we traverse left-to-right every time.Optimized Java Solutionclass Solution { public int[] pivotArray(int[] nums, int pivot) { int[] ans = new int[nums.length]; int index = 0; // Smaller than pivot for(int i = 0; i < nums.length; i++) { if(nums[i] < pivot) { ans[index] = nums[i]; index++; } } // Equal to pivot for(int i = 0; i < nums.length; i++) { if(nums[i] == pivot) { ans[index] = nums[i]; index++; } } // Greater than pivot for(int i = 0; i < nums.length; i++) { if(nums[i] > pivot) { ans[index] = nums[i]; index++; } } return ans; }}Step-by-Step ExplanationStep 1: Create Answer Arrayint[] ans = new int[nums.length];Stores final partitioned result.Step 2: Insert Smaller Elementsif(nums[i] < pivot)All smaller elements go first.Step 3: Insert Equal Elementsif(nums[i] == pivot)Pivot values are placed in the middle.Step 4: Insert Larger Elementsif(nums[i] > pivot)Larger elements go to the end.Dry RunInputnums = [9,12,5,10,14,3,10]pivot = 10Pass 1: Smaller ElementsAdd:9, 5, 3Current array:[9,5,3]Pass 2: Equal ElementsAdd:10, 10Current array:[9,5,3,10,10]Pass 3: Greater ElementsAdd:12, 14Final array:[9,5,3,10,10,12,14]Time ComplexityWe traverse the array 3 times.Time ComplexityO(N)Because:3N → O(N)Space ComplexityWe use an extra array.Space ComplexityO(N)Why This Problem is ImportantThis problem teaches:Stable partitioningArray groupingRelative order preservationMulti-pass array processingClean implementation strategyThese concepts are frequently used in:Sorting systemsData pipelinesStream processingPartition-based algorithmsCommon Mistakes1. Using QuickSort Partition LogicQuickSort partitioning does NOT preserve order.This problem specifically requires stable ordering.2. Forgetting Equal ElementsSome solutions only handle:< pivotand> pivotBut pivot values must remain in the center.3. Overcomplicating with Two PointersA simple three-pass solution is cleaner and easier to understand.Interview ExplanationIn interviews explain:Since relative order must remain preserved, we cannot use traditional in-place partitioning. Instead, we perform stable partitioning by collecting smaller, equal, and larger elements sequentially.This demonstrates:Understanding of stable operationsStrong array fundamentalsClean coding approachAlternative ApproachAnother approach is using:Three separate listsThen merging themExample:small + equal + largeBut using one answer array is more space efficient.ConclusionLeetCode 2161 is a simple yet important stable partition problem.The key insight is:We must preserve relative ordering while grouping elements around the pivot.Using a clean three-pass traversal gives an elegant and efficient O(N) solution.

LeetCodeJavaMediumArrayArray PartitionPivot

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

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

LeetCodeBinary SearchMediumJava

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

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

LeetCodeBinary SearchMountain ArrayMediumJava

LeetCode 2784: Check if Array is Good – Java HashMap Solution Explained

IntroductionLeetCode 2784 – Check if Array is Good is a beginner-friendly array and hashing problem that tests your understanding of:Frequency countingHashMap usageArray validationPermutation logicEdge case handlingAlthough the problem looks simple initially, many candidates fail because they misunderstand the exact structure of the required array.This problem is commonly asked to test:Attention to detailLogical validationCounting techniquesHashing fundamentalsProblem Link🔗 https://leetcode.com/problems/check-if-array-is-good/Problem StatementAn array is considered good if it is a permutation of:base[n] = [1, 2, 3, ..., n-1, n, n]Meaning:Numbers from:1 to n-1appear exactly once.Number:nappears exactly twice.You need to return:trueif the given array is good, otherwise:falseUnderstanding the PatternA valid good array must follow:[1, 2, 3, ..., n-1, n, n]Examples:[1,1][1,2,3,3][1,2,3,4,4]Invalid examples:[1,2,2][1,2,4,4][1,1,2,2]Key ObservationsObservation 1The maximum element determines:nObservation 2Array size must be:n + 1because:1 to n-1 => n-1 elementsn appears twice => 2 elementsTotal = n + 1Observation 3Frequency conditions:NumberFrequency1 to n-1Exactly 1nExactly 2Brute Force ApproachIdeaSort arrayCompare with expected arrayReturn resultBrute Force AlgorithmStep 1Find maximum element:nStep 2Create expected array:[1,2,3,...,n,n]Step 3Sort both arrays and compare.Brute Force ComplexityTime ComplexityO(N log N)due to sorting.Space ComplexityO(N)Optimized HashMap ApproachInstead of sorting:Count frequencies directlyValidate conditionsThis makes the solution faster and cleaner.Intuition Behind HashMap SolutionWe store frequency of every number.Then verify:Maximum element appears twiceEvery other number appears onceArray length equals:max + 1Java HashMap Solutionclass Solution { public boolean isGood(int[] nums) { if(nums.length == 1) return false; int maxElement = Integer.MIN_VALUE; HashMap<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++) { map.put(nums[i], map.getOrDefault(nums[i], 0) + 1); maxElement = Math.max(maxElement, nums[i]); } int n = maxElement; if(nums.length != n + 1) { return false; } for(int i = 1; i <= n; i++) { if(!map.containsKey(i)) { return false; } if(i == n) { if(map.get(i) != 2) return false; } else { if(map.get(i) != 1) return false; } } return true; }}Dry RunInputnums = [1,3,3,2]Step 1 – Find MaximumMaximum element:3So:n = 3Step 2 – Length CheckExpected length:n + 1 = 4Actual length:4Valid.Step 3 – Frequency CountFrequency map:NumberCount112132Step 4 – Validate ConditionsNumbers 1 and 2 appear once ✅Number 3 appears twice ✅Return:trueEdge CasesCase 1[1]Invalid because:base[1] = [1,1]Case 2[1,1]Valid.Case 3[1,2,2]Invalid because:n = 2Expected:[1,2,2]Actually valid.Case 4[3,4,4,1,2,1]Invalid because:length != max + 1Optimized Alternative Using SortingAnother clean solution:Sort arrayVerify:nums[i] == i + 1for all except last.Last two elements should be equal.Java Sorting Solutionclass Solution { public boolean isGood(int[] nums) { Arrays.sort(nums); int n = nums.length - 1; for(int i = 0; i < n; i++) { if(nums[i] != i + 1) return false; } return nums[n] == n; }}Time Complexity AnalysisHashMap SolutionTime ComplexityO(N)Space ComplexityO(N)Sorting SolutionTime ComplexityO(N log N)Space ComplexityO(1)excluding sorting overhead.HashMap vs SortingApproachTime ComplexitySpace ComplexityHashMapO(N)O(N)SortingO(N log N)O(1)Interview ExplanationIn interviews, explain:A good array must follow the exact pattern [1,2,3,...,n,n]. The maximum element determines n, and frequency counting helps verify whether all required numbers appear correctly.This demonstrates strong understanding of:Frequency countingValidation logicEdge case handlingCommon Mistakes1. Forgetting Length CheckAlways verify:length == max + 12. Ignoring Missing NumbersArray must contain:1 to ncompletely.3. Wrong Frequency ValidationOnly maximum element should appear twice.All others must appear once.FAQsQ1. Why does maximum element determine n?Because:base[n]always ends with:n,nQ2. Why should array size be n + 1?Because:1 to n-1 => n-1 elementsn repeated twice => 2 elementsTotal = n+1Q3. Which approach is better?HashMap solution is faster.Sorting solution is simpler.Q4. Is this problem important for interviews?Yes.It tests:HashingValidation logicEdge case thinkingRelated ProblemsAfter mastering this problem, practice:Contains DuplicateFind All Duplicates in an ArrayValid AnagramConclusionLeetCode 2784 is a great beginner-friendly hashing problem.It teaches:Frequency countingValidation logicHashMap usageEdge case handlingThe key insight is:A good array must exactly match the structure [1,2,3,...,n,n].Once you understand this pattern, the problem becomes straightforward and easy to implement.

LeetCodeJavaHashMapArrayFrequency CountEasy

LeetCode 41: First Missing Positive – O(n) Time and O(1) Space Java Solution

IntroductionFinding the smallest positive integer missing from an unsorted array appears simple at first, but the problem becomes significantly more interesting because of its strict constraints.Problem Link -: First Missing PositiveGiven an unsorted integer array nums, the task is to return the smallest positive integer that does not appear in the array.For example:nums = [1,2,0]The positive integers begin with:1, 2, 3, 4, ...Both 1 and 2 are present, while 3 is missing.Therefore, the answer is:3The challenge is that the solution must run in:O(n) timeO(1) auxiliary spaceThis rules out several common approaches such as sorting and using a HashSet.Problem StatementGiven an unsorted integer array nums, return the smallest positive integer that is not present in the array.ExampleInput: nums = [3,4,-1,1]Output: 2The positive integers are:1, 2, 3, 4, ...1 exists in the array, but 2 does not.Therefore:Answer = 2Another example:Input: nums = [7,8,9,11,12]Output: 1Since 1 itself is missing, the answer is immediately:1Understanding the Important ObservationFor an array of length n, the answer can never be greater than:n + 1Consider:nums = [1,2,3]The first three positive integers are present:1, 2, 3Therefore, the smallest missing positive integer is:4Since n = 3:answer <= n + 1This observation is the key to the optimal solution.Numbers that are:<= 0or> ncannot directly determine the smallest missing positive number.The useful values are only:1 ... nThe Submitted HashSet ApproachA straightforward approach is to store every value in a HashSet and then search for the first missing positive integer.The basic idea is:Store all numbers ↓Check 1 ↓Check 2 ↓Check 3 ↓...The submitted implementation follows this idea:class Solution { public int firstMissingPositive(int[] nums) { int max = Integer.MIN_VALUE; HashSet<Integer> ms = new HashSet<>(); for (int a : nums) { max = Math.max(a, max); ms.add(a); } for (int i = 1; i <= max; i++) { if (!ms.contains(i)) { return i; } } if (max < 0) { return 1; } return max + 1; }}This approach is logically valid for finding the answer, but it does not satisfy the required constraints.Space ComplexityThe HashSet can store up to n elements.Therefore:O(n) auxiliary spaceThe problem requires:O(1) auxiliary spaceSo a different technique is required.Why Sorting Is Also Not EnoughSorting the array might appear to solve the problem easily.For example:[3,4,-1,1]After sorting:[-1,1,3,4]The missing positive integer can then be identified by scanning the array.However, sorting requires:O(n log n)time in the general case.The problem specifically requires:O(n)time.Therefore, sorting does not satisfy the required complexity either.The Core Idea: Put Every Number in Its Correct PositionThe optimal solution uses an in-place cyclic placement technique.The important relationship is:value 1 → index 0value 2 → index 1value 3 → index 2value 4 → index 3...In general:value x → index x - 1Consider:nums = [3,4,-1,1]The desired arrangement for useful values is:index: 0 1 2 3value: 1 2 3 4After placing the valid values into their corresponding positions, the array can become:[1, -1, 3, 4]Index 1 should contain:2but it contains -1.Therefore:answer = index + 1 = 1 + 1 = 2This transforms the problem from:Search for a missing number.into:Place every useful number at the position where it belongs, then find the first incorrect position.Which Numbers Should Be Placed?For an array of length n, only values satisfying:1 <= nums[i] <= nneed to be placed.Why?Suppose:n = 5The answer can only be one of:1,2,3,4,5,6A value such as:-4cannot be the answer.Similarly:10cannot prevent 1...6 from determining the answer.Therefore, values outside the range [1,n] can safely remain where they are.The Cyclic Placement ProcessFor every index i, check the current value:nums[i]If it belongs to the range:1 <= nums[i] <= nits correct index is:nums[i] - 1So the value should be swapped into:nums[nums[i] - 1]The process continues until the current position contains a value that either:is outside the useful range, oris already in its correct position.Why the Duplicate Check Is NecessaryConsider:nums = [1,1]The value 1 belongs at index 0.The first element is already correct.At index 1, the value is again 1.Trying to swap it repeatedly would cause an infinite loop because another 1 already occupies its correct position.Therefore, the swap condition must also ensure:nums[nums[i] - 1] != nums[i]This duplicate check is extremely important.Optimized Java Solutionclass Solution { public int firstMissingPositive(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { while ( nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i] ) { int correctIndex = nums[i] - 1; int temp = nums[i]; nums[i] = nums[correctIndex]; nums[correctIndex] = temp; } } for (int i = 0; i < n; i++) { if (nums[i] != i + 1) { return i + 1; } } return n + 1; }}Dry RunConsider:nums = [3,4,-1,1]Array length:n = 4Initial Array[3, 4, -1, 1]At index 0:nums[0] = 3The correct index for 3 is:3 - 1 = 2Swap:[3, 4, -1, 1] ↓[-1, 4, 3, 1]The value at index 0 is now -1.Since -1 is outside [1,4], no further placement is required for this index.At index 1:nums[1] = 4Correct index:4 - 1 = 3Swap:[-1, 4, 3, 1] ↓[-1, 1, 3, 4]Now:nums[1] = 1The correct index of 1 is 0.Swap:[-1, 1, 3, 4] ↓[1, -1, 3, 4]Now index 1 contains -1, so placement stops.Final Arrangement[1, -1, 3, 4]The expected value at each index is:index 0 → 1 ✓index 1 → 2 ✗index 2 → 3 ✓index 3 → 4 ✓The first incorrect position is:index = 1Therefore:answer = index + 1 = 2Another ExampleConsider:nums = [1,2,0]The values 1 and 2 are already in their correct positions:[1,2,0]Expected arrangement:index 0 → 1 ✓index 1 → 2 ✓index 2 → 3 ✗The first incorrect position is index 2.Therefore:answer = 2 + 1 = 3Edge Case: All Positive Numbers Are PresentConsider:nums = [1,2,3]Every position contains the expected value:index 0 → 1index 1 → 2index 2 → 3No missing value exists between 1 and n.Therefore, the smallest missing positive integer is:n + 1So:answer = 4Edge Case: The Answer Is 1Consider:nums = [7,8,9,11,12]All values are greater than 1.After the placement phase, there is no 1 at index 0.Therefore:answer = 1Complexity AnalysisThe algorithm uses the array itself to store values in their correct positions.Time ComplexityAlthough the algorithm contains a nested while loop, the total number of swaps is bounded by O(n) because every successful swap places a useful value into its correct position.Therefore:Time Complexity: O(n)Space ComplexityNo additional data structure proportional to the input size is used.Only a few variables are required:Space Complexity: O(1)This satisfies the required constraints.Why the Algorithm WorksThe central invariant is:Whenever a value x lies in the range [1,n], the algorithm attempts to place it at index x-1.After the placement phase, every value that can occupy a meaningful position is either:at its correct indexorabsent from the arrayTherefore, scanning from left to right provides a direct answer.If:nums[i] != i + 1then i + 1 is missing.If every position is correct, then all values from:1 ... nexist, making:n + 1the smallest missing positive integer.Interview InsightThis problem is an important example of in-place array positioning.The key pattern is:Value x ↓Correct index = x - 1Whenever an array problem asks for a missing, duplicate, or misplaced number within a known range, it is worth checking whether the values themselves can be mapped directly to indices.This technique appears in several interview problems involving:Missing numbersDuplicate numbersCyclic sortIn-place rearrangementFrequency representation without extra memoryThe biggest clue in this problem is the combination of:Unsorted array+O(n) time+O(1) space+Positive integersThat combination strongly suggests an in-place index/value mapping strategy.ConclusionLeetCode 41, First Missing Positive, is a classic example of turning the array itself into auxiliary storage.A HashSet provides an easy solution but requires O(n) extra space. Sorting simplifies the search but requires O(n log n) time. The optimal solution instead uses the relationship:value x → index x - 1to rearrange useful values directly inside the input array.After this placement, the first index whose value does not match index + 1 identifies the smallest missing positive integer.The final complexity is:O(n) timeO(1) auxiliary spacemaking the approach suitable for the strict constraints and an important pattern to recognize in technical interviews.

LeetCodeJavaArraysCyclic SortHardHashSet

LeetCode 1306: Jump Game III – Java DFS & Graph Traversal Solution Explained

IntroductionLeetCode 1306 – Jump Game III is an interesting graph traversal problem that combines:Depth First Search (DFS)Breadth First Search (BFS)RecursionVisited trackingCycle detectionAt first glance, this problem looks like an array problem.But internally, it behaves exactly like a graph traversal problem where:Each index acts like a nodeEach jump acts like an edgeThis problem is commonly asked in coding interviews because it tests:Recursive thinkingGraph traversal intuitionAvoiding infinite loopsState trackingProblem Link🔗 https://leetcode.com/problems/jump-game-iii/Problem StatementYou are given:An array arrA starting index startFrom index i, you can jump:i + arr[i]ori - arr[i]Your goal is to determine whether you can reach any index having value:0ExampleInputarr = [4,2,3,0,3,1,2]start = 5OutputtrueExplanationPossible path:5 → 4 → 1 → 3At index:3Value becomes:0So answer is:trueUnderstanding the ProblemThink of every index as a graph node.From each node:index iwe have two possible edges:i + arr[i]andi - arr[i]The goal is simply:Can we reach any node containing value 0?Brute Force IntuitionA naive recursive solution would:Try both forward and backward jumpsContinue recursivelyStop when we find zeroWhy Brute Force FailsWithout tracking visited indices, recursion may enter infinite loops.Example:1 → 3 → 1 → 3 → 1...This creates cycles.So we must track visited nodes.DFS IntuitionWe perform DFS traversal from the starting index.At every index:Check boundariesCheck if already visitedCheck if value is zeroExplore both possible jumpsKey DFS ObservationEach index should only be visited once.Why?Because revisiting creates cycles and unnecessary computation.So we use:HashSet<Integer> visitedorboolean[] visitedRecursive DFS ApproachSteps1. Boundary CheckIf index goes outside array:return false2. Visited CheckIf already visited:return false3. Found ZeroIf current index contains:0Return:true4. Explore Both DirectionsTry:start + arr[start]andstart - arr[start]Java DFS Solutionclass Solution { public boolean solve(HashSet<Integer> zeroIndexes, HashSet<Integer> visited, int start, int[] arr) { if(start >= arr.length || start < 0) return false; if(visited.contains(start)) return false; visited.add(start); if(zeroIndexes.contains(start)) return true; return solve(zeroIndexes, visited, start + arr[start], arr) || solve(zeroIndexes, visited, start - arr[start], arr); } public boolean canReach(int[] arr, int start) { HashSet<Integer> visited = new HashSet<>(); HashSet<Integer> zeroIndexes = new HashSet<>(); for(int i = 0; i < arr.length; i++) { if(arr[i] == 0) { zeroIndexes.add(i); } } return solve(zeroIndexes, visited, start, arr); }}Simpler Optimized DFS SolutionWe actually do not need a separate set for zero indexes.We can directly check:arr[start] == 0Cleaner Java DFS Solutionclass Solution { public boolean dfs(int[] arr, boolean[] visited, int start) { if(start < 0 || start >= arr.length) return false; if(visited[start]) return false; if(arr[start] == 0) return true; visited[start] = true; return dfs(arr, visited, start + arr[start]) || dfs(arr, visited, start - arr[start]); } public boolean canReach(int[] arr, int start) { return dfs(arr, new boolean[arr.length], start); }}Dry RunInputarr = [4,2,3,0,3,1,2]start = 5Step 1Current index:5Value:1Possible jumps:5 + 1 = 65 - 1 = 4Step 2Visit index:4Value:3Possible jumps:4 + 3 = 7 (invalid)4 - 3 = 1Step 3Visit index:1Value:2Possible jumps:1 + 2 = 31 - 2 = -1 (invalid)Step 4Visit index:3Value:0Return:trueBFS ApproachThis problem can also be solved using BFS.Instead of recursion:Use queueExplore neighbors level by levelJava BFS Solutionclass Solution { public boolean canReach(int[] arr, int start) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[arr.length]; queue.offer(start); while(!queue.isEmpty()) { int index = queue.poll(); if(index < 0 || index >= arr.length) continue; if(visited[index]) continue; if(arr[index] == 0) return true; visited[index] = true; queue.offer(index + arr[index]); queue.offer(index - arr[index]); } return false; }}Time Complexity AnalysisDFS ComplexityTime ComplexityO(N)Each index is visited at most once.Space ComplexityO(N)Due to recursion stack and visited array.BFS ComplexityTime ComplexityO(N)Space ComplexityO(N)DFS vs BFSApproachAdvantagesDisadvantagesDFSSimple recursive logicRecursion stackBFSIterative solutionQueue managementInterview ExplanationIn interviews, explain:This problem behaves like graph traversal where each index acts as a node and jumps act as edges. We use DFS or BFS with visited tracking to avoid infinite cycles.This demonstrates strong graph intuition.Common Mistakes1. Forgetting Visited TrackingThis causes infinite recursion.2. Missing Boundary ChecksAlways check:start < 0 || start >= arr.length3. Revisiting NodesAvoid processing already visited indices.FAQsQ1. Is this an array problem or graph problem?Internally it is a graph traversal problem.Q2. Which is better: DFS or BFS?Both are valid.DFS is usually simpler for this problem.Q3. Why do we need visited tracking?To avoid infinite loops caused by cycles.Q4. Can this be solved greedily?No.Because multiple paths must be explored.ConclusionLeetCode 1306 is an excellent beginner-friendly graph traversal problem.It teaches:DFS traversalBFS traversalCycle detectionRecursive thinkingVisited state managementThe most important insight is:Treat every index as a graph node.Once you understand this idea, many graph and traversal interview problems become much easier.

LeetCodeMediumDFSBFSGraph TraversalJavaRecursion

LeetCode 88 Merge Sorted Array Explained: Brute Force to Optimal Java Solution (3 Pointer Approach)

IntroductionLeetCode 88 — Merge Sorted Array is one of the most important beginner-friendly array problems asked in coding interviews.At first glance, the problem looks very easy because both arrays are already sorted. But the real challenge is:How do we merge them efficiently without using extra space?This question is commonly asked by companies because it tests:Array manipulationTwo pointer techniqueIn-place modificationEdge case handlingSpace optimizationThe most important learning from this problem is understanding:Why merging from the back is the optimal strategy.In this article, we will cover:Problem understandingBrute force approachBetter approachOptimal 3-pointer solutionStep-by-step dry runTime & space complexityCommon mistakesInterview tipsFAQsBy the end, you will completely understand the logic behind this problem.Try This Problem👉 https://leetcode.com/problems/merge-sorted-array/Problem StatementYou are given two sorted arrays:nums1nums2Along with two integers:m → valid elements in nums1n → elements in nums2The array nums1 has size:m + nThe last n positions are empty spaces represented by 0.Your task is to merge nums2 into nums1 such that the final array remains sorted.ExampleExample 1Inputnums1 = [1,2,3,0,0,0]m = 3nums2 = [2,5,6]n = 3Output[1,2,2,3,5,6]Understanding the ProblemLet us simplify what the question is asking.We have:nums1 → already sortednums2 → already sortedWe need:one final sorted arrayBut there is one important condition:We must store the answer inside nums1 itself.That means:No returning new arrayModify nums1 directlyWhy This Problem is TrickyMany beginners immediately think:Copy nums2 into nums1Then sort nums1This works.But interviews usually expect a more optimized solution.The challenge is:Can we merge without sorting again?Yes — using the Two Pointer technique.Approach 1 — Brute Force SolutionIdeaCopy all elements of nums2 into empty positions of nums1Sort the final arrayJava Codeclass Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { // Copy nums2 into nums1 for(int i = 0; i < n; i++) { nums1[m + i] = nums2[i]; } // Sort final array Arrays.sort(nums1); }}Dry Run of Brute ForceInitial:nums1 = [1,2,3,0,0,0]nums2 = [2,5,6]After copying:[1,2,3,2,5,6]After sorting:[1,2,2,3,5,6]Time ComplexityCopyingO(n)SortingO((m+n) log(m+n))Space ComplexityO(1)Drawback of Brute ForceSorting again is unnecessary because:Arrays are already sortedWe can merge smarterApproach 2 — Extra Array MergeIdeaUse a third temporary array.This works exactly like merge step in Merge Sort.StepsCompare elements from both arraysInsert smaller one into temp arrayCopy final temp array into nums1Java Codeclass Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] temp = new int[m + n]; int i = 0; int j = 0; int k = 0; while(i < m && j < n) { if(nums1[i] <= nums2[j]) { temp[k++] = nums1[i++]; } else { temp[k++] = nums2[j++]; } } while(i < m) { temp[k++] = nums1[i++]; } while(j < n) { temp[k++] = nums2[j++]; } for(i = 0; i < m + n; i++) { nums1[i] = temp[i]; } }}Time ComplexityO(m + n)Space ComplexityO(m + n)Can We Do Better?Yes.The interview-expected solution uses:Optimal Approach — Three Pointers from BackMost Important ObservationThe end of nums1 already contains empty spaces.So instead of merging from front:We merge from the back.This avoids overwriting important elements.Main IdeaWe use 3 pointers:left → last valid element in nums1right → last element in nums2insertPos → last position of nums1We compare:nums1[left]nums2[right]The larger element is placed at:nums1[insertPos]Then move pointers backward.Why Backward Merging WorksSuppose:nums1 = [1,2,3,0,0,0]nums2 = [2,5,6]If we start from front:we overwrite existing valuesBut from back:empty spaces already existSo no data loss occurs.Optimal Java Solutionclass Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int left = m - 1; int right = n - 1; int insertPos = m + n - 1; for(int i = insertPos; i >= 0; i--) { if(right < 0 || (left >= 0 && nums1[left] >= nums2[right])) { nums1[i] = nums1[left]; left--; } else { nums1[i] = nums2[right]; right--; } } }}Step-by-Step Dry RunInputnums1 = [1,2,3,0,0,0]nums2 = [2,5,6]Initial Pointersleft = 2 → value 3right = 2 → value 6insertPos = 5Step 1Compare:3 vs 66 is larger.Place 6 at end.[1,2,3,0,0,6]Move:right--insertPos--Step 2Compare:3 vs 5Place 5.[1,2,3,0,5,6]Step 3Compare:3 vs 2Place 3.[1,2,3,3,5,6]Step 4Compare:2 vs 2Place 2.[1,2,2,3,5,6]Done.Time ComplexityWe traverse both arrays once.O(m + n)Space ComplexityNo extra space used.O(1)Why This is the Best SolutionThis solution is optimal because:✅ No sorting required ✅ No extra array required ✅ Single traversal ✅ In-place merging ✅ Interview preferred solutionCommon Mistakes1. Merging from FrontThis overwrites elements in nums1.2. Forgetting Edge CasesExample:m = 0orn = 03. Wrong Pointer InitializationCorrect:left = m - 1right = n - 14. Array Index Out of BoundsAlways check:left >= 0right >= 0Interview TipsIf interviewer asks:“Why merge from back?”Your answer:Because nums1 already has empty spaces at the end. Backward traversal prevents overwriting existing sorted elements.Frequently Asked QuestionsQ1. Why not use sorting?Because arrays are already sorted.Sorting again wastes time.Q2. Why start from end?To safely place larger elements without overwriting.Q3. Is this similar to Merge Sort?Yes.This is essentially the merge step of Merge Sort.Q4. What if nums2 is empty?Then nums1 remains unchanged.Q5. What if nums1 has no valid elements?Then copy all elements from nums2.Final TakeawayThe biggest learning from this problem is:Whenever extra space exists at the end of an array, think about backward traversal.This pattern appears frequently in interview questions.ConclusionLeetCode 88 is one of the best beginner problems to master:Two pointersIn-place array modificationEfficient mergingSpace optimizationAlthough the brute force solution works, the optimal 3-pointer approach is the real interview solution.Once you understand why backward merging works, this problem becomes extremely easy to solve in interviews and coding rounds.

ArraysTwo PointersSortingJavaEasyLeetcode

Count the Number of Good Subarrays – Apple OA DSA Problem & Java Solution

IntroductionThis is an interesting question asked in the Apple OA because the condition is slightly different from the usual subarray problems.Instead of asking whether a subarray itself satisfies some property, the task is to remove a subarray and check whether the elements left behind are strictly increasing.The challenge is to count every possible contiguous subarray whose removal leaves a strictly increasing sequence.With n as large as 10⁵, a direct brute-force solution becomes extremely expensive, making this a good problem for thinking about how the structure of the array can be exploited.Problem StatementGiven an integer array arr of size n, find the number of good subarrays.A subarray arr[l...r] is called good if, after removing all elements from index l through r, the remaining elements form a strictly increasing array.In other words, after removing:arr[l], arr[l+1], ..., arr[r]the elements before l and after r are joined together.The resulting array must satisfy:remaining[i] < remaining[i + 1]for every pair of adjacent elements.Constraints1 ≤ n ≤ 10⁵-10⁹ ≤ arr[i] ≤ 10⁹ExampleConsider:arr = [1, 2, 3, 4, 0, 5]There are 10 good subarrays.Some valid removals are:[0][0, 5][4, 0][4, 0, 5][3, 4, 0][3, 4, 0, 5][2, 3, 4, 0][2, 3, 4, 0, 5][1, 2, 3, 4, 0][1, 2, 3, 4]For example, removing:[3, 4, 0]from:[1, 2, 3, 4, 0, 5]leaves:[1, 2, 5]which is strictly increasing.Therefore, [3,4,0] is a good subarray.Similarly, removing:[0,5]leaves:[1,2,3,4]which is also strictly increasing.Hence:Answer = 10Key ObservationThe array:[1, 2, 3, 4, 0, 5]is already strictly increasing except around:4 → 0Removing a suitable contiguous section containing this problematic portion can reconnect two increasing parts.For example:[1, 2, 3, 4] [0, 5]Removing [0] gives:[1, 2, 3, 4, 5]Removing [4,0] gives:[1, 2, 3, 5]Removing [3,4,0] gives:[1, 2, 5]The important condition is therefore not just whether the removed part is valid. The remaining left and right portions must also connect correctly.Brute-Force Backtracking ApproachA straightforward way to explore the problem is to generate possible selections of indices using recursion.The recursive function maintains:currwhich contains the indices currently selected for removal.For every index, there are two choices:Include the index in the selected set.Do not include the index.Once a selection is created, the ch2() function removes those selected positions and checks whether the remaining array is strictly increasing.A HashSet is also used to avoid counting the same index selection more than once.Checking a CandidateThe ch2() function performs the validation.It first creates an array containing the elements that were not selected for removal.For example:Original:[1, 2, 3, 4, 0, 5]Selected indices:[2, 3, 4]Remaining:[1, 2, 5]Then the remaining array is scanned.If any adjacent pair violates:arr[i] < arr[i + 1]the candidate is rejected.Otherwise, it is considered good.Java SolutionThe following is the provided recursive implementation, with comments added to make the logic easier to follow.public class question {// Stores already counted selections.static int an = 0;static HashSet<List<Integer>> msl = new HashSet<>();// Checks whether removing the selected indices// leaves a strictly increasing array.public static boolean ch2(List<Integer> lis, int[] arr) {// No selected elements means nothing is removed.if (lis.size() == 0) {return false;}// If the entire array is removed,// this implementation does not count it.int[] dum = new int[arr.length - lis.size()];if (dum.length == 0) {return false;}// Store the selected indices.HashSet<Integer> ms = new HashSet<>();for (int a : lis) {ms.add(a);}int c = 0;// Construct the remaining array.for (int i = 0; i < arr.length; i++) {// Keep only indices that were not selected.if (!ms.contains(i)) {dum[c] = arr[i];c++;}}// Check whether the remaining array// is strictly increasing.for (int i = 0; i < dum.length - 1; i++) {if (dum[i] > dum[i + 1]) {return false;}}return true;}public static void main(String[] args) {int[] arr = {1, 2, 3, 4, 0, 5};List<Integer> lis = new ArrayList<>();if (arr.length == 1) {System.out.println(1);}// Explore both possibilities for the first index.sol2(arr, 0, lis, true);sol2(arr, 0, lis, false);System.out.println(an);}// Generates different selections using recursion.public static void sol2(int[] arr,int ind,List<Integer> lis,boolean boo) {// All indices have been processed.if (ind == arr.length) {// Check whether this selection is good// and has not already been counted.if (!msl.contains(lis) && ch2(lis, arr)) {an++;// Store a copy because the original list// continues changing during backtracking.msl.add(new ArrayList<>(lis));System.out.println(lis);}return;}// Check the current selection as well.if (!msl.contains(lis) && ch2(lis, arr)) {an++;msl.add(new ArrayList<>(lis));System.out.println(lis);}// Include the current index.if (boo) {lis.add(ind);}// Continue recursively.sol2(arr, ind + 1, lis, true);// Backtrack and remove the last selected index.if (lis.size() != 0) {lis.remove(lis.size() - 1);}// Explore the branch where the current index// is not selected.sol2(arr, ind + 1, lis, false);}}Dry RunFor:[1, 2, 3, 4, 0, 5]Suppose the selected indices are:[4]Index 4 contains 0.Removing it gives:[1, 2, 3, 4, 5]This is strictly increasing.Therefore:[0]is counted.Now consider:[3, 4]Removing indices 2 and 3 gives:[1, 2, 0, 5]Since:2 > 0the remaining array is not increasing.Therefore, this candidate is rejected.Another candidate:[2, 3, 4]removes:[3, 4, 0]and leaves:[1, 2, 5]which is strictly increasing.So this candidate is counted.The recursion continues until all possible selections have been explored.Important Detail: Subarray vs SubsetThere is an important distinction worth understanding when reviewing this implementation.The problem asks for a subarray, which means the removed elements must be contiguous.For example:[2, 3, 4]is a subarray.But:[2, 4]is not a subarray if the original array contains another element between them.The recursive code, however, chooses individual indices independently. Therefore, it explores subsets of indices rather than explicitly restricting the selection to contiguous ranges.This is an important conceptual difference.For a production or interview solution, the recursion should be changed to work directly with:left indexright indexso that only contiguous removals are considered.Why This Approach Is Not Suitable for n = 10⁵For every index, the recursion can make two choices:includeexcludeThis creates approximately:2ⁿpossible selections.Furthermore, each candidate is checked by constructing another array and scanning it.Therefore, the brute-force approach grows exponentially and cannot handle:n = 100000efficiently.This makes the problem much more interesting: the real challenge is finding the structure that allows the count to be obtained without examining every possible subarray individually.Toward an Optimized SolutionA useful way to analyze the problem is to split the remaining array into two parts.After removing arr[l...r], the remaining array is:arr[0...l-1] + arr[r+1...n-1]For this combined array to be strictly increasing, three things must be true:Left part must be increasingarr[0...l-1]must already be strictly increasing.Right part must be increasingarr[r+1...n-1]must already be strictly increasing.The two parts must connectIf both parts exist:arr[l-1] < arr[r+1]must hold.This observation removes the need to construct the remaining array for every candidate.The Main PatternThe problem can therefore be viewed as:Increasing Prefix|| removed subarray↓Increasing SuffixThe only difficult part is determining whether the last element of the prefix can connect to the first element of the suffix.This is the key observation that leads from brute force toward an efficient two-pointer/prefix-suffix based solution.Complexity of the Provided SolutionThe recursive generation can explore up to:O(2ⁿ)different index selections.For every candidate, ch2() may also scan the entire array.Therefore, the overall worst-case complexity is approximately:O(n × 2ⁿ)with substantial additional memory for the recursion and stored selections.This is only practical for very small arrays and should be considered a brute-force exploration, not a solution for the stated n = 10⁵ constraint.Interview TakeawayThis problem teaches an important DSA lesson:Before optimizing code, identify exactly what the problem is asking for.There is a significant difference between:subsetand:subarrayA subset can select arbitrary indices, while a subarray must be contiguous.Once the problem is represented correctly, the next question becomes:What must be true about the array remaining after removing [l...r]?That leads directly to the prefix/suffix observation:Left side increasing+Right side increasing+Left boundary < Right boundaryThis type of transformation is often much more valuable in an OA than trying to optimize an exponential recursion line by line.ConclusionThis Apple OA-style problem combines subarray reasoning, recursion, and array properties in an interesting way.The provided solution takes a brute-force route by recursively exploring possible index selections and checking whether the remaining elements form a strictly increasing sequence.Although this approach is useful for understanding the problem and verifying small test cases, the constraint of 10⁵ requires a much more efficient strategy.The major insight is to stop thinking about the removed portion itself and instead analyze the increasing prefix and increasing suffix that remain after the removal.That shift in perspective turns an exponential search problem into one that can be approached using prefix/suffix preprocessing and two-pointer techniques.

Apple OAArraysSubarraysRecursionBacktrackingHashSetBrute ForceJavaContignous Array

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

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

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

GeeksForGeeksEasyBinary SearchSorted Array

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

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

Binary SearchLeetCodeMedium

LeetCode 1732: Find the Highest Altitude – Java Prefix Sum Solution Explained

IntroductionLeetCode 1732, Find the Highest Altitude, is a simple yet important problem that introduces the concept of Prefix Sums (Running Sums).The problem simulates a biker traveling through different points on a road trip. Instead of directly providing the altitude at each point, we're given the altitude gain or loss between consecutive points.Our task is to determine the highest altitude reached during the journey.Although this is an Easy-level problem, it teaches a fundamental technique frequently used in array and cumulative sum problems.Problem Link -: Find the Highest AltitudeProblem StatementA biker starts at altitude:0You are given an array:gain[i]where:gain[i]represents the change in altitude between point i and point i + 1.Return the highest altitude reached during the entire trip.Example 1Inputgain = [-5,1,5,0,-7]Altitude CalculationStart = 00 + (-5) = -5-5 + 1 = -4-4 + 5 = 11 + 0 = 11 + (-7) = -6Altitudes:[0, -5, -4, 1, 1, -6]Output1Example 2Inputgain = [-4,-3,-2,-1,4,3,2]Altitudes[0,-4,-7,-9,-10,-6,-3,-1]Output0The biker never goes above the starting altitude.Key ObservationWe are not required to store all altitudes.Instead:Keep track of the current altitude.Update it using each gain value.Continuously track the maximum altitude seen so far.This allows us to solve the problem in a single traversal.Understanding the Prefix Sum ApproachSuppose:gain = [-5,1,5,0,-7]Initialize:currentAltitude = 0maxAltitude = 0Process each value:GainCurrent AltitudeMaximum Altitude-5-501-40511011-7-61Final answer:1Java Solutionclass Solution { public int largestAltitude(int[] gain) { int max = 0; int altitude = 0; for (int value : gain) { altitude += value; max = Math.max(max, altitude); } return max; }}Dry RunInputgain = [-5,1,5,0,-7]Initial Statealtitude = 0max = 0Step 1altitude += -5Result:altitude = -5max = 0Step 2altitude += 1Result:altitude = -4max = 0Step 3altitude += 5Result:altitude = 1max = 1Step 4altitude += 0Result:altitude = 1max = 1Step 5altitude += -7Result:altitude = -6max = 1Final Answer1Alternative Approach: Build Complete Altitude ArrayAnother way is to explicitly construct all altitudes.class Solution { public int largestAltitude(int[] gain) { int[] altitude = new int[gain.length + 1]; int max = 0; for (int i = 1; i < altitude.length; i++) { altitude[i] = altitude[i - 1] + gain[i - 1]; max = Math.max(max, altitude[i]); } return max; }}Why This Is Less OptimalRequires extra memory.Stores values we don't actually need.Same time complexity but worse space complexity.Optimized Approach (Recommended)Instead of storing every altitude:Maintain a running altitude.Update the maximum altitude immediately.Benefits:Single pass.Constant extra memory.Cleaner implementation.Complexity AnalysisTime ComplexityO(n)We traverse the array exactly once.Space ComplexityO(1)Only a few variables are used.Common MistakesMistake 1: Forgetting the Starting AltitudeThe biker starts at:0This altitude must be considered when finding the maximum.Example:gain = [-4,-3,-2]Highest altitude:0not:-4Mistake 2: Using Only Individual Gain ValuesSome beginners try:max = Math.max(max, gain[i]);This is incorrect.The altitude depends on the cumulative sum, not a single gain value.Mistake 3: Building Unnecessary ArraysCreating an altitude array works but wastes memory.A running sum is sufficient.Why This Problem MattersThis problem introduces:Prefix Sum fundamentalsRunning Sum techniquesCumulative calculationsMaximum tracking patternsThese concepts frequently appear in:Array problemsDynamic ProgrammingSliding Window problemsFinancial data calculationsPath and graph simulationsMastering this pattern helps solve many more advanced interview questions.Key TakeawaysStart altitude is always 0.Each gain modifies the current altitude.Use a running sum to calculate altitude.Track the maximum altitude during traversal.No extra array is required.Optimal solution runs in O(n) time and O(1) space.ConclusionLeetCode 1732: Find the Highest Altitude is a classic running-sum problem that demonstrates how cumulative calculations can be performed efficiently without storing unnecessary data.By maintaining the current altitude and continuously updating the highest altitude encountered, we obtain a clean and optimal solution that runs in linear time with constant space.While the problem is straightforward, the underlying prefix-sum concept is extremely important and appears repeatedly in coding interviews and competitive programming.

LeetcodeJavaEasyPrefix Sum

Recursion in Java - Complete Guide With Examples and Practice Problems

IntroductionIf there is one topic in programming that confuses beginners more than anything else, it is recursion. Most people read the definition, nod their head, and then immediately freeze when they have to write recursive code themselves.The problem is not that recursion is genuinely hard. The problem is that most explanations start with code before building the right mental model. Once you have the right mental model, recursion clicks permanently and you start seeing it everywhere — in tree problems, graph problems, backtracking, dynamic programming, divide and conquer, and more.This guide covers everything from the ground up. What recursion is, how the call stack works, how to identify base cases and recursive cases, every type of recursion, common patterns, time and space complexity analysis, the most common mistakes, and the top LeetCode problems to practice.By the end of this article, recursion will not feel like magic anymore. It will feel like a natural tool you reach for confidently.What Is Recursion?Recursion is when a function calls itself to solve a smaller version of the same problem.That is the complete definition. But let us make it concrete.Imagine you want to count down from 5 to 1. One way is a loop. Another way is — print 5, then solve the exact same problem for counting down from 4 to 1. Then print 4, solve for 3. And so on until you reach the base — there is nothing left to count down.void countDown(int n) { if (n == 0) return; // stop here System.out.println(n); countDown(n - 1); // solve the smaller version}The function countDown calls itself with a smaller input each time. Eventually it reaches 0 and stops. That stopping condition is the most important part of any recursive function — the base case.The Two Parts Every Recursive Function Must HaveEvery correctly written recursive function has exactly two parts. Without both, the function either gives wrong answers or runs forever.Part 1: Base CaseThe base case is the condition under which the function stops calling itself and returns a direct answer. It is the smallest version of the problem that you can solve without any further recursion.Without a base case, recursion never stops and you get a StackOverflowError — Java's way of telling you the call stack ran out of memory.Part 2: Recursive CaseThe recursive case is where the function calls itself with a smaller or simpler input — moving closer to the base case with each call. If your recursive case does not make the problem smaller, you have an infinite loop.Think of it like a staircase. The base case is the ground floor. The recursive case is each step going down. Every step must genuinely bring you one level closer to the ground.How Recursion Works — The Call StackThis is the mental model that most explanations skip, and it is the reason recursion confuses people.Every time a function is called in Java, a new stack frame is created and pushed onto the call stack. This frame stores the function's local variables, parameters, and where to return to when the function finishes.When a recursive function calls itself, a new frame is pushed on top. When that call finishes, its frame is popped and execution returns to the previous frame.Let us trace countDown(3) through the call stack:countDown(3) called → frame pushed prints 3 calls countDown(2) → frame pushed prints 2 calls countDown(1) → frame pushed prints 1 calls countDown(0) → frame pushed n == 0, return → frame popped back in countDown(1), return → frame popped back in countDown(2), return → frame popped back in countDown(3), return → frame poppedOutput: 3, 2, 1The call stack grows as calls go deeper, then shrinks as calls return. This is why recursion uses O(n) space for n levels deep — each level occupies one stack frame in memory.Your First Real Recursive Function — FactorialFactorial is the classic first recursion example. n! = n × (n-1) × (n-2) × ... × 1Notice the pattern — n! = n × (n-1)!. The factorial of n is n times the factorial of n-1. That recursive structure makes it perfect for recursion.public int factorial(int n) { // base case if (n == 0 || n == 1) return 1; // recursive case return n * factorial(n - 1);}Dry Run — factorial(4)factorial(4)= 4 * factorial(3)= 4 * 3 * factorial(2)= 4 * 3 * 2 * factorial(1)= 4 * 3 * 2 * 1= 24The call stack builds up going in, then multiplications happen coming back out. This "coming back out" phase is called the return phase or unwinding of the stack.Time Complexity: O(n) — n recursive calls Space Complexity: O(n) — n frames on the call stackThe Two Phases of RecursionEvery recursive function has two phases and understanding both is critical.Phase 1: The Call Phase (Going In)This happens as the function keeps calling itself with smaller inputs. Things you do before the recursive call happen in this phase — in order from the outermost call to the innermost.Phase 2: The Return Phase (Coming Back Out)This happens as each call finishes and returns to its caller. Things you do after the recursive call happen in this phase — in reverse order, from the innermost call back to the outermost.This distinction explains why the output order can be surprising:void printBothPhases(int n) { if (n == 0) return; System.out.println("Going in: " + n); // call phase printBothPhases(n - 1); System.out.println("Coming out: " + n); // return phase}For printBothPhases(3):Going in: 3Going in: 2Going in: 1Coming out: 1Coming out: 2Coming out: 3This two-phase understanding is what makes problems like reversing a string or printing a linked list backwards via recursion feel natural.Types of RecursionRecursion is not one-size-fits-all. There are several distinct types and knowing which type applies to a problem shapes how you write the solution.1. Direct RecursionThe function calls itself directly. This is the most common type — what we have seen so far.void direct(int n) { if (n == 0) return; direct(n - 1); // calls itself}2. Indirect RecursionFunction A calls Function B which calls Function A. They form a cycle.void funcA(int n) { if (n <= 0) return; System.out.println("A: " + n); funcB(n - 1);}void funcB(int n) { if (n <= 0) return; System.out.println("B: " + n); funcA(n - 1);}Used in: state machines, mutual recursion in parsers, certain mathematical sequences.3. Tail RecursionThe recursive call is the last operation in the function. Nothing happens after the recursive call returns — no multiplication, no addition, nothing.// NOT tail recursive — multiplication happens after returnint factorial(int n) { if (n == 1) return 1; return n * factorial(n - 1); // multiply after return — not tail}// Tail recursive — recursive call is the last thingint factorialTail(int n, int accumulator) { if (n == 1) return accumulator; return factorialTail(n - 1, n * accumulator); // last operation}Why does tail recursion matter? In languages that support tail call optimization (like Scala, Kotlin, and many functional languages), tail recursive functions can be converted to iteration internally — no stack frame accumulation, O(1) space. Java does NOT perform tail call optimization, but understanding tail recursion is still important for interviews and functional programming concepts.4. Head RecursionThe recursive call happens first, before any other processing. All processing happens in the return phase.void headRecursion(int n) { if (n == 0) return; headRecursion(n - 1); // call first System.out.println(n); // process after}// Output: 1 2 3 4 5 (processes in reverse order of calls)5. Tree RecursionThe function makes more than one recursive call per invocation. This creates a tree of calls rather than a linear chain. Fibonacci is the classic example.int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); // TWO recursive calls}The call tree for fibonacci(4): fib(4) / \ fib(3) fib(2) / \ / \ fib(2) fib(1) fib(1) fib(0) / \ fib(1) fib(0)Time Complexity: O(2ⁿ) — exponential! Each call spawns two more. Space Complexity: O(n) — maximum depth of the call treeThis is why memoization (caching results) is so important for tree recursion — it converts O(2ⁿ) to O(n) by never recomputing the same subproblem twice.6. Mutual RecursionA specific form of indirect recursion where two functions call each other alternately to solve a problem. Different from indirect recursion in that the mutual calls are the core mechanism of the solution.// Check if a number is even or odd using mutual recursionboolean isEven(int n) { if (n == 0) return true; return isOdd(n - 1);}boolean isOdd(int n) { if (n == 0) return false; return isEven(n - 1);}Common Recursion Patterns in DSAThese are the patterns you will see over and over in interview problems. Recognizing them is more important than memorizing solutions.Pattern 1: Linear Recursion (Do Something, Recurse on Rest)Process the current element, then recurse on the remaining problem.// Sum of arrayint arraySum(int[] arr, int index) { if (index == arr.length) return 0; // base case return arr[index] + arraySum(arr, index + 1); // current + rest}Pattern 2: Divide and Conquer (Split Into Two Halves)Split the problem into two halves, solve each recursively, combine results.// Merge Sortvoid mergeSort(int[] arr, int left, int right) { if (left >= right) return; // base case — single element int mid = (left + right) / 2; mergeSort(arr, left, mid); // sort left half mergeSort(arr, mid + 1, right); // sort right half merge(arr, left, mid, right); // combine}Pattern 3: Backtracking (Try, Recurse, Undo)Try a choice, recurse to explore it, undo the choice when backtracking.// Generate all subsetsvoid subsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) { if (index == nums.length) { result.add(new ArrayList<>(current)); return; } // Choice 1: include nums[index] current.add(nums[index]); subsets(nums, index + 1, current, result); current.remove(current.size() - 1); // undo // Choice 2: exclude nums[index] subsets(nums, index + 1, current, result);}Pattern 4: Tree Recursion (Left, Right, Combine)Recurse on left subtree, recurse on right subtree, combine or process results.// Height of binary treeint height(TreeNode root) { if (root == null) return 0; // base case int leftHeight = height(root.left); // solve left int rightHeight = height(root.right); // solve right return 1 + Math.max(leftHeight, rightHeight); // combine}Pattern 5: Memoization (Cache Recursive Results)Store results of recursive calls so the same subproblem is never solved twice.Map<Integer, Integer> memo = new HashMap<>();int fibonacci(int n) { if (n <= 1) return n; if (memo.containsKey(n)) return memo.get(n); // return cached int result = fibonacci(n - 1) + fibonacci(n - 2); memo.put(n, result); // cache before returning return result;}This converts Fibonacci from O(2ⁿ) to O(n) time with O(n) space — a massive improvement.Recursion vs Iteration — When to Use WhichThis is one of the most common interview questions about recursion. Here is a clear breakdown:Use Recursion when:The problem has a naturally recursive structure (trees, graphs, divide and conquer)The solution is significantly cleaner and easier to understand recursivelyThe problem involves exploring multiple paths or choices (backtracking)The depth of recursion is manageable (not too deep to cause stack overflow)Use Iteration when:The problem is linear and a loop is equally clearMemory is a concern (iteration uses O(1) stack space vs O(n) for recursion)Performance is critical and function call overhead mattersJava's stack size limit could be hit (default around 500-1000 frames for deep recursion)The key rule: Every recursive solution can be converted to an iterative one (usually using an explicit stack). But recursive solutions for tree and graph problems are almost always cleaner to write and understand.Time and Space Complexity of Recursive FunctionsAnalyzing complexity for recursive functions requires a specific approach.The Recurrence Relation MethodExpress the time complexity as a recurrence relation and solve it.Factorial:T(n) = T(n-1) + O(1) = T(n-2) + O(1) + O(1) = T(1) + n×O(1) = O(n)Fibonacci (naive):T(n) = T(n-1) + T(n-2) + O(1) ≈ 2×T(n-1) = O(2ⁿ)Binary Search:T(n) = T(n/2) + O(1) = O(log n) [by Master Theorem]Merge Sort:T(n) = 2×T(n/2) + O(n) = O(n log n) [by Master Theorem]Space Complexity Rule for RecursionSpace complexity of a recursive function = maximum depth of the call stack × space per frameLinear recursion (factorial, sum): O(n) spaceBinary recursion (Fibonacci naive): O(n) space (maximum depth, not number of nodes)Divide and conquer (merge sort): O(log n) space (depth of recursion tree)Memoized Fibonacci: O(n) space (memo table + call stack)Classic Recursive Problems With SolutionsProblem 1: Reverse a StringString reverse(String s) { if (s.length() <= 1) return s; // base case // last char + reverse of everything before last char return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));}Dry run for "hello":reverse("hello") = 'o' + reverse("hell")reverse("hell") = 'l' + reverse("hel")reverse("hel") = 'l' + reverse("he")reverse("he") = 'e' + reverse("h")reverse("h") = "h"Unwinding: "h" → "he" → "leh" → "lleh" → "olleh" ✅Problem 2: Power Function (x^n)double power(double x, int n) { if (n == 0) return 1; // base case if (n < 0) return 1.0 / power(x, -n); // handle negative if (n % 2 == 0) { double half = power(x, n / 2); return half * half; // x^n = (x^(n/2))^2 } else { return x * power(x, n - 1); }}This is the fast power algorithm — O(log n) time instead of O(n).Problem 3: Fibonacci With Memoizationint[] memo = new int[100];Arrays.fill(memo, -1);int fib(int n) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fib(n - 1) + fib(n - 2); return memo[n];}Time: O(n) — each value computed once Space: O(n) — memo array + call stackProblem 4: Tower of HanoiThe classic recursion teaching problem. Move n disks from source to destination using a helper rod.void hanoi(int n, char source, char destination, char helper) { if (n == 1) { System.out.println("Move disk 1 from " + source + " to " + destination); return; } // Move n-1 disks from source to helper hanoi(n - 1, source, helper, destination); // Move the largest disk from source to destination System.out.println("Move disk " + n + " from " + source + " to " + destination); // Move n-1 disks from helper to destination hanoi(n - 1, helper, destination, source);}Time Complexity: O(2ⁿ) — minimum moves required is 2ⁿ - 1 Space Complexity: O(n) — call stack depthProblem 5: Generate All Subsets (Power Set)void generateSubsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) { result.add(new ArrayList<>(current)); // add current subset for (int i = index; i < nums.length; i++) { current.add(nums[i]); // include generateSubsets(nums, i + 1, current, result); // recurse current.remove(current.size() - 1); // exclude (backtrack) }}For [1, 2, 3] — generates all 8 subsets: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]Time: O(2ⁿ) — 2ⁿ subsets Space: O(n) — recursion depthProblem 6: Binary Search Recursivelyint binarySearch(int[] arr, int target, int left, int right) { if (left > right) return -1; // base case — not found int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) return binarySearch(arr, target, mid + 1, right); else return binarySearch(arr, target, left, mid - 1);}Time: O(log n) — halving the search space each time Space: O(log n) — log n frames on the call stackRecursion on Trees — The Natural HabitatTrees are where recursion truly shines. Every tree problem becomes elegant with recursion because a tree is itself a recursive structure — each node's left and right children are trees themselves.// Maximum depth of binary treeint maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}// Check if tree is symmetricboolean isSymmetric(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if (left == null || right == null) return false; return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);}// Path sum — does any root-to-leaf path sum to target?boolean hasPathSum(TreeNode root, int target) { if (root == null) return false; if (root.left == null && root.right == null) return root.val == target; return hasPathSum(root.left, target - root.val) || hasPathSum(root.right, target - root.val);}Notice the pattern in all three — base case handles null, recursive case handles left and right subtrees, result combines both.How to Think About Any Recursive Problem — Step by StepThis is the framework you should apply to every new recursive problem you encounter:Step 1 — Identify the base case What is the smallest input where you know the answer directly without any recursion? For arrays it is usually empty array or single element. For trees it is null node. For numbers it is 0 or 1.Step 2 — Trust the recursive call Assume your function already works correctly for smaller inputs. Do not trace through the entire recursion mentally — just trust it. This is the Leap of Faith and it is what makes recursion feel natural.Step 3 — Express the current problem in terms of smaller problems How does the answer for size n relate to the answer for size n-1 (or n/2, or subtrees)? This relationship is your recursive case.Step 4 — Make sure each call moves toward the base case The input must become strictly smaller with each call. If it does not, you have infinite recursion.Step 5 — Write the base case first, then the recursive case Always. Writing the recursive case first leads to bugs because you have not defined when to stop.Common Mistakes and How to Avoid ThemMistake 1: Missing or wrong base case The most common mistake. Missing the base case causes StackOverflowError. Wrong base case causes wrong answers.Always ask — what is the simplest possible input, and what should the function return for it? Write that case first.Mistake 2: Not moving toward the base case If you call factorial(n) inside factorial(n) without reducing n, you loop forever. Every recursive call must make the problem strictly smaller.Mistake 3: Trusting your brain to trace deep recursion Do not try to trace 10 levels of recursion in your head. Trust the recursive call, verify the base case, and check that each call reduces the problem. That is all you need.Mistake 4: Forgetting to return the recursive result// WRONG — result is computed but not returnedint sum(int n) { if (n == 0) return 0; sum(n - 1) + n; // computed but discarded!}// CORRECTint sum(int n) { if (n == 0) return 0; return sum(n - 1) + n;}Mistake 5: Modifying shared state without backtracking In backtracking problems, if you add something to a list before a recursive call, you must remove it after the call returns. Forgetting to backtrack leads to incorrect results and is one of the trickiest bugs to find.Mistake 6: Recomputing the same subproblems Naive Fibonacci computes fib(3) multiple times when computing fib(5). Use memoization whenever you notice overlapping subproblems in your recursion tree.Top LeetCode Problems on RecursionThese are organized by pattern — work through them in this order for maximum learning:Pure Recursion Basics:509. Fibonacci Number — Easy — start here, implement with and without memoization344. Reverse String — Easy — recursion on arrays206. Reverse Linked List — Easy — recursion on linked list50. Pow(x, n) — Medium — fast power with recursionTree Recursion (Most Important):104. Maximum Depth of Binary Tree — Easy — simplest tree recursion112. Path Sum — Easy — decision recursion on tree101. Symmetric Tree — Easy — mutual recursion on tree110. Balanced Binary Tree — Easy — bottom-up recursion236. Lowest Common Ancestor of a Binary Tree — Medium — classic tree recursion124. Binary Tree Maximum Path Sum — Hard — advanced tree recursionDivide and Conquer:148. Sort List — Medium — merge sort on linked list240. Search a 2D Matrix II — Medium — divide and conquerBacktracking:78. Subsets — Medium — generate all subsets46. Permutations — Medium — generate all permutations77. Combinations — Medium — generate combinations79. Word Search — Medium — backtracking on grid51. N-Queens — Hard — classic backtrackingMemoization / Dynamic Programming:70. Climbing Stairs — Easy — Fibonacci variant with memoization322. Coin Change — Medium — recursion with memoization to DP139. Word Break — Medium — memoized recursionRecursion Cheat Sheet// Linear recursion templatereturnType solve(input) { if (baseCase) return directAnswer; // process current return solve(smallerInput);}// Tree recursion templatereturnType solve(TreeNode root) { if (root == null) return baseValue; returnType left = solve(root.left); returnType right = solve(root.right); return combine(left, right, root.val);}// Backtracking templatevoid backtrack(choices, current, result) { if (goalReached) { result.add(copy of current); return; } for (choice : choices) { make(choice); // add to current backtrack(...); // recurse undo(choice); // remove from current }}// Memoization templateMap<Input, Output> memo = new HashMap<>();returnType solve(input) { if (baseCase) return directAnswer; if (memo.containsKey(input)) return memo.get(input); returnType result = solve(smallerInput); memo.put(input, result); return result;}FAQs — People Also AskQ1. What is recursion in Java with a simple example? Recursion is when a function calls itself to solve a smaller version of the same problem. A simple example is factorial — factorial(5) = 5 × factorial(4) = 5 × 4 × factorial(3) and so on until factorial(1) returns 1 directly.Q2. What is the difference between recursion and iteration? Iteration uses loops (for, while) and runs in O(1) space. Recursion uses function calls and uses O(n) stack space for n levels deep. Recursion is often cleaner for tree and graph problems. Iteration is better when memory is a concern or the problem is inherently linear.Q3. What causes StackOverflowError in Java recursion? StackOverflowError happens when recursion goes too deep — too many frames accumulate on the call stack before any of them return. This is caused by missing base case, wrong base case, or input too large for Java's default stack size limit.Q4. What is the difference between recursion and dynamic programming? Recursion solves a problem by breaking it into subproblems. Dynamic programming is recursion plus memoization — storing results of subproblems so they are never computed twice. DP converts exponential recursive solutions into polynomial ones by eliminating redundant computation.Q5. What is tail recursion and does Java support tail call optimization? Tail recursion is when the recursive call is the absolute last operation in the function. Java does NOT support tail call optimization — Java always creates a new stack frame for each call even if it is tail recursive. Languages like Scala and Kotlin (on the JVM) do support it with the tailrec keyword.Q6. How do you convert recursion to iteration? Every recursive solution can be converted to iterative using an explicit stack data structure. The call stack's behavior is replicated manually — push the initial call, loop while stack is not empty, pop, process, and push sub-calls. Tree traversals are a common example of this conversion.ConclusionRecursion is not magic. It is a systematic way of solving problems by expressing them in terms of smaller versions of themselves. Once you internalize the two parts (base case and recursive case), understand the call stack mentally, and learn to trust the recursive call rather than trace it completely, everything clicks.The learning path from here is clear — start with simple problems like Fibonacci and array sum. Move to tree problems where recursion is most natural. Then tackle backtracking. Finally add memoization to bridge into dynamic programming.Every hour you spend understanding recursion deeply pays dividends across the entire rest of your DSA journey. Trees, graphs, divide and conquer, backtracking, dynamic programming — all of them build on this foundation.

RecursionJavaBase CaseCall StackBacktrackingDynamic Programming

Intersection of Two Arrays

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

LeetCodeArrayEasyHashMap

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

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

MathMedianMediumLeetCodeJavaArrayTwo PointerSorting

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

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

Binary SearchJavaRotated Sorted ArrayLeetCodeMedium

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

LeetCode 769: Max Chunks To Make Sorted – Java Solution, Approach & Explanation

IntroductionLeetCode 769, Max Chunks To Make Sorted, is an interesting array partitioning problem.The array is a permutation of numbers from 0 to n - 1. The goal is to divide the array into multiple contiguous chunks, sort each chunk independently, and then join all the sorted chunks together.The challenge is to find the maximum number of chunks for which the final concatenated array becomes completely sorted.For example:arr = [1,0,2,3,4]The array can be divided as:[1,0] [2] [3] [4]After sorting every chunk:[0,1] [2] [3] [4]The final array is:[0,1,2,3,4]Therefore, the answer is 4.The given solution approaches the problem using recursion and backtracking to generate possible partitions and then checks which partitions produce a sorted array.Question LinkLeetCode 769 – Max Chunks To Make SortedUnderstanding the ProblemThe important word in the problem is chunks.A chunk must contain consecutive elements from the original array.For example:[4,3,2,1,0]Possible partition:[4,3] [2,1,0]After sorting:[3,4] [0,1,2]Combining them gives:[3,4,0,1,2]which is not sorted.So this partition is invalid.The task is not simply to split the array into as many pieces as possible. Every chosen partition must satisfy the condition that sorting each piece independently produces the globally sorted array.Approach: Recursion + BacktrackingThe given solution tries every possible way of partitioning the array.At every index, it considers every possible ending position for the current chunk.For example:arr = [1,0,2]Starting from index 0, possible first chunks are:[1][1,0][1,0,2]For each choice, recursion continues from the next index.This generates different partition configurations such as:[1] [0] [2][1,0] [2][1] [0,2][1,0,2]Each complete partition is then checked to determine whether it produces a sorted array.Generating the ChunksThe recursive function is:public void sol(int[] arr, int ind, List<List<Integer>> chunk)Here:ind represents the current starting index.chunk stores the chunks selected so far.The loop:for(int i = ind; i < arr.length; i++){ List<Integer> lis = subar(arr, ind, i); chunk.add(lis); sol(arr, i + 1, chunk); chunk.remove(chunk.size() - 1);}tries every possible ending point for the current chunk.The important part is:sol(arr, i + 1, chunk);Once a chunk from ind to i has been selected, the next chunk must begin at i + 1.Creating a ChunkThe subar() method creates a list containing the elements between two indices.public List<Integer> subar(int[] arr, int st, int en){ List<Integer> lis = new ArrayList<>(); for(int i = st; i <= en; i++){ lis.add(arr[i]); } return lis;}For example:arr = [1,0,2,3]st = 0en = 1produces:[1,0]Checking a PartitionOnce a complete partition has been generated, the vali() method checks whether it is valid.First, every chunk is sorted:Collections.sort(a);Then all sorted chunks are concatenated into one list:res.add(a.get(i));Finally, the resulting array is checked to see whether it is globally sorted.for(int i = 0; i < res.size() - 1; i++){ if(res.get(i) > res.get(i + 1)){ return false; }}If no decreasing pair exists, the partition is valid.Java Solutionclass Solution { int an = 0; // Generates all possible partitions public void sol(int[] arr, int ind, List<List<Integer>> chunk) { // A complete partition has been created if(ind == arr.length){ // Check whether this partition produces // the completely sorted array if(vali(chunk)){ an = Math.max(an, chunk.size()); } return; } // Try every possible ending point // for the current chunk for(int i = ind; i < arr.length; i++){ // Create the current chunk List<Integer> lis = subar(arr, ind, i); // Choose the chunk chunk.add(lis); // Recursively create the remaining chunks sol(arr, i + 1, chunk); // Backtrack chunk.remove(chunk.size() - 1); } } // Creates a subarray from st to en public List<Integer> subar(int[] arr, int st, int en){ List<Integer> lis = new ArrayList<>(); for(int i = st; i <= en; i++){ lis.add(arr[i]); } return lis; } // Checks whether the selected partition is valid public boolean vali(List<List<Integer>> liss){ List<Integer> res = new ArrayList<>(); // Sort every chunk independently for(List<Integer> a : liss){ Collections.sort(a); // Add the sorted chunk to the result for(int i = 0; i < a.size(); i++){ res.add(a.get(i)); } } // Check whether the final array is sorted for(int i = 0; i < res.size() - 1; i++){ if(res.get(i) > res.get(i + 1)){ return false; } } return true; } public int maxChunksToSorted(int[] arr){ List<List<Integer>> liss = new ArrayList<>(); sol(arr, 0, liss); return an; }}Dry RunConsider:arr = [1,0,2,3,4]One of the partitions generated by recursion is:[1,0] [2] [3] [4]The chunks are individually sorted:[0,1] [2] [3] [4]After concatenation:[0,1,2,3,4]The resulting array is sorted, so the partition is valid.It contains:4 chunksThe recursion also examines partitions with fewer chunks, such as:[1,0,2,3,4][1,0] [2,3,4][1] [0,2,3,4][1,0] [2] [3,4]Among all valid partitions, the solution keeps the maximum number of chunks using:an = Math.max(an, chunk.size());Therefore:Answer = 4Why Does the Maximum Number of Chunks Matter?A partition with fewer chunks can still produce the sorted array.For example:[1,0,2,3,4]can be split as:[1,0] [2,3,4]After sorting:[0,1] [2,3,4]which produces:[0,1,2,3,4]So this is valid.But it is not the maximum because:[1,0] [2] [3] [4]also works and gives more chunks.Therefore, every valid partition cannot simply be accepted—the number of chunks must also be maximized.Complexity AnalysisThe number of ways to split an array of length n into contiguous chunks is:2^(n-1)because every gap between two elements can either contain a partition or not.For example, with:[a,b,c]there are two gaps:a | b | cEach gap has two choices, giving:2² = 4possible partitions.For every complete partition, the solution also sorts the chunks and constructs the resulting array.Therefore, the overall complexity is exponential.Time Complexity: Approximately O(2^n × n log n)Space Complexity: Approximately O(n × 2^n) in the worst case because many partition configurations and temporary lists are generated.Since the given constraint is only:n <= 10this brute-force approach is feasible.A Better ObservationAlthough recursion works for the small constraint, this problem has a much simpler O(n) greedy solution.The key observation comes from the fact that the array is a permutation of:0, 1, 2, ..., n-1Suppose the current chunk ends at index i.If the maximum value seen so far is exactly i, then the current elements contain exactly the values that should occupy positions 0 through i.Therefore, the chunk can safely end at this position.For example:arr = [1,0,2,3,4]Track the maximum:index value max 0 1 1 1 0 1 2 2 2 3 3 3 4 4 4Whenever:max == indexa new chunk can be created.This happens at:index 1index 2index 3index 4So the answer is:4The optimized implementation is:class Solution { public int maxChunksToSorted(int[] arr) { int max = 0; int chunks = 0; for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); if(max == i){ chunks++; } } return chunks; }}This reduces the complexity to:Time Complexity: O(n)Space Complexity: O(1)Interview TipWhen a problem says the array is a permutation from 0 to n-1, that property is usually extremely important.Instead of immediately trying to generate all possibilities, look for a relationship between:the current indexthe values seen so farthe final sorted positionFor this problem, the condition:maximum value seen so far == current indexmeans that the current portion contains exactly the values needed for that prefix of the sorted array.That single observation turns an exponential backtracking solution into a linear greedy solution.ConclusionLeetCode 769 is a good example of how the same problem can be approached at different levels.The recursive solution explores every possible contiguous partition, sorts each chunk, and checks whether the final result is sorted. It is straightforward and works well under the small constraint n <= 10.However, the permutation property provides a much stronger observation. Whenever the maximum value seen so far equals the current index, a chunk can safely end there.That leads to a simple:O(n) timeO(1) spacegreedy solution.The main lesson is to first understand the brute-force structure, then look for properties in the input that can eliminate the need to explore every possibility.

LeetCodeJavaRecursionBacktrackingGreedyArraysSortingPermutationPartitioningMedium

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

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

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

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

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

LeetCode 55: Jump Game – Java Greedy Solution with Explanation and Dry Run

Problem StatementYou are given an integer array nums, where nums[i] represents the maximum number of steps you can jump forward from index i.You start at the first index of the array.Your task is to determine whether you can reach the last index.Return true if the last index is reachable; otherwise, return false.Problem Link -: Jump GameExample 1Input: nums = [2,3,1,1,4]Output: trueOne possible sequence is:Index 0 → Index 1 → Index 4From index 0, we can jump up to 2 positions.From index 1, we can jump up to 3 positions, which allows us to reach the last index.Example 2Input: nums = [3,2,1,0,4]Output: falseWe can reach index 3, but:nums[3] = 0Therefore, we cannot move any further and the last index cannot be reached.Understanding the ProblemThe important thing to understand is that we do not need to find the exact sequence of jumps.We only need to answer:"How far can I reach from all the positions I have been able to reach so far?"For example:nums = [2,3,1,1,4]index: 0 1 2 3 4value: 2 3 1 1 4Initially, we are at index 0.Since:nums[0] = 2we can reach:index 0, 1, 2So our current farthest reachable index is:2When we reach index 1, it allows us to jump 3 positions.Therefore:1 + 3 = 4Now we can reach index 4, which is the last index.The key idea is therefore to continuously maintain the farthest index we can reach.Greedy ApproachWe maintain a variable:jwhich represents the farthest index that we can currently reach.Initially:j = nums[0];At every index i, we first check:Can we even reach index i?If:i > jthen index i is unreachable.That means the answer must be:falseOtherwise, index i is reachable, so we can use its jump length to potentially extend our reachable range.The new farthest position becomes:max(current farthest, i + nums[i])In Java:j = Math.max(j, i + nums[i]);If this reaches the last index, we can immediately return true.Java Solutionclass Solution {public boolean canJump(int[] nums) {if (nums.length == 1) {return true;}int j = nums[0];for (int i = 1; i < nums.length; i++) {// Current index cannot be reachedif (i > j) {return false;}// Update the farthest reachable indexj = Math.max(j, i + nums[i]);// Last index is reachableif (j >= nums.length - 1) {return true;}}return false;}}Step-by-Step ExplanationLet's break the important part of the algorithm down.1. Start with the first reachable positionint j = nums[0];If:nums[0] = 2then from index 0, we can initially reach index 2.So:j = 22. Iterate through the arrayfor (int i = 1; i < nums.length; i++)We examine every index that we potentially can reach.3. Check whether the current index is reachableif (i > j) {return false;}Suppose:i = 4j = 3This means:4 > 3We can only reach up to index 3, so index 4 is unreachable.There is no way to continue.Therefore:return false;4. Extend the reachable rangeIf the current index is reachable, we calculate how far we can jump from it:i + nums[i]But this might not necessarily be better than our existing reachable position.Therefore we take the maximum:j = Math.max(j, i + nums[i]);This is the core greedy step.Dry RunConsider:nums = [2,3,1,1,4]Initially:j = nums[0]j = 2Now iterate.i = 1Current reachable range:j = 2Can we reach index 1?1 <= 2Yes.From index 1:1 + nums[1]= 1 + 3= 4Update:j = max(2, 4)j = 4Since:j >= last index4 >= 4we can reach the last index.Therefore:trueAnother Dry Run: Impossible CaseConsider:nums = [3,2,1,0,4]Initially:j = 3i = 11 <= 3Reachable.From index 1:1 + 2 = 3So:j = max(3,3)j = 3i = 22 <= 3Reachable.2 + 1 = 3So:j = 3i = 33 <= 3Reachable.But:3 + nums[3]= 3 + 0= 3We are still stuck at:j = 3i = 4Now:4 > 3Index 4 cannot be reached.Therefore:falseWhy Does the Greedy Approach Work?The important observation is that we don't care which particular jump we take.We care only about the farthest position that can be reached from the positions already available to us.Suppose we can reach index i.From there, we can reach:i + nums[i]If this is farther than our previous maximum, we update our reachable boundary.Therefore, at every step:farthest reachable positioncontains all the information we need.We don't need to remember every possible path.This is what makes the solution greedy rather than recursive or dynamic programming based.Why Not Try Every Possible Jump?A straightforward recursive approach might try:index 0├── jump 1│ ├── jump 1│ └── jump 2│└── jump 2├── jump 1└── jump 2The number of possible paths can grow very quickly.We don't actually need to explore these paths.For example, if we can reach:0 → 1and:0 → 2we don't need to separately remember both paths.What matters is simply:Farthest reachable index = 2That removes a huge amount of unnecessary work.A Slightly Cleaner VersionThe same greedy logic can be written using a more descriptive variable name:class Solution {public boolean canJump(int[] nums) {int farthest = 0;for (int i = 0; i < nums.length; i++) {if (i > farthest) {return false;}farthest = Math.max(farthest, i + nums[i]);if (farthest >= nums.length - 1) {return true;}}return true;}}Here:farthestmakes the purpose of the variable clearer than j.The logic is exactly the same.Complexity AnalysisLet n be the length of the array.Time ComplexityWe traverse the array only once:O(n)Space ComplexityWe use only a few variables:O(1)So the final complexity is:Time: O(n)Space: O(1)Important Edge Cases1. Array contains only one elementnums = [0]We are already at the last index.Answer:true2. First position cannot movenums = [0,1]We cannot reach index 1.Answer:false3. Last index is directly reachablenums = [5,0,0,0,0]The first position can jump directly to the end.Answer:true4. Zeros in the middleZeros are not necessarily a problem.For example:[2,0,2]We can jump from index 0 directly to index 2.So the answer is:trueA zero only becomes a problem when it prevents our reachable boundary from extending far enough.Key TakeawayThe most important idea behind Jump Game is:Don't try to decide which jump to make. Track how far you can reach.At every index:Check whether the index is reachable.Calculate how far this index can take us.Update the farthest reachable position.If the last index becomes reachable, return true.If we encounter an index beyond the reachable boundary, return false.The pattern can be summarized as:Reachable?↓Calculate new reach↓Update farthest↓Can we reach the end?This is a classic example of a Greedy Array Traversal problem and is an important pattern to recognize in coding interviews.Final ComplexityApproachTimeSpaceBrute Force / RecursionPotentially exponentialO(n) recursionGreedyO(n)O(1)The greedy solution is optimal because we only need to maintain the farthest position reachable at each point rather than exploring every possible jump sequence.

JavaLeetcodeArrayGreedy ApproachMedium

Left and Right Sum Differences

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

LeetCodePrefixSuffix

LeetCode 2033: Minimum Operations to Make a Uni-Value Grid | Java Solution Explained (Median Approach)

IntroductionIn this problem, we are given a 2D grid and an integer x.We can perform one operation where we either:Add x to any grid elementSubtract x from any grid elementOur goal is to make all elements in the grid equal using the minimum number of operations.If making all values equal is not possible, we return -1.This problem may initially look like a matrix manipulation question, but the actual logic is based on:Array transformationMedian propertyGreedy optimization# Problem LinkProblem StatementYou are given:A 2D integer grid of size m × nAn integer xYou can perform operations where you add or subtract x from any cell.A grid becomes uni-value when all elements become equal.Return the minimum number of operations needed.If impossible, return -1.ExampleExample 1Input:grid = [[2,4],[6,8]]x = 2Output:4Explanation:We can make every element equal to 4.2 → 4 (1 operation)6 → 4 (1 operation)8 → 4 (2 operations)Total = 4 operations.Key ObservationBefore solving the problem, we must understand one important rule.If we can add or subtract only x, then:All numbers must belong to the same remainder group when divided by x.Meaning:value % x must be same for every elementWhy?Because if two numbers have different remainders, they can never become equal using only +x or -x operations.IntuitionWe need to convert all numbers into a single target value.But what target value gives minimum operations?The answer is:MedianFor minimizing total absolute distance, median gives the optimal answer.Since every operation changes value by x, we can:Flatten grid into a listSort the listPick median as targetCalculate operations requiredWhy Median Works?Median minimizes:Sum of absolute differencesFor example:Numbers = [1, 2, 3, 10]If target = 2|1-2| + |2-2| + |3-2| + |10-2| = 10If target = 5|1-5| + |2-5| + |3-5| + |10-5| = 14Median gives minimum total distance.Approach 1: Brute ForceWe can try every possible number as target.For each target:Calculate operations requiredStore minimum answerTime ComplexityO(N²)Where N = total grid elementsThis is slow for large constraints.Approach 2: Optimal Median ApproachThis is the best approach.StepsStep 1: Flatten GridConvert 2D grid into 1D array.Step 2: Sort ArraySorting helps us find median.Step 3: Check ValidityAll values must have same remainder when divided by x.value % x must matchOtherwise return -1.Step 4: Pick MedianMedian minimizes operations.Step 5: Count OperationsFor every element:operations += abs(value - median) / xJava Solutionclass Solution {public int minOperations(int[][] grid, int x) {List<Integer> lis = new ArrayList<>();for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {lis.add(grid[i][j]);}}Collections.sort(lis);int mid = lis.size() / 2;int remainder = lis.get(0) % x;for (int value : lis) {if (value % x != remainder) {return -1;}}int ans = 0;for (int value : lis) {int diff = Math.abs(lis.get(mid) - value);ans += diff / x;}return ans;}}Code ExplanationStep 1: Flatten Matrixlis.add(grid[i][j]);We convert grid into list.Step 2: Sort ListCollections.sort(lis);Sorting allows median selection.Step 3: Check Possibilityif(value % x != remainder)If remainders differ, answer becomes impossible.Step 4: Select Medianint mid = lis.size()/2;Median becomes target value.Step 5: Calculate Operationsans += diff/x;Difference divided by x gives operations.Dry RunInput:grid = [[2,4],[6,8]]x = 2Flatten:[2,4,6,8]Sort:[2,4,6,8]Median:6Operations:2 → 6 = 2 operations4 → 6 = 1 operation6 → 6 = 0 operation8 → 6 = 1 operationTotal:4 operationsTime ComplexityFlatten GridO(N)SortingO(N log N)Traverse ArrayO(N)Total ComplexityO(N log N)Where:N = m × nSpace ComplexityWe store all elements in list.O(N)Common Mistakes1. Forgetting Mod CheckMany people directly calculate operations.But without checking:value % xanswer may become invalid.2. Choosing Average Instead of MedianAverage does not minimize absolute distance.Median is required.3. Not Sorting Before Finding MedianMedian requires sorted array.4. Forgetting Division by xOperations are not direct difference.Correct formula:abs(target - value) / xEdge CasesCase 1All values already equal.Answer = 0Case 2Different modulo values.Return -1Case 3Single cell grid.No operation neededFAQsQ1. Why do we use median?Median minimizes total absolute difference.Q2. Why not average?Average minimizes squared distance, not absolute operations.Q3. Why modulo condition is important?Because we can only move by multiples of x.Q4. Can we solve without sorting?Sorting is easiest way to get median.Alternative median-finding algorithms exist but are unnecessary here.Interview InsightInterviewers ask this problem to test:Greedy thinkingMedian propertyMathematical observationArray flatteningOptimization logicConclusionLeetCode 2033 is a great problem that combines math with greedy logic.The most important learning points are:Flatten the gridValidate modulo conditionUse median as targetCalculate operations using difference divided by xThis approach is optimal and easy to implement.Once you understand why median works, this problem becomes very straightforward.

ArraySortingMathMedianMediumMatrixGridLeetCodeJava

Mastering Binary Search – LeetCode 704 Explained

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

Binary SearchLeetCodeEasy

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

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

DataStructuresJavaStackDataStructureLIFO

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

Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

🔗 Problem LinkLeetCode 242 – Valid Anagram 👉 https://leetcode.com/problems/valid-anagram/IntroductionThis is one of the most important string frequency problems in coding interviews.The idea of checking whether two strings are anagrams appears in many variations:Group AnagramsRansom NoteFind the DifferencePermutation in StringIf you master this pattern, you unlock a whole category of problems.Let’s break it down step by step.📌 Problem UnderstandingTwo strings are anagrams if:They contain the same charactersWith the same frequenciesOrder does not matterExample 1Input: s = "anagram" t = "nagaram"Output: trueBoth contain:a → 3n → 1g → 1r → 1m → 1Example 2Input: s = "rat" t = "car"Output: falseDifferent character frequencies.🧠 IntuitionThe core idea:If two strings are anagrams, their character frequencies must match exactly.So we:Check if lengths are equal.Count frequency of characters in first string.Subtract frequencies using second string.If at any point frequency becomes negative → not anagram.💻 Your Codeclass Solution { public boolean isAnagram(String s, String t) { if(s.length() != t.length()) return false; HashMap<Character,Integer> mp = new HashMap<>(); for(int i =0;i<s.length();i++){ mp.put(s.charAt(i),mp.getOrDefault(s.charAt(i),0)+1); } for(int i =0; i < t.length();i++){ if(mp.containsKey(t.charAt(i)) && mp.get(t.charAt(i)) > 0){ mp.put(t.charAt(i),mp.get(t.charAt(i))-1); }else{ return false; } } return true; }}🔍 Step-by-Step Explanation1️⃣ Length Checkif(s.length() != t.length()) return false;If lengths differ → cannot be anagrams.2️⃣ Build Frequency Mapmp.put(s.charAt(i), mp.getOrDefault(s.charAt(i), 0) + 1);Count occurrences of each character in s.3️⃣ Subtract Using Second Stringif(mp.containsKey(t.charAt(i)) && mp.get(t.charAt(i)) > 0)If character exists and frequency is available → reduce it.Otherwise → return false immediately.🎯 Why This WorksWe treat:First string as frequency builderSecond string as frequency consumerIf all frequencies match perfectly, we return true.⏱ Complexity AnalysisTime Complexity: O(n)One pass to build mapOne pass to compareSpace Complexity: O(26) ≈ O(1)Only lowercase English letters allowed.🔥 Optimized Approach – Using Array Instead of HashMapSince the problem guarantees:s and t consist of lowercase English lettersWe can replace HashMap with an integer array of size 26.This is faster and cleaner.Optimized Versionclass Solution { public boolean isAnagram(String s, String t) { if(s.length() != t.length()) return false; int[] freq = new int[26]; for(char c : s.toCharArray()){ freq[c - 'a']++; } for(char c : t.toCharArray()){ freq[c - 'a']--; if(freq[c - 'a'] < 0){ return false; } } return true; }}🚀 Why This Is BetterNo HashMap overheadDirect index accessCleaner codeFaster in interviews🏁 Final ThoughtsThis problem teaches:Frequency counting patternEarly exit optimizationUsing arrays instead of HashMap when character set is limitedThinking in terms of resource balanceValid Anagram is a foundation problem.Once you master it, you can easily solve:Ransom NoteFind the DifferenceGroup AnagramsCheck Equal Character Occurrences

HashMapStringFrequency CountArraysLeetCodeEasy

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

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

GeeksforGeeksBinary SearchEasy

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

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

Binary StringsHashingCantor DiagonalizationLeetCodeMedium

LeetCode 2078: Two Furthest Houses With Different Colors | Java Solution Explained (Step-by-Step Guide)

Why This Problem Is InterestingAt first glance, this looks like a basic array problem. But here’s the twist:👉 If you try solving it “normally,” you’ll overthink it. 👉 If you observe patterns, it becomes one of the easiest O(n) problems.This is exactly the kind of question interviewers use to test:Do you brute force blindly?Or do you see patterns in constraints?🚀 Problem Linkhttps://leetcode.com/problems/two-furthest-houses-with-different-colors/🧩 Problem Breakdown (Understand Like a Beginner)You are given:colors = [1,1,1,6,1,1,1]Each index = house Each value = colorYou need to:👉 Pick two houses with different colors 👉 Maximize the distance between themDistance formula:|i - j|🧠 First Thought (What Most People Do)“Let me check all pairs…”(0,1), (0,2), (0,3), ...(1,2), (1,3), ...Yes, it works. But…👉 That’s O(n²) 👉 Completely unnecessary for n ≤ 100? Maybe fine 👉 But logically inefficient🟡 Approach 1: Brute Force (Baseline Thinking)💻 Codeclass Solution { public int maxDistance(int[] colors) { int n = colors.length; int max = 0; for (int i = 0; i < n; i++) { for (int j = n - 1; j > i; j--) { if (colors[i] != colors[j]) { max = Math.max(max, j - i); } } } return max; }}⏱ Time Complexity (Why O(n²)?)Outer loop → runs n timesInner loop → runs n times👉 Total = n * n = O(n²)❌ Why This Is WastefulYou are:Checking close houses (useless)When the answer depends on far houses💡 Key Turning Point (Where Real Thinking Starts)Ask yourself:👉 “To maximize |i - j|, what do I need?”Answer:👉 Make i and j as far apart as possibleThat means:i should be near 0j should be near n-1🔥 Critical Observation👉 The answer will always involve either:First house (index 0), ORLast house (index n-1)Why?Because they give maximum possible distance🟢 Approach 2: Two Direction ScanNow your idea makes perfect sense:Step 1Fix first element → find farthest different colorStep 2Fix last element → find farthest different color💻 Your Codeclass Solution { public int maxDistance(int[] colors) { int i = 0; int i2 = colors.length - 1; int j1 = 1; int j2 = colors.length - 2; int max1 = Integer.MIN_VALUE; int max2 = Integer.MIN_VALUE; while (j1 < colors.length) { if (colors[i] != colors[j1]) { max1 = Math.max(max1, Math.abs(j1 - i)); } j1++; } while (j2 >= 0) { if (colors[i2] != colors[j2]) { max2 = Math.max(max2, Math.abs(j2 - i2)); } j2--; } return Math.max(max1, max2); }}🔍 Dry Run (Deep Understanding)Input:colors = [1,1,1,6,1,1,1]🔹 First Loop (Fix index 0)Compare:0 vs 1 → same0 vs 2 → same0 vs 3 → different ✅ → distance = 30 vs 4 → same0 vs 5 → same0 vs 6 → same👉 max1 = 3🔹 Second Loop (Fix last index)Compare:6 vs 5 → same6 vs 4 → same6 vs 3 → different ✅ → distance = 36 vs 2 → same...👉 max2 = 3✅ Final Answer:max(3, 3) = 3⏱ Time Complexity (Why O(n)?)First loop → O(n)Second loop → O(n)👉 Total = O(n) + O(n) = O(n)🟢 Approach 3: Cleaner Optimization (Best Version)We can compress both loops into one:💻 Codeclass Solution { public int maxDistance(int[] colors) { int n = colors.length; int max = 0; for (int i = 0; i < n; i++) { if (colors[i] != colors[0]) { max = Math.max(max, i); } if (colors[i] != colors[n - 1]) { max = Math.max(max, n - 1 - i); } } return max; }}🔍 Why This Works (Core Insight)We only check:Distance from startDistance from endBecause:👉 Any maximum distance pair must include one endpointThis avoids:Redundant comparisonsNested loops🧠 Mental Model (Remember This)Instead of thinking:❌ “Check all pairs”Think:✅ “Where can maximum distance even exist?”🎯 Final TakeawaysAlways question brute forceDistance problems → think endpoints firstConstraints often hide optimizationsObservations > Code

LeetCodeJavaArraysTwoPointersEasy

LeetCode 496: Next Greater Element I — Java Solution With All Approaches Explained

IntroductionLeetCode 496 Next Greater Element I is your gateway into one of the most important and frequently tested patterns in coding interviews — the Monotonic Stack. Once you understand this problem deeply, problems like Next Greater Element II, Daily Temperatures, and Largest Rectangle in Histogram all start to make sense.Here is the Link of Question -: LeetCode 496This article covers plain English explanation, real life analogy, brute force and optimal approaches in Java, detailed dry runs, complexity analysis, common mistakes, and FAQs.What Is the Problem Really Asking?You have two arrays. nums2 is the main array. nums1 is a smaller subset of nums2. For every element in nums1, find its position in nums2 and look to the right — what is the first element that is strictly greater? If none exists, return -1.Example:nums1 = [4,1,2], nums2 = [1,3,4,2]For 4 in nums2: elements to its right are [2], none greater → -1For 1 in nums2: elements to its right are [3,4,2], first greater is 3For 2 in nums2: no elements to its right → -1Output: [-1, 3, -1]Real Life Analogy — The Taller Person in a QueueImagine you are standing in a queue and you want to know — who is the first person taller than you standing somewhere behind you in the line?You look to your right one by one until you find someone taller. That person is your "next greater element." If everyone behind you is shorter, your answer is -1.Now imagine doing this for every person in the queue efficiently — instead of each person looking one by one, you use a smart system that processes everyone in a single pass. That smart system is the Monotonic Stack.Approach 1: Brute Force (Beginner Friendly)The IdeaFor each element in nums1, find its position in nums2, then scan everything to its right to find the first greater element.javapublic int[] nextGreaterElement(int[] nums1, int[] nums2) { int[] ans = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { int found = -1; boolean seen = false; for (int j = 0; j < nums2.length; j++) { if (seen && nums2[j] > nums1[i]) { found = nums2[j]; break; } if (nums2[j] == nums1[i]) { seen = true; } } ans[i] = found; } return ans;}Simple to understand but inefficient. For each element in nums1 you scan the entire nums2.Time Complexity: O(m × n) — where m = nums1.length, n = nums2.length Space Complexity: O(1) — ignoring output arrayThis works for the given constraints (n ≤ 1000) but will not scale for larger inputs. The follow-up specifically asks for better.Approach 2: Monotonic Stack + HashMap (Optimal Solution) ✅The IdeaThis is your solution and the best one. The key insight is — instead of answering queries for nums1 elements one by one, precompute the next greater element for every element in nums2 and store results in a HashMap. Then answering nums1 queries becomes just a HashMap lookup.To precompute efficiently, we use a Monotonic Stack — a stack that always stays in decreasing order from bottom to top.Why traverse from right to left? Because we are looking for the next greater element to the right. Starting from the right end, by the time we process any element, we have already seen everything to its right.Algorithm:Traverse nums2 from right to leftMaintain a stack of "candidate" next greater elementsFor current element, pop all stack elements that are smaller or equal — they can never be the next greater for anything to the leftIf stack is empty → next greater is -1, else → top of stack is the answerPush current element onto stackStore result in HashMapLook up each nums1 element in the HashMapjavapublic int[] nextGreaterElement(int[] nums1, int[] nums2) { Stack<Integer> st = new Stack<>(); HashMap<Integer, Integer> mp = new HashMap<>(); // Precompute next greater for every element in nums2 for (int i = nums2.length - 1; i >= 0; i--) { // Pop elements smaller than current — they are useless while (!st.empty() && nums2[i] >= st.peek()) { st.pop(); } // Top of stack is the next greater, or -1 if empty mp.put(nums2[i], st.empty() ? -1 : st.peek()); // Push current element as a candidate for elements to its left st.push(nums2[i]); } // Answer queries for nums1 int[] ans = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { ans[i] = mp.get(nums1[i]); } return ans;}Why Is the Stack Monotonic?After popping smaller elements, the stack always maintains a decreasing order from bottom to top. This means the top of the stack at any point is always the smallest element seen so far to the right — making it the best candidate for "next greater."This is called a Monotonic Decreasing Stack and it is the heart of this entire pattern.Detailed Dry Run — nums2 = [1,3,4,2]We traverse from right to left:i = 3, nums2[3] = 2Stack is emptyNo elements to popStack empty → mp.put(2, -1)Push 2 → stack: [2]i = 2, nums2[2] = 4Stack top is 2, and 4 >= 2 → pop 2 → stack: []Stack empty → mp.put(4, -1)Push 4 → stack: [4]i = 1, nums2[1] = 3Stack top is 4, and 3 < 4 → stop poppingStack not empty → mp.put(3, 4)Push 3 → stack: [4, 3]i = 0, nums2[0] = 1Stack top is 3, and 1 < 3 → stop poppingStack not empty → mp.put(1, 3)Push 1 → stack: [4, 3, 1]HashMap after processing nums2:1 → 3, 2 → -1, 3 → 4, 4 → -1Now answer nums1 = [4, 1, 2]:nums1[0] = 4 → mp.get(4) = -1nums1[1] = 1 → mp.get(1) = 3nums1[2] = 2 → mp.get(2) = -1✅ Output: [-1, 3, -1]Time Complexity: O(n + m) — n for processing nums2, m for answering nums1 queries Space Complexity: O(n) — HashMap and Stack both store at most n elementsWhy Pop Elements Smaller Than Current?This is the most important thing to understand in this problem. When we are at element x and we see a stack element y where y < x, we pop y. Why?Because x is to the right of everything we will process next (we go right to left), and x is already greater than y. So for any element to the left of x, if they are greater than y, they are definitely also greater than y — meaning y would never be the "next greater" for anything. It becomes useless and gets discarded.This is why the stack stays decreasing — every element we keep is a legitimate candidate for being someone's next greater element.How This Differs From Previous Stack ProblemsYou have been solving stack problems with strings — backspace, stars, adjacent duplicates. This problem introduces the stack for arrays and searching, which is a step up in complexity.The pattern shift is: instead of using the stack to build or reduce a string, we use it to maintain a window of candidates while scanning. This monotonic stack idea is what powers many hard problems like Largest Rectangle in Histogram, Trapping Rain Water, and Daily Temperatures.Common Mistakes to AvoidUsing >= instead of > in the pop condition We pop when nums2[i] >= st.peek(). If you use only >, equal elements stay on the stack and give wrong answers since we need strictly greater.Traversing left to right instead of right to left Going left to right makes it hard to know what is to the right of the current element. Always go right to left for "next greater to the right" problems.Forgetting HashMap lookup handles the nums1 query efficiently Some people recompute inside the nums1 loop. Always precompute in a HashMap — that is the whole point of the optimization.FAQs — People Also AskQ1. What is a Monotonic Stack and why is it used in LeetCode 496? A Monotonic Stack is a stack that maintains its elements in either increasing or decreasing order. In LeetCode 496, a Monotonic Decreasing Stack is used to efficiently find the next greater element for every number in nums2 in a single pass, reducing time complexity from O(n²) to O(n).Q2. What is the time complexity of LeetCode 496 optimal solution? The optimal solution runs in O(n + m) time where n is the length of nums2 and m is the length of nums1. Processing nums2 takes O(n) and answering all nums1 queries via HashMap takes O(m).Q3. Why do we traverse nums2 from right to left? Because we are looking for the next greater element to the right. Starting from the right end means by the time we process any element, we have already seen all elements to its right and stored them in the stack as candidates.Q4. Is LeetCode 496 asked in coding interviews? Yes, it is commonly used as an introduction to the Monotonic Stack pattern at companies like Amazon, Google, and Microsoft. It often appears as a warmup before harder follow-ups like Next Greater Element II (circular array) or Daily Temperatures.Q5. What is the difference between LeetCode 496 and LeetCode 739 Daily Temperatures? Both use the same Monotonic Stack pattern. In 496 you return the actual next greater value. In 739 you return the number of days (index difference) until a warmer temperature. The core stack logic is identical.Similar LeetCode Problems to Practice Next739. Daily Temperatures — Medium — days until warmer temperature, same pattern503. Next Greater Element II — Medium — circular array version901. Online Stock Span — Medium — monotonic stack with span counting84. Largest Rectangle in Histogram — Hard — classic monotonic stack42. Trapping Rain Water — Hard — monotonic stack or two pointerConclusionLeetCode 496 Next Greater Element I is the perfect entry point into the Monotonic Stack pattern. The brute force is easy to understand, but the real learning happens when you see why the stack stays decreasing and how that single insight collapses an O(n²) problem into O(n).Once you truly understand why we pop smaller elements and how the HashMap bridges the gap between precomputation and query answering, the entire family of Next Greater Element problems becomes approachable — including the harder circular and histogram variants.

ArrayStackMonotonic StackHashMapEasyLeetCode

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

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

LeetCodeGreedyTwo PointersDynamic ProgrammingMediumJavaArrays

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

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

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

LeetCodeBinary SearchMediumJavaBinary Search on AnswerArraysCeiling Division

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

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

LeetCodeTwo PointersEasyJavaDSA

LeetCode 39: Combination Sum – Java Backtracking Solution with Dry Run & Complexity

IntroductionIf you are preparing for coding interviews or improving your Data Structures and Algorithms skills, LeetCode 39 Combination Sum is one of the most important backtracking problems to learn. This problem helps you understand how recursion explores multiple possibilities and how combinations are generated efficiently. It is a foundational problem that builds strong problem-solving skills and prepares you for many advanced recursion and backtracking questions.Why Should You Solve This Problem?Combination Sum is not just another coding question — it teaches you how to think recursively and break a complex problem into smaller decisions. By solving it, you learn how to manage recursive paths, avoid duplicate combinations, and build interview-level backtracking intuition. Once you understand this pattern, problems like subsets, permutations, N-Queens, and Sudoku Solver become much easier to approach.LeetCode Problem LinkProblem Name: Combination SumProblem Link: Combination SumProblem StatementGiven an array of distinct integers called candidates and a target integer target, you need to return all unique combinations where the chosen numbers sum to the target.Important rules:You can use the same number unlimited times.Only unique combinations should be returned.Order of combinations does not matter.ExampleExample 1Input:candidates = [2,3,6,7]target = 7Output:[[2,2,3],[7]]Explanation2 + 2 + 3 = 77 itself equals targetUnderstanding the Problem in Simple WordsWe are given some numbers.We need to:Pick numbers from the arrayAdd them togetherReach the target sumUse numbers multiple times if neededAvoid duplicate combinationsThis problem belongs to the Backtracking + Recursion category.Real-Life AnalogyImagine you have coins of different values.You want to make an exact payment.You can reuse coins multiple times.You need to find every possible valid coin combination.This is exactly what Combination Sum does.Intuition Behind the SolutionAt every index, we have two choices:Pick the current numberSkip the current numberSince numbers can be reused unlimited times, when we pick a number, we stay at the same index.This creates a recursion tree.We continue until:Target becomes 0 → valid answerTarget becomes negative → invalid pathArray ends → stop recursionWhy Backtracking Works HereBacktracking helps us:Explore all possible combinationsUndo previous decisionsTry another pathIt is useful whenever we need:All combinationsAll subsetsPath explorationRecursive searchingApproach 1: Backtracking Using Pick and SkipCore IdeaAt every element:Either take itOr move to next elementJava Code (Pick and Skip Method)class Solution {List<List<Integer>> result = new ArrayList<>();public void solve(int[] candidates, int index, int target, List<Integer> current) {if (target == 0) {result.add(new ArrayList<>(current));return;}if (index == candidates.length) {return;}if (candidates[index] <= target) {current.add(candidates[index]);solve(candidates, index, target - candidates[index], current);current.remove(current.size() - 1);}solve(candidates, index + 1, target, current);}public List<List<Integer>> combinationSum(int[] candidates, int target) {solve(candidates, 0, target, new ArrayList<>());return result;}}Approach 2: Backtracking Using Loop (Optimized)This is the cleaner and more optimized version.Your code belongs to this category.Java Code (Loop-Based Backtracking)class Solution {List<List<Integer>> result = new ArrayList<>();public void solve(int[] arr, int index, int target, List<Integer> current) {if (target == 0) {result.add(new ArrayList<>(current));return;}if (index == arr.length) {return;}for (int i = index; i < arr.length; i++) {if (arr[i] > target) {continue;}current.add(arr[i]);solve(arr, i, target - arr[i], current);current.remove(current.size() - 1);}}public List<List<Integer>> combinationSum(int[] candidates, int target) {solve(candidates, 0, target, new ArrayList<>());return result;}}Dry Run of the AlgorithmInputcandidates = [2,3,6,7]target = 7Step-by-Step ExecutionStart:solve([2,3,6,7], index=0, target=7, [])Pick 2[2]target = 5Pick 2 again:[2,2]target = 3Pick 2 again:[2,2,2]target = 1No valid choice possible.Backtrack.Try 3[2,2,3]target = 0Valid answer found.Add:[2,2,3]Try 7[7]target = 0Valid answer found.Add:[7]Final Output[[2,2,3],[7]]Recursion Tree Visualization[]/ | | \2 3 6 7/2/2/3Every branch explores a different combination.Time Complexity AnalysisTime ComplexityO(2^Target)More accurately:O(N^(Target/minValue))Where:N = Number of candidatesTarget = Required sumReason:Every number can be picked multiple times.This creates many recursive branches.Space ComplexityO(Target)Reason:Recursion stack stores elements.Maximum recursion depth depends on target.Why We Pass Same Index AgainNotice this line:solve(arr, i, target - arr[i], current);We pass i, not i+1.Why?Because we can reuse the same number unlimited times.If we used i+1, we would move forward and lose repetition.Why Duplicate Combinations Are Not CreatedWe start loop from current index.This guarantees:[2,3]and[3,2]are not both generated.Order remains controlled.Common Mistakes Beginners Make1. Using i+1 Instead of iWrong:solve(arr, i+1, target-arr[i], current)This prevents reuse.2. Forgetting Backtracking StepWrong:current.remove(current.size()-1)Without removing, recursion keeps incorrect values.3. Missing Target == 0 Base CaseThis is where valid answer is stored.Important Interview InsightCombination Sum is a foundational problem.It helps build understanding for:Combination Sum IISubsetsPermutationsN-QueensWord SearchSudoku SolverThis question is frequently asked in coding interviews.Pattern RecognitionUse Backtracking when problem says:Find all combinationsGenerate all subsetsFind all pathsUse recursionExplore possibilitiesOptimized Thinking StrategyWhenever you see:Target sumRepeated selectionMultiple combinationsThink:Backtracking + DFSEdge CasesCase 1candidates = [2]target = 1Output:[]No possible answer.Case 2candidates = [1]target = 3Output:[[1,1,1]]Interview Answer in One Line“We use backtracking to recursively try all candidate numbers while reducing the target and backtrack whenever a path becomes invalid.”Final Java Codeclass Solution {List<List<Integer>> result = new ArrayList<>();public void solve(int[] arr, int index, int target, List<Integer> current) {if (target == 0) {result.add(new ArrayList<>(current));return;}for (int i = index; i < arr.length; i++) {if (arr[i] > target) {continue;}current.add(arr[i]);solve(arr, i, target - arr[i], current);current.remove(current.size() - 1);}}public List<List<Integer>> combinationSum(int[] candidates, int target) {solve(candidates, 0, target, new ArrayList<>());return result;}}Key TakeawaysCombination Sum uses Backtracking.Reuse same element by passing same index.Target becomes smaller in recursion.Backtracking removes last element.Very important for interview preparation.Frequently Asked QuestionsIs Combination Sum DP or Backtracking?It is primarily solved using Backtracking.Dynamic Programming can also solve it but recursion is more common.Why is this Medium difficulty?Because:Requires recursion understandingRequires backtracking logicRequires duplicate preventionCan we sort the array?Yes.Sorting can help with pruning.ConclusionLeetCode 39 Combination Sum is one of the best problems to learn recursion and backtracking.Once you understand this pattern, many interview problems become easier.The loop-based recursive solution is clean, optimized, and interview-friendly.If you master this question, you gain strong understanding of recursive decision trees and combination generation.

LeetcodeMediumRecursionBacktrackingJava

Find All Numbers Disappeared in an Array

LeetCode Problem 448Link of the Problem to try -: LinkGiven an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums. Example 1:Input: nums = [4,3,2,7,8,2,3,1]Output: [5,6]Example 2:Input: nums = [1,1]Output: [2] Constraints:n == nums.length1 <= n <= 1051 <= nums[i] <= nSolution:In this question as the question suggests we have to find the missing element from the array that is not in the array but comes in that range of 1 to array.length and we can solve this by creating an HashMap where we simply store all the elements and then run the loop again from 1 to array.length and then check is that element present if not then store it on our ArrayList and return it this is how we can solve this question easily in O(n) Time Complexity.Code: public List<Integer> findDisappearedNumbers(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],0); } for(int i = 1;i<=nums.length;i++){ if(!mp.containsKey(i)){ lis.add(i); } } return lis; }

LeetCodeHashMapEasy

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 3838: Weighted Word Mapping – Java Solution Explained with Multiple Approaches

IntroductionLeetCode 3838, Weighted Word Mapping, is a straightforward yet interesting problem that combines several fundamental programming concepts:Character mappingHashingModular arithmeticString processingOptimization techniquesAt first glance, the problem appears to be a simple implementation exercise. However, it provides a great opportunity to discuss different approaches and understand how fixed-size alphabets can help us write more efficient code.In this article, we'll explore the problem step-by-step, discuss multiple solutions, perform a dry run, and analyze the complexity of each approach.Problem Link -: Weighted Word MappingProblem StatementYou are given:An array of strings wordsAn integer array weights of length 26Each index in the weights array corresponds to a lowercase English letter.For every word:Calculate the sum of character weights.Take the result modulo 26.Convert the modulo result into a letter using reverse alphabetical order:0 → z1 → y2 → x...25 → aReturn a string formed by concatenating all mapped letters.ExampleInputwords = ["abcd", "def", "xyz"]Output"rij"ExplanationFor the word "abcd":a = 5b = 3c = 12d = 14Total Weight = 3434 % 26 = 88 → rFor "def":14 + 1 + 2 = 1717 % 26 = 1717 → iFor "xyz":7 + 7 + 2 = 1616 % 26 = 1616 → jFinal Answer:"rij"Understanding the Core IdeaThe problem consists of three independent operations:Step 1: Calculate Word WeightFor each word:Weight(word) = Sum of character weightsExample:abca = 5b = 3c = 12Weight = 20Step 2: Apply Modulo 26The problem requires:Weight % 26This guarantees that the result always lies between:0 and 25Step 3: Reverse Alphabet MappingUnlike normal alphabet indexing:0 → a1 → b2 → cthe problem uses:0 → z1 → y2 → x...25 → aThis reverse mapping generates the final encoded character.Approach 1: HashMap-Based SolutionIntuitionCreate:Map 1Character → WeightExample:a → 5b → 3c → 12Map 2Modulo Value → CharacterExample:0 → z1 → y2 → xThen process each word and build the answer.Java Implementationclass Solution { public String mapWordWeights(String[] words, int[] weights) { HashMap<Character,Integer> weightMap = new HashMap<>(); HashMap<Integer,Character> reverseMap = new HashMap<>(); for(int i = 0; i < 26; i++) { char letter = (char)('a' + i); char reverseLetter = (char)('z' - i); weightMap.put(letter, weights[i]); reverseMap.put(i, reverseLetter); } StringBuilder answer = new StringBuilder(); for(String word : words) { int sum = 0; for(char ch : word.toCharArray()) { sum += weightMap.get(ch); } answer.append(reverseMap.get(sum % 26)); } return answer.toString(); }}Approach 2: Optimized Array SolutionObservationThe English alphabet contains only 26 letters.Instead of using HashMaps:weightMap.get(ch)we can directly access:weights[ch - 'a']This eliminates hashing overhead entirely.Why Is This Better?HashMap operations are O(1) on average, but they still involve:Hash computationBucket lookupInternal object handlingArray indexing is faster because it directly accesses memory.Optimized Java Solutionclass Solution { public String mapWordWeights(String[] words, int[] weights) { StringBuilder answer = new StringBuilder(); for(String word : words) { int sum = 0; for(char ch : word.toCharArray()) { sum += weights[ch - 'a']; } int mod = sum % 26; answer.append((char)('z' - mod)); } return answer.toString(); }}Dry RunInputwords = ["abcd"]Assume:a = 7b = 5c = 3d = 4Calculate Weight7 + 5 + 3 + 4 = 19Apply Modulo19 % 26 = 19Reverse Mapping0 → z1 → y2 → x...19 → gResult:"g"Complexity AnalysisHashMap SolutionTime ComplexityO(T)where T is the total number of characters across all words.Space ComplexityO(1)Only fixed-size maps of 26 elements are stored.Optimized Array SolutionTime ComplexityO(T)Space ComplexityO(1)No additional data structures are required.Which Solution Should You Use?ApproachTimeSpaceInterview PreferenceHashMapO(T)O(1)GoodDirect ArrayO(T)O(1)BestBoth solutions are efficient.However, the array-based approach is typically preferred in coding interviews because:Simpler implementationFaster executionLower memory overheadNo unnecessary hashingInterview DiscussionA common follow-up question is:Can we eliminate both HashMaps?Yes.Since:'a' to 'z'are contiguous ASCII characters, we can directly compute:weights[ch - 'a']Similarly:(char)('z' - mod)can generate the reverse mapping without storing another lookup table.This reduces code complexity while maintaining the same asymptotic performance.Key TakeawaysFixed-size alphabets often allow array-based optimizations.HashMaps improve readability but may not always be necessary.Modular arithmetic is useful for reducing values into a bounded range.Character arithmetic can replace lookup tables in many string problems.Always look for opportunities to replace generic data structures with direct indexing when the input domain is small and fixed.ConclusionLeetCode 3838: Weighted Word Mapping is an excellent beginner-friendly problem that demonstrates the practical use of hashing, modular arithmetic, and character manipulation.While a HashMap-based solution is intuitive and easy to understand, recognizing that the alphabet size is fixed allows us to develop a cleaner and more optimized array-based solution.Understanding both approaches not only helps solve this problem efficiently but also strengthens the problem-solving mindset needed for technical interviews and competitive programming.

LeetCodeEasyArrayHashMapStringFrequencyJava