Search Blogs

Showing results for "GeeksForGeeks"

Found 17 results

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

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

GeeksforGeeksBinary SearchEasy

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

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

GeeksForGeeksEasyBinary SearchSorted Array

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

Equilibrium Point

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

GeeksforGeeksPrefix SumEasy

Sort a Stack Using Recursion - Java Solution Explained

IntroductionSort a Stack is one of those problems that feels impossible at first — you only have access to the top of a stack, you cannot index into it, and the only tools you have are push, pop, and peek. How do you sort something with such limited access?The answer is recursion. And this problem is a perfect example of how recursion can do something elegant that feels like it should require much more complex logic.You can find this problem here — Sort a Stack — GeeksForGeeksThis article explains the complete intuition, both recursive functions in detail, a thorough dry run, all approaches, and complexity analysis.What Is the Problem Really Asking?You have a stack of integers. Sort it so that the smallest element is at the bottom and the largest element is at the top.Input: [41, 3, 32, 2, 11] (11 is at top)Output: [41, 32, 11, 3, 2] (2 is at top, 41 at bottom)Wait — if smallest is at bottom and largest at top, then popping gives you the smallest first. So the stack is sorted in ascending order from top to bottom when you pop.The constraints make this interesting — you can only use stack operations (push, pop, peek, isEmpty). No arrays, no sorting algorithms directly on the data, no random access.Real Life Analogy — Sorting a Stack of BooksImagine a stack of books of different thicknesses on your desk. You want the thinnest book on top and thickest at the bottom. But you can only take from the top.Here is what you do — pick up books one by one from the top and set them aside. Once you have removed enough, place each book back in its correct position. If the book you are placing is thicker than what is currently on top, slide the top books aside temporarily, place the thick book down, then put the others back.That is exactly what the recursive sort does — take elements out one by one, and insert each back into the correct position.The Core Idea — Two Recursive Functions Working TogetherThe solution uses two recursive functions that work hand in hand:sortStack(st) — removes elements one by one until the stack is empty, then inserts each back using insertinsert(st, temp) — inserts a single element into its correct sorted position in an already-sorted stackThink of it like this — sortStack is the manager that empties the stack recursively, and insert is the worker that places each element in the right position on the way back.Function 1: sortStack — The Main Recursive Driverpublic void sortStack(Stack<Integer> st) { // base case — empty or single element is already sorted if (st.empty() || st.size() == 1) return; // Step 1: remove the top element int temp = st.pop(); // Step 2: recursively sort the remaining stack sortStack(st); // Step 3: insert the removed element in correct position insert(st, temp);}How to Think About ThisThe leap of faith here — trust that sortStack correctly sorts whatever is below. After the recursive call, the remaining stack is perfectly sorted. Now your only job is to insert temp (the element you removed) into its correct position in that sorted stack.This is the classic "solve smaller, fix current" recursion pattern. Reduce the problem by one element, trust recursion for the rest, then fix the current element's position.Function 2: insert — Placing an Element in Sorted Positionvoid insert(Stack<Integer> st, int temp) { // base case 1: stack is empty — just push // base case 2: top element is smaller or equal — push on top if (st.empty() || st.peek() <= temp) { st.push(temp); return; } // top element is greater than temp // temp needs to go below the top element int val = st.pop(); // temporarily remove the top insert(st, temp); // try inserting temp deeper st.push(val); // restore the removed element on top}How to Think About ThisYou want to insert temp in sorted order. The stack is already sorted (largest on top). So:If the top is smaller than or equal to temp → temp belongs on top. Push it.If the top is greater than temp → temp needs to go below the top. So pop the top temporarily, try inserting temp deeper, then push the top back.This is the same "pop, recurse deeper, push back" pattern you saw in the Baseball Game problem — when you need to access elements below the top without permanent removal.Complete Solutionclass Solution { // insert temp into its correct position in sorted stack void insert(Stack<Integer> st, int temp) { if (st.empty() || st.peek() <= temp) { st.push(temp); return; } int val = st.pop(); insert(st, temp); st.push(val); } // sort the stack using recursion public void sortStack(Stack<Integer> st) { if (st.empty() || st.size() == 1) return; int temp = st.pop(); // remove top sortStack(st); // sort remaining insert(st, temp); // insert top in correct position }}Detailed Dry Run — st = [3, 2, 1] (1 at top)Let us trace every single call carefully.sortStack calls (going in):sortStack([3, 2, 1]) temp = 1, remaining = [3, 2] call sortStack([3, 2]) temp = 2, remaining = [3] call sortStack([3]) size == 1, return ← base case now insert(st=[3], temp=2) peek=3 > 2, pop val=3 insert(st=[], temp=2) st empty, push 2 ← base case push val=3 back stack is now [2, 3] (3 on top) sortStack([3,2]) done → stack = [2, 3] now insert(st=[2,3], temp=1) peek=3 > 1, pop val=3 insert(st=[2], temp=1) peek=2 > 1, pop val=2 insert(st=[], temp=1) st empty, push 1 ← base case push val=2 back stack = [1, 2] push val=3 back stack = [1, 2, 3] (3 on top)sortStack done → stack = [1, 2, 3]✅ Final stack (3 on top, 1 at bottom): largest at top, smallest at bottom — correctly sorted!Detailed Dry Run — st = [41, 3, 32, 2, 11] (11 at top)Let us trace at a higher level to see the pattern:sortStack calls unwinding (popping phase):sortStack([41, 3, 32, 2, 11]) pop 11, sortStack([41, 3, 32, 2]) pop 2, sortStack([41, 3, 32]) pop 32, sortStack([41, 3]) pop 3, sortStack([41]) base case — return insert([41], 3) → [3, 41] (41 on top) insert([3, 41], 32) → [3, 32, 41] (41 on top) insert([3, 32, 41], 2) → [2, 3, 32, 41] (41 on top) insert([2, 3, 32, 41], 11) → [2, 3, 11, 32, 41] (41 on top)✅ Final: [2, 3, 11, 32, 41] with 41 at top, 2 at bottom — correct!Let us verify the insert([3, 32, 41], 2) step in detail since it involves multiple pops:insert(st=[3, 32, 41], temp=2) peek=41 > 2, pop val=41 insert(st=[3, 32], temp=2) peek=32 > 2, pop val=32 insert(st=[3], temp=2) peek=3 > 2, pop val=3 insert(st=[], temp=2) st empty, push 2 push val=3 back → [2, 3] push val=32 back → [2, 3, 32] push val=41 back → [2, 3, 32, 41]Beautiful chain of pops followed by a chain of pushes — recursion handling what would be very messy iterative logic.Approach 2: Using an Additional Stack (Iterative)If recursion is not allowed or you want an iterative solution, you can use a second stack.public void sortStack(Stack<Integer> st) { Stack<Integer> tempStack = new Stack<>(); while (!st.empty()) { int curr = st.pop(); // move elements from tempStack back to st // until we find the right position for curr while (!tempStack.empty() && tempStack.peek() > curr) { st.push(tempStack.pop()); } tempStack.push(curr); } // move everything back to original stack while (!tempStack.empty()) { st.push(tempStack.pop()); }}How This WorkstempStack is maintained in sorted order (smallest on top). For each element popped from st, we move elements from tempStack back to st until we find the right position, then push. At the end, transfer everything back.Time Complexity: O(n²) — same as recursive approach Space Complexity: O(n) — explicit extra stackApproach 3: Using Collections.sort (Cheat — Not Recommended)public void sortStack(Stack<Integer> st) { List<Integer> list = new ArrayList<>(st); Collections.sort(list); // ascending st.clear(); for (int num : list) { st.push(num); // smallest pushed first = smallest at bottom }}This gives the right answer but completely defeats the purpose of the problem. Never use this in an interview — it shows you do not understand the problem's intent.Time Complexity: O(n log n) Space Complexity: O(n)Approach ComparisonApproachTimeSpaceAllowed in InterviewCode ComplexityRecursive (Two Functions)O(n²)O(n)✅ Best answerMediumIterative (Two Stacks)O(n²)O(n)✅ Good alternativeMediumCollections.sortO(n log n)O(n)❌ Defeats purposeEasyTime and Space Complexity AnalysisRecursive ApproachTime Complexity: O(n²)For each of the n elements popped by sortStack, the insert function may traverse the entire stack to find the correct position — O(n) per insert. Total: O(n) × O(n) = O(n²).This is similar to insertion sort — and in fact, this recursive approach IS essentially insertion sort implemented on a stack using recursion.Space Complexity: O(n)No extra data structure is used. But the call stack holds up to n frames for sortStack and up to n additional frames for insert. In the worst case, total recursion depth is O(n) + O(n) = O(n) space.The Connection to Insertion SortIf you have studied sorting algorithms, this solution will look very familiar. It is Insertion Sort implemented recursively on a stack:sortStack is like the outer loop — take one element at a timeinsert is like the inner loop — find the correct position by comparing and shiftingThe key difference from array-based insertion sort is that "shifting" in an array is done by moving elements right. Here, "shifting" is done by temporarily popping elements off the stack, inserting at the right depth, then pushing back. Recursion handles the "shift" naturally.Common Mistakes to AvoidWrong base case in insert The base case is st.empty() || st.peek() <= temp. Both conditions are needed. Without st.empty(), you call peek() on an empty stack and get an exception. Without st.peek() <= temp, you never stop even when you find the right position.Using < instead of <= in insert Using strictly less than means equal elements get treated as "wrong position" and cause unnecessary recursion. Using <= correctly handles duplicates — equal elements stay in their current relative order.Calling sortStack instead of insert inside insert insert should only call itself recursively. Calling sortStack inside insert re-sorts an already-sorted stack — completely wrong and causes incorrect results.Not pushing val back after the recursive insert call This is the most common bug. After insert(st, temp) places temp in the correct position, you must push val back on top. Forgetting this loses elements from the stack permanently.FAQs — People Also AskQ1. How do you sort a stack without using extra space in Java? Using recursion — the call stack itself serves as temporary storage. sortStack removes elements one by one and insert places each back in its correct sorted position. No explicit extra data structure is needed, but O(n) implicit call stack space is used.Q2. What is the time complexity of sorting a stack using recursion? O(n²) in all cases — for each of the n elements, the insert function traverses up to n elements to find the correct position. This is equivalent to insertion sort applied to a stack.Q3. Can you sort a stack without recursion? Yes — using a second auxiliary stack. Pop elements from the original stack one by one and insert each into the correct position in the second stack by temporarily moving elements back. Transfer everything back to the original stack at the end.Q4. Why does the insert function need to push val back after the recursive call? Because the goal of insert is to place temp in the correct position WITHOUT losing any existing elements. When we pop val temporarily to go deeper, we must restore it after temp has been placed. Not restoring it means permanently losing that element from the stack.Q5. Is sorting a stack asked in coding interviews? Yes, it appears frequently at companies like Amazon, Adobe, and in platforms like GeeksForGeeks and InterviewBit. It tests whether you understand recursion deeply enough to use it as a mechanism for reordering — not just for computation.Similar Problems to Practice NextDelete Middle Element of a Stack — use same recursive pop-recurse-push patternReverse a Stack — very similar recursive approach, great warmup84. Largest Rectangle in Histogram — advanced stack problem946. Validate Stack Sequences — stack simulation150. Evaluate Reverse Polish Notation — stack with operationsConclusionSort a Stack Using Recursion is a beautiful problem that demonstrates the true power of recursion — using the call stack itself as temporary storage to perform operations that would otherwise require extra data structures.The key insight is splitting the problem into two clean responsibilities. sortStack handles one job — peel elements off one by one until the base case, then trigger insert on the way back up. insert handles one job — place a single element into its correct position in an already-sorted stack by temporarily moving larger elements aside.Once you see those two responsibilities clearly, the code almost writes itself. And once this pattern clicks, it directly prepares you for more advanced recursive problems like reversing a stack, deleting the middle element, and even understanding how recursive backtracking works at a deeper level.

StackRecursionJavaGeeksForGeeksMedium

Delete Middle Element of Stack Without Extra Space | Java Recursive Solution

IntroductionStack-based problems are a core part of data structures and algorithms (DSA) interviews. One such interesting and frequently asked question is deleting the middle element of a stack without using any additional data structure.At first glance, this problem may seem tricky because stacks only allow access to the top element. However, with the help of recursion, it becomes an elegant and intuitive solution.In this article, we will break down the problem, build the intuition, and implement an efficient recursive approach step by step.Link of Problem: GeeksforGeeks – Delete Middle of a StackProblem StatementGiven a stack s, delete the middle element of the stack without using any additional data structure.Definition of Middle ElementThe middle element is defined as:floor((size_of_stack + 1) / 2)Indexing starts from the bottom of the stack (1-based indexing)ExamplesExample 1Input:s = [10, 20, 30, 40, 50]Output:[50, 40, 20, 10]Explanation:Middle index = (5+1)/2 = 3Middle element = 30 → removedExample 2Input:s = [10, 20, 30, 40]Output:[40, 30, 10]Explanation:Middle index = (4+1)/2 = 2Middle element = 20 → removedKey InsightStacks follow LIFO (Last In, First Out), meaning:You can only access/remove the top elementYou cannot directly access the middleSo how do we solve it?We use recursion to:Pop elements until we reach the middleRemove the middle elementPush back all other elementsThis way, no extra data structure is used—just the recursion call stack.Approach: Recursive SolutionIdeaCalculate the middle positionRecursively remove elements from the topWhen the middle is reached → delete itWhile returning, push elements backCode (Java)import java.util.Stack;class Solution {void findMid(Stack<Integer> s, int mid) {// When current stack size equals middle positionif (s.size() == mid) {s.pop(); // delete middle elementreturn;}int temp = s.pop(); // remove top element// Recursive callfindMid(s, mid);// Push element back after recursions.push(temp);}// Function to delete middle element of a stackpublic void deleteMid(Stack<Integer> s) {int mid = (s.size() + 1) / 2;findMid(s, mid);}}Step-by-Step Dry RunLet’s take:Stack (bottom → top): [10, 20, 30, 40, 50]Middle index = 3Recursion pops: 50 → 40Now stack size = 3 → remove 30Push back: 40 → 50Final Stack:[10, 20, 40, 50]Complexity AnalysisTime Complexity: O(n)Each element is removed and added onceAuxiliary Space: O(n)Due to recursion call stackWhy This Approach WorksRecursion simulates stack behaviorNo extra data structures like arrays or lists are usedMaintains original order after deletionEfficient and interview-friendly solutionKey TakeawaysDirect access to middle is not possible in a stackRecursion is the key to solving such constraintsAlways think of breaking + rebuilding for stack problemsThis pattern is useful in many stack-based interview questionsWhen This Problem Is AskedThis problem is commonly seen in:Technical interviewsCoding platforms like GeeksforGeeksStack and recursion-based problem setsIt evaluates:Understanding of stack operationsRecursive thinkingProblem-solving under constraintsConclusionDeleting the middle element of a stack without extra space is a classic example of using recursion effectively. While the problem may seem restrictive, the recursive approach provides a clean and optimal solution.Mastering this concept will help you tackle more advanced stack and recursion problems with confidence.Frequently Asked Questions (FAQs)1. Can this be solved without recursion?Not efficiently without using another data structure. Recursion is the best approach under given constraints.2. Why not use an array or list?The problem explicitly restricts the use of additional data structures.3. What is the best approach?The recursive approach is optimal with O(n) time and space complexity.

GeeksofGeeksEasyStackRecursionJava

Find Length of Loop in Linked List — Complete Guide with Intuition, Dry Run & Floyd’s Cycle Algorithm

🔗 Try This ProblemPractice here:GeeksforGeeks link📌 Problem OverviewYou are given the head of a singly linked list.Your task is:Detect whether a loop (cycle) existsIf a loop exists → return the length of the loopIf no loop exists → return 0🧠 Understanding the ProblemA loop in a linked list means:👉 A node’s next pointer is pointing to a previous node, forming a cycle.Example1 → 2 → 3 → 4 → 5↑ ↓← ← ← ←Here:Loop starts at node 3Loop nodes = 3 → 4 → 5Loop length = 3💡 Intuition — How to Think About This ProblemThere are two main challenges:🔹 1. Detect if a loop exists🔹 2. Find the length of that loop🤔 Brute Force ThinkingStore visited nodes in a HashSetIf node repeats → loop detected✔ Works❌ Extra space O(n)🚀 Optimized Thinking (Floyd’s Cycle Detection)We use:Slow pointer → moves 1 stepFast pointer → moves 2 steps🧠 Key Idea👉 If a loop exists:Fast pointer will eventually meet slow pointer👉 If no loop:Fast pointer reaches null🎥 Visual Intuition & Dry Run⚙️ Optimized Approach (Step-by-Step)Step 1: Detect LoopInitialize:slow = headfast = headMove:slow → 1 stepfast → 2 stepsIf:slow == fast → loop existsStep 2: Find Length of LoopOnce loop is detected:Keep one pointer fixedMove another pointer until it comes backCount stepsWhy This Works?Because:Inside a loop, traversal becomes circularSo eventually, we will return to the same node🧪 Dry Run (Manual Understanding)Example:Loop: 3 → 4 → 5 → 3Step 1: Detect LoopSlow and fast meet inside loopStep 2: Count Loop LengthStart from meeting point:Move one pointer:3 → 4 → 5 → 3Count = 3💻 Code (Java)class Solution {public int lengthOfLoop(Node head) {Node slow = head;Node fast = head;// Step 1: Detect loopwhile(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;if(fast == slow){// Step 2: Count loop lengthint length = 1;Node temp = slow.next;while(temp != slow){temp = temp.next;length++;}return length;}}return 0; // No loop}}⏱️ Complexity AnalysisTypeValueTime ComplexityO(n)Space ComplexityO(1)🔍 Deep Insight — Why Fast Meets Slow?Fast moves twice as fast as slowInside a loop → paths become circularDifference in speed guarantees collision👉 This is a mathematical certainty in cyclic structures⚠️ Edge CasesNo loop → return 0Single node loop → return 1Large loop → still works efficiently🧩 Key TakeawaysFloyd’s Cycle Detection is powerfulLoop detection + loop length can be done in one traversalNo extra space needed🏁 Final ThoughtsThis problem is a classic linked list concept and very important for interviews.👉 Once you master this:Detect cycleFind loop lengthFind loop starting nodeAll become easier.

GeeksforGeeksLinkedListMediumFast and Slow Pointer

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

Reverse a Stack Without Extra Space | Java Recursive Solution

IntroductionReversing a stack is a classic data structures problem that frequently appears in coding interviews and competitive programming. While it may seem straightforward, the challenge lies in reversing the stack without using any additional data structure.This problem is a great way to understand the power of recursion and stack manipulation.In this article, we will explore an intuitive recursive approach, understand how it works step by step, and also briefly discuss alternative methods.Link of Problem: GeeksforGeeks – Reverse a StackProblem StatementYou are given a stack st[]. The task is to reverse the stack.Important NotesThe input array represents the stack from bottom to topThe last element is considered the topOutput should display elements from top to bottom after reversalExamplesExample 1Input:st = [1, 2, 3, 4]Output:[1, 2, 3, 4]Explanation:After reversing, the internal order becomes [4, 3, 2, 1],so when printed from top → bottom, it appears as [1, 2, 3, 4].Example 2Input:st = [3, 2, 1]Output:[3, 2, 1]Explanation:Reversed stack becomes [1, 2, 3] internally.Key InsightA stack only allows:push() → insert at toppop() → remove from topChallengeWe cannot directly insert an element at the bottom of the stack.Solution StrategyUse recursion to:Remove all elements from the stackInsert each element back at the bottomThis effectively reverses the stack.Approach: Recursive SolutionIdeaPop the top elementReverse the remaining stack recursivelyInsert the popped element at the bottomCode (Java)import java.util.Stack;class Solution {static void rever(Stack<Integer> s) {if (s.size() == 1) return;int temp = s.pop();// Reverse remaining stackrever(s);// Insert element at bottominsre(s, temp);}static void insre(Stack<Integer> s, int val) {// Base condition: empty stackif (s.empty()) {s.push(val);return;}int temp = s.pop();// Recursive callinsre(s, val);// Push back previous elementss.push(temp);}public static void reverseStack(Stack<Integer> st) {rever(st);}}Step-by-Step Dry RunLet’s take:Stack (bottom → top): [1, 2, 3, 4]Execution Flow:Pop 4 → reverse [1, 2, 3]Pop 3 → reverse [1, 2]Pop 2 → reverse [1]Insert elements at bottom in orderFinal Stack:[4, 3, 2, 1]Complexity AnalysisTime Complexity: O(n²)Each insertion at bottom takes O(n)Auxiliary Space: O(n)Due to recursion call stackWhy This Approach WorksRecursion helps access deeper elements of the stackThe helper function inserts elements at the bottomMaintains order while reversing without extra structuresAlternative Approaches1. Using Two StacksTransfer elements between stacks multiple timesEasy but uses extra space2. Using Array/ListStore elements in a listPush them back into stack⚠️ These methods violate the constraint of not using extra data structures.Key TakeawaysStack problems often require creative recursionReversing a stack without extra space is a common interview patternUnderstanding insert at bottom is crucialTime complexity is higher due to repeated insert operationsWhen This Problem Is AskedThis question is commonly seen in:Technical interviewsStack and recursion problem setsPlatforms like GeeksforGeeksIt evaluates:Understanding of stack operationsRecursive thinkingProblem-solving under constraintsConclusionReversing a stack without using extra space is a great example of how recursion can simplify complex constraints. While the solution may not be the most optimal in terms of time complexity, it is elegant and widely accepted in interviews.Mastering this pattern will help you solve many similar problems involving stack manipulation.Frequently Asked Questions (FAQs)1. Why is the time complexity O(n²)?Because inserting an element at the bottom takes O(n), and this is done for each element.2. Can this be optimized further?Not without using extra data structures. The recursive approach is optimal under constraints.3. What is the key concept to learn here?Understanding how to insert an element at the bottom of a stack using recursion.

JavaGeeksofGeeksStackRecursionReverse

All Subsequences of a String (Power Set) | Recursion & Backtracking Java Solution

IntroductionThe Power Set problem for strings is a classic question in recursion and backtracking, frequently asked in coding interviews and platforms like GeeksforGeeks.In this problem, instead of numbers, we deal with strings and generate all possible subsequences (not substrings). This makes it slightly more interesting and practical for real-world applications like pattern matching, text processing, and combinatorics.In this article, we will cover:Intuition behind subsequencesRecursive (backtracking) approachSorting for lexicographical orderAlternative approachesComplexity analysisProblem StatementGiven a string s of length n, generate all non-empty subsequences of the string.RequirementsReturn only non-empty subsequencesOutput must be in lexicographically sorted orderExamplesExample 1Input:s = "abc"Output:a ab abc ac b bc cExample 2Input:s = "aa"Output:a a aaSubsequence vs Substring (Important)Substring: Continuous charactersSubsequence: Characters can be skippedExample for "abc":Subsequences → a, b, c, ab, ac, bc, abcKey InsightFor every character, we have two choices:Include it OR Exclude itSo total subsequences:2^nWe generate all and then remove the empty string.Approach 1: Recursion (Backtracking)IntuitionAt each index:Skip the characterInclude the characterBuild all combinations recursivelyJava Code (With Explanation)import java.util.*;class Solution { // List to store all subsequences List<String> a = new ArrayList<>(); void sub(String s, int ind, String curr) { // Base case: reached end of string if (ind == s.length()) { a.add(curr); // add current subsequence return; } // Choice 1: Exclude current character sub(s, ind + 1, curr); // Choice 2: Include current character sub(s, ind + 1, curr + s.charAt(ind)); } public List<String> AllPossibleStrings(String s) { // Start recursion sub(s, 0, ""); // Remove empty string (not allowed) a.remove(""); // Sort lexicographically Collections.sort(a); return a; }}Step-by-Step Dry Run (s = "abc")Start: ""→ Exclude 'a' → "" → Exclude 'b' → "" → Exclude 'c' → "" → Include 'c' → "c" → Include 'b' → "b" → Exclude 'c' → "b" → Include 'c' → "bc"→ Include 'a' → "a" → Exclude 'b' → "a" → Exclude 'c' → "a" → Include 'c' → "ac" → Include 'b' → "ab" → Exclude 'c' → "ab" → Include 'c' → "abc"Final Output (After Sorting)a ab abc ac b bc cApproach 2: Bit ManipulationIntuitionEach subsequence can be represented using binary numbers:0 → exclude1 → includeCodeimport java.util.*;class Solution { public List<String> AllPossibleStrings(String s) { List<String> result = new ArrayList<>(); int n = s.length(); int total = 1 << n; // 2^n for (int i = 1; i < total; i++) { // start from 1 to avoid empty StringBuilder sb = new StringBuilder(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { sb.append(s.charAt(j)); } } result.add(sb.toString()); } Collections.sort(result); return result; }}Approach 3: Iterative (Expanding List)IdeaStart with empty listFor each character:Add it to all existing subsequencesCodeimport java.util.*;class Solution { public List<String> AllPossibleStrings(String s) { List<String> result = new ArrayList<>(); result.add(""); for (char ch : s.toCharArray()) { int size = result.size(); for (int i = 0; i < size; i++) { result.add(result.get(i) + ch); } } result.remove(""); Collections.sort(result); return result; }}Complexity AnalysisTime Complexity: O(n × 2ⁿ)Space Complexity: O(n × 2ⁿ)Why?Total subsequences = 2ⁿEach subsequence takes O(n) to buildWhy Sorting is RequiredThe recursion generates subsequences in random order, so we sort them:Collections.sort(result);This ensures lexicographical order as required.Key TakeawaysThis is a power set problem for stringsEach character → 2 choicesRecursion = most intuitive approachBit manipulation = most optimized thinkingAlways remove empty string if requiredCommon Interview VariationsSubsets of arrayPermutations of stringCombination sumSubsequence with conditionsConclusionThe Power Set problem is a fundamental building block in recursion and combinatorics. Once you understand the include/exclude pattern, you can solve a wide range of problems efficiently.Mastering this will significantly improve your ability to tackle backtracking and decision tree problems.Frequently Asked Questions (FAQs)1. Why is the empty string removed?Because the problem requires only non-empty subsequences.2. Why is time complexity O(n × 2ⁿ)?Because there are 2ⁿ subsequences and each takes O(n) time to construct.3. Which approach is best?Recursion → best for understandingBit manipulation → best for optimization

GeeksforGeeksRecursionJavaBacktrackingMedium

Reverse a Stack — GFG Problem Solved (3 Approaches Explained)

What Is This Problem About?This is a classic stack problem from GeeksForGeeks — "Reverse a Stack" (Medium | 4 Points). You can find it on GFG by Reverse a Stack.You are given a stack. Your job is simple — reverse it. The element that was at the bottom should now be at the top, and vice versa.Example:Input: [1, 2, 3, 4] → bottom to top, so 4 is on topOutput: [1, 2, 3, 4] → after reversal, 1 is on topWait — the input and output look the same? That is because GFG displays the result top to bottom after reversal. So after reversing, 1 comes to the top, and printing top to bottom gives [1, 2, 3, 4]. The stack is indeed reversed internally.Approach 1 — Using Two Extra StacksIntuition: Pop everything from the original stack into Stack 1 — this reverses the order once. Then pop everything from Stack 1 into Stack 2 — this reverses it again, back to original order. Now push everything from Stack 2 back into the original stack. The result? The original stack is reversed.Why does this work? Two reversals cancel each other out to give you... wait, that sounds wrong. Let us trace it:Original: [1, 2, 3, 4] → top is 4After → S1: [4, 3, 2, 1] → top is 1After → S2: [1, 2, 3, 4] → top is 4Push S2 back → st: [1, 2, 3, 4] → top is 4Hmm, that brings it back to the same thing. This approach with two stacks actually does NOT work correctly — it ends up restoring the original order. This is why the approach was commented out in the original code. Good observation to catch in an interview.Lesson: Two full reversals = no change. One reversal = what we want. Keep this in mind.Approach 2 — Using an ArrayList (Clean & Simple) ✅Intuition: Pop all elements from the stack into an ArrayList. At this point, the ArrayList holds elements in reverse order (because popping reverses). Then push them back from index 0 to end. This is the clean, working solution.Stack: [1, 2, 3, 4] → top is 4Pop into ArrayList: [4, 3, 2, 1]Push back index 0→end: push 4 → st: [4] push 3 → st: [4, 3] push 2 → st: [4, 3, 2] push 1 → st: [4, 3, 2, 1] → top is now 1 ✓The stack is now reversed. 1 is on top.public static void reverseStack(Stack<Integer> st) { if (st.empty()) return; ArrayList<Integer> list = new ArrayList<>(); // Pop all elements — goes in reverse order into list while (!st.empty()) { list.add(st.pop()); } // Push back from index 0 — restores in reversed order for (int i = 0; i < list.size(); i++) { st.push(list.get(i)); }}Time Complexity: O(n) — one pass to pop, one pass to push.Space Complexity: O(n) — for the ArrayList.Why this works: When you pop all elements into a list, the top element (last inserted) goes to index 0. When you push back from index 0, that element goes in first and ends up at the bottom. The bottom element (first inserted) was popped last, sits at the end of the list, and gets pushed last — ending up on top. That is a perfect reversal.Approach 3 — Using Recursion (No Extra Space) ✅This is the most elegant approach and the one interviewers love to ask about.Intuition: Use two recursive functions:reverseStack — pops the top element, recursively reverses the rest, then inserts the popped element at the bottom.insertAtBottom — holds all elements out while inserting one element at the very bottom, then restores everything.// Insert an item at the bottom of the stackstatic void insertAtBottom(Stack<Integer> st, int item) { if (st.empty()) { st.push(item); return; } int top = st.pop(); insertAtBottom(st, item); st.push(top);}// Reverse the stackpublic static void reverseStack(Stack<Integer> st) { if (st.empty()) return; int top = st.pop(); reverseStack(st); // reverse remaining stack insertAtBottom(st, top); // put popped element at the bottom}```**Dry Run with [1, 2, 3]:**```reverseStack([1,2,3]) → pop 3, reverseStack([1,2]) reverseStack([1,2]) → pop 2, reverseStack([1]) reverseStack([1]) → pop 1, reverseStack([]) base case → return insertAtBottom([], 1) → push 1 → [1] insertAtBottom([1], 2) → 2 < 1? no → pop 1, insert 2, push 1 → [2,1]insertAtBottom([2,1], 3) → pop 1, pop 2, push 3, push 2, push 1 → [3,2,1]Final stack top → 3... wait, let us recheck display.Top is 3, which was originally at bottom. ✓ Reversed!Time Complexity: O(n²) — for each of n elements, insertAtBottom takes O(n).Space Complexity: O(n) — recursive call stack.Which Approach Should You Use?ApproachTimeSpaceSimplicityInterview ValueTwo Extra Stacks❌ Does not workO(n)SimpleLowArrayListO(n)O(n)Very EasyMediumRecursionO(n²)O(n)ModerateHighFor a coding interview, always mention the recursive approach — it shows you understand stack mechanics deeply. For production code, the ArrayList approach is cleaner and faster.Key TakeawayReversing a stack is fundamentally about understanding LIFO. Because a stack only allows access from the top, you need a systematic way to invert the order — whether that is using auxiliary storage like an ArrayList, or using the call stack itself via recursion. Both are valid. Both teach you something different about how stacks behave.The next time you see a problem that involves reversing, reordering, or inserting at the bottom of a stack — your first instinct should be recursion with insertAtBottom. It is a pattern that appears again and again in DSA.And if you want to understand Stack from Scratch?If you are just getting started with stacks or want a complete reference — I have written a detailed in-depth guide on the Stack Data Structure in Java covering everything from what a stack is, how LIFO works, all three implementations (Array, ArrayList, LinkedList), every operation explained with code, time complexity, advantages, disadvantages, real-world use cases, and six practice problems with full solutions.Check it out here → Stack Data Structure in Java: The Complete GuideIt is the perfect companion to this problem walkthrough — start there if you want the full picture, then come back here for the problem-solving side.

StackProblemsJavaMediumGeeksForGeeksReverseStack

Permutation with Spaces Explained Using Recursion & Decision Tree | Java Solution GFG

IntroductionThe Permutation with Spaces problem is a classic recursion question that helps build a strong understanding of decision-making and backtracking patterns.Instead of generating permutations by rearranging characters, this problem focuses on inserting spaces between characters in all possible ways.What makes this problem powerful is its decision tree structure, which you’ve already visualized perfectly. In this article, we will directly connect that intuition with code.Link of Problem: GeeksforGeeks – Permutation with SpacesProblem StatementGiven a string s, generate all possible strings by placing:Either a spaceOr no spacebetween every pair of characters.Return all results in sorted order.ExampleInput:s = "ABC"Output:A B CA BCAB CABCUnderstanding Your Decision Tree (Very Important)Two Choices at Each Step:❌ Do NOT add space before the character✔️ Add space before the characterMapping TreeFrom diagram:At B:"AB" → no space"A B" → spaceAt C:From "AB":"ABC""AB C"From "A B":"A BC""A B C"Final Output (Leaf Nodes)As shown in your diagram:ABC, AB C, A BC, A B C📌 This is exactly what recursion generates.Key InsightAt every index (except first), we have:2 choices → space OR no spaceSo total combinations:2^(n-1)Approach: Recursion + Decision MakingIdeaFix the first characterFor every next character:Add space + characterAdd character directlyContinue recursivelyJava Code with Detailed Commentsimport java.util.*;class Solution { // List to store all results ArrayList<String> lis = new ArrayList<>(); void solve(String s, int ind, String curr) { // Base case: // If index reaches end of string, // we have formed one valid permutation if (ind == s.length()) { lis.add(curr); // store the result return; } // Choice 1: Add SPACE before current character // Example: "A" → "A B" solve(s, ind + 1, curr + " " + s.charAt(ind)); // Choice 2: Do NOT add space // Example: "A" → "AB" solve(s, ind + 1, curr + s.charAt(ind)); } ArrayList<String> permutation(String s) { // Start with first character (no space before it) String curr = "" + s.charAt(0); // Start recursion from index 1 solve(s, 1, curr); // Sort results as required in problem Collections.sort(lis); return lis; }}Step-by-Step Execution (Using Your Tree)For "ABC":Start → "A"At "B":"AB""A B"At "C":"ABC", "AB C""A BC", "A B C"Exactly matches your decision tree leaf nodes ✅Complexity AnalysisTime Complexity: O(2ⁿ)Space Complexity: O(2ⁿ)Why This Approach WorksRecursion explores every possible choiceEach level = one characterEach branch = decision (space / no space)Leaf nodes = final answersKey TakeawaysThis is a binary decision recursion problemAlways identify:ChoicesBase conditionYour decision tree = direct blueprint of recursionSame pattern applies to:SubsetsBinary choices problemsConclusionThe Permutation with Spaces problem becomes extremely simple once the decision tree is understood—and your diagram already captures that perfectly.The recursion directly follows the same structure:Every branch = one decisionEvery leaf = one answerMaster this pattern, and you’ll find many recursion problems much easier to solve.

MediumGeeksforGeeksRecursionJava

Merge Sort Algorithm Explained | Java Implementation, Intuition & Complexity

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

GeekfOfGeeksMediumSortingMerge SortJava

Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

IntroductionQuick Sort is one of the most powerful and widely used sorting algorithms in computer science. It follows the Divide and Conquer approach and is known for its excellent average-case performance.What makes Quick Sort special is:It sorts in-place (no extra array required)It is faster in practice than many O(n log n) algorithms like Merge SortIt is heavily used in real-world systems and librariesIn this article, we’ll go deep into:Intuition behind Quick SortPartition logic (most important part)Step-by-step dry runJava implementation with commentsTime complexity analysisCommon mistakes and optimizations🔗 Problem LinkGeeksforGeeks: Quick SortProblem StatementGiven an array arr[], sort it in ascending order using Quick Sort.Requirements:Use Divide and ConquerChoose pivot elementPlace pivot in correct positionElements smaller → left sideElements greater → right sideExamplesExample 1Input:arr = [4, 1, 3, 9, 7]Output:[1, 3, 4, 7, 9]Example 2Input:arr = [2, 1, 6, 10, 4, 1, 3, 9, 7]Output:[1, 1, 2, 3, 4, 6, 7, 9, 10]Core Idea of Quick SortPick a pivot → Place it correctly → Recursively sort left & right🔥 Key Insight (Partition is Everything)Quick Sort depends entirely on partitioning:👉 After partition:Pivot is at its correct sorted positionLeft side → smaller elementsRight side → larger elementsIntuition (Visual Understanding)Consider:[4, 1, 3, 9, 7]Step 1: Choose PivotLet’s say pivot = 4Step 2: Rearrange Elements[1, 3] 4 [9, 7]Now:Left → smallerRight → largerStep 3: Apply RecursivelyLeft: [1, 3]Right: [9, 7]Final result:[1, 3, 4, 7, 9]Partition Logic (Most Important)Your implementation uses:Pivot = first elementTwo pointers:i → moves forwardj → moves backwardJava Codeclass Solution { public void quickSort(int[] arr, int low, int high) { // Base case: if array has 1 or 0 elements if (low < high) { // Partition array and get pivot index int pivotInd = partition(arr, low, high); // Sort left part quickSort(arr, low, pivotInd - 1); // Sort right part quickSort(arr, pivotInd + 1, high); } } // Function to swap two elements void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private int partition(int[] arr, int low, int high) { int pivot = arr[low]; // choosing first element as pivot int i = low + 1; // start from next element int j = high; // start from end while (i <= j) { // Move i forward until element > pivot while (i <= high && arr[i] <= pivot) { i++; } // Move j backward until element <= pivot while (j >= low && arr[j] > pivot) { j--; } // Swap if pointers haven't crossed if (i < j) { swap(arr, i, j); } } // Place pivot at correct position swap(arr, low, j); return j; // return pivot index }}Step-by-Step Dry RunInput:[4, 1, 3, 9, 7]Execution:Pivot = 4i → moves until element > 4j → moves until element ≤ 4Swaps happen → pivot placed correctlyFinal partition:[1, 3, 4, 9, 7]Complexity AnalysisTime ComplexityCaseComplexityBest CaseO(n log n)Average CaseO(n log n)Worst CaseO(n²)Why Worst Case Happens?When array is:Already sortedReverse sortedPivot always becomes smallest/largest.Space ComplexityO(log n) (recursion stack)❌ Common MistakesWrong partition logicInfinite loops in while conditionsIncorrect pivot placementNot handling duplicates properly⚡ Optimizations1. Random PivotAvoid worst-case:int pivotIndex = low + new Random().nextInt(high - low + 1);swap(arr, low, pivotIndex);2. Median of ThreeChoose better pivot:median(arr[low], arr[mid], arr[high])Quick Sort vs Merge SortFeatureQuick SortMerge Sort link to get moreSpaceO(log n)O(n)SpeedFaster (practical)StableWorst CaseO(n²)O(n log n)Why Quick Sort is PreferredCache-friendlyIn-place sortingFaster in real-world scenariosKey TakeawaysPartition is the heart of Quick SortPivot must be placed correctlyRecursion splits problem efficientlyAvoid worst case using random pivotWhen to Use Quick SortLarge arraysMemory constraints (in-place)Performance-critical applicationsConclusionQuick Sort is one of the most efficient and practical sorting algorithms. Mastering its partition logic is crucial for solving advanced problems and performing well in coding interviews.Understanding how pointers move and how pivot is placed will make this algorithm intuitive and powerful.Frequently Asked Questions (FAQs)1. Is Quick Sort stable?No, it is not stable.2. Why is Quick Sort faster than Merge Sort?Because it avoids extra space and is cache-efficient.3. What is the most important part?👉 Partition logic

MediumJavaSortingQuick SortGeeksofGeeks

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

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

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