Search Blogs

Showing results for "GeeksofGeeks"

Found 3 results

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

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

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