Search Blogs

Showing results for "Brute Force Solution"

Found 50 results

LeetCode 110: Balanced Binary Tree – Java Optimized DFS Solution Explained

IntroductionLeetCode 110 – Balanced Binary Tree is one of the most important binary tree interview problems.This problem teaches:Tree recursionHeight calculationDepth First Search (DFS)Bottom-up recursionOptimization techniquesIt is frequently asked in coding interviews because it checks whether you can:Traverse trees efficientlyAvoid repeated calculationsCombine recursion with conditionsOptimize brute force tree solutionsThis problem is also a foundation for advanced tree problems like:AVL TreesHeight-balanced treesDiameter of Binary TreeTree DP problemsProblem Link🔗 https://leetcode.com/problems/balanced-binary-tree/Problem StatementGiven the root of a binary tree:Return:trueif the tree is:height-balancedOtherwise return:falseWhat is a Balanced Binary Tree?A binary tree is balanced if:For every node,|height(left subtree) - height(right subtree)| <= 1Meaning:Left and right subtree heights should not differ by more than:1Example 1Inputroot = [3,9,20,null,null,15,7]Tree:3/ \9 20/ \15 7OutputtrueExplanation:Every node satisfies:height difference <= 1Example 2Inputroot = [1,2,2,3,3,null,null,4,4]Tree:1/ \2 2/ \3 3/ \4 4OutputfalseExplanation:Left subtree becomes much deeper than right subtree.Difference becomes greater than:1Key ObservationTo determine if tree is balanced:At every node we need:Height of left subtreeHeight of right subtreeCompare differenceThis naturally becomes a recursive DFS problem.Brute Force ApproachIntuitionFor every node:Calculate left heightCalculate right heightCompare differenceRecursively check childrenBrute Force Java Solutionclass Solution {public int height(TreeNode root) {if(root == null)return 0;return 1 + Math.max(height(root.left), height(root.right));}public boolean isBalanced(TreeNode root) {if(root == null)return true;int left = height(root.left);int right = height(root.right);if(Math.abs(left - right) > 1)return false;return isBalanced(root.left) && isBalanced(root.right);}}Problem with Brute ForceThe height function gets called repeatedly.For every node:Heights are recalculated again and again.This increases complexity significantly.Brute Force ComplexityTime ComplexityO(N²)because height calculation repeats.Space ComplexityO(H)for recursion stack.Optimized DFS ApproachInstead of:Calculating heights separatelyWe can:Calculate height and balance together.Core Optimization IdeaWhile calculating height:If subtree becomes unbalanced:Return negative value immediatelyThis avoids unnecessary computation.Optimized Java Solutionclass Solution {public int solve(TreeNode roo) {if(roo == null)return 0;int left = solve(roo.left);if(left < 0) {return -1;}int right = solve(roo.right);if(right < 0) {return -1;}if(Math.abs(left - right) > 1) {return -1000;}return 1 + Math.max(left, right);}public boolean isBalanced(TreeNode root) {int ans = solve(root);return ans < 0 ? false : true;}}Cleaner Optimized VersionWe can simplify negative returns using:-1consistently.Cleaner Java Solutionclass Solution {public int height(TreeNode root) {if(root == null)return 0;int left = height(root.left);if(left == -1)return -1;int right = height(root.right);if(right == -1)return -1;if(Math.abs(left - right) > 1)return -1;return 1 + Math.max(left, right);}public boolean isBalanced(TreeNode root) {return height(root) != -1;}}Why This WorksAt every node:Recursively calculate left heightRecursively calculate right heightIf difference > 1:Tree is unbalancedPropagate failure upward immediately.Dry RunInput1/ \2 2/ \3 3/ \4 4Step 1Start from leaf nodes:4 → height = 1Step 2Node:3gets:left = 1right = 1Difference:0Balanced.Height:2Step 3At node:2Left height:2Right height:0Difference:2Unbalanced.Return:-1Final ResultTree is:Not balancedReturn:falseTime Complexity AnalysisOptimized DFS SolutionTime ComplexityO(N)because every node is visited once.Space ComplexityO(H)where:H = height of treeWorst case:O(N)for skewed tree.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(H)Optimized DFSO(N)O(H)Interview ExplanationIn interviews, explain:Instead of recalculating heights repeatedly, we combine height calculation and balance checking into a single DFS traversal.This demonstrates:Optimization skillsRecursive DFS understandingBottom-up tree processingCommon Mistakes1. Recalculating Heights RepeatedlyThis causes:O(N²)complexity.2. Forgetting Absolute DifferenceAlways use:Math.abs(left - right)3. Not Handling Null NodesBase case:if(root == null)return 0;is necessary.FAQsQ1. What is a balanced binary tree?A tree where left and right subtree heights differ by at most:1for every node.Q2. Why use DFS?Because height calculation naturally follows recursive depth traversal.Q3. Why return -1?It acts as a signal:Subtree already unbalancedQ4. Is this problem important for interviews?Very important.It is one of the most common tree optimization questions.ConclusionLeetCode 110 is an excellent binary tree optimization problem.It teaches:DFS traversalHeight calculationBottom-up recursionOptimization techniquesThe key insight is:Combine balance checking and height calculation in one DFS traversal.Once you understand this optimization pattern, many advanced tree problems become much easier.

LeetCodeBalanced Binary TreeJavaBinary TreeDFSTree HeightRecursionTree

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

LeetCode 3751: Total Waviness of Numbers in Range I – Java Solution with Dry Run and Explanation

IntroductionLeetCode 3751 introduces an interesting digit-based pattern problem where we calculate the total waviness of numbers inside a given range.This problem combines:Digit traversalPattern recognitionPeaks and valleys logicString manipulationBrute force iterationThe problem is straightforward once we clearly understand how peaks and valleys work.Problem StatementYou are given two integers:num1 and num2representing the inclusive range:[num1, num2]For every number:A digit is called a peak if it is strictly greater than both neighbors.A digit is called a valley if it is strictly smaller than both neighbors.The first and last digits can never be peaks or valleys.Return the total waviness across all numbers in the range.ExampleInputnum1 = 120num2 = 130Output3ExplanationNumbers contributing to waviness:120 → 2 is a peak → waviness = 1121 → 2 is a peak → waviness = 1130 → 3 is a peak → waviness = 1Total:1 + 1 + 1 = 3Understanding Peaks and ValleysPeak ConditionA digit is a peak if:digit > left neighborANDdigit > right neighborExample:484Here:8 > 48 > 4So 8 is a peak.Valley ConditionA digit is a valley if:digit < left neighborANDdigit < right neighborExample:202Here:0 < 20 < 2So 0 is a valley.Key ObservationWe only need to check:index 1 to length-2because:First digit has no left neighborLast digit has no right neighborIntuitionThe simplest way:Iterate through every number in the rangeConvert number into charactersCheck each middle digitCount peaks and valleysAdd to final answerSince constraints are small:num2 <= 10^5a brute force approach works efficiently.Java Solutionclass Solution { public int totalWaviness(int num1, int num2) { int ans = 0; if(num1 == num2) { int temp = num1; String c = Integer.toString(temp); char[] arr = c.toCharArray(); for(int i = 1; i < arr.length - 1; i++) { if((arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) || (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])) { ans++; } } return ans; } for(int i = num1; i <= num2; i++) { String c = Integer.toString(i); char[] carr = c.toCharArray(); for(int j = 1; j < carr.length - 1; j++) { if((carr[j] < carr[j - 1] && carr[j] < carr[j + 1]) || (carr[j] > carr[j - 1] && carr[j] > carr[j + 1])) { ans++; } } } return ans; }}Step-by-Step ExplanationStep 1: Iterate Through Rangefor(int i = num1; i <= num2; i++)Process every number.Step 2: Convert Number to Character ArrayString c = Integer.toString(i);char[] carr = c.toCharArray();This makes digit comparison easier.Step 3: Check Middle Digitsfor(int j = 1; j < carr.length - 1; j++)Skip first and last digits.Step 4: Check Peak or Valley(carr[j] < carr[j-1] && carr[j] < carr[j+1])OR(carr[j] > carr[j-1] && carr[j] > carr[j+1])If true:ans++;Dry RunInputnum1 = 198num2 = 202Number 198Digits:1 9 8Check 9:9 > 19 > 8Peak found.Waviness:1Number 1991 9 99 is not strictly greater than right neighbor.No waviness.Number 2012 0 10 is smaller than both neighbors.Valley found.Number 2022 0 2Again:0 < 20 < 2Valley found.Final Answer198 → 1201 → 1202 → 1Total = 3Time Complexity AnalysisLet:N = num2 - num1 + 1D = number of digitsTime ComplexityO(N × D)At most:D = 6which is very small.Efficient for constraints.Space ComplexityO(D)due to character array conversion.Why Brute Force Works HereConstraints are small:num2 <= 100000So checking every number directly is acceptable.For larger constraints:Digit DP would be needed.But here:Simplicity is better.Common Mistakes1. Including First or Last DigitThese digits cannot be peaks or valleys.2. Using Non-Strict ComparisonWrong:>=<=Correct:><because definition says:strictly greaterstrictly smaller3. Forgetting Both ConditionsNeed to check:PeakValleyEdge CasesSingle Digit NumbersWaviness:0because fewer than 3 digits.Repeated DigitsExample:111No peak or valley.Alternating DigitsExample:4848Produces multiple waviness counts.Interview ExplanationIn interviews explain:Since the constraints are small, we can directly iterate through every number, convert it into digits, and count peaks and valleys by checking neighboring digits.This demonstrates:Observation skillsConstraint analysisClean implementationConclusionLeetCode 3751 is a clean implementation problem focused on:Digit traversalPattern recognitionPeaks and valleysBrute force optimizationThe key insight is:A digit contributes to waviness only if it is strictly greater or strictly smaller than both immediate neighbors.Once this condition is understood, the implementation becomes very straightforward.

LeetCodeJavaStringPeaks and ValleysBrute Force SolutionDigit ProblemsMediumArray

LeetCode 230: Kth Smallest Element in a BST – Java Recursive Inorder Traversal Solution

IntroductionLeetCode 230 – Kth Smallest Element in a BST is one of the most important Binary Search Tree interview problems.This question is popular because it tests:BST propertiesInorder traversalDFS recursionTree traversal optimizationRecursive state managementUnderstanding this problem properly builds a strong foundation for advanced BST problems.Problem Link🔗 https://leetcode.com/problems/kth-smallest-element-in-a-bst/Problem StatementGiven:Root of a Binary Search TreeInteger kReturn:The kth smallest value in the BSTThe indexing is:1-indexedExample 1Inputroot = [3,1,4,null,2]k = 1Output1ExplanationBST inorder traversal becomes:[1,2,3,4]1st smallest element is:1Example 2Inputroot = [5,3,6,2,4,null,null,1]k = 3Output3Key ObservationThe most important BST property:Inorder Traversal of BST gives sorted orderExample:5/ \3 6/ \2 4/1Inorder traversal:1 → 2 → 3 → 4 → 5 → 6So:kth smallest = kth node in inorder traversalIntuitionWe perform:Left → Root → RightWhile traversing:Keep counting visited nodesWhen count becomes kStore answerNo need to traverse entire tree after finding answer.Brute Force ApproachIdeaStore complete inorder traversal in listReturn:list.get(k - 1)Brute Force Java Solutionclass Solution {public void inorder(TreeNode root, List<Integer> list) {if(root == null) return;inorder(root.left, list);list.add(root.val);inorder(root.right, list);}public int kthSmallest(TreeNode root, int k) {List<Integer> list = new ArrayList<>();inorder(root, list);return list.get(k - 1);}}Complexity of Brute ForceTime ComplexityO(N)Space ComplexityO(N)Extra list storage required.Optimized Recursive ApproachIdeaInstead of storing entire traversal:Maintain counterStop when kth node is reachedThis saves unnecessary storage.Java Solutionclass Solution {int coun = 0;int ans = -1;public void inorder(TreeNode root, int k, List<Integer> lis) {if(root == null) return;inorder(root.left, k, lis);coun++;if(coun == k) {ans = root.val;return;}inorder(root.right, k, lis);}public int kthSmallest(TreeNode root, int k) {List<Integer> lis = new ArrayList<>();inorder(root, k, lis);return ans;}}Cleaner Optimized Versionclass Solution {int count = 0;int answer = -1;public void inorder(TreeNode root, int k) {if(root == null) return;inorder(root.left, k);count++;if(count == k) {answer = root.val;return;}inorder(root.right, k);}public int kthSmallest(TreeNode root, int k) {inorder(root, k);return answer;}}Why This WorksBST inorder traversal always visits nodes in:sorted ascending orderSo:1st visited node = smallest2nd visited node = second smallestkth visited node = kth smallestDry RunInputroot = [5,3,6,2,4,null,null,1]k = 3BST Structure5/ \3 6/ \2 4/1Inorder Traversal1 → 2 → 3 → 4 → 5 → 6Counter ProgressNodeCount112233At count = 3:answer = 3Final Output3Iterative Stack ApproachIdeaUse explicit stack instead of recursion.Iterative Java Solutionclass Solution {public int kthSmallest(TreeNode root, int k) {Stack<TreeNode> stack = new Stack<>();while(true) {while(root != null) {stack.push(root);root = root.left;}root = stack.pop();k--;if(k == 0) {return root.val;}root = root.right;}}}Time Complexity AnalysisOptimized RecursiveTime ComplexityO(H + k)Where:H = tree heightWe visit only required nodesWorst case:O(N)Space ComplexityO(H)Recursive stack space.Iterative ComplexityTime ComplexityO(H + k)Space ComplexityO(H)Stack space.Follow-Up OptimizationProblem Follow-UpWhat if BST changes frequently?Example:Insert operationsDelete operationsFrequent kth smallest queriesAdvanced OptimizationStore:size of subtreeinside every node.This allows:O(log N)kth smallest queries.This concept is used in:Order Statistic TreesAugmented BSTsIndexed TreesInterview ExplanationIn interviews, explain:Inorder traversal of a BST gives nodes in sorted order. Therefore, the kth visited node during inorder traversal is the kth smallest element.This demonstrates:BST understandingDFS recursionTree traversal masteryOptimization thinkingCommon Mistakes1. Forgetting BST PropertyThis solution works because BST inorder traversal is sorted.Not true for normal binary trees.2. Using Extra Array UnnecessarilyOptimized approach avoids storing entire traversal.3. Incorrect Counter PlacementCounter must increase:AFTER left traversalBEFORE right traversal4. Forgetting Early ReturnOnce kth element is found:answer should be stored immediatelyFAQsQ1. Why does inorder traversal work?Because BST inorder traversal produces sorted order.Q2. Can this be solved iteratively?Yes.Using stack-based inorder traversal.Q3. Why is BST important here?Without BST ordering property:kth smallest cannot be determined using inorderQ4. Is this frequently asked?Yes.It is one of the most common BST interview questions.ConclusionLeetCode 230 is an excellent BST problem for mastering:Inorder traversalBST propertiesDFS recursionStack traversalTree optimizationThe core insight is:Inorder traversal of a BST always produces sorted order.Once this concept becomes intuitive, many BST interview problems become much easier.

LeetCodeKth Smallest Element in BSTBinary Search TreeJavaInorder TraversalBSTMedium

Inorder Successor in BST – Java Optimized BST Solution with Dry Run

IntroductionThe Inorder Successor in BST problem is one of the most important Binary Search Tree interview questions asked in coding interviews and online coding platforms like GeeksforGeeks.This problem tests your understanding of:Binary Search Tree propertiesInorder traversalRecursive searchingTree optimization techniquesSuccessor logic in BSTUnderstanding this problem properly helps in solving many advanced BST questions efficiently.Problem Link🔗 GeeksforGeeks – Inorder Successor in BSTProblem StatementGiven:A Binary Search TreeA reference node kFind the:Inorder Successorof that node.What is Inorder Successor?The inorder successor of a node is:The next greater node in the inorder traversal of the BST.Example 1Inputroot = [2,1,3]k = 2Inorder Traversal1 2 3Output3Example 2Inputroot = [20,8,22,4,12,null,null,null,null,10,14]k = 8Inorder Traversal4 8 10 12 14 20 22Output10Key BST ObservationIn a BST:Left subtree -> smaller valuesRight subtree -> greater valuesThe inorder traversal of BST is always:Sorted orderThis property helps us optimize the search.IntuitionSuppose:k = 8and current node is:20Since:20 > 8this node can potentially be the inorder successor.But there may exist a smaller valid successor in the left subtree.So:Store current node as possible answerMove leftBrute Force ApproachIdeaPerform inorder traversalStore traversal in listFind node kReturn next elementBrute Force Java Solutionclass Solution { List<Integer> inorder = new ArrayList<>(); void traverse(Node root) { if(root == null) return; traverse(root.left); inorder.add(root.data); traverse(root.right); } public int inOrderSuccessor(Node root, Node k) { traverse(root); for(int i = 0; i < inorder.size() - 1; i++) { if(inorder.get(i) == k.data) { return inorder.get(i + 1); } } return -1; }}Brute Force ComplexityTime ComplexityO(N)Space ComplexityO(N)because of traversal list.Optimized BST ApproachInstead of traversing the entire tree:Use BST propertiesReduce unnecessary traversalSearch efficientlyOptimized Java Solutionclass Solution { int c = -1; int solve(Node root, Node x, int c) { if(root == null) return c; if(root.data > x.data) { c = root.data; return solve(root.left, x, c); } else { return solve(root.right, x, c); } } public int inOrderSuccessor(Node root, Node k) { return solve(root, k, c); }}How This Solution WorksWhenever:root.data > k.datathe current node becomes a possible successor candidate.But there may exist a smaller valid successor in the left subtree.So:Store current nodeMove leftWhy Move Right Otherwise?If:root.data <= k.datathen current node cannot be successor.Move right to search for larger values.Dry RunInput 20 / \ 8 22 / \ 4 12 / \ 10 14k = 8Step 1Current node:20Since:20 > 8possible successor:20Move left.Step 2Current node:8Since:8 <= 8Move right.Step 3Current node:12Since:12 > 8update successor:12Move left.Step 4Current node:10Since:10 > 8update successor:10Move left.Step 5Node becomes null.Return:10Final Answer10Alternative Inorder Traversal ApproachAnother common approach:Perform inorder traversalTrack previous nodeWhen previous node becomes k, current node is successorAlternative Recursive Solutionclass Solution { Node prev = null; Node succ = null; void solve(Node root, Node k) { if(root == null || succ != null) return; solve(root.left, k); if(prev != null && prev.data == k.data) { succ = root; } prev = root; solve(root.right, k); } public int inOrderSuccessor(Node root, Node k) { solve(root, k); return succ != null ? succ.data : -1; }}Time Complexity AnalysisOptimized BST SolutionBest CaseO(log N)Balanced BST.Worst CaseO(N)Skewed BST.Space ComplexityRecursive StackO(H)where:H = height of treeInterview ExplanationIn interviews explain:Whenever we encounter a node greater than k, it becomes a possible inorder successor candidate. Then we move left to search for a smaller valid successor.This demonstrates:BST optimization understandingRecursive traversal logicEfficient searching skillsCommon Mistakes1. Traversing Entire Tree UnnecessarilyBST property already reduces search space.2. Returning First Greater NodeNeed the:smallest greater nodenot any greater node.3. Forgetting Candidate UpdateAlways update candidate before moving left.4. Confusing Floor/Ceil LogicSuccessor logic is different from:FloorCeilPredecessorFAQsQ1. What is inorder successor?The next greater node in inorder traversal.Q2. Why BST helps optimization?BST ordering allows skipping unnecessary branches.Q3. Can inorder successor be absent?Yes.If node is largest element, answer is:-1Q4. Can this be solved iteratively?Yes.Iterative solution is also common in interviews.Related BST ProblemsPractice these next:Search in BSTCeil in BSTFloor in BSTValidate BSTLowest Common Ancestor in BSTKth Smallest Element in BSTConclusionInorder Successor in BST is a very important interview problem because it teaches:BST optimizationRecursive searchingSuccessor logicTree traversal efficiencyThe key idea is:Whenever a node is greater than k, it becomes a possible successor candidate, but a smaller valid successor may still exist in the left subtree.Mastering this logic makes advanced BST problems significantly easier.

BSTGFGTreeBinary Search TreeJavaTree TraversalRecursionEasy

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

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

MediumLeetCodeJavaArrayBinary SearchTwo Pointer

LeetCode 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

LeetCode 2126: Destroying Asteroids – Java Greedy Algorithm Solution with Dry Run

IntroductionLeetCode 2126 – Destroying Asteroids is a classic greedy algorithm problem that tests your ability to:Recognize optimal orderingUse sorting effectivelyApply greedy decision-makingHandle large integer growthUnderstand simulation problemsThis is a very interview-friendly problem because the optimal strategy is not immediately obvious.Problem Link🔗 https://leetcode.com/problems/destroying-asteroids/Problem StatementYou are given:An integer mass representing the planet’s initial massAn array asteroidsRules:If planet mass ≥ asteroid mass → asteroid is destroyedPlanet gains asteroid massOtherwise → planet gets destroyedReturn:true -> if all asteroids can be destroyedfalse -> otherwiseExampleInputmass = 10asteroids = [3,9,19,5,21]OutputtrueKey ObservationThe most important insight:Destroy smaller asteroids first.Why?Because every destroyed asteroid increases planet mass.So destroying smaller asteroids early helps you grow enough to destroy larger ones later.IntuitionSuppose:mass = 5asteroids = [100,1,2]If you attack:100 firstYou instantly lose.But if you destroy:1 → 2Your mass becomes:5 + 1 + 2 = 8Still not enough for 100.So answer remains false.This demonstrates:Ordering matters.Greedy StrategyThe optimal strategy is:Step 1Sort asteroids in ascending order.Step 2Destroy the smallest asteroid possible first.Step 3Keep increasing mass.Why Sorting WorksIf you cannot destroy the smallest remaining asteroid:You definitely cannot destroy larger asteroids either.That is why sorting guarantees the optimal greedy order.Java Solutionclass Solution { public boolean asteroidsDestroyed(int mass, int[] asteroids) { Arrays.sort(asteroids); if(mass >= asteroids[asteroids.length - 1]) { return true; } for(int i = 0; i < asteroids.length; i++) { if(mass >= asteroids[asteroids.length - 1]) { return true; } if(asteroids[i] <= mass) { mass += asteroids[i]; } if(mass < asteroids[i]) { return false; } } return true; }}Cleaner Optimized VersionOne important improvement:Use long instead of int.Why?Because mass can grow very large.Optimized Java Solutionclass Solution { public boolean asteroidsDestroyed(int mass, int[] asteroids) { Arrays.sort(asteroids); long currentMass = mass; for(int asteroid : asteroids) { if(currentMass < asteroid) { return false; } currentMass += asteroid; } return true; }}Why Use Long?Constraints allow:1 <= asteroids.length <= 1000001 <= asteroid[i] <= 100000Mass can exceed:Integer.MAX_VALUEUsing long prevents overflow issues.Dry RunInputmass = 10asteroids = [3,9,19,5,21]Step 1: Sort[3,5,9,19,21]Step 2: Destroy AsteroidsDestroy 310 >= 3mass = 13Destroy 513 >= 5mass = 18Destroy 918 >= 9mass = 27Destroy 1927 >= 19mass = 46Destroy 2146 >= 21mass = 67All asteroids destroyed.Final OutputtrueBrute Force ApproachA brute force approach would try:All possible asteroid ordersThis means:N! permutationsWhich is impossible for:N = 100000So brute force is completely infeasible.Why Greedy Is OptimalGreedy works because:Smaller asteroids are easiest to destroyThey increase massIncreased mass helps destroy bigger asteroidsThis creates a natural optimal progression.Time Complexity AnalysisSortingO(N log N)TraversalO(N)Total Time ComplexityO(N log N)Space ComplexityO(1)Ignoring sorting space.Interview ExplanationIn interviews, explain:Since destroying an asteroid increases our mass, the optimal strategy is to destroy smaller asteroids first. Sorting ensures we always maximize future growth opportunities.This demonstrates:Greedy thinkingSorting optimizationSimulation handlingProof of correctnessCommon Mistakes1. Not SortingWithout sorting:You may attempt larger asteroids too early.2. Using int Instead of longMass can overflow.Always use:long currentMass3. Brute Force PermutationsTrying all orders leads to:O(N!)which is impossible.4. Incorrect Early ReturnYour logic should only fail when:currentMass < asteroidFAQsQ1. Why is sorting necessary?Sorting guarantees we always destroy the smallest possible asteroid first.Q2. Is this a greedy problem?Yes.The optimal local decision:Destroy smallest asteroid firstleads to global optimality.Q3. Why use long?Because mass can grow beyond integer limits.Q4. Is this asked in interviews?Yes.It is a common greedy + sorting interview problem.ConclusionLeetCode 2126 is an excellent greedy problem for mastering:Sorting-based optimizationGreedy decision-makingSimulation problemsOverflow handlingInterview reasoningThe key insight is:Always destroy smaller asteroids first to maximize future mass growth.Once this greedy intuition becomes natural, many scheduling and optimization problems become easier to solve.

LeetCodeGreedy AlgorithmJavaSortingArrayMedium

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

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

StringStackMediumLeetCode

LeetCode 3120: Count the Number of Special Characters I – Java HashSet Solution Explained

IntroductionLeetCode 3120 – Count the Number of Special Characters I is a beginner-friendly string and hashing problem.This problem focuses on:Character manipulationUppercase and lowercase conversionHashSet usageString traversalBasic optimization techniquesIt is a good interview problem for testing:Understanding of ASCII charactersJava Character methodsSet operationsProblem-solving logicProblem Link🔗 https://leetcode.com/problems/count-the-number-of-special-characters-i/Problem StatementYou are given a string:wordA character is called:specialif it appears in both:LowercaseUppercaseReturn:Total number of special charactersExample 1Inputword = "aaAbcBC"Output3ExplanationCharacters:'a' and 'A''b' and 'B''c' and 'C'All appear in both cases.So answer is:3Example 2Inputword = "abc"Output:0No uppercase letters exist.Example 3Inputword = "abBCab"Output:1Only:'b' and 'B'appear in both forms.IntuitionWe need to check:For every lowercase character:Does its uppercase version exist?Using HashSet makes lookup very fast.Brute Force ApproachIdeaFor every character:Traverse entire stringSearch for uppercase/lowercase pairCount valid matchesBrute Force ComplexityTime ComplexityO(N²)because nested traversal is required.Space ComplexityO(1)Optimized HashSet ApproachIdeaUse two sets:One for lowercase lettersOne for uppercase lettersThen check matching pairs.Java Solutionclass Solution {public int numberOfSpecialChars(String word) {HashSet<Character> lower = new HashSet<>();HashSet<Character> upper = new HashSet<>();for(int i = 0; i < word.length(); i++) {if(word.charAt(i) >= 'a' && word.charAt(i) <= 'z') {lower.add(word.charAt(i));}else {upper.add(word.charAt(i));}}int ans = 0;for(int i = 0; i < word.length(); i++) {char up = Character.toUpperCase(word.charAt(i));if(lower.contains(word.charAt(i)) && upper.contains(up)) {ans++;lower.remove(word.charAt(i));upper.remove(up);}}return ans;}}Cleaner Optimized Versionclass Solution {public int numberOfSpecialChars(String word) {HashSet<Character> lower = new HashSet<>();HashSet<Character> upper = new HashSet<>();for(char ch : word.toCharArray()) {if(Character.isLowerCase(ch)) {lower.add(ch);}else {upper.add(ch);}}int count = 0;for(char ch : lower) {if(upper.contains(Character.toUpperCase(ch))) {count++;}}return count;}}Why This WorksWe separate:Lowercase charactersUppercase charactersThen for every lowercase letter:We check whether uppercase version exists.HashSet lookup works in:O(1)average time.Dry RunInputword = "aaAbcBC"Step 1Lowercase set:[a, b, c]Uppercase set:[A, B, C]Step 2Check:'a' → 'A' exists'b' → 'B' exists'c' → 'C' existsCount becomes:3Final Answer3Time Complexity AnalysisOptimized HashSet SolutionTime ComplexityO(N)because string traversal happens only once.Space ComplexityO(1)Maximum alphabet size is fixed:26 lowercase + 26 uppercaseBrute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(1)HashSet ApproachO(N)O(1)Interview ExplanationIn interviews, explain:We use two HashSets to separately store lowercase and uppercase letters. Then we check whether a lowercase character has its uppercase counterpart.This demonstrates:Efficient lookup usageHashing knowledgeCharacter manipulation skillsCommon Mistakes1. Double Counting CharactersWithout removing counted characters:same letter may be counted multiple times2. Forgetting Case ConversionAlways convert:Character.toUpperCase(ch)before comparison.3. Using Nested Loops UnnecessarilyHashSet reduces lookup complexity significantly.FAQsQ1. Why use HashSet?Because lookup operations are very fast.Q2. Can this be solved without extra space?Yes.Using arrays of size 26 is also possible.Q3. Why remove characters after counting?To avoid duplicate counting.Q4. Is this problem important for interviews?Yes.It tests:String handlingCharacter conversionHashSet usageOptimization thinkingRelated ProblemsPractice these next:Valid AnagramFirst Unique Character in a StringRansom NoteConclusionLeetCode 3120 is a simple but effective problem for learning:HashSet operationsString traversalCase conversionEfficient lookup techniquesThe key idea is:Store lowercase and uppercase letters separately, then check matching pairs efficiently.Once this pattern becomes clear, many string hashing problems become much easier.

LeetCodeJavaHashSetStringEasy

LeetCode 3121: Count the Number of Special Characters II – Java HashMap Solution Explained

IntroductionLeetCode 3121 – Count the Number of Special Characters II is an interesting string and hashing problem that extends the logic of the previous Special Characters problem.This problem tests:Character indexingString traversalHashMap usageUppercase and lowercase handlingOrder-based conditionsUnlike Part I, this version adds an important restriction:Every lowercase occurrence must appear before the first uppercase occurrence.This additional condition makes the problem more challenging and interview-relevant.Problem Link🔗 https://leetcode.com/problems/count-the-number-of-special-characters-ii/Problem StatementYou are given a string:wordA character is called:specialif:It appears in both lowercase and uppercaseEvery lowercase occurrence appears before the first uppercase occurrenceReturn:Number of special charactersExample 1Inputword = "aaAbcBC"Output3ExplanationSpecial characters:'a''b''c'because:Lowercase letters appear firstUppercase letters appear laterExample 2Inputword = "abc"Output:0No uppercase letters exist.Example 3Inputword = "AbBCab"Output:0Explanation:Lowercase letters appear after uppercase letters.Condition fails.Key ObservationFor a character to be special:Last lowercase index < First uppercase indexThis is the entire logic of the problem.IntuitionWe need two pieces of information.For every character:Last occurrence of lowercase letterFirst occurrence of uppercase letterIf:lastLowercase < firstUppercasethen character is special.Brute Force ApproachIdeaFor every character:Traverse entire stringFind lowercase occurrencesFind uppercase occurrencesVerify ordering conditionBrute Force ComplexityTime ComplexityO(N²)because repeated traversal is required.Space ComplexityO(1)Optimized HashMap ApproachIdeaUse two HashMaps:Lowercase map stores last indexUppercase map stores first indexThen compare indices.Java Solutionclass Solution { public int numberOfSpecialChars(String word) { HashMap<Character, Integer> lower = new HashMap<>(); HashMap<Character, Integer> upper = new HashMap<>(); for(int i = 0; i < word.length(); i++) { if(word.charAt(i) >= 'a' && word.charAt(i) <= 'z') { lower.put(word.charAt(i), i); } else { if(!upper.containsKey(word.charAt(i))) { upper.put(word.charAt(i), i); } } } int ans = 0; for(int i = 0; i < word.length(); i++) { char up = Character.toUpperCase(word.charAt(i)); if(lower.containsKey(word.charAt(i)) && upper.containsKey(up)) { if(lower.get(word.charAt(i)) < upper.get(up)) { ans++; lower.remove(word.charAt(i)); upper.remove(up); } } } return ans; }}Cleaner Optimized Versionclass Solution { public int numberOfSpecialChars(String word) { int[] lastLower = new int[26]; int[] firstUpper = new int[26]; Arrays.fill(lastLower, -1); Arrays.fill(firstUpper, Integer.MAX_VALUE); for(int i = 0; i < word.length(); i++) { char ch = word.charAt(i); if(Character.isLowerCase(ch)) { lastLower[ch - 'a'] = i; } else { firstUpper[ch - 'A'] = Math.min(firstUpper[ch - 'A'], i); } } int count = 0; for(int i = 0; i < 26; i++) { if(lastLower[i] != -1 && firstUpper[i] != Integer.MAX_VALUE && lastLower[i] < firstUpper[i]) { count++; } } return count; }}Why This WorksFor every character:We store:last lowercase positionand:first uppercase positionThen simply check:lastLowercase < firstUppercaseIf true:Character satisfies problem condition.Dry RunInputword = "aaAbcBC"Step 1: Store IndicesLowercase positions:'a' → 1'b' → 3'c' → 4Uppercase positions:'A' → 2'B' → 5'C' → 6Step 2: Compare1 < 2 → valid3 < 5 → valid4 < 6 → validCount becomes:3Final Answer3Time Complexity AnalysisOptimized HashMap SolutionTime ComplexityO(N)because string traversal happens once.Space ComplexityO(1)Maximum alphabet size remains fixed.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(1)HashMap / Array ApproachO(N)O(1)Interview ExplanationIn interviews, explain:A character is special only if its last lowercase occurrence appears before its first uppercase occurrence. We track indices efficiently using HashMaps or arrays.This demonstrates:String manipulation skillsIndex trackingHashing knowledgeOptimization thinkingCommon Mistakes1. Checking Only PresenceMany solutions only verify:lowercase exists && uppercase existsBut ordering condition is also required.2. Storing Wrong IndicesWe need:Last lowercase indexFirst uppercase indexnot the opposite.3. Double Counting CharactersAlways remove counted characters or use controlled traversal.4. Ignoring Case ConversionAlways convert correctly using:Character.toUpperCase(ch)FAQsQ1. Why store last lowercase occurrence?Because all lowercase letters must appear before uppercase.Q2. Why store first uppercase occurrence?Because it defines the earliest uppercase appearance.Q3. Can arrays replace HashMaps?Yes.Arrays are even more optimized because alphabet size is fixed.Q4. Is this problem interview important?Yes.It tests:String traversalIndex trackingCharacter handlingOptimization techniquesRelated ProblemsPractice these next:Count the Number of Special Characters IFirst Unique Character in a StringValid AnagramConclusionLeetCode 3121 is an excellent medium-level hashing and string problem.It teaches:Efficient index trackingHashMap usageOrder-based validationCharacter manipulationThe key insight is:A character is special only if its last lowercase occurrence appears before its first uppercase occurrence.Once this pattern becomes clear, many advanced string indexing problems become much easier.

LeetCodeJavaHashMapStringMedium

LeetCode 387: First Unique Character in a String – Java HashMap Solution Explained

IntroductionLeetCode 387 – First Unique Character in a String is one of the most common beginner-friendly string and hashing interview problems.This problem helps developers understand:Frequency countingHashMap usageString traversalCharacter manipulationEfficient lookup techniquesIt is frequently asked in coding interviews because it tests both:Logical thinkingTime complexity optimizationProblem Link🔗 https://leetcode.com/problems/first-unique-character-in-a-string/Problem StatementGiven a string:sReturn:Index of the first non-repeating characterIf no unique character exists:Return -1Example 1Inputs = "leetcode"Output0Explanation:'l'appears only once and is the first unique character.Example 2Inputs = "loveleetcode"Output2Explanation:'v'is the first character that appears only once.Example 3Inputs = "aabb"Output-1All characters repeat.IntuitionTo identify the first unique character:We first need to know:How many times every character appearsA HashMap is perfect for frequency counting.After counting:We traverse the string again and return the first character whose frequency is:1Brute Force ApproachIdeaFor every character:Traverse the entire stringCount occurrencesReturn the first character with count = 1Brute Force ComplexityTime ComplexityO(N²)because nested traversal is required.Space ComplexityO(1)Optimized HashMap ApproachIdeaUse a HashMap to store:character → frequencyThen scan the string again.The first character with frequency:1is the answer.Java Solutionclass Solution {public int firstUniqChar(String s) {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 < s.length(); i++) {if(mp.get(s.charAt(i)) == 1) {return i;}}return -1;}}Cleaner Optimized Versionclass Solution {public int firstUniqChar(String s) {int[] freq = new int[26];for(char ch : s.toCharArray()) {freq[ch - 'a']++;}for(int i = 0; i < s.length(); i++) {if(freq[s.charAt(i) - 'a'] == 1) {return i;}}return -1;}}Why This WorksThe algorithm works in two passes.First PassStore frequency of every character.Example:"leetcode"Frequency map:l → 1e → 3t → 1c → 1o → 1d → 1Second PassTraverse string from left to right.The first character whose frequency equals:1is returned.Dry RunInputs = "loveleetcode"Step 1: Frequency Countingl → 2o → 2v → 1e → 4t → 1c → 1d → 1Step 2: Traverse AgainIndex 0:'l' → frequency 2Index 1:'o' → frequency 2Index 2:'v' → frequency 1Return:2Time Complexity AnalysisOptimized HashMap SolutionTime ComplexityO(N)because string traversal happens twice.Space ComplexityO(1)Only lowercase English letters exist.Maximum storage remains fixed.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(1)HashMap / Frequency ArrayO(N)O(1)Interview ExplanationIn interviews, explain:We use a frequency map to count occurrences of every character. Then we scan the string again to locate the first character whose frequency is exactly one.This demonstrates:Hashing knowledgeFrequency countingEfficient lookup usageOptimization skillsCommon Mistakes1. Returning Character Instead of IndexThe problem asks for:indexnot the character itself.2. Using Nested LoopsNested traversal increases complexity unnecessarily.3. Forgetting Second TraversalHashMap only stores frequencies.You still need:left-to-right traversalto find the first unique character.FAQsQ1. Why use HashMap?Because frequency lookup becomes very efficient.Q2. Can we use arrays instead?Yes.Since only lowercase letters exist:int[26]works perfectly.Q3. Why traverse the string twice?First pass counts frequency.Second pass preserves original order.Q4. Is this problem important for interviews?Yes.It is one of the most common hashing interview questions.Related ProblemsPractice these next:Valid AnagramRansom NoteCount the Number of Special CharactersConclusionLeetCode 387 is an excellent beginner-level problem for learning:Frequency countingHashMap usageString traversalEfficient lookup techniquesThe key insight is:Count character frequencies first, then find the first character with frequency equal to one.This pattern is widely used in many real interview problems involving strings and hashing.

LeetCodeJavaHashMapStringEasy

LeetCode 543: Diameter of Binary Tree – Java DFS Solution Explained

IntroductionLeetCode 543 – Diameter of Binary Tree is one of the most popular binary tree interview problems.This problem teaches:Depth First Search (DFS)Tree height calculationRecursive traversalBottom-up recursionTree optimization techniquesIt is extremely important because it introduces a very common pattern in tree problems:Use recursion to calculate subtree heights while simultaneously updating a global answer.This same idea is used in:Balanced Binary TreeMaximum Path SumLongest ZigZag PathTree DP problemsProblem Link🔗 https://leetcode.com/problems/diameter-of-binary-tree/Problem StatementGiven the root of a binary tree:Return:Length of the diameter of the treeThe diameter is:The length of the longest path between any two nodes in the tree.This path:May pass through the rootMay not pass through the rootImportant NoteThe diameter is measured in:EDGESnot nodes.Example 1Inputroot = [1,2,3,4,5]Tree: 1 / \ 2 3 / \ 4 5Output3Explanation:Longest path:4 → 2 → 1 → 3Edges count:3Example 2Inputroot = [1,2]Tree: 1 / 2Output:1Understanding DiameterAt every node:Possible longest path through that node is:left subtree height + right subtree heightWhy?Because:One side contributes left edgesOther side contributes right edgesTogether they form a path.Key ObservationFor every node:Diameter through node=leftHeight + rightHeightWe compute this for all nodes.Maximum among them becomes answer.Brute Force ApproachIntuitionFor every node:Calculate left subtree heightCalculate right subtree heightCompute diameterRecursively repeat for childrenBrute Force ComplexityHeight gets recalculated repeatedly.Time ComplexityO(N²)Space ComplexityO(H)where:H = tree heightOptimized DFS ApproachInstead of separately calculating:HeightDiameterWe calculate both in one DFS traversal.Core IdeaWhile calculating subtree height:We also update:max diameterThis avoids repeated traversal.Java Solutionclass Solution { int max = Integer.MIN_VALUE; public int solve(TreeNode roo) { if(roo == null) return 0; int left = solve(roo.left); int right = solve(roo.right); max = Math.max(max, left + right); return 1 + Math.max(left, right); } public int diameterOfBinaryTree(TreeNode root) { solve(root); return max; }}Cleaner Optimized Versionclass Solution { int diameter = 0; public int height(TreeNode root) { if(root == null) return 0; int left = height(root.left); int right = height(root.right); diameter = Math.max(diameter, left + right); return 1 + Math.max(left, right); } public int diameterOfBinaryTree(TreeNode root) { height(root); return diameter; }}Why This WorksAt every node:Find left subtree heightFind right subtree heightCompute:left + rightUpdate global maximum diameterReturn current subtree height upwardDry RunInput 1 / \ 2 3 / \ 4 5Step 1Leaf nodes:4 → height = 15 → height = 13 → height = 1Step 2At node:2Left height:1Right height:1Diameter through node:1 + 1 = 2Update:max = 2Height of node 2:2Step 3At root:1Left height:2Right height:1Diameter:2 + 1 = 3Update:max = 3Final Answer3Recursive Visualizationheight(1) ├── height(2) │ ├── height(4) │ └── height(5) │ └── height(3)Diameter gets updated during return phase.Time Complexity AnalysisOptimized DFS SolutionTime ComplexityO(N)because every node is visited once.Space ComplexityO(H)where:H = tree heightWorst case:O(N)for skewed tree.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(H)Optimized DFSO(N)O(H)Interview ExplanationIn interviews, explain:While recursively calculating subtree heights, we simultaneously compute the maximum possible path passing through every node.This demonstrates:DFS understandingBottom-up recursionOptimization skillsTree DP thinkingCommon Mistakes1. Counting Nodes Instead of EdgesDiameter measures:edgesnot nodes.2. Forgetting Global VariableDiameter must be updated across all nodes.3. Returning Diameter Instead of HeightRecursive function should return:heightnot diameter.FAQsQ1. Does diameter always pass through root?No.It can exist completely inside a subtree.Q2. Why use DFS?Because height calculation naturally follows recursive depth traversal.Q3. Why update diameter globally?Because longest path may occur at any node.Q4. Is this problem important for interviews?Very important.It is one of the most common recursive tree questions.ConclusionLeetCode 543 is one of the best problems for learning recursive tree optimization.It teaches:DFS traversalHeight calculationBottom-up recursionGlobal answer trackingThe key insight is:Diameter through a node equals left subtree height + right subtree height.Once you understand this pattern, many advanced binary tree problems become much easier.

LeetCodeDiameter of Binary TreeJavaBinary TreeDFSTreeRecursionEasy

LeetCode 124: Binary Tree Maximum Path Sum – Java DFS Solution Explained

IntroductionLeetCode 124 – Binary Tree Maximum Path Sum is one of the most important and frequently asked hard-level binary tree interview problems.This problem teaches:Depth First Search (DFS)Bottom-up recursionTree Dynamic ProgrammingRecursive optimizationGlobal answer trackingIt is considered a classic interview problem because it combines:Tree traversalRecursive decision makingPath optimizationNegative value handlingMastering this problem helps in understanding advanced binary tree patterns used in:Diameter problemsTree DPMaximum path problemsGraph recursion problemsProblem Link🔗 https://leetcode.com/problems/binary-tree-maximum-path-sum/Problem StatementGiven the root of a binary tree:Return:Maximum path sum of any non-empty pathA path:Can start from any nodeCan end at any nodeMust follow parent-child connectionsCannot visit a node more than onceImportant:Path does NOT need to pass through rootExample 1Inputroot = [1,2,3]Tree: 1 / \ 2 3Output6Explanation:Best path:2 → 1 → 3Path sum:2 + 1 + 3 = 6Example 2Inputroot = [-10,9,20,null,null,15,7]Tree: -10 / \ 9 20 / \ 15 7Output42Explanation:Best path:15 → 20 → 7Sum:15 + 20 + 7 = 42Key ObservationAt every node:We have two important possibilities.Possibility 1Path continues upward to parent.In this case:We can choose only:ONE sidebecause path cannot split upward.Return value becomes:node + max(left, right)Possibility 2Current node becomes:Highest point of pathThen we can use:left + node + rightThis candidate updates global maximum answer.Core Recursive IdeaAt every node:Calculate left maximum contributionCalculate right maximum contributionIgnore negative pathsUpdate global answerReturn best single-side path upwardWhy Ignore Negative Paths?Negative paths reduce total sum.So:Math.max(path, 0)ensures:Negative contribution is discardedOnly profitable paths are consideredThis is the most important optimization.Your Java Solutionclass Solution { int max = Integer.MIN_VALUE; public int solve(TreeNode roo) { if(roo == null) return 0; int left = Math.max(solve(roo.left), 0); int right = Math.max(solve(roo.right), 0); max = Math.max(max, roo.val + left + right); return roo.val + Math.max(left, right); } public int maxPathSum(TreeNode root) { solve(root); return max; }}Why This WorksFor every node:We calculate:Best path passing through current nodewhich is:left + node + rightThis path may become global maximum.But while returning upward:We can only choose:one directionbecause paths cannot split.Dry RunInput -10 / \ 9 20 / \ 15 7Step 1Leaf nodes:9 → return 915 → return 157 → return 7Step 2At node:20Left:15Right:7Current best path:15 + 20 + 7 = 42Update:max = 42Return upward:20 + max(15,7)= 35Step 3At node:-10Left:9Right:35Candidate:9 + (-10) + 35 = 34Global maximum remains:42Final Answer42Recursive Visualizationsolve(-10) ├── solve(9) │ └── solve(20) ├── solve(15) └── solve(7)Global maximum gets updated during return phase.Brute Force ApproachA brute force approach would:Generate all possible pathsCalculate sumsTrack maximumBut number of paths becomes extremely large.This is inefficient.Brute Force ComplexityTime ComplexityCan become:O(N²)or worse depending on implementation.Optimized DFS ComplexityTime ComplexityO(N)because every node is visited once.Space ComplexityO(H)where:H = height of treeWorst case:O(N)for skewed tree.Important InsightTwo values exist at every node.1. Value Returned UpwardOnly one side allowed:node + max(left, right)2. Value Used for Global MaximumBoth sides allowed:left + node + rightThis distinction is the heart of the problem.Interview ExplanationIn interviews, explain:Every node acts as a potential highest point of a path. We compute the best path through that node while recursively returning the best single-side contribution upward.This demonstrates:Advanced DFS understandingTree DP conceptsRecursive optimizationHandling negative pathsCommon Mistakes1. Returning Both Sides UpwardIncorrect:left + node + rightA path cannot branch upward.2. Forgetting Negative Path HandlingAlways use:Math.max(value, 0)3. Assuming Path Must Pass RootThe path can exist entirely inside a subtree.4. Not Using Global VariableMaximum path may occur anywhere.FAQsQ1. Does path need to start from root?No.It can start and end anywhere.Q2. Why ignore negative sums?Negative paths reduce overall answer.Q3. Why can we return only one side?Because a path moving upward cannot split into two directions.Q4. Is this problem important for interviews?Extremely important.It is one of the most famous hard-level tree problems.Related ProblemsAfter mastering this problem, practice:Diameter of Binary TreeBalanced Binary TreeMaximum Depth of Binary TreeConclusionLeetCode 124 is one of the best problems for learning advanced binary tree recursion.It teaches:DFS optimizationTree dynamic programmingRecursive decision makingNegative path handlingGlobal answer trackingThe key insight is:Every node can become the highest point of a maximum path.Once this recursive pattern becomes clear, many advanced tree and graph problems become much easier to solve.

LeetCodeBinary Tree Maximum Path SumJavaBinary TreeDFSTreeRecursionDynamic Programming on TreesHard

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

Maximum Average Subarray I — Efficient Solution Using Sliding Window (LeetCode 643)

IntroductionLeetCode Problem 643: Maximum Average Subarray I is a classic problem that tests understanding of arrays and the sliding window technique.The task is simple in description but requires optimization to work efficiently for large inputs.We are given:An integer array numsAn integer kWe must find a contiguous subarray of length k that has the maximum average value, and return that average.If you want to try solving the problem yourself before reading further, you can attempt it here:👉 Try the problem on LeetCode: https://leetcode.com/problems/maximum-average-subarray-i/Problem UnderstandingA brute-force solution would compute the sum for every subarray of length k and track the maximum average. However, recalculating sums repeatedly results in O(n × k) time complexity, which becomes inefficient for large arrays.Instead, we can use the sliding window technique to optimize the process.Key Idea: Sliding WindowInstead of recomputing sums:Compute the sum of the first window of size k.Slide the window forward by:Adding the next elementRemoving the element leaving the windowUpdate the maximum average at each step.This reduces time complexity to O(n).ApproachMaintain two pointers representing the window.Keep adding elements until window size becomes k.Compute average and update maximum.Slide the window by removing the left element.Continue until the end of the array.Implementation (Java)class Solution { public double findMaxAverage(int[] nums, int k) { double ans = Integer.MIN_VALUE; int i = 0; int j = 0; int sum = 0; while (j < nums.length) { sum += nums[j]; if (j - i + 1 < k) { j++; } else { ans = Math.max(ans, (double) sum / k); sum -= nums[i]; i++; j++; } } return ans; }}Dry Run ExampleInput:nums = [1,12,-5,-6,50,3], k = 4Windows examined:[1,12,-5,-6] → avg = 0.5[12,-5,-6,50] → avg = 12.75 (maximum)[-5,-6,50,3] → avg = 10.5Maximum average = 12.75Complexity AnalysisTime Complexity: O(n) Each element enters and leaves the window once.Space Complexity: O(1) No extra space is used apart from variables.Edge Cases ConsideredSingle element array (k = 1)All negative numbersLarge input sizeLarge positive or negative valuesWhy Sliding Window MattersSliding window is a crucial technique used in many interview problems:Subarray sum problemsLongest substring problemsFixed or variable window size optimizationsMastering this pattern greatly improves coding interview performance.ConclusionThis problem demonstrates how recognizing patterns like sliding window can transform a slow brute-force solution into an efficient one.If you are preparing for coding interviews, mastering sliding window problems is essential since they appear frequently.

LeetCodeSliding WindowEasy

LeetCode 1665: Minimum Initial Energy to Finish Tasks – Java Greedy Solution Explained

IntroductionLeetCode 1665 – Minimum Initial Energy to Finish Tasks is an important greedy algorithm problem frequently asked in coding interviews.The problem looks difficult initially because tasks can be completed in any order. The real challenge is finding the best order that minimizes the starting energy required.This problem teaches:Greedy strategyCustom sortingOptimization thinkingSimulation techniquesInterview-level problem solvingProblem Link🔗 https://leetcode.com/problems/minimum-initial-energy-to-finish-tasks/Problem StatementYou are given an array:tasks[i] = [actuali, minimumi]Where:actuali = energy spent after completing the taskminimumi = minimum energy required to start the taskYou can complete tasks in any order.Return the minimum initial energy required to finish all tasks.ExampleInput[[1,2],[2,4],[4,8]]Output8Understanding the ProblemSuppose a task is:[4,8]This means:You need at least 8 energy to begin.After completing it, your energy decreases by 4.If your current energy is:10After finishing:10 - 4 = 6Brute Force ApproachIntuitionTry every possible order of tasks and calculate the minimum starting energy needed.Then return the smallest answer.Why Brute Force FailsIf there are N tasks:Total permutations = N!For large constraints up to 10^5, brute force becomes impossible.Brute Force ComplexityTime ComplexityO(N!)Space ComplexityO(N)Greedy IntuitionFor every task:[actual, minimum]The value:minimum - actualrepresents how restrictive the task is.Tasks with larger differences require high starting energy and should be completed earlier.Key Greedy ObservationWe should sort tasks in descending order of:minimum - actualThis minimizes the extra starting energy required later.Why This Greedy WorksSuppose we have:A = [1,10]B = [5,6]Differences:A -> 9B -> 1Task A is more restrictive.If we delay task A, we may lose too much energy before attempting it.So we perform tasks with larger (minimum - actual) first.Optimal Greedy ApproachSteps1. Sort TasksSort tasks by:(minimum - actual) in descending order2. Maintain Current Energycurr = current available energytotal = minimum initial energy required3. Add Energy When NeededIf:minimum > currAdd extra energy.4. Complete the TaskReduce current energy by actual energy spent.Java Greedy Solutionclass Solution { public int minimumEffort(int[][] tasks) { Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]) ); int total = 0; int curr = 0; for (int i = 0; i < tasks.length; i++) { if (tasks[i][1] > curr) { int diff = tasks[i][1] - curr; curr += diff; total += diff; } curr -= tasks[i][0]; } return total; }}Dry RunInput[[1,2],[2,4],[4,8]]Step 1: Sort TasksDifferences:TaskDifference[1,2]1[2,4]2[4,8]4Sorted Order:[[4,8],[2,4],[1,2]]Step 2: Process TasksTask [4,8]Need energy:8Current energy:0Add:8After completion:8 - 4 = 4Task [2,4]Already have enough energy.After completion:4 - 2 = 2Task [1,2]After completion:2 - 1 = 1Final Answer8Time Complexity AnalysisTime ComplexityO(N log N)Sorting dominates the complexity.Space ComplexityO(1)Ignoring sorting space.Interview ExplanationIn interviews, explain:Tasks with larger (minimum - actual) are more restrictive because they require high starting energy. Performing them earlier prevents us from needing larger initial energy later.This demonstrates strong greedy reasoning.Common Mistakes1. Sorting by Minimum OnlyIncorrect because actual energy consumption also matters.2. Sorting by Actual OnlyAlso incorrect.The important factor is:minimum - actual3. Forgetting to Increase Current EnergyAlways check:if(tasks[i][1] > curr)before performing the task.FAQsQ1. Why sort by (minimum - actual)?Because it measures how restrictive a task is.Q2. Is this Dynamic Programming?No.This is a Greedy + Sorting problem.Q3. Why is this problem considered hard?The greedy observation is difficult to identify.The implementation itself is straightforward.ConclusionLeetCode 1665 is an excellent greedy problem for mastering:Custom sortingGreedy intuitionTask schedulingOptimization techniquesThe key idea is sorting tasks by:minimum - actualin descending order.Once this intuition clicks, many advanced greedy interview problems become easier to solve.

LeetCodeGreedy AlgorithmJavaSortingHardArray

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

Climbing Stairs Problem (LeetCode 70) – Complete Guide with Optimized Solutions

IntroductionThe Climbing Stairs problem is one of the most commonly asked coding interview questions for beginners. It is a perfect example to understand recursion, memoization, and dynamic programming (DP).In this article, we will break down the problem step by step and explore multiple approaches—from brute force recursion to an optimized space-efficient solution.Link of Problem: LeetCode – Climbing StairsProblem StatementYou are climbing a staircase that has n steps.Each time, you can either climb 1 step or 2 steps.The goal is to calculate the total number of distinct ways to reach the top.ExampleInput:n = 2Output:2Explanation:1 + 12Input:n = 3Output:3Explanation:1 + 1 + 11 + 22 + 1Key InsightTo reach step n, there are only two possibilities:From step n-1 (taking 1 step)From step n-2 (taking 2 steps)So, the recurrence relation becomes:ways(n) = ways(n-1) + ways(n-2)This is identical to the Fibonacci sequence, making this problem a classic DP question.Approach 1: Recursive Solution (Brute Force)IdeaBreak the problem into smaller subproblems:Count ways to reach n-1Count ways to reach n-2Add both resultsCodeclass Solution { public int climbStairs(int n) { if(n == 0) return 1; if(n < 0) return 0; return climbStairs(n-1) + climbStairs(n-2); }}ComplexityTime Complexity: O(2^n)Space Complexity: O(n)DrawbackThis solution recalculates the same subproblems multiple times, leading to Time Limit Exceeded (TLE) for larger values.Approach 2: Recursion with Memoization (Top-Down DP)IdeaTo optimize recursion, store already computed results using a HashMap.Avoid repeated calculationsConvert exponential time into linear timeCodeimport java.util.HashMap;class Solution { private HashMap<Integer, Integer> memo = new HashMap<>(); public int climbStairs(int n) { if(n == 0) return 1; if(n < 0) return 0; if(memo.containsKey(n)) { return memo.get(n); } int result = climbStairs(n-1) + climbStairs(n-2); memo.put(n, result); return result; }}ComplexityTime Complexity: O(n)Space Complexity: O(n)Why It WorksMemoization ensures each subproblem is solved only once, making recursion efficient and practical.Approach 3: Dynamic Programming (Bottom-Up)IdeaInstead of recursion, build the solution iteratively:Use an array dp[]Store results for each stepBuild from smaller values to larger onesCodeclass Solution { public int climbStairs(int n) { if(n == 1) return n; if(n == 2) return n; if(n == 3) return n; int dp[] = new int[n+1]; dp[0] = 0; dp[1] = 1; dp[2] = 2; for(int i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }}ComplexityTime Complexity: O(n)Space Complexity: O(n)Approach 4: Optimal Solution (Space Optimized)IdeaWe only need the last two values instead of the whole array.Codeclass Solution { public int climbStairs(int n) { if(n <= 2) return n; int prev1 = 1; int prev2 = 2; for(int i = 3; i <= n; i++) { int current = prev1 + prev2; prev1 = prev2; prev2 = current; } return prev2; }}ComplexityTime Complexity: O(n)Space Complexity: O(1)Key TakeawaysThe problem follows a Fibonacci-like patternBrute force recursion is simple but inefficientMemoization converts recursion into an efficient solutionDynamic programming avoids recursion completelySpace optimization reduces memory usage to constant spaceWhen This Problem Is AskedThis question is frequently asked in:Coding interviews (product-based companies)Data Structures & Algorithms examsOnline coding platformsIt evaluates:Problem-solving abilityUnderstanding of recursionOptimization skillsConclusionThe Climbing Stairs problem is a foundational example for learning dynamic programming. Starting with recursion and improving it using memoization and iterative DP demonstrates how to optimize algorithms effectively.Understanding this pattern will help solve many similar problems related to sequences and decision-making.Frequently Asked Questions (FAQs)1. Is this problem related to Fibonacci?Yes, the recurrence relation is exactly the same as the Fibonacci sequence.2. Why does recursion fail for large inputs?Because it recalculates the same values repeatedly, leading to exponential time complexity.3. What is the best approach?The space-optimized approach is the most efficient with O(n) time and O(1) space.

EasyJavaLeetCodeRecursionMemoization

LeetCode 61 Rotate List Java Solution | Brute Force + Optimal Approach Explained (Linked List Rotation)

🚀 IntroductionThe Rotate List problem is a classic linked list question frequently asked in coding interviews.It tests your understanding of:linked list traversalpointer manipulationhandling large constraints efficiently👉 Try the problem yourself: https://leetcode.com/problems/rotate-list/🧠 IntuitionRotating a list means shifting elements to the right.Example:1 → 2 → 3 → 4 → 5, k = 2 → 4 → 5 → 1 → 2 → 3Instead of rotating one by one, we can:either simulate using extra spaceor optimize using pointer manipulation📘 Problem ExplanationYou are given:Head of a linked listInteger kReturn the list after rotating it k times to the right🧩 Approach 1: Brute Force (Array-Based)💡 IdeaStore values in arrayRotate indicesrebuild linked list💻 Java Codeclass Solution { public ListNode rotateRight(ListNode head, int k) { if(head == null) return head; int count = 0; ListNode curr= head; while(curr != null){ count++; curr = curr.next; } curr = head; int[] arr = new int[count]; for(int i =0; i <count;i++){ arr[i] = curr.val; curr = curr.next; } ListNode ans = new ListNode(-1); ListNode finAns = ans; k = k % count; for(int i = 0;i < arr.length;i++){ int ind =(i+(count-k))%arr.length; ans.next = new ListNode(arr[ind]); ans = ans.next; } return finAns.next; }}🔍 Dry Run (Brute Force)Input:[1,2,3,4,5], k = 2Array:[1,2,3,4,5]After rotation logic:[4,5,1,2,3]Rebuild list → ✅ Final Answer⏱️ ComplexityTypeValueTimeO(n)SpaceO(n)⚠️ DrawbackUses extra spaceNot optimal for large inputs⚡ Approach 2: Optimal (Circular Linked List)💡 IdeaInstead of rebuilding:convert list into circularbreak at correct position💻 Java Codeclass Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null || k == 0) return head; int length = 1; ListNode curr = head; while (curr.next != null) { curr = curr.next; length++; } curr.next = head; k = k % length; int steps = length - k; ListNode newTail = curr; while (steps-- > 0) { newTail = newTail.next; } ListNode newHead = newTail.next; newTail.next = null; return newHead; }}🔍 Dry Run (Optimal)Input: [1,2,3,4,5], k = 2Length = 5k = 2Steps = 5 - 2 = 3Move 3 steps → new tail = 3new head = 4Final:4 → 5 → 1 → 2 → 3⏱️ ComplexityTypeValueTimeO(n)SpaceO(1)📊 ComparisonApproachTimeSpaceBest ForArray (Brute)O(n)O(n)BeginnersCircular (Optimal)O(n)O(1)Interviews📚 Related ProblemsSimilar PatternLinksReverse Linked ListProblem LinkLinked List CycleProblem LinkRemove Nth Node From EndProblem Link⚠️ Common MistakesForgetting k % lengthIncorrect pointer breakingNot handling single nodeOff-by-one in traversal🎯 Key Points to RememberAlways optimize kUse circular approach for best performanceUnderstand pointer movement carefully❓ FAQQ1: Why do we use k % length?Because rotating more than length gives same result.Q2: Which approach is better?Optimal circular linked list approach.Q3: Can we use array approach in interviews?Yes, but optimal is preferred.Q4: What is the key trick here?Convert linked list into circular structure.

Linked ListTwo PointerLeetCodeJavaMedium

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 102: Binary Tree Level Order Traversal – Java BFS Solution Explained

IntroductionLeetCode 102 – Binary Tree Level Order Traversal is one of the most important Binary Tree traversal problems for coding interviews.This problem introduces:Breadth First Search (BFS)Queue data structureLevel-by-level traversalTree traversal patternsInterview-level BFS thinkingUnlike DFS traversals like preorder, inorder, and postorder, this problem explores the tree level by level.This traversal is widely used in:Graph traversalShortest path problemsTree serializationZigzag traversalBFS-based interview questionsProblem Link🔗 https://leetcode.com/problems/binary-tree-level-order-traversal/Problem StatementGiven the root of a binary tree, return the level order traversal of its nodes' values.Traversal should happen:Level by levelLeft to rightExampleInputroot = [3,9,20,null,null,15,7]Tree Structure: 3 / \ 9 20 / \ 15 7Level Order TraversalLevel 1:[3]Level 2:[9,20]Level 3:[15,7]Final Output:[[3],[9,20],[15,7]]Understanding the ProblemThe main challenge is:Process nodes level by level.This is exactly what:Breadth First Search (BFS)is designed for.Why Queue is Used?A queue follows:First In First Out (FIFO)This ensures:Nodes are processed in insertion orderParent nodes are processed before child nodesLevels are traversed correctlyBrute Force IntuitionOne brute force idea is:Calculate height of treeTraverse each level separatelyStore nodes level by levelBrute Force ComplexityThis approach becomes inefficient because:Each level traversal may revisit nodesComplexity may become:O(N²)for skewed trees.Optimal BFS IntuitionInstead of traversing each level separately:Use a queueProcess nodes level by level naturallyAt every level:Store queue sizeProcess exactly those many nodesAdd children into queueMove to next levelKey BFS ObservationBefore processing a level:int size = queue.size();This tells us:How many nodes belong to the current level.BFS AlgorithmSteps1. Initialize QueueInsert root node.2. Process Until Queue Becomes EmptyWhile queue is not empty:Find current level sizeTraverse current levelStore valuesPush child nodes3. Store Current LevelAfter processing one level:ans.add(levelList);Java BFS Solution/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * } */class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); if(root == null) return ans; queue.offer(root); while(!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for(int i = 0; i < size; i++) { root = queue.poll(); level.add(root.val); if(root.left != null) queue.offer(root.left); if(root.right != null) queue.offer(root.right); } ans.add(level); } return ans; }}Dry RunInputroot = [3,9,20,null,null,15,7]Tree: 3 / \ 9 20 / \ 15 7Initial Queue[3]Level 1Queue size:1Process:3Add children:9, 20Level result:[3]Queue now:[9,20]Level 2Queue size:2Process:9, 20Add children:15, 7Level result:[9,20]Queue now:[15,7]Level 3Queue size:2Process:15, 7Level result:[15,7]Queue becomes empty.Final Answer[[3],[9,20],[15,7]]Time Complexity AnalysisTime ComplexityO(N)Every node is visited exactly once.Space ComplexityO(N)Queue may store an entire level of nodes.DFS Alternative ApproachThis problem can also be solved using DFS recursion.Idea:Pass current level during recursionCreate new list when level appears first timeAdd node into correct level listJava DFS Solutionclass Solution { public void dfs(TreeNode root, int level, List<List<Integer>> ans) { if(root == null) return; if(level == ans.size()) { ans.add(new ArrayList<>()); } ans.get(level).add(root.val); dfs(root.left, level + 1, ans); dfs(root.right, level + 1, ans); } public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); dfs(root, 0, ans); return ans; }}BFS vs DFS for Level Order TraversalApproachAdvantagesDisadvantagesBFSNatural level traversalUses queueDFSRecursive solutionSlightly harder intuitionInterview ExplanationIn interviews, explain:Level order traversal is a BFS problem because we process nodes level by level. A queue naturally supports this traversal order.This demonstrates strong BFS understanding.Common Mistakes1. Forgetting Queue SizeWithout storing:int size = queue.size();levels cannot be separated correctly.2. Using DFS IncorrectlySimple DFS alone does not guarantee level ordering.3. Forgetting Null CheckAlways handle:if(root == null)FAQsQ1. Why is BFS preferred here?Because BFS naturally processes nodes level by level.Q2. Can this problem be solved recursively?Yes.Using DFS with level tracking.Q3. What data structure is mainly used?Queue.Q4. Is Level Order Traversal important?Yes.It is one of the most frequently asked BFS tree problems.Related ProblemsAfter mastering this problem, practice:Binary Tree Zigzag Level Order TraversalAverage of Levels in Binary TreeRight Side View of Binary TreeBinary Tree Vertical Order TraversalMaximum Depth of Binary TreeConclusionLeetCode 102 is one of the most important BFS tree traversal problems.It teaches:BFS traversalQueue usageLevel-by-level processingTree traversal fundamentalsThe key idea is:Use queue size to separate levels.Once this intuition becomes clear, many BFS-based tree interview problems become much easier.

LeetCodeBinary Tree Level Order TraversalBFSQueueBinary TreeJavaTree TraversalMedium

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

Longest Substring with K Unique Characters – Efficient Sliding Window Solution

IntroductionFinding substrings with unique characters is a common problem in string manipulation and interview questions.GFG’s Longest Substring with K Unique Characters problem challenges you to find the length of the longest substring containing exactly K distinct characters.The focus is not just on brute-force solutions, but on using sliding window with a HashMap to efficiently track character frequencies and window boundaries.If you’d like to try solving the problem first, you can attempt it here: Try the problem on GeeksforGeeks: https://leetcode.com/problems/max-consecutive-ones-iii/Problem UnderstandingYou are given:A string s of lowercase lettersAn integer kYour task: Return the length of the longest substring containing exactly k distinct characters.Examples:Input: s = "aabacbebebe", k = 3Output: 7Explanation: "cbebebe" is the longest substring with 3 distinct characters.Input: s = "aaaa", k = 2Output: -1Explanation: No substring contains exactly 2 distinct characters.Input: s = "aabaaab", k = 2Output: 7Explanation: "aabaaab" has exactly 2 unique characters.A naive approach would try all possible substrings, count unique characters, and track the max length.Time Complexity: O(n²)Inefficient for large stringsKey Idea: Sliding Window + HashMapInstead of recomputing the unique characters for every substring:Use a HashMap to store character frequencies in the current windowUse two pointers (i and j) to maintain the windowExpand the window by moving j and add characters to the mapShrink the window from the left when the number of unique characters exceeds kUpdate the max length whenever the window has exactly k unique charactersThis ensures each character is processed only once, giving a linear solution.Approach (Step-by-Step)Initialize a HashMap mp to store character countsUse two pointers i (window start) and j (window end)Iterate over the string with jAdd s[j] to the map and update its countCheck the map size:If size < k → move j forwardIf size == k → update max length, move j forwardIf size > k → shrink window from i until map size <= kAfter iterating, return max (or -1 if no valid substring exists)Optimization:Using a HashMap avoids recalculating the number of unique characters for every substringSliding window ensures O(n) complexityImplementation (Java)class Solution {public int longestKSubstr(String s, int k) {HashMap<Character,Integer> mp = new HashMap<>();int i = 0, j = 0;int max = -1;while (j < s.length()) {// Add current character to mapmp.put(s.charAt(j), mp.getOrDefault(s.charAt(j), 0) + 1);if (mp.size() < k) {j++;}else if (mp.size() == k) {// Update max length when exactly k unique charactersmax = Math.max(max, j - i + 1);j++;}else {// Shrink window until map size <= kwhile (mp.size() > k) {mp.put(s.charAt(i), mp.get(s.charAt(i)) - 1);if (mp.get(s.charAt(i)) == 0) {mp.remove(s.charAt(i));}i++;}max = Math.max(max, j - i + 1);j++;}}return max;}}Dry Run ExampleInput:s = "aabacbebebe", k = 3Execution:Window [0-4] = "aaba" → unique = 2 → continueWindow [1-6] = "abacb" → unique = 3 → max = 5Window [4-10] = "cbebebe" → unique = 3 → max = 7Output:7Complexity AnalysisTime Complexity: O(n) → Each character enters and leaves the window onceSpace Complexity: O(k) → HashMap stores at most k unique charactersEdge Cases Consideredk greater than number of unique characters → return -1Entire string has exactly k unique charactersString with repeated characters onlyMinimum string length (1)Sliding Window Pattern ImportanceThis problem reinforces a common sliding window + hashmap pattern used in:Longest substring problems with constraintsCounting substrings with exactly K conditionsOptimizing brute-force approaches to linear solutionsConclusionBy combining sliding window with HashMap frequency tracking, we reduce an O(n²) problem to O(n).Once you master this approach, many string and substring problems with constraints on unique characters become much easier to solve efficiently.

SlidingWindowHashMapStringsGFG

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

Floor in BST – Java Recursive Binary Search Tree Solution with Dry Run

IntroductionThe Floor in BST problem is one of the most important Binary Search Tree interview questions for beginners.This problem helps you understand:BST traversalRecursive searchingTree optimizationDecision making using BST propertiesEfficient searching techniquesThe main idea is to efficiently find the:Greatest value smaller than or equal to k.Problem Link🔗 GeeksforGeeks – Floor in BSTProblem StatementGiven the root of a Binary Search Tree and an integer:kfind the:Floor(k)The floor of a number is:The greatest value in the BST that is less than or equal to k.If no such value exists:return -1Example 1Inputroot = [10,7,15,2,8,11,16]k = 14Output11ExplanationThe largest value smaller than or equal to:14is:11Example 2Inputroot = [5,2,12,1,3,9,21,null,null,null,null,null,null,19,25]k = 24Output21Key ObservationBinary Search Tree follows:Left subtree -> smaller valuesRight subtree -> greater valuesThis ordering allows optimized searching.IntuitionSuppose:k = 14and current node is:10Since:10 < 14this node can potentially be the floor.But maybe there exists a larger valid floor in the right subtree.So:Store current node as possible answerMove rightBST LogicCase 1If:root.data == kthen exact floor exists.Return immediately.Case 2If:root.data > kcurrent node cannot be floor.Move left.Case 3If:root.data < kcurrent node becomes possible floor.Move right to search for larger valid answer.Brute Force ApproachIdeaTraverse the entire BST:Store all values smaller than or equal to kReturn maximum among themBrute Force ComplexityTime ComplexityO(N)Space ComplexityO(N)If storing nodes.Optimized Recursive BST ApproachUsing BST properties:Ignore unnecessary branchesSearch efficientlyReduce traversal operationsJava Solutionclass Solution { int f = -1; public int findMaxFork(Node root, int k) { if(root == null) return f; if(root.data == k) return root.data; if(root.data > k) { return findMaxFork(root.left, k); } else { f = root.data; return findMaxFork(root.right, k); } }}How the Solution WorksWhenever:root.data < kthe node becomes a possible floor candidate.But there may exist a larger valid floor in the right subtree.So:Save current nodeMove rightDry RunInput 10 / \ 7 15 / \ / \ 2 8 11 16k = 14Step 1Current node:10Since:10 < 14Possible floor:10Move right.Step 2Current node:15Since:15 > 14Move left.Step 3Current node:11Since:11 < 14Update floor:11Move right.Step 4Right child is null.Return:11Final Answer11Optimized Iterative ApproachThe same problem can also be solved iteratively.Iterative Java Solutionclass Solution { int findFloor(Node root, int k) { int floor = -1; while(root != null) { if(root.data == k) { return root.data; } if(root.data > k) { root = root.left; } else { floor = root.data; root = root.right; } } return floor; }}Why Iterative Approach is BetterAdvantages:Avoids recursion stackMore memory efficientBetter for skewed treesPreferred in some interviewsTime Complexity AnalysisBest CaseO(log N)Balanced BST.Worst CaseO(N)Skewed BST.Space ComplexityRecursiveO(H)where H is tree height.IterativeO(1)extra space.Interview ExplanationIn interviews explain:Whenever we encounter a node smaller than k, it becomes a possible floor candidate. Then we move right to search for a larger valid floor.This demonstrates:BST property understandingSearch optimizationRecursive reasoningEfficient traversalCommon Mistakes1. Traversing Entire TreeBST ordering already helps reduce search space.2. Forgetting to Update FloorAlways update:floor = root.databefore moving right.3. Returning First Smaller ValueNeed the:largest smaller valuenot any smaller value.4. Ignoring Exact MatchIf:root.data == kreturn immediately.FAQsQ1. What is floor in BST?Largest value smaller than or equal to k.Q2. Why move right after finding smaller value?To search for a larger valid floor.Q3. Can this be solved iteratively?Yes.Iterative solution is highly optimized.Q4. What if floor does not exist?Return:-1Related BST ProblemsPractice these next:Ceil in BSTSearch in BSTInsert into BSTValidate BSTLowest Common Ancestor in BSTConclusionFloor in BST is an excellent problem for understanding:BST traversalRecursive searchingSearch space optimizationInterview tree conceptsThe key insight is:Whenever a node is smaller than k, it becomes a possible floor candidate, but a larger valid floor may still exist in the right subtree.Mastering this logic makes many BST interview problems much easier.

BSTBinary Search TreeJavaGFGRecursionTree Data StructureEasy

LeetCode 2144: Minimum Cost of Buying Candies With Discount – Java Greedy Approach Explained

IntroductionLeetCode 2144 – Minimum Cost of Buying Candies With Discount is a classic greedy + sorting problem.The question looks simple initially, but the key challenge is understanding:Which candies should be free?How can we minimize the total payment?Why sorting helps?This is a good beginner-friendly greedy interview problem that teaches how to maximize discounts strategically.Problem Link🔗 Minimum Cost of Buying Candies With DiscountProblem StatementA candy shop offers a discount:For every two candies bought, you can get one additional candy for free.Condition:The free candy’s price must be less than or equal to the cheaper purchased candy.You are given an array:cost[i]representing candy prices.Return the minimum total amount needed to buy all candies.Example 1Inputcost = [1,2,3]Output5ExplanationBuy:3 and 2Get:1 freeTotal:3 + 2 = 5Example 2Inputcost = [6,5,7,9,2,2]Output23IntuitionTo maximize savings:The most expensive candies should be grouped together.Why?Because every third candy becomes free.So we want:Expensive candies paidCheapest among the group freeKey Greedy ObservationIf we sort candies in descending order:9, 7, 6, 5, 2, 2Then:Pay 9Pay 7Get 6 freeThen:Pay 5Pay 2Get 2 freeThis produces maximum discount.Brute Force ApproachIdeaTry every grouping combination:Select 2 candiesChoose possible free candyCompute total minimumWhy Brute Force is BadThe number of combinations becomes huge.Time complexity becomes exponential.Not suitable for interviews.Optimized Greedy ApproachStepsSort candies in descending orderTraverse arraySkip every 3rd candyAdd remaining candies to answerJava Solutionclass Solution {public int minimumCost(int[] cost) {if(cost.length == 1) return cost[0];if(cost.length == 2) return cost[0] + cost[1];Arrays.sort(cost);int[] arr = new int[cost.length];int o = 0;for(int j = cost.length - 1; j >= 0; j--) {arr[o] = cost[j];o++;}int sum = 0;int c = 0;for(int i = 0; i < arr.length; i++) {c = i + 1;if(c % 3 == 0) continue;sum += arr[i];}return sum;}}Cleaner Optimized VersionYou can simplify the logic further:class Solution {public int minimumCost(int[] cost) {Arrays.sort(cost);int sum = 0;int count = 0;for(int i = cost.length - 1; i >= 0; i--) {count++;if(count % 3 == 0) continue;sum += cost[i];}return sum;}}Why This WorksAfter descending sorting:Most expensive candies appear firstEvery 3rd candy becomes free.This guarantees:Maximum discount possibleDry RunInputcost = [6,5,7,9,2,2]Step 1: Sort Descending9,7,6,5,2,2Step 2: TraverseGroup 19 -> pay7 -> pay6 -> freeTotal:16Group 25 -> pay2 -> pay2 -> freeTotal:16 + 7 = 23Final Answer23Time Complexity AnalysisSortingO(N log N)TraversalO(N)Total ComplexityO(N log N)Space ComplexityO(N)Because of extra reversed array.Optimized VersionO(1)Ignoring sorting space.Interview ExplanationIn interviews explain:To maximize savings, we should make the free candies as expensive as possible. Sorting in descending order ensures every third candy is the maximum eligible free candy.This demonstrates:Greedy thinkingSorting optimizationMathematical observation skillsCommon Mistakes1. Sorting AscendingAscending order gives smaller discounts.Descending order is necessary.2. Forgetting Every 3rd Candy is FreeCorrect pattern:Pay, Pay, Free3. Using Extra Arrays UnnecessarilyYou can directly traverse sorted array backward.4. Incorrect GroupingAlways group expensive candies together.FAQsQ1. Why descending sorting?To maximize free candy value.Q2. Why skip every third candy?Because the offer gives:1 free candy after buying 2Q3. Can this be solved without sorting?Not optimally.Sorting guarantees best grouping.Q4. Is this a greedy problem?Yes.This is a classic greedy sorting optimization problem.ConclusionLeetCode 2144 is an excellent beginner greedy problem.Main learning points:Sorting strategyGreedy groupingMaximizing discountsEfficient array traversalThe core insight is:Sort candies from largest to smallest and make every third candy free.Once this pattern becomes intuitive, many greedy interview problems become easier to solve.

LeetCodeJavaSortingArrayGreedy ApproachEasy

LeetCode 98: Validate Binary Search Tree – Java DFS Recursive Solution Explained

IntroductionLeetCode 98 – Validate Binary Search Tree is one of the most important Binary Search Tree interview problems.This question is extremely popular because it tests:BST propertiesRecursive tree traversalDFS recursionRange validationTree constraints handlingMany beginners make mistakes on this problem because checking only parent-child relationships is not enough.Understanding the correct BST validation logic is very important for interviews.Problem Link🔗 https://leetcode.com/problems/validate-binary-search-tree/Problem StatementGiven the root of a binary tree, determine whether it is a valid Binary Search Tree (BST).A valid BST follows:Left subtree contains only smaller valuesRight subtree contains only greater valuesBoth left and right subtrees must also be BSTsExample 1Inputroot = [2,1,3]OutputtrueExplanation 2 / \ 1 3All BST conditions are satisfied.Example 2Inputroot = [5,1,4,null,null,3,6]OutputfalseWhy False? 5 / \ 1 4 / \ 3 6Although:4 < 6the node:4exists inside the right subtree of:5and should therefore be greater than 5.This violates BST rules.Key InsightThe most important understanding:Every node must satisfy an entire valid range, not just parent comparison.This is where many incorrect solutions fail.Common Wrong ThinkingMany beginners try:if(root.left.val < root.val && root.right.val > root.val)This is incorrect.Because BST validation depends on:ALL ancestor constraintsnot just immediate parent.Correct IntuitionEach node has:Minimum allowed valueMaximum allowed valueFor example:Left subtree -> values smaller than rootRight subtree -> values greater than rootAs recursion goes deeper:constraints become tighterVisual Understanding 10 / \ 5 15 / \ 6 20Node:6is invalid because:6 < 10even though:6 < 15This proves:Parent-only checking is insufficient.Brute Force ApproachIdeaFor every node:Find maximum in left subtreeFind minimum in right subtreeValidate BST conditionsBrute Force ComplexityTime ComplexityO(N²)Because subtree traversal repeats for every node.Space ComplexityO(H)Recursive stack space.Optimized Recursive DFS ApproachThe optimized idea:Pass valid range during recursion.Each node must satisfy:min < node.val < maxJava Solutionclass Solution { public boolean solve(TreeNode root, long min, long max) { if(root == null) return true; if(root.val <= min || root.val >= max) { return false; } return solve(root.left, min, root.val) && solve(root.right, root.val, max); } public boolean isValidBST(TreeNode root) { if(root == null) return true; return solve(root, Long.MIN_VALUE, Long.MAX_VALUE); }}Why Use Long Instead of Int?Constraints allow:-2³¹ <= Node.val <= 2³¹ - 1Using:Integer.MIN_VALUEInteger.MAX_VALUEcan create edge-case failures.So we safely use:Long.MIN_VALUELong.MAX_VALUEHow This WorksFor every node:Left SubtreeAllowed range:(min, root.val)Right SubtreeAllowed range:(root.val, max)This guarantees global BST validity.Dry RunInputroot = [2,1,3]Step 1Current node:2Allowed range:(-∞, +∞)Valid.Step 2Move left:1Allowed range:(-∞, 2)Valid.Step 3Move right:3Allowed range:(2, +∞)Valid.Final OutputtrueAnother Dry RunInputroot = [5,1,4,null,null,3,6]Step 1Node:5Range:(-∞, +∞)Valid.Step 2Move right to:4Range:(5, +∞)Now:4 <= 5Invalid BST.Final OutputfalseTime Complexity AnalysisTime ComplexityO(N)Every node visited once.Space ComplexityO(H)Where:H = height of treeWorst case:O(N)for skewed tree.Alternative Approach Using Inorder TraversalKey PropertyBST inorder traversal produces:strictly increasing orderInorder Java Solutionclass Solution { TreeNode prev = null; public boolean inorder(TreeNode root) { if(root == null) return true; if(!inorder(root.left)) return false; if(prev != null && root.val <= prev.val) { return false; } prev = root; return inorder(root.right); } public boolean isValidBST(TreeNode root) { return inorder(root); }}Interview ExplanationIn interviews, explain:A valid BST requires every node to satisfy ancestor constraints, not just parent constraints. Therefore, we recursively maintain valid minimum and maximum bounds for each node.This demonstrates:Deep BST understandingRecursive DFS masteryConstraint propagationEdge-case handlingCommon Mistakes1. Comparing Only Parent NodesIncorrect approach:root.left.val < root.valThis misses ancestor violations.2. Forgetting Strict InequalityBST requires:strictly smallerstrictly greaterDuplicates are invalid.3. Using int Instead of longCan fail on edge values.Always use:long minlong max4. Incorrect Range PassingCorrect recursion:left -> (min, root.val)right -> (root.val, max)FAQsQ1. Why does parent comparison fail?Because BST validity depends on all ancestor constraints.Q2. Why use min/max bounds?Bounds propagate BST restrictions correctly.Q3. Can inorder traversal solve this?Yes.BST inorder traversal must be strictly increasing.Q4. Is this asked frequently?Very frequently.It is one of the most important BST interview questions.Related ProblemsPractice these next:Search in BSTInsert into BSTLowest Common Ancestor in BSTKth Smallest Element in BSTConclusionLeetCode 98 is an excellent problem for mastering:BST validationRecursive DFSConstraint propagationTree traversalInterview problem-solvingThe key insight is:Every BST node must satisfy a valid global range, not just local parent conditions.Once this concept becomes intuitive, many advanced BST problems become significantly easier.

LeetCodeBinary Search TreeBSTJavaDFS TraversalBinary TreeRecursionMedium

LeetCode 235: Lowest Common Ancestor of a Binary Search Tree – Java BST Solution with Dry Run

IntroductionLeetCode 235 – Lowest Common Ancestor of a Binary Search Tree is one of the most important BST interview problems.This problem helps you understand:Binary Search Tree propertiesRecursive traversalTree navigationAncestor relationshipsOptimized searchingIt is frequently asked in coding interviews because it combines tree traversal with BST optimization.Problem Link🔗 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/Problem StatementGiven:Root of a Binary Search TreeTwo nodes p and qReturn:The Lowest Common Ancestor (LCA) of p and qThe LCA is the lowest node in the tree that has both nodes as descendants.A node can also be a descendant of itself.Example 1Inputroot = [6,2,8,0,4,7,9,null,null,3,5]p = 2q = 8Output6Example 2Inputroot = [6,2,8,0,4,7,9,null,null,3,5]p = 2q = 4Output2Understanding the BST PropertyA Binary Search Tree follows:Left Subtree < RootRight Subtree > RootExample: 6 / \ 2 8 / \ / \ 0 4 7 9 / \ 3 5This property allows us to find the LCA efficiently.Key ObservationThere are only three possible cases:Case 1Both nodes are smaller than root.Move LeftCase 2Both nodes are greater than root.Move RightCase 3One node is on the left and the other is on the right.OROne node equals root.Then:Current root is the LCAIntuitionSuppose:p = 2q = 8root = 6Now:2 < 68 > 6This means:One node is in left subtreeOne node is in right subtreeSo:6 is the first common split pointHence:6 is the Lowest Common AncestorBrute Force ApproachIdeaFind path from root to pFind path from root to qCompare both pathsLast common node is the LCABrute Force ComplexityTime ComplexityO(N)Space ComplexityO(N)Extra path storage required.Optimized BST ApproachUsing BST properties:No need to store pathsNo need to traverse entire treeMove intelligentlyThis gives a much cleaner solution.Java Solutionclass Solution { public TreeNode solve(TreeNode root, TreeNode p, TreeNode q) { if(root == null) return root; if(root.val < p.val && root.val < q.val) { return solve(root.right, p, q); } else if(root.val > p.val && root.val > q.val) { return solve(root.left, p, q); } else { return root; } } public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null) return root; return solve(root, p, q); }}Cleaner Recursive Versionclass Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root.val > p.val && root.val > q.val) { return lowestCommonAncestor(root.left, p, q); } if(root.val < p.val && root.val < q.val) { return lowestCommonAncestor(root.right, p, q); } return root; }}Iterative ApproachWe can also solve this without recursion.Iterative Java Solutionclass Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while(root != null) { if(root.val > p.val && root.val > q.val) { root = root.left; } else if(root.val < p.val && root.val < q.val) { root = root.right; } else { return root; } } return null; }}Dry RunInputroot = [6,2,8,0,4,7,9,null,null,3,5]p = 2q = 8Step 1Current root:6Check:2 < 68 > 6One node is on left.One node is on right.So:6 is the LCAFinal Output6Another Dry RunInputp = 2q = 4Step 1Current root:6Both nodes smaller than 6.Move left.Step 2Current root:2Now:p == rootSo:2 is the LCAWhy This WorksBST ordering helps us eliminate half the tree at every step.If:p and q both smallerthen LCA must exist in left subtree.If:p and q both greaterthen LCA must exist in right subtree.Otherwise:Current node is the split pointwhich becomes the Lowest Common Ancestor.Time Complexity AnalysisOptimized BST SolutionAverage Time ComplexityO(log N)Because BST halves search space.Worst Case Time ComplexityO(N)Occurs when BST becomes skewed.Space ComplexityRecursiveO(H)Where:H = height of treeIterativeO(1)No recursion stack used.Interview ExplanationIn interviews, explain:Since this is a BST, we can use node ordering to decide whether both nodes lie in the left subtree, right subtree, or on different sides. The first split point becomes the Lowest Common Ancestor.This demonstrates:BST understandingTree recursionSearch optimizationEfficient traversal logicCommon Mistakes1. Treating It Like a Normal Binary TreeThis problem becomes easier because it is a BST.Use BST properties.2. Forgetting Split Point LogicThe LCA occurs when:p <= root <= qor vice versa.3. Traversing Entire TreeUnnecessary.BST lets us eliminate half the tree.4. Confusing Ancestor DefinitionA node can be ancestor of itself.Important for cases like:p = 2q = 4Answer becomes:2FAQsQ1. Why is BST important here?BST ordering allows efficient searching.Without BST property, we need a completely different approach.Q2. Can this be solved iteratively?Yes.Iterative traversal is even more space-efficient.Q3. Is recursion necessary?No.Both recursive and iterative solutions work.Q4. What is the Lowest Common Ancestor?The deepest node that has both target nodes as descendants.ConclusionLeetCode 235 is an excellent BST problem for mastering:BST propertiesRecursive traversalTree navigationOptimized searchingAncestor-based reasoningThe main insight is:In a BST, the first node where paths to p and q split becomes the Lowest Common Ancestor.Once this concept becomes intuitive, many BST interview problems become much easier to solve.

LeetCodeBinary Search TreeBSTJavaTreeMedium

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 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 450: Delete Node in a BST – Java Optimized Recursive Solution with Dry Run

IntroductionThe Delete Node in a BST problem is one of the most important Binary Search Tree interview questions because it combines:BST traversalTree restructuringRecursive thinkingNode replacement logicTree manipulationUnlike searching or insertion, deletion is slightly more complex because we must maintain BST properties after removing a node.This problem is frequently asked in coding interviews and online assessments.Problem Link🔗 LeetCode 450 – Delete Node in a BSTProblem StatementGiven:The root of a Binary Search TreeA key valueDelete the node containing the key while preserving BST properties.Return the updated BST root.BST Property ReminderIn a Binary Search Tree:Left subtree -> smaller valuesRight subtree -> greater valuesAfter deletion:Tree must still remain a valid BST.Example 1Inputroot = [5,3,6,2,4,null,7]key = 3Output[5,4,6,2,null,null,7]VisualizationBefore deletion: 5 / \ 3 6 / \ \ 2 4 7After deleting 3: 5 / \ 4 6 / \ 2 7Key Deletion CasesBST deletion has 3 important cases.Case 1: Node Has No ChildSimply remove the node.Case 2: Node Has One ChildReplace the node with its child.Case 3: Node Has Two ChildrenThis is the tricky part.We:Find inorder predecessor or successorReplace nodeReconnect subtrees properlyIntuitionSuppose we want to delete:3from: 5 / \ 3 6 / \ 2 4Since node 3 has:Left childRight childwe cannot directly delete it.Instead:Attach right subtree to rightmost node of left subtreeReturn left subtree as replacementThis preserves BST ordering.Brute Force ApproachIdeaStore inorder traversalRemove target nodeRebuild BSTWhy Brute Force is BadProblems:Extra memory usageRebuilding tree is expensiveUnnecessary traversalBrute Force ComplexityTime ComplexityO(N)Space ComplexityO(N)Optimized BST Deletion ApproachUse BST properties to:Search efficientlyModify only required nodesPreserve tree structureJava Solutionclass Solution { public TreeNode deleteNode(TreeNode root, int key) { if(root == null) return root; if(root.val == key) return solve(root); TreeNode originalRoot = root; while(root != null) { if(root.val > key) { if(root.left != null && root.left.val == key) { root.left = solve(root.left); } else { root = root.left; } } else { if(root.right != null && root.right.val == key) { root.right = solve(root.right); } else { root = root.right; } } } return originalRoot; } public TreeNode solve(TreeNode root) { if(root.left == null) return root.right; if(root.right == null) return root.left; TreeNode rightChild = root.right; TreeNode leftChild = asright(root.left); leftChild.right = rightChild; return root.left; } public TreeNode asright(TreeNode root) { if(root.right == null) return root; return asright(root.right); }}How This Solution WorksThe main logic happens inside:solve(root)This function deletes the node safely.Understanding solve()Case 1If:root.left == nullreturn right subtree.Case 2If:root.right == nullreturn left subtree.Case 3If both children exist:Save right subtreeFind rightmost node in left subtreeAttach right subtree thereReturn left subtreeWhy Rightmost Node?Because:Rightmost node of left subtreeis the:largest node smaller than rootThis maintains BST ordering perfectly.Dry RunInput 5 / \ 3 6 / \ \ 2 4 7key = 3Step 1Search node:3Step 2Node has:Left child = 2Right child = 4Step 3Find rightmost node in left subtree.Rightmost node:2Step 4Attach right subtree:2.right = 4Step 5Return left subtree:2Updated BST becomes valid.Time Complexity AnalysisBest CaseO(log N)Balanced BST.Worst CaseO(N)Skewed BST.Space ComplexityRecursive HelperO(H)where:H = tree heightAlternative Recursive ApproachAnother common method:Replace node with inorder successorDelete successor recursivelyThis approach is also interview friendly.Interview ExplanationIn interviews explain:When deleting a node with two children, we preserve BST properties by connecting the right subtree to the rightmost node of the left subtree.This demonstrates:BST restructuring knowledgeTree manipulation skillsRecursive reasoningPointer managementCommon Mistakes1. Forgetting BST PropertyDeletion should not break ordering.2. Losing SubtreesAlways reconnect children carefully.3. Incorrect Node ReplacementMany candidates replace node incorrectly.4. Not Handling Null CasesAlways check:root == nullproperly.FAQsQ1. Why is BST deletion difficult?Because tree structure must remain valid after removal.Q2. Why use rightmost node of left subtree?It is the largest smaller value.Perfect replacement candidate.Q3. Can we use inorder successor instead?Yes.Both predecessor and successor approaches work.Q4. What is deletion complexity?Balanced BST:O(log N)Worst case:O(N)Related BST ProblemsPractice these next:Insert into BSTSearch in BSTValidate BSTLowest Common Ancestor in BSTKth Smallest Element in BSTInorder Successor in BSTConclusionDelete Node in BST is one of the most important BST interview problems because it teaches:Tree restructuringRecursive manipulationPointer handlingBST property maintenanceThe key insight is:When deleting a node with two children, reconnect subtrees carefully so BST ordering remains valid.Mastering this problem makes advanced BST operations significantly easier.

BSTJavaBinary Search TreeLeetCodeTreeRecursionMedium

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

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

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

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

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

MonotonicStackNextGreaterElementStackProblemsJavaGeeksForGeeksStackPattern

LeetCode 701: Insert into a Binary Search Tree – Java Recursive Solution with Dry Run

IntroductionLeetCode 701 – Insert into a Binary Search Tree is one of the most important Binary Search Tree problems for coding interviews.This problem helps developers understand:BST propertiesRecursive traversalTree modificationNode insertion logicDFS recursionIt is frequently asked because BST insertion is a foundational concept used in:Search operationsTree balancingDatabase indexingOrdered data structuresProblem Link🔗 https://leetcode.com/problems/insert-into-a-binary-search-tree/Problem StatementYou are given:Root of a Binary Search TreeA value to insertReturn:Root of BST after insertionThe inserted value is guaranteed to be unique.What is a Binary Search Tree?A BST follows this rule:Left subtree values < RootRight subtree values > RootExample: 4 / \ 2 7 / \ 1 3If we insert:5It becomes: 4 / \ 2 7 / \ / 1 3 5Key ObservationWhile traversing:If value is smaller → go leftIf value is larger → go rightEventually:We reach a null positionThat is the insertion point.IntuitionBST insertion behaves exactly like BST search.We recursively move:left or rightuntil we find:nullThen create the new node there.Brute Force ThinkingA beginner might think:Store tree in arrayInsert valueSort againRebuild BSTBut rebuilding the tree is unnecessary and inefficient.BST already provides ordered traversal naturally.Optimized Recursive ApproachIdeaAt every node:If value is smaller → insert into left subtreeElse → insert into right subtreeWhen root becomes:nullcreate a new node.Java Solutionclass Solution { public void solve(TreeNode root, TreeNode prevnode, int val) { if(root == null) { if(prevnode.val < val) { prevnode.right = new TreeNode(val); } else { prevnode.left = new TreeNode(val); } return; } if(root.val > val) { solve(root.left, root, val); } else { solve(root.right, root, val); } } public TreeNode insertIntoBST(TreeNode root, int val) { if(root == null) { return new TreeNode(val); } TreeNode originalRoot = root; solve(root, root, val); return originalRoot; }}Cleaner Recursive Versionclass Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if(root == null) { return new TreeNode(val); } if(val < root.val) { root.left = insertIntoBST(root.left, val); } else { root.right = insertIntoBST(root.right, val); } return root; }}Why This WorksBST property guarantees:Smaller values go leftLarger values go rightSo recursion naturally finds the correct insertion position.When recursion reaches:nullwe create the new node.Dry RunInputroot = [4,2,7,1,3]val = 5Step 1Current node:4Since:5 > 4move right.Step 2Current node:7Since:5 < 7move left.Step 3Left child is:nullInsert:5Final Tree 4 / \ 2 7 / \ / 1 3 5Time Complexity AnalysisAverage CaseTime ComplexityO(log N)Balanced BST height remains logarithmic.Space ComplexityO(log N)due to recursion stack.Worst CaseIf BST becomes skewed:1 -> 2 -> 3 -> 4Then:Time ComplexityO(N)Space ComplexityO(N)Recursive vs IterativeApproachTime ComplexitySpace ComplexityRecursiveO(H)O(H)IterativeO(H)O(1)Where:H = height of BSTIterative Java Solutionclass Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if(root == null) { return new TreeNode(val); } TreeNode curr = root; while(true) { if(val < curr.val) { if(curr.left == null) { curr.left = new TreeNode(val); break; } curr = curr.left; } else { if(curr.right == null) { curr.right = new TreeNode(val); break; } curr = curr.right; } } return root; }}Interview ExplanationIn interviews, explain:Binary Search Tree insertion follows BST ordering rules. We recursively traverse left or right depending on the value until we reach a null node, where the new node is inserted.This demonstrates:BST understandingRecursive traversalTree manipulationDFS logicCommon Mistakes1. Forgetting to Return RootAlways return original root after insertion.2. Breaking BST PropertyIncorrect comparisons can violate BST ordering.Correct logic:if(val < root.val)3. Missing Base CaseWithout:if(root == null)recursion never stops.4. Rebuilding Entire TreeInsertion should modify existing BST directly.FAQsQ1. Why use recursion?BST naturally divides into smaller subtrees.Recursion simplifies traversal logic.Q2. Can insertion be iterative?Yes.Using loops avoids recursion stack usage.Q3. Why does BST insertion work efficiently?Because BST reduces search space at every step.Q4. Is this problem important for interviews?Absolutely.BST insertion is one of the most frequently asked tree concepts.ConclusionLeetCode 701 is an excellent BST problem for learning:Recursive tree traversalBST propertiesNode insertion logicDFS recursionThe core insight is:Move left for smaller values and right for larger values until a null position is found.Once this becomes intuitive, most BST operations become much easier to solve.

LeetCodeBSTBinary Search TreeJavaRecursionTreeMedium

Find the Difference – Smart ASCII Sum Trick (LeetCode 389)

🔗 Problem LinkLeetCode 389 – Find the Difference 👉 https://leetcode.com/problems/find-the-difference/IntroductionThis is a very clever problem.At first glance, you might think:Use a HashMapCount frequenciesCompare both stringsBut there’s a much smarter and cleaner way to solve it using character arithmetic (ASCII values).This problem teaches an important lesson:Sometimes math can replace extra space.Let’s break it down.📌 Problem UnderstandingYou are given two strings:stString t is created by:Shuffling string sAdding one extra character at a random positionYour task:Return the extra character added to t.Example 1Input: s = "abcd" t = "abcde"Output: "e"Example 2Input: s = "" t = "y"Output: "y"🧠 First Intuition (Brute Force Thinking)When solving this for the first time, a common approach would be:Count frequency of characters in sCount frequency of characters in tCompare bothThe one with extra count is the answerThat works in O(n) time and O(26) space.But we can do better.🚀 Smarter Approach – ASCII Sum Trick💡 Key InsightCharacters are stored as integer ASCII values.If:We add all ASCII values of characters in tSubtract all ASCII values of characters in sWhat remains?👉 The ASCII value of the extra character.Because:All matching characters cancel out.Only the added character remains.💻 Your Codeclass Solution { public char findTheDifference(String s, String t) { int tot = 0; for(int i = 0; i < t.length(); i++){ tot += (int)t.charAt(i); } for(int i = 0; i < s.length(); i++){ tot -= (int)s.charAt(i); } return (char)tot; }}🔍 Step-by-Step Explanation1️⃣ Initialize Totalint tot = 0;This will store the running ASCII difference.2️⃣ Add All Characters of ttot += (int)t.charAt(i);We add ASCII values of every character in t.3️⃣ Subtract All Characters of stot -= (int)s.charAt(i);We subtract ASCII values of every character in s.4️⃣ Return Remaining Characterreturn (char)tot;After subtraction, only the extra character’s ASCII value remains.We convert it back to char.🎯 Why This WorksLet’s take example:s = "abcd"t = "abcde"ASCII Sum:t = a + b + c + d + es = a + b + c + dSubtract:(t sum) - (s sum) = eEverything cancels except the extra letter.Simple and powerful.⏱ Complexity AnalysisTime Complexity: O(n)One loop over tOne loop over sSpace Complexity: O(1)No extra data structure used.🔥 Even Smarter Approach – XOR TrickAnother elegant method is using XOR:Why XOR Works?Properties:a ^ a = 0a ^ 0 = aXOR is commutativeIf we XOR all characters in both strings:Matching characters cancel out.Only the extra character remains.XOR Versionclass Solution { public char findTheDifference(String s, String t) { char result = 0; for(char c : s.toCharArray()){ result ^= c; } for(char c : t.toCharArray()){ result ^= c; } return result; }}This is considered the most elegant solution.🏁 Final ThoughtsThis problem teaches:Thinking beyond brute forceUsing mathematical propertiesUnderstanding ASCII representationUsing XOR smartlySometimes the best solution is not about data structures — it’s about recognizing hidden math patterns.

StringMath TrickASCIIBit ManipulationLeetCodeEasy

LeetCode 402: Remove K Digits — Java Solution Explained

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

LeetCodeJavaStackMonotonic StackGreedyStringMedium

Ceil in BST – Java Recursive Binary Search Tree Solution with Dry Run

IntroductionThe Ceil in BST problem is one of the most important Binary Search Tree interview questions.This problem teaches:BST traversalRecursive searchingDecision making using BST propertiesTree optimizationInterview-level recursion conceptsThe main challenge is understanding how BST ordering helps us efficiently locate the smallest value greater than or equal to a target number.Problem Link🔗 GeeksforGeeks – Ceil in BSTProblem StatementGiven a Binary Search Tree and an integer:xfind the:Ceil(x)The ceil of a number is:The smallest value in the BST that is greater than or equal to x.If no such value exists:return -1Example 1Inputroot = [5,1,7,N,2,N,N,N,3]x = 3Output3ExplanationSince:3 exists in the BSTthe ceil is:3Example 2Inputroot = [10,5,11,4,7,N,N,N,N,N,8]x = 6Output7ExplanationThe smallest value greater than or equal to:6is:7Key ObservationBinary Search Trees follow:Left subtree -> smaller valuesRight subtree -> greater valuesThis allows efficient searching.IntuitionSuppose:x = 6and current node is:10Since:10 > 6this node can potentially be the answer.But maybe a smaller valid ceil exists in the left subtree.So:Store current node as possible answerMove leftImportant BST LogicIf:root.data == xWe found exact ceil.Return immediately.If:root.data > xCurrent node can be ceil.Move left to find smaller possible ceil.If:root.data < xCurrent node cannot be ceil.Move right.Brute Force ApproachIdeaTraverse the entire BST:Store all values greater than or equal to xReturn minimum among themBrute Force ComplexityTime ComplexityO(N)Space ComplexityO(N)If storing elements.Optimized BST Recursive ApproachUsing BST properties:Ignore unnecessary branchesSearch intelligentlyReduce traversal workJava Solutionclass Solution { int c = -1; int solve(Node root, int x, int c) { if(root == null) return c; if(root.data == x) return root.data; if(root.data > x) { c = root.data; return solve(root.left, x, c); } else { return solve(root.right, x, c); } } int findCeil(Node root, int x) { return solve(root, x, c); }}How the Solution WorksThe recursion maintains:current best ceil candidateWhenever:root.data > xupdate ceil candidate.Then search left subtree for smaller valid answer.Dry RunInput 10 / \ 5 11 / \ 4 7 \ 8x = 6Step 1Current node:10Since:10 > 6Possible ceil:10Move left.Step 2Current node:5Since:5 < 6Move right.Step 3Current node:7Since:7 > 6Update ceil:7Move left.Step 4Left child is null.Return:7Final Answer7Optimized Iterative ApproachYou can also solve this iteratively.Iterative Java Solutionclass Solution { int findCeil(Node root, int x) { int ceil = -1; while(root != null) { if(root.data == x) { return root.data; } if(root.data > x) { ceil = root.data; root = root.left; } else { root = root.right; } } return ceil; }}Why Iterative is BetterIterative solution avoids recursion stack.Better for:Large treesMemory optimizationInterview follow-up questionsTime Complexity AnalysisBest CaseO(log N)Balanced BST.Worst CaseO(N)Skewed BST.Space ComplexityRecursiveO(H)Recursion stack.IterativeO(1)Extra space.Interview ExplanationIn interviews explain:Since BST maintains sorted ordering, we can intelligently move left or right. Whenever a node is greater than x, it becomes a potential ceil candidate.This demonstrates:BST understandingRecursive reasoningSearch optimizationEfficient traversal logicCommon Mistakes1. Traversing Entire TreeUnnecessary because BST already provides ordering.2. Not Updating Ceil ProperlyAlways update:ceil = root.databefore moving left.3. Returning First Greater ElementNeed the:smallest greater valuenot just any greater value.4. Ignoring Exact MatchIf:root.data == xreturn immediately.FAQsQ1. What is ceil in BST?Smallest value greater than or equal to x.Q2. Why move left after finding larger value?To search for a smaller valid ceil.Q3. Can this be solved iteratively?Yes.Iterative solution is highly optimized.Q4. What if ceil does not exist?Return:-1Related BST ProblemsPractice these next:Search in BSTInsert into BSTKth Smallest in BSTLowest Common Ancestor in BSTConclusionCeil in BST is an excellent problem for learning:BST traversalRecursive decision makingSearch optimizationInterview tree logicThe key insight is:Whenever a node is greater than x, it becomes a potential answer, but a smaller valid ceil may still exist in the left subtree.Mastering this concept makes many BST interview problems significantly easier.

Binary Search TreeBSTJavaRecursionGFGMedium

LeetCode 3174: Clear Digits — Multiple Approaches Explained

What's the Problem Really Asking?Imagine you're editing a text document and every time you type a number, it acts like a backspace key — it deletes itself AND the character just before it. That's exactly what this problem is!Given a string like "cb34":3 deletes b → "c4"4 deletes c → ""Simple idea, right? Let's look at all the ways to solve it.Here is the problem link-: Leetcode 3174Approach 1: Using a Stack (Classic & Intuitive)The IdeaA stack is the most natural fit here. Think of it like a stack of plates:If the character is a letter → push it onto the stack (add a plate)If the character is a digit → pop from the stack (remove the top plate, the digit deletes itself too)At the end, whatever's left on the stack is your answer.Codepublic String clearDigits(String s) { Stack<Character> st = new Stack<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c >= '0' && c <= '9') { if (!st.empty()) { st.pop(); // digit eats the closest left non-digit } } else { st.push(c); // letter goes in } } StringBuilder sb = new StringBuilder(); while (!st.empty()) { sb.append(st.pop()); } return sb.reverse().toString(); // stack gives reverse order}Real Life AnalogyThink of a Jenga tower. Every time a digit appears, it pulls out the topmost block (the closest left letter). At the end, whatever blocks remain standing — that's your result.ComplexityTime: O(n) — single pass through the stringSpace: O(n) — stack can hold up to n characters in worst case (no digits)Approach 2: StringBuilder as a Stack (Optimal & Clean) ✅The IdeaThis is the smartest approach and the one you already have in your solution. A StringBuilder naturally behaves like a stack:Append letters to the endWhen a digit appears, delete the last character (.deleteCharAt(sb.length() - 1))No extra data structure needed!Codepublic String clearDigits(String s) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c >= '0' && c <= '9') { sb.deleteCharAt(sb.length() - 1); // digit acts as backspace } else { sb.append(c); // letter gets added } } return sb.toString();}Walkthrough with ExampleLet's trace "cb34" step by step:StepCharacterActionStringBuilder1cappend"c"2bappend"cb"33delete last"c"44delete last""Final answer: ""Another example — "a1b2c3":StepCharacterActionStringBuilder1aappend"a"21delete last""3bappend"b"42delete last""5cappend"c"63delete last""Final answer: ""ComplexityTime: O(n) — one pass, each character processed onceSpace: O(n) — StringBuilder storageApproach 3: Brute Force / Simulation (Beginner-Friendly)The IdeaJust simulate exactly what the problem says — find the first digit, remove it and its closest left non-digit, repeat.public String clearDigits(String s) { StringBuilder sb = new StringBuilder(s); boolean found = true; while (found) { found = false; for (int i = 0; i < sb.length(); i++) { if (Character.isDigit(sb.charAt(i))) { sb.deleteCharAt(i); // delete the digit if (i > 0) { sb.deleteCharAt(i - 1); // delete closest left non-digit } found = true; break; // restart the search } } } return sb.toString();}ComplexityTime: O(n²) — for each digit found, we restart scanning from the beginningSpace: O(n) — StringBuilder storageThis works fine for the given constraints (n ≤ 100), but it's not scalable for large inputs.Approach ComparisonApproachTimeSpaceCode SimplicityBest ForBrute ForceO(n²)O(n)⭐⭐⭐Understanding the problemStackO(n)O(n)⭐⭐⭐⭐Interviews (clear intent)StringBuilderO(n)O(n)⭐⭐⭐⭐⭐Production / Best solutionKey Takeaways1. Recognize the Stack Pattern Anytime a problem says "delete the closest left element," your brain should immediately scream stack. This pattern appears in many problems like Valid Parentheses, Asteroid Collision, and Backspace String Compare.2. StringBuilder is a hidden stack In Java, StringBuilder supports append() (push) and deleteCharAt(length-1) (pop). Using it directly instead of a Stack<Character> saves you the overhead of boxing/unboxing characters and the extra reverse step.3. The problem guarantees all digits can be deleted This means you'll never call deleteCharAt on an empty StringBuilder. In a real interview, you'd still want to add a guard check (if (sb.length() > 0)) to be safe and show defensive coding habits.Similar Problems to Practice844. Backspace String Compare — almost identical concept1047. Remove All Adjacent Duplicates In String — same stack pattern2390. Removing Stars From a String — stars act as backspace, same idea

StringStackString BuilderEasyLeetCode

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

Intersection of Two Linked Lists – The Smart Trick Most People Miss (LeetCode 160)

🚀 Try the ProblemPractice here:https://leetcode.com/problems/intersection-of-two-linked-lists/🤔 Let’s Start With a ThoughtImagine two roads:Road A: 4 → 1 → 8 → 4 → 5 Road B: 5 → 6 → 1 → 8 → 4 → 5At some point… both roads merge into one.👉 That merging point is the intersection node🧠 Problem in Simple WordsYou are given:Head of List AHead of List B👉 Find the node where both linked lists intersect👉 If no intersection exists → return null⚠️ Important Clarification👉 Intersection means:Same memory node (same reference)NOT:Same value ❌📌 Example InsightList A: 1 → 9 → 1 → 2 → 4 List B: 3 → 2 → 4Even though both lists have 2 and 4:👉 They intersect ONLY if they point to the same node in memory📦 Constraints1 <= m, n <= 3 * 10^41 <= Node.val <= 10^5No cycles in the list🔍 First Thought (Brute Force)IdeaFor every node in List A:👉 Traverse entire List B and check if nodes matchComplexityTime: O(m * n) ❌Space: O(1)Too slow.🧩 Better Approach: Length Difference MethodIdeaFind length of both listsMove the longer list ahead by the differenceNow traverse both togetherWhy This Works👉 After skipping extra nodes, both pointers are equally far from intersectionComplexityTime: O(m + n)Space: O(1)🚀 Optimal Approach: Two Pointer Switching TrickNow comes the most beautiful trick 🔥🧠 Core IdeaWe use two pointers:pointerA → starts from headApointerB → starts from headB🎯 The Magic Trick👉 When a pointer reaches end → switch it to the other list🔄 VisualizationLet’s say:Length A = mLength B = nPointer paths:pointerA travels: A → BpointerB travels: B → ASo both travel:m + n distance💡 Why They Meet👉 If intersection exists → they meet at intersection👉 If not → both reach null at same time🔥 Step-by-Step ExampleA: 4 → 1 → 8 → 4 → 5 B: 5 → 6 → 1 → 8 → 4 → 5Iteration:A pointer: 4 → 1 → 8 → 4 → 5 → null → 5 → 6 → 1 → 8 B pointer: 5 → 6 → 1 → 8 → 4 → 5 → null → 4 → 1 → 8👉 They meet at 8💻 Clean Java Code (Optimal Solution)public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode tempa = headA; ListNode tempb = headB; // Traverse until both pointers meet while(tempa != tempb){ // Move pointer A if(tempa != null) tempa = tempa.next; else tempa = headB; // Move pointer B if(tempb != null) tempb = tempb.next; else tempb = headA; } // Either intersection node OR null return tempa; }}⏱️ ComplexityTime ComplexityO(m + n)Space ComplexityO(1)⚖️ Approach ComparisonApproachTimeSpaceNotesBrute ForceO(m*n)O(1)Too slowLength DifferenceO(m+n)O(1)GoodTwo Pointer SwitchO(m+n)O(1)Best & elegant❌ Common MistakesComparing values instead of nodes ❌Forgetting to switch listsNot handling null correctlyAssuming intersection always exists🔥 Interview InsightThis is one of the most clever pointer problems.It teaches:👉 How to equalize paths without extra memory👉 How pointer switching solves alignment problems🧠 Final ThoughtAt first, this trick feels like magic…But actually it’s just:Equalizing path lengths🚀 ConclusionThe Intersection of Two Linked Lists problem is a perfect example of:Smart thinking > brute forceClean logic > complex code👉 Tip: Whenever two lists need alignment, think:"Can I make both pointers travel equal distance?"That’s where the magic begins ✨

Linked ListTwo PointersIntersectionPointer SwitchingDSALeetCodeEasy

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 187 – Repeated DNA Sequences (Java Solution with Sliding Window and HashSet)

IntroductionIn this article, we will solve LeetCode 187: Repeated DNA Sequences using Java. This is a popular string problem that tests your understanding of the sliding window technique and efficient use of hash-based data structures.DNA sequences are composed of four characters:A (Adenine)C (Cytosine)G (Guanine)T (Thymine)The goal is to identify all 10-letter-long substrings that appear more than once in a given DNA string.You can try solving the problem directly on LeetCode here: https://leetcode.com/problems/repeated-dna-sequences/Problem StatementGiven a string s that represents a DNA sequence, return all the 10-letter-long substrings that occur more than once.Example 1Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"Output: ["AAAAACCCCC", "CCCCCAAAAA"]Example 2Input: s = "AAAAAAAAAAAAA"Output: ["AAAAAAAAAA"]Key ObservationsWe only need substrings of fixed length 10.The maximum length of the string can be up to 10^5.A brute-force solution checking all substrings multiple times would be inefficient.This problem can be solved efficiently using a sliding window and hash-based data structures.Approach 1: Sliding Window with HashSet (Given Solution)IdeaUse two pointers (i and j) to maintain a sliding window.Build a substring of size 10 dynamically.Store previously seen substrings in a HashSet.If a substring is already present in the set:Check if it is already in the result list.If not, add it to the result list.Slide the window forward and continue.Java Code (Your Implementation)class Solution { public List<String> findRepeatedDnaSequences(String s) { HashSet<String> ms = new HashSet<>(); List<String> lis = new ArrayList<>(); int i = 0; int j = 0; String tes = ""; while (j < s.length()) { tes += s.charAt(j); if (j - i + 1 < 10) { j++; } else { if (j - i + 1 == 10) { if (ms.contains(tes)) { boolean fl = false; for (String a : lis) { if (a.equals(tes)) { fl = true; } } if (!fl) { lis.add(tes); } } else { ms.add(tes); } tes = tes.substring(1); i++; j++; } } } return lis; }}ExplanationThe variable tes maintains the current substring.ms stores all previously seen substrings of length 10.If a substring already exists in ms, we manually check whether it has already been added to the result list.This avoids duplicate entries in the final output.Time ComplexitySliding through the string: O(n)Checking duplicates in the result list: O(n) in the worst caseOverall worst-case complexity: O(n²)Space ComplexityHashSet storage: O(n)Limitation of Approach 1The manual duplicate check using a loop inside the result list introduces unnecessary overhead. This makes the solution less efficient.We can improve this by using another HashSet to automatically handle duplicates.Approach 2: Optimized Solution Using Two HashSetsIdeaUse one HashSet called seen to track all substrings of length 10.Use another HashSet called repeated to store substrings that appear more than once.Iterate from index 0 to s.length() - 10.Extract substring of length 10.If adding to seen fails, it means it has appeared before.Add it directly to repeated.This removes the need for a nested loop.Optimized Java Codeclass Solution { public List<String> findRepeatedDnaSequences(String s) { Set<String> seen = new HashSet<>(); Set<String> repeated = new HashSet<>(); for (int i = 0; i <= s.length() - 10; i++) { String substring = s.substring(i, i + 10); if (!seen.add(substring)) { repeated.add(substring); } } return new ArrayList<>(repeated); }}Why This Approach is BetterNo manual duplicate checking.Cleaner and more readable code.Uses HashSet properties efficiently.Each substring is processed only once.Time Complexity (Optimized)Single traversal of the string: O(n)Substring extraction of fixed length 10: O(1)Overall time complexity: O(n)Space ComplexityTwo HashSets storing substrings: O(n)ConclusionLeetCode 187 is a classic example of combining the sliding window technique with hash-based data structures.The first approach works but has unnecessary overhead due to manual duplicate checks.The second approach is more optimal, cleaner, and recommended for interviews.Always leverage the properties of HashSet to avoid redundant checks.This problem highlights the importance of choosing the right data structure to optimize performance.

JavaSliding WindowMedium

Reverse Vowels of a String – From Extra Space Approach to Two Pointer Optimization (LeetCode 345)

🔗 Problem LinkLeetCode 345 – Reverse Vowels of a String 👉 https://leetcode.com/problems/reverse-vowels-of-a-string/IntroductionThis problem is very similar to Reverse Only Letters, but with a small twist:Instead of reversing all letters, we only reverse the vowels.At first, we might think of extracting vowels, reversing them, and putting them back. That works — but it is not the most optimal approach.In this article, we’ll:Understand the brute-force style approach (your solution)Analyze its time complexityOptimize it using the Two Pointer patternCompare both approaches📌 Problem UnderstandingYou are given a string s.You must:Reverse only the vowelsKeep all other characters in the same positionVowels include:a, e, i, o, uA, E, I, O, UExample 1Input: "IceCreAm"Output: "AceCreIm"Vowels: ['I','e','e','A'] Reversed: ['A','e','e','I']Example 2Input: "leetcode"Output: "leotcede"🧠 Your First Approach – Extract, Reverse, ReplaceYour idea:Extract all vowels into a string.Store their indices.Reverse the vowel string.Replace vowels at stored indices.Let’s look at your code.💻 Your Code (Extract & Replace Method)class Solution { public String reverseVowels(String s) { String vow = ""; List<Integer> lis = new ArrayList<>(); HashMap<Integer,Character> mp = new HashMap<>(); for(int i =0;i<s.length();i++){ if(((s.charAt(i) == 'a') || (s.charAt(i) == 'e') || (s.charAt(i) == 'i') || (s.charAt(i) == 'o') || (s.charAt(i) == 'u') || (s.charAt(i) == 'A') || (s.charAt(i) == 'E') || (s.charAt(i) == 'I') || (s.charAt(i) == 'O') || (s.charAt(i) == 'U')) ){ vow += s.charAt(i); lis.add(i); } } String so = ""; for(int i = vow.length()-1; i >= 0; i--){ so += vow.charAt(i); } for(int i =0; i< lis.size();i++){ mp.put(lis.get(i), so.charAt(i)); } String ans = ""; for(int i =0 ; i< s.length();i++){ if(mp.containsKey(i)){ ans += mp.get(i); }else{ ans += s.charAt(i); } } return ans; }}🔍 How This WorksStep 1 – Extract VowelsStore:Vowel characters in vowTheir indices in lisStep 2 – Reverse the Vowel StringCreate new reversed string so.Step 3 – Map Indices to Reversed VowelsUse a HashMap to store:index → reversed vowelStep 4 – Build Final StringTraverse original string:If index in map → use reversed vowelElse → use original character⚠️ Problem with This ApproachAlthough correct, it has inefficiencies:String concatenation (+=) → O(n²) in worst caseExtra space used:Vowel stringList of indicesHashMapFinal answer stringTime Complexity: O(n²) (due to string concatenation) Space Complexity: O(n)We can do better.🚀 Optimized Approach – Two Pointers (Best Solution)Instead of extracting vowels separately, we can:Convert string into char arrayUse two pointersSwap vowels directlyThis avoids extra structures.💻 Optimized Two Pointer Solutionclass Solution { public String reverseVowels(String s) { int i = 0, j = s.length() - 1; char[] arr = s.toCharArray(); while(i < j){ if(!isVowel(arr[i])){ i++; } else if(!isVowel(arr[j])){ j--; } else{ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } return new String(arr); } private boolean isVowel(char c){ return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'|| c=='A'||c=='E'||c=='I'||c=='O'||c=='U'; }}🎯 Why This WorksWe:Move left pointer until vowel foundMove right pointer until vowel foundSwapContinueNo extra storage needed.⏱ Complexity ComparisonYour ApproachTime: O(n²) (string concatenation)Space: O(n)Two Pointer ApproachTime: O(n)Space: O(n) (char array)Much cleaner and faster.🔥 Key LearningThis problem reinforces:Two pointer patternIn-place modificationAvoiding unnecessary extra spaceRecognizing optimization opportunitiesWhenever you see:"Reverse something but keep other elements fixed"Think:👉 Two Pointers🏁 Final ThoughtsYour approach shows strong logical thinking:Extract → Reverse → ReplaceThat’s a valid way to solve it.But the optimized two-pointer approach is more interview-friendly.If you master this pattern, you can easily solve:Reverse Only LettersReverse StringValid PalindromeRemove Duplicates from Sorted Array

Two PointersString ManipulationHashMapLeetCodeEasy

LeetCode 104: Maximum Depth of Binary Tree – Java Recursive Solution Explained

IntroductionLeetCode 104 – Maximum Depth of Binary Tree is one of the most important beginner tree problems in Data Structures and Algorithms.This problem teaches:Binary Tree TraversalDepth First Search (DFS)RecursionTree Height CalculationDivide and ConquerIt is one of the most frequently asked tree questions in coding interviews because it builds the foundation for:Tree recursionHeight problemsBalanced tree problemsDiameter problemsDFS traversalIf you are starting binary trees, this is one of the best problems to master first.Problem Link🔗 https://leetcode.com/problems/maximum-depth-of-binary-tree/Problem StatementGiven the root of a binary tree:Return:Maximum depth of the treeMaximum depth means:Number of nodes along the longest path from root to the farthest leaf node.Example 1Inputroot = [3,9,20,null,null,15,7]Tree: 3 / \ 9 20 / \ 15 7Output3Explanation:Longest path:3 → 20 → 15contains:3 nodesExample 2Inputroot = [1,null,2]Tree:1 \ 2Output:2Understanding Maximum DepthDepth means:How many levels exist in the treeFor example: 1 / \ 2 3 / 4Levels:Level 1 → 1Level 2 → 2,3Level 3 → 4Maximum depth:3Key ObservationThe depth of a tree depends on:Maximum depth of left subtreeandMaximum depth of right subtreeSo:Depth(root)=1 + max(leftDepth, rightDepth)This is the core recursive formula.Recursive IntuitionAt every node:Find depth of left subtreeFind depth of right subtreeTake maximumAdd current nodeThis naturally becomes a recursive DFS problem.Java Recursive Solutionclass Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); return 1 + Math.max(left, right); }}Why This WorksAt every node:Recursively calculate left depthRecursively calculate right depthChoose bigger depthAdd:1for current node.This continues until leaf nodes.Dry RunInput 3 / \ 9 20 / \ 15 7Step 1Start from root:3Step 2Left subtree:9Depth:1Step 3Right subtree:20Its children:15 and 7Depth becomes:2Step 4At root:1 + max(1,2)Result:3Recursive Call FlowmaxDepth(3) ├── maxDepth(9) │ ├── 0 │ └── 0 │ └── maxDepth(20) ├── maxDepth(15) └── maxDepth(7)Then values return upward.Alternative BFS ApproachWe can also solve this using:Level Order Traversalusing a queue.Every level increases depth by:1BFS Java Solutionclass Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int depth = 0; while(!queue.isEmpty()) { int size = queue.size(); for(int i = 0; i < size; i++) { TreeNode node = queue.poll(); if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } depth++; } return depth; }}DFS vs BFSApproachTechniqueSpaceDFSRecursionO(H)BFSQueueO(N)Time Complexity AnalysisRecursive DFS SolutionTime ComplexityO(N)because every node is visited once.Space ComplexityO(H)where:H = tree heightWorst case:O(N)for skewed tree.BFS SolutionTime ComplexityO(N)Space ComplexityO(N)queue may contain full level.Interview ExplanationIn interviews, explain:The depth of a node depends on the maximum depth between its left and right subtree. This naturally forms a recursive divide-and-conquer problem.This demonstrates:Tree recursion understandingDFS traversal knowledgeDivide and conquer thinkingCommon Mistakes1. Forgetting Base CaseAlways handle:if(root == null) return 0;2. Using Min Instead of MaxWe need:Longest pathnot shortest.3. Incorrect Depth CountingRemember to add:1for current node.FAQsQ1. What is maximum depth?It is the number of nodes in the longest root-to-leaf path.Q2. Why is recursion preferred?Tree problems naturally fit recursive structures.Q3. Can this be solved iteratively?Yes.Using BFS with queue.Q4. Is this problem important for interviews?Very important.It is one of the most fundamental tree recursion problems.Related ProblemsAfter mastering this problem, practice:Minimum Depth of Binary TreeBalanced Binary TreeDiameter of Binary TreeBinary Tree Level Order TraversalPath SumConclusionLeetCode 104 is one of the most important beginner binary tree problems.It teaches:Recursive DFSTree height calculationDivide and conquerBinary tree traversalThe key insight is:Maximum depth equals 1 + maximum depth of left and right subtree.Once this recursive pattern becomes clear, many advanced tree problems become easier to solve.

LeetCodeDepth of Binary TreeJavaBinary TreeDFSBFSRecursionTreeEasy

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

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

LeetCodeSliding WindowMedium