Search Blogs

Showing results for "Parentheses"

Found 9 results

LeetCode 1190 Reverse Substrings Between Each Pair of Parentheses – Java Solution & Explanation

IntroductionLeetCode 1190 – Reverse Substrings Between Each Pair of Parentheses is a string manipulation problem that requires reversing the substring inside every matching pair of parentheses.The important part is that reversals must happen from the innermost parentheses outward.For example:(u(love)i)The substring love is reversed first:(u(evol)i)Then the complete content inside the outer parentheses is reversed, producing:iloveuThe final answer should contain only the letters. All parentheses must be removed.A stack is useful here because it allows the opening parenthesis of the current substring to be tracked until its matching closing parenthesis is encountered.ProblemQuestion Link-: Reverse Substrings Between Each Pair of ParenthesesGiven a string s containing lowercase English letters and parentheses, reverse the strings inside each pair of matching parentheses, starting from the innermost pair.Return the resulting string without any parentheses.ExampleInput:s = "(u(love)i)"Output:"iloveu"Another example:Input:s = "(ed(et(oc))el)"Output:"leetcode"ApproachThe key observation is that when a closing parenthesis ) is encountered, the substring belonging to the most recently opened parenthesis needs to be reversed first.This naturally matches the behavior of a stack.Step 1: Store opening parenthesesWhenever ( is encountered, its index is pushed onto the stack.For example:(ed(et(oc))el)When reaching nested opening parentheses, the stack stores their positions.The most recently added opening parenthesis belongs to the innermost substring.Step 2: Process a closing parenthesisWhen ) is encountered:Get the index of the matching ( from the top of the stack.Reverse the characters between those two parentheses.Remove the opening parenthesis index from the stack.For example:(oc)When ) is reached, oc is reversed:coThe same process then happens for the next outer pair.Step 3: Remove the parenthesesAfter all reversals are complete, the character array still contains ( and ).The final traversal simply collects all characters except the parentheses.Java SolutionThe following solution uses a Stack<Integer> to keep track of opening-parenthesis positions and a character array so that the reversals can be performed directly on the string representation.class Solution { public void rev(char[] s, int en, int st) { String rev = ""; for (int i = en; i >= st; i--) { rev += s[i]; } int co = 0; for (int i = st; i <= en; i++) { s[i] = rev.charAt(co); co++; } } public String reverseParentheses(String s) { Stack<Integer> st = new Stack<>(); char[] sa = s.toCharArray(); for (int i = 0; i < sa.length; i++) { if (sa[i] == '(') { st.push(i); } if (sa[i] == ')') { int star = st.peek(); rev(sa, i, star + 1); st.pop(); } } String an = ""; for (int i = 0; i < sa.length; i++) { if (sa[i] != ')' && sa[i] != '(') { an += sa[i]; } } return an; }}How the Code Worksrev() methodThe rev() method receives:s → character arrayen → ending indexst → starting indexIt first builds the reversed substring:for (int i = en; i >= st; i--) { rev += s[i];}Then the reversed characters are copied back into the original character array:for (int i = st; i <= en; i++) { s[i] = rev.charAt(co); co++;}This changes the substring directly inside the character array.Stack processingThe main method scans the string from left to right.When an opening parenthesis is found:if (sa[i] == '(') { st.push(i);}Its index is stored in the stack.When a closing parenthesis is found:if (sa[i] == ')') { int star = st.peek(); rev(sa, i, star + 1); st.pop();}The top of the stack gives the matching opening parenthesis.The substring between them is reversed, and then the opening parenthesis is removed from the stack.This automatically processes nested parentheses from the inside out.Dry RunConsider:s = "(u(love)i)"Initial character array:(u(love)i)1. First (Its index is pushed onto the stack.Stack:[0]2. Second (The opening parenthesis before love is pushed.Stack:[0, 2]3. First )The top of the stack is index 2.The substring between index 3 and 6 is:loveReverse it:evolNow the string is effectively:(u(evol)i)The inner opening parenthesis is removed from the stack.Stack:[0]4. Final )The remaining opening parenthesis corresponds to the outer substring.Its contents are now:uevoliReverse it:iloveuFinally, the parentheses are removed.Result:iloveuWhy a Stack WorksThe problem specifically says to process the innermost parentheses first.A stack follows Last In, First Out (LIFO).For:(ed(et(oc))el)the opening parentheses are encountered in order:(((The last opening parenthesis belongs to:(oc)Therefore, it must be processed first.The stack gives exactly this behavior:Last opened ↓ (oc) ↓ (etco) ↓(edoc...el)This is why a stack is a natural data structure for this problem.Complexity AnalysisLet n be the length of the input string.The stack operations themselves take O(n) time.However, the actual reversal is performed every time a closing parenthesis is encountered. In the provided implementation, the rev() method also builds a temporary String using repeated concatenation.Therefore, the worst-case time complexity of this implementation can reach O(n²).The final construction also uses:an += sa[i];Repeated string concatenation can additionally introduce quadratic behavior in Java.Time ComplexityO(n²) worst caseSpace ComplexityO(n)The stack and character array require linear auxiliary space.A Useful OptimizationThe overall idea is correct, but two parts of the implementation can be improved:String rev = "";andan += sa[i];Since Java String objects are immutable, repeated concatenation can create many intermediate strings.A StringBuilder is generally more appropriate for repeated character construction.The core stack-based idea, however, remains the same.Interview TipWhen a string problem involves nested structures, ask whether the processing order follows the structure of a stack.For parentheses:((()))the last opened section is the first one that must be completed.That is a strong signal for using a stack.A useful pattern to remember is:Opening bracket → push its positionClosing bracket → use the latest opening positionProcess inner section → popRecognizing this pattern can make similar nested-string and bracket problems much easier to approach.ConclusionLeetCode 1190 demonstrates how a simple stack can handle nested string operations efficiently at the algorithmic level.The main idea is to store the positions of opening parentheses and, whenever a closing parenthesis appears, reverse the substring associated with the most recently opened pair.The important pattern is:Opening parenthesis → push indexClosing parenthesis → reverse current substring → popFinal pass → remove parenthesesThis approach provides a straightforward way to process nested parentheses from the inside out while keeping the implementation relatively simple in Java.

LeetCodeJavaStackStringsParenthesesMedium

LeetCode 1614: Maximum Nesting Depth of Parentheses — Java Solution Explained

IntroductionLeetCode 1614 Maximum Nesting Depth of Parentheses is a natural follow-up to LeetCode 20 Valid Parentheses. While LeetCode 20 asks "are the brackets valid?", this problem asks "how deeply are they nested?" It is a clean, focused problem that teaches you how to think about bracket depth — a concept that appears in compilers, parsers, JSON validators, and XML processors in real world software.Here is the Link of Question -: LeetCode 1614In this article we cover plain English explanation, real life analogy, two Java approaches with dry runs, complexity analysis, and all the important details you need for interviews.What Is the Problem Really Asking?You are given a valid parentheses string. You need to find the maximum number of nested (not just sequential) open parentheses at any point in the string.The key distinction here is nested vs sequential:"()()()" → depth is 1, brackets are sequential not nested"((()))" → depth is 3, brackets are fully nested inside each other"()(())" → depth is 2, the second pair is nested one level deepReal Life Analogy — Folders Inside FoldersThink of your computer's file system. You have a folder, inside that a subfolder, inside that another subfolder. The depth is how many folders deep you are at the deepest point."(1+(2*3)+((8)/4))+1" is like:Outer folder ( → depth 1Inner folder ( inside it → depth 2Innermost folder (( → depth 3The answer is how deep the deepest file is buried. You do not care about other folders — just the maximum depth reached at any single moment.Approach 1: Stack Based Solution (Classic)The IdeaUse a stack exactly like LeetCode 20. Every time you push an opening bracket, increment a counter. Every time you pop a closing bracket, record the max before decrementing. The stack size at any moment represents current depth.public int maxDepth(String s) { Stack<Character> st = new Stack<>(); int current = 0; int max = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '(') { st.push(c); current++; max = Math.max(max, current); // record depth when going deeper } else if (c == ')') { if (!st.empty() && st.peek() == '(') { max = Math.max(max, current); current--; st.pop(); } } } return max;}Dry Run — s = "()(())((()()))"( → push, current = 1, max = 1) → pop, current = 0( → push, current = 1, max = 1( → push, current = 2, max = 2) → pop, current = 1) → pop, current = 0( → push, current = 1, max = 2( → push, current = 2, max = 2( → push, current = 3, max = 3 ✅) → pop, current = 2( → push, current = 3, max = 3) → pop, current = 2) → pop, current = 1) → pop, current = 0✅ Output: 3Time Complexity: O(n) — single pass Space Complexity: O(n) — stack holds up to n/2 opening bracketsApproach 2: Counter Only — No Stack (Optimal) ✅The IdeaThis is the smartest approach and the real insight of this problem. You do not actually need a stack at all! Think about it — the depth at any moment is simply how many unmatched opening brackets we have seen so far. That is just a counter!( → increment counter, update max) → decrement counterEverything else → ignorepublic int maxDepth(String s) { int current = 0; int max = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { current++; max = Math.max(max, current); } else if (s.charAt(i) == ')') { current--; } } return max;}This is beautifully simple. No stack, no extra memory, just two integer variables.Dry Run — s = "(1+(2*3)+((8)/4))+1"Only tracking ( and ), ignoring digits and operators:( → current = 1, max = 1( → current = 2, max = 2) → current = 1( → current = 2, max = 2( → current = 3, max = 3 ✅) → current = 2) → current = 1) → current = 0✅ Output: 3Time Complexity: O(n) — single pass Space Complexity: O(1) — only two integer variables, no extra storage!Why Update Max on ( Not on )?This is the most important implementation detail. You update max when you open a bracket, not when you close it. Why?Because when you encounter (, your depth just increased to a new level — that is when you might have hit a new maximum. When you encounter ), you are going back up — depth is decreasing, so it can never be a new maximum.Always capture the peak on the way down into nesting, not on the way back out.Stack vs Counter — Which to Use?The counter approach is strictly better here — same time complexity but O(1) space instead of O(n). In an interview, start by mentioning the stack approach to show you recognize the stack pattern, then immediately offer the counter optimization to show deeper understanding.This mirrors the same progression as LeetCode 844 Backspace String Compare — where the O(1) two pointer follow-up impressed interviewers more than the standard stack solution.How This Fits the Stack Pattern SeriesLooking at the full series you have been solving:20 Valid Parentheses — are brackets correctly matched? 1614 Maximum Nesting Depth — how deeply are they nested?These two problems are complementary. One validates structure, the other measures depth. Together they cover the two most fundamental questions you can ask about a bracket string. Real world parsers need to answer both — "is this valid?" and "how complex is the nesting?"Common Mistakes to AvoidUpdating max after decrementing on ) If you write current-- before Math.max, you will always be one level too low and miss the true maximum. Always capture max before or at the moment of increment, never after decrement.Counting all characters not just brackets Digits, operators like +, -, *, / must be completely ignored. Only ( and ) affect depth.Using a Stack when a counter suffices Since the problem guarantees a valid parentheses string, you never need to validate matching — just track depth. A Stack adds unnecessary complexity and memory overhead here.FAQs — People Also AskQ1. What is nesting depth in LeetCode 1614? Nesting depth is the maximum number of open parentheses that are simultaneously unclosed at any point in the string. For example "((()))" has depth 3 because at the innermost point, three ( are open at the same time.Q2. What is the best approach for LeetCode 1614 in Java? The counter approach is optimal — O(n) time and O(1) space. Increment a counter on (, update max, decrement on ). No stack needed since the string is guaranteed to be a valid parentheses string.Q3. What is the time complexity of LeetCode 1614? Both approaches are O(n) time. The Stack approach uses O(n) space while the counter approach uses O(1) space, making the counter approach strictly better.Q4. What is the difference between LeetCode 20 and LeetCode 1614? LeetCode 20 validates whether a bracket string is correctly formed. LeetCode 1614 assumes the string is already valid and asks how deeply the brackets are nested. LeetCode 20 needs a stack for matching; LeetCode 1614 only needs a counter.Q5. Is LeetCode 1614 asked in coding interviews? It appears occasionally as a warmup or follow-up after LeetCode 20. The more important skill it tests is recognizing when a stack can be replaced by a simpler counter — that kind of space optimization thinking is valued in interviews.Similar LeetCode Problems to Practice Next20. Valid Parentheses — Easy — validate bracket structure1021. Remove Outermost Parentheses — Easy — depth-based filtering1249. Minimum Remove to Make Valid Parentheses — Medium — remove minimum brackets32. Longest Valid Parentheses — Hard — longest valid substring394. Decode String — Medium — nested brackets with encodingConclusionLeetCode 1614 Maximum Nesting Depth of Parentheses teaches a deceptively simple but important lesson — not every bracket problem needs a stack. When the string is guaranteed valid and you only need to measure depth, a counter is all you need.The progression from LeetCode 20 to 1614 perfectly illustrates how understanding the core problem deeply leads to elegant simplifications. Master both, understand why one needs a stack and the other does not, and you will have a strong foundation for every bracket problem in your interview journey.

StringStackLeetCodeEasy

LeetCode 22 Generate Parentheses | Backtracking Java Solution Explained

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

MediumLeetCodeJavaRecursion

LeetCode 1021: Remove Outermost Parentheses — Java Solution Explained

IntroductionLeetCode 1021 Remove Outermost Parentheses sounds intimidating with words like "primitive decomposition" but once you strip away the fancy terminology, it is a beautifully simple problem. It builds directly on the depth-counting technique from LeetCode 1614 and is a perfect example of how one clean insight can collapse a seemingly complex problem into just a few lines of code.Here is the Link of Question -: LeetCode 1021In this article we cover plain English explanation, what "primitive" really means, two Java approaches with detailed dry runs, complexity analysis, and everything you need to ace this in an interview.What Is the Problem Really Asking?Let us ignore the formal definition for a moment and think practically.A primitive string is the smallest self-contained valid bracket group. Think of it as a top-level unit — it opens, closes completely, and is not part of a bigger bracket group.For "(()())(())":"(()())" is one primitive — it opens and fully closes"(())" is another primitive — it opens and fully closes afterNow from each primitive, remove only the outermost opening and closing bracket, keep everything inside."(()())" → remove outer → "()()""(())" → remove outer → "()"Combined → "()()()"That is literally the whole problem!Real Life Analogy — Gift Boxes Inside a Shipping BoxImagine you ordered gifts online. They all arrive in one big shipping box. Inside that box are individual gift boxes. Inside some gift boxes are smaller boxes.The "primitive decomposition" is identifying each individual gift box inside the shipping box. Removing the outermost parentheses is like removing just the outer gift box wrapping but keeping everything inside it intact.You are not unpacking the inner boxes — just peeling off one layer from each top-level group.Understanding Primitive Decomposition VisuallyFor s = "(()())(())(()(()))":( ( ) ( ) ) ( ( ) ) ( ( ) ( ( ) ) )|_________| |_______| |_____________| primitive1 primitive2 primitive3Each group that starts at depth 0 and returns to depth 0 is one primitive. Remove the outermost ( and ) from each and concatenate what remains.The depth analogy from LeetCode 1614 is the key — a primitive starts when depth goes from 0 to 1 and ends when depth returns to 0.Approach 1: Counter With Substring (Your Solution) ✅The IdeaTrack depth with a counter. Use start and end pointers to mark the boundaries of each primitive. When depth hits 0, you have found a complete primitive — append everything between start+1 and end (skipping the outermost brackets) to the result.public String removeOuterParentheses(String s) { StringBuilder sb = new StringBuilder(); int c = 0; int start = 0; int end = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { c++; } else { c--; } if (c == 0) { // primitive found from index start to end (inclusive) sb.append(s.substring(start + 1, end)); // skip outermost ( and ) start = end + 1; // next primitive starts after current end } end++; } return sb.toString();}Dry Run — s = "(()())(())"Tracking c, start, end at each step:i=0, ( → c=1, end=1i=1, ( → c=2, end=2i=2, ) → c=1, end=3i=3, ( → c=2, end=4i=4, ) → c=1, end=5i=5, ) → c=0 → primitive found! append s.substring(1, 5) = "()()" → start=6, end=6i=6, ( → c=1, end=7i=7, ( → c=2, end=8i=8, ) → c=1, end=9i=9, ) → c=0 → primitive found! append s.substring(7, 9) = "()" → start=10, end=10Result: "()()" + "()" = "()()()" ✅Time Complexity: O(n) — single pass plus substring operations Space Complexity: O(n) — StringBuilder stores the resultApproach 2: Counter With Depth Filter (Cleaner & More Intuitive)The IdeaInstead of tracking start/end pointers, use depth directly to decide whether to include each character. The insight is:The outermost ( of each primitive is always encountered when c goes from 0 to 1 — skip itThe outermost ) of each primitive is always encountered when c goes from 1 to 0 — skip itEvery other character is inside some primitive — include itpublic String removeOuterParentheses(String s) { StringBuilder sb = new StringBuilder(); int depth = 0; for (char c : s.toCharArray()) { if (c == '(') { if (depth > 0) { sb.append(c); // not the outermost (, include it } depth++; } else { depth--; if (depth > 0) { sb.append(c); // not the outermost ), include it } } } return sb.toString();}This is arguably the most elegant solution. No pointers, no substring, just one rule — if depth is already greater than 0 when you see (, it is not the outer one. If depth is still greater than 0 after decrementing on ), it is not the outer one.Dry Run — s = "()()" (Edge Case)( → depth=0, skip it, depth becomes 1) → depth becomes 0, depth=0 so skip it( → depth=0, skip it, depth becomes 1) → depth becomes 0, depth=0 so skip itResult: "" ✅ Both are primitives "()" and "()", removing outer from each gives empty string.Dry Run — s = "(()())(())(()(()))"Let us trace just which characters get included vs skipped:For the first primitive "(()())":( at depth 0 → skip (outermost opener)( at depth 1 → include) at depth 2→1 → include( at depth 1 → include) at depth 2→1 → include) at depth 1→0 → skip (outermost closer)Inner content "()()" included ✅Same logic applies to each subsequent primitive. Final result: "()()()()(())" ✅Time Complexity: O(n) — single pass Space Complexity: O(n) — StringBuilder stores resultApproach 3: Stack Based (Verbose but Clear)The IdeaUse an explicit stack to track open brackets. When the stack becomes empty after a ), you have found a complete primitive. Collect all characters between the outermost brackets.public String removeOuterParentheses(String s) { StringBuilder sb = new StringBuilder(); Stack<Character> st = new Stack<>(); int start = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { st.push('('); } else { st.pop(); } if (st.empty()) { // primitive ends at i, extract inner content sb.append(s.substring(start + 1, i)); start = i + 1; } } return sb.toString();}This is the most verbose but makes the primitive detection very explicit — stack empty means primitive complete. Great for explaining your thought process in an interview before optimizing.Time Complexity: O(n) Space Complexity: O(n) — stack storageApproach ComparisonThe Stack approach is clearest for explaining primitive detection. The pointer-based counter approach (your solution) is direct and efficient. The depth-filter counter approach is the most elegant — no pointers, no substrings, just a single depth check per character. All three are O(n) time. The depth-filter approach wins on code clarity.How This Connects to the Full SeriesLooking at the bracket problem series you have been building:20 Valid Parentheses — is the string valid? 1614 Maximum Nesting Depth — how deep is the nesting? 1021 Remove Outermost Parentheses — identify and strip top-level groupsEach problem adds one more layer of understanding about bracket strings. The depth counter technique from 1614 directly powers the optimal solution here. This is pattern building at its best.Common Mistakes to AvoidOff-by-one in substring indices In your solution, s.substring(start+1, end) skips the outermost ( by using start+1, and end (not end+1) naturally excludes the outermost ) since end points to it. Getting these indices wrong by even one position gives completely wrong output.Appending the outermost brackets in the depth-filter approach The condition order matters — for (, check depth BEFORE incrementing. For ), check depth AFTER decrementing. Flipping these gives wrong results.Forgetting to update start after each primitive In pointer-based approaches, always set start = end + 1 (or start = i + 1) after appending each primitive, otherwise the next primitive's start index is wrong.FAQs — People Also AskQ1. What is a primitive valid parentheses string in LeetCode 1021? A primitive is the smallest self-contained valid bracket group that cannot be split into two smaller valid groups. It starts when depth goes from 0 to 1 and ends when depth returns to 0. For example in "(()())(())", the primitives are "(()())" and "(())".Q2. What is the most elegant solution for LeetCode 1021? The depth-filter counter approach — increment depth on (, decrement on ), and only append characters when depth is greater than 0 for ( and still greater than 0 after decrement for ). This skips outermost brackets naturally without tracking indices.Q3. What is the time complexity of LeetCode 1021? All approaches run in O(n) time with a single pass. Space complexity is O(n) for storing the output string in StringBuilder.Q4. How is LeetCode 1021 different from LeetCode 1614? LeetCode 1614 finds the maximum depth by tracking a counter. LeetCode 1021 uses the same counter technique but to identify primitive boundaries and strip their outermost characters. 1614 returns a number, 1021 returns a modified string.Q5. Is LeetCode 1021 asked in coding interviews? It appears occasionally as a follow-up to Valid Parentheses or Nesting Depth problems. The real skill it tests is understanding primitive decomposition — identifying self-contained units within a bracket string — which appears in real world parser and compiler design.Similar LeetCode Problems to Practice Next20. Valid Parentheses — Easy — validate bracket structure1614. Maximum Nesting Depth of Parentheses — Easy — find max depth1249. Minimum Remove to Make Valid Parentheses — Medium — remove minimum brackets394. Decode String — Medium — nested brackets with encoding32. Longest Valid Parentheses — Hard — longest valid substringConclusionLeetCode 1021 Remove Outermost Parentheses is a satisfying problem once you realize that "primitive decomposition" is just a fancy way of saying "find each top-level bracket group." The depth counter is the key — depth 0 to 1 marks the start of a primitive, depth 1 to 0 marks its end.The depth-filter approach is the cleanest solution — one pass, one counter, one condition. No substring, no pointers, just elegance. Master this alongside LeetCode 20 and 1614 and you will have a complete toolkit for any bracket string problem that comes your way.

StringStackEasyLeetCode

LeetCode 20: Valid Parentheses — Java Solution Explained

IntroductionLeetCode 20 Valid Parentheses is arguably the single most asked Easy problem in coding interviews. It appears at Google, Amazon, Microsoft, Meta, and virtually every company that does technical interviews. It is the textbook introduction to the Stack data structure and teaches you a pattern that shows up in compilers, code editors, HTML parsers, and mathematical expression evaluators.Here is the Link of Question -: LeetCode 20In this article we cover plain English explanation, real life analogy, the optimal stack solution with detailed dry run, all tricky edge cases, complexity analysis, common mistakes, and FAQs.What Is the Problem Really Asking?You are given a string containing only bracket characters — (, ), {, }, [, ]. You need to check if the brackets are correctly matched and nested.Three rules must hold:Every opening bracket must be closed by the same type of closing bracketBrackets must be closed in the correct order — the most recently opened must be closed firstEvery closing bracket must have a corresponding opening bracketReal Life Analogy — Russian Nesting DollsThink of Russian nesting dolls. You open the biggest doll first, then a medium one inside it, then a small one inside that. To close them back, you must close the smallest first, then medium, then biggest. You cannot close the biggest doll while the smallest is still open inside.That is exactly how brackets work. The last opened bracket must be the first one closed. This Last In First Out behavior is precisely what a Stack is built for.Another analogy — think of a text editor like VS Code. When you type (, it automatically adds ). If you try to close with ] instead, the editor highlights an error. This problem is essentially building that validation logic.The Only Approach You Need: StackThe IdeaScan the string left to rightIf you see an opening bracket → push it onto the stackIf you see a closing bracket → check the top of the stack. If the top is the matching opening bracket, pop it. Otherwise the string is invalid.At the end, if the stack is empty → all brackets matched → return true. If stack still has elements → some brackets were never closed → return false.public boolean isValid(String s) {if (s.length() == 1) return false; // single char can never be validStack<Character> st = new Stack<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '(' || c == '{' || c == '[') {st.push(c); // opening bracket — push and wait for its match} else {if (!st.empty()) {// check if top of stack is the matching openerif ((c == ')' && st.peek() != '(') ||(c == '}' && st.peek() != '{') ||(c == ']' && st.peek() != '[')) {return false; // wrong type of closing bracket} else {st.pop(); // matched! remove the opener}} else {return false; // closing bracket with nothing open}}}return st.empty(); // true only if all openers were matched}Detailed Dry Run — s = "([)]"This is the trickiest example. Looks balanced at first glance but is actually invalid.( → opening, push → stack: [(][ → opening, push → stack: [(, []) → closing, peek is [, but ) needs ( → mismatch → return false ✅The stack correctly catches that [ was opened after ( but we tried to close ( before closing [ — wrong order!Dry Run — s = "([{}])"( → push → stack: [(][ → push → stack: [(, []{ → push → stack: [(, [, {]} → peek is {, match! pop → stack: [(, []] → peek is [, match! pop → stack: [(]) → peek is (, match! pop → stack: []Stack is empty → return true ✅Dry Run — s = "(["( → push → stack: [(][ → push → stack: [(, []Loop ends. Stack is NOT empty → return false ✅Two brackets were opened but never closed.All the Edge Cases You Must KnowSingle character like "(" or ")" A single character can never be valid — an opener has nothing to close it, a closer has nothing before it. The early return if (s.length() == 1) return false handles this cleanly.Only closing brackets like "))" The stack is empty when the first ) arrives → return false immediately.Only opening brackets like "(((" All get pushed, nothing gets popped, stack is not empty at end → return false.Interleaved wrong types like "([)]" Caught by the mismatch check when the closing bracket does not match the stack top.Empty string Stack stays empty → st.empty() returns true → returns true. An empty string is technically valid since there are no unmatched brackets. The constraints say length ≥ 1 so this is just good to know.A Cleaner Variation Using HashMapSome developers prefer using a HashMap to store bracket pairs, making the matching condition more readable:public boolean isValid(String s) {Stack<Character> st = new Stack<>();Map<Character, Character> map = new HashMap<>();map.put(')', '(');map.put('}', '{');map.put(']', '[');for (char c : s.toCharArray()) {if (map.containsKey(c)) {// closing bracketif (st.empty() || st.peek() != map.get(c)) {return false;}st.pop();} else {st.push(c); // opening bracket}}return st.empty();}The HashMap maps each closing bracket to its expected opening bracket. This makes adding new bracket types trivial — just add one line to the map. Great for extensibility in real world code.Both versions are O(n) time and O(n) space. Choose whichever feels more readable to you.Time Complexity: O(n) — single pass through the string Space Complexity: O(n) — stack holds at most n/2 opening bracketsWhy Stack Is the Perfect Data Structure HereThe key property this problem exploits is LIFO — Last In First Out. The most recently opened bracket must be the first one closed. That is literally the definition of a stack's behavior.Any time you see a problem where the most recently seen item determines what comes next — think Stack immediately. Valid Parentheses is the purest example of this principle.How This Fits Into the Bigger Stack PatternLooking at everything you have solved so far, notice the pattern evolution:844 Backspace String Compare — # pops the last character 1047 Remove Adjacent Duplicates — matching character pops itself 2390 Removing Stars — * pops the last character 3174 Clear Digits — digit pops the last character 20 Valid Parentheses — closing bracket pops its matching openerAll of these are stack simulations. The difference here is that instead of any character being popped, only the correct matching opener is popped. This matching condition is what makes Valid Parentheses a step up in logic from the previous problems.Common Mistakes to AvoidNot checking if stack is empty before peeking If a closing bracket arrives and the stack is empty, calling peek() throws an EmptyStackException. Always check !st.empty() before peeking or popping.Returning true without checking if stack is empty Even if the loop completes without returning false, unclosed openers remain on the stack. Always return st.empty() at the end, not just true.Pushing closing brackets onto the stack Only push opening brackets. Pushing closing brackets gives completely wrong results and is the most common beginner mistake.Not handling odd length strings If s.length() is odd, it is impossible for all brackets to be matched — you can add if (s.length() % 2 != 0) return false as an early exit for a small optimization.FAQs — People Also AskQ1. Why is a Stack used to solve Valid Parentheses? Because the problem requires LIFO matching — the most recently opened bracket must be the first one closed. Stack's Last In First Out behavior maps perfectly to this requirement, making it the natural and optimal data structure choice.Q2. What is the time complexity of LeetCode 20? O(n) time where n is the length of the string. We make a single pass through the string, and each character is pushed and popped at most once. Space complexity is O(n) in the worst case when all characters are opening brackets.Q3. Can LeetCode 20 be solved without a Stack? Technically yes for simple cases using counters, but only when dealing with a single type of bracket. With three types of brackets that can be nested, a Stack is the only clean solution. Counter-based approaches break down on cases like "([)]".Q4. Is LeetCode 20 asked in FAANG interviews? Absolutely. It is one of the most commonly asked problems across all major tech companies. It tests understanding of the Stack data structure and is often used as a warmup before harder stack problems like Largest Rectangle in Histogram or Decode String.Q5. What happens if the input string has an odd length? An odd-length string can never be valid since brackets always come in pairs. You can add if (s.length() % 2 != 0) return false as an early optimization, though the stack logic handles this correctly on its own.Similar LeetCode Problems to Practice Next1047. Remove All Adjacent Duplicates In String — Easy — stack pattern with characters394. Decode String — Medium — nested brackets with encoding678. Valid Parenthesis String — Medium — wildcards added32. Longest Valid Parentheses — Hard — longest valid substring1249. Minimum Remove to Make Valid Parentheses — Medium — remove minimum brackets to make validConclusionLeetCode 20 Valid Parentheses is the definitive introduction to the Stack data structure in competitive programming and technical interviews. The logic is elegant — push openers, pop on matching closers, check empty at the end. Three rules, one data structure, one pass.Master this problem thoroughly, understand every edge case, and you will have a rock-solid foundation for every stack problem that follows — from Decode String to Largest Rectangle in Histogram.

StringStackEasyLeetCode

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

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

DataStructuresJavaStackDataStructureLIFO

LeetCode 735: Asteroid Collision — Java Solution Explained

IntroductionIf you have been building your stack skills through problems like Valid Parentheses, Next Greater Element, and Backspace String Compare, then LeetCode 735 Asteroid Collision is the problem where everything comes together. It is one of the most satisfying Medium problems on LeetCode because it feels like a real simulation — you are literally modelling asteroids flying through space and crashing into each other.You can find the problem here — LeetCode 735 Asteroid Collision.This article breaks everything down in plain English so that anyone — beginner or experienced — can understand exactly what is happening and why the stack is the perfect tool for this problem.What Is the Problem Really Asking?You have a row of asteroids moving through space. Each asteroid has a size and a direction:Positive number → asteroid moving to the rightNegative number → asteroid moving to the leftAll asteroids move at the same speed. When a right-moving asteroid and a left-moving asteroid meet head-on, they collide:The smaller one explodesIf they are the same size, both explodeThe bigger one survives and keeps movingTwo asteroids moving in the same direction never meet, so they never collide.Return the final state of all surviving asteroids after every possible collision has happened.Real Life Analogy — Cars on a HighwayImagine a highway with cars driving in both directions. Cars going right are in one lane, cars going left are in another lane. Now imagine the lanes overlap at some point.A small car going right crashes into a big truck going left — the car gets destroyed, the truck keeps going. Two equally sized cars crash — both are destroyed. A massive truck going right demolishes everything coming from the left until it meets something bigger or nothing at all.That is exactly the asteroid problem. The stack helps us track which asteroids are still "alive" and moving right, waiting to potentially collide with the next left-moving asteroid that comes along.Why Stack Is the Perfect Data Structure HereThe key observation is this — only a right-moving asteroid followed by a left-moving asteroid can collide. A left-moving asteroid might destroy several right-moving ones in a chain before it either survives or gets destroyed itself.This chain reaction behavior — where the outcome of one collision immediately triggers the possibility of another — is exactly what a stack handles naturally. The stack holds right-moving asteroids that are still alive and waiting. When a left-moving asteroid arrives, it battles the top of the stack repeatedly until either it is destroyed or no more collisions are possible.All Possible Collision ScenariosBefore looking at code it is important to understand every case that can happen:Case 1 — Right-moving asteroid (ast[i] > 0) No collision possible immediately. Push it onto the stack and move on.Case 2 — Left-moving asteroid, stack is empty Nothing to collide with. Push it onto the stack.Case 3 — Left-moving asteroid, top of stack is also left-moving (negative) Two asteroids going the same direction never meet. Push it onto the stack.Case 4 — Left-moving asteroid meets right-moving asteroid (collision!) Three sub-cases:Stack top is bigger → left-moving asteroid explodes, stack top survivesStack top is smaller → stack top explodes, left-moving asteroid continues (loop again)Same size → both explodeThe Solution — Stack Simulationpublic int[] asteroidCollision(int[] ast) { Stack<Integer> st = new Stack<>(); for (int i = 0; i < ast.length; i++) { boolean survived = true; // assume current asteroid survives // collision only happens when stack top is positive // and current asteroid is negative while (!st.empty() && st.peek() > 0 && ast[i] < 0) { if (st.peek() > Math.abs(ast[i])) { // stack top is bigger — current asteroid explodes survived = false; break; } else if (st.peek() < Math.abs(ast[i])) { // current asteroid is bigger — stack top explodes // current asteroid keeps going, check next stack element st.pop(); } else { // equal size — both explode st.pop(); survived = false; break; } } if (survived) { st.push(ast[i]); } } // build result array from stack (stack gives reverse order) int[] ans = new int[st.size()]; for (int i = ans.length - 1; i >= 0; i--) { ans[i] = st.pop(); } return ans;}Step-by-Step Dry Run — asteroids = [10, 2, -5]Let us trace exactly what happens:Processing 10:Stack is empty, no collision possiblesurvived = true → push 10Stack: [10]Processing 2:Stack top is 10 (positive), current is 2 (positive) — same direction, no collisionsurvived = true → push 2Stack: [10, 2]Processing -5:Stack top is 2 (positive), current is -5 (negative) — collision!2 < 5 → stack top smaller, pop 2. survived stays trueStack: [10]Stack top is 10 (positive), current is -5 (negative) — collision again!10 > 5 → stack top bigger, current asteroid destroyed. survived = false, breakStack: [10]survived = false → do not push -5Final stack: [10] → output: [10] ✅Step-by-Step Dry Run — asteroids = [3, 5, -6, 2, -1, 4]Processing 3: stack empty → push. Stack: [3]Processing 5: both positive, same direction → push. Stack: [3, 5]Processing -6:Collision with 5: 5 < 6 → pop 5. Stack: [3]Collision with 3: 3 < 6 → pop 3. Stack: []Stack empty → survived = true → push -6Stack: [-6]Processing 2: stack top is -6 (negative), current is 2 (positive) — same direction check fails, no collision → push. Stack: [-6, 2]Processing -1:Collision with 2: 2 > 1 → stack top bigger, -1 explodes. survived = falseStack: [-6, 2]Processing 4: stack top is 2 (positive), current is 4 (positive) — same direction → push. Stack: [-6, 2, 4]Final stack: [-6, 2, 4] → output: [-6, 2, 4] ✅Understanding the survived FlagThe survived boolean flag is the most important design decision in this solution. It tracks whether the current asteroid makes it through all collisions.It starts as true — we assume the asteroid survives until proven otherwise. It only becomes false in two situations — when the stack top is bigger (current asteroid destroyed) or when both are equal size (mutual destruction). If survived is still true after the while loop, the asteroid either won all its battles or never had any — either way it gets pushed onto the stack.This flag eliminates the need for complicated nested conditions and makes the logic clean and readable.Building the Result ArrayOne important detail — when you pop everything from a stack to build an array, the order is reversed. The stack gives you elements from top to bottom (last to first). So we fill the result array from the end to the beginning using i = ans.length - 1 going down to 0. This preserves the original left-to-right order of surviving asteroids.Time and Space ComplexityTime Complexity: O(n) — each asteroid is pushed onto the stack at most once and popped at most once. Even though there is a while loop inside the for loop, each element participates in at most one push and one pop across the entire run. Total operations stay linear.Space Complexity: O(n) — in the worst case (all asteroids moving right, no collisions) all n asteroids sit on the stack simultaneously.Common Mistakes to AvoidForgetting that same-direction asteroids never collide The collision condition is specifically st.peek() > 0 && ast[i] < 0. Two positive asteroids, two negative asteroids, or a negative followed by a positive — none of these collide. Only right then left.Not using a loop for chain collisions A single left-moving asteroid can destroy multiple right-moving ones in sequence. If you only check the stack top once instead of looping, you will miss chain destructions like in the [3, 5, -6] example.Forgetting the survived flag and always pushing Without the flag, a destroyed asteroid still gets pushed onto the stack, giving wrong results.Wrong array reconstruction from stack Forgetting that stack order is reversed and filling the array from left to right gives a backwards answer. Always fill from the last index downward.How This Problem Differs From Previous Stack ProblemsEvery previous stack problem in this series had a simple push-or-pop decision per character. Asteroid Collision introduces something new — a while loop inside the for loop. This is because one incoming asteroid can trigger multiple consecutive pops (chain collisions). The stack is no longer just storing history — it is actively participating in a simulation where multiple stored elements can be affected by a single incoming element.This is the defining characteristic of harder stack problems and is exactly what appears in problems like Largest Rectangle in Histogram and Trapping Rain Water.FAQs — People Also AskQ1. Why is a Stack used to solve LeetCode 735 Asteroid Collision? Because right-moving asteroids wait on the stack until a left-moving asteroid arrives. The left-moving asteroid battles the top of the stack repeatedly — this LIFO chain reaction behavior is exactly what a stack handles naturally and efficiently.Q2. What is the time complexity of LeetCode 735? O(n) time because each asteroid is pushed and popped at most once regardless of how many chain collisions happen. Space complexity is O(n) for the stack in the worst case.Q3. When do two asteroids NOT collide in LeetCode 735? Two asteroids never collide when both move right (both positive), both move left (both negative), or when a left-moving asteroid comes before a right-moving one — they move away from each other in that case.Q4. Is LeetCode 735 asked in coding interviews? Yes, it is commonly asked at companies like Amazon, Google, and Microsoft as a Medium stack problem. It tests whether you can handle simulation problems with multiple conditional branches and chain reactions — skills that translate directly to real world system design thinking.Q5. What is the difference between LeetCode 735 and LeetCode 496 Next Greater Element? Both use a stack and involve comparing elements. In Next Greater Element, you search forward for something bigger. In Asteroid Collision, collisions happen between the current element and stack contents, and the current element might destroy multiple previous elements in a chain before settling. The collision logic in 735 is more complex.Similar LeetCode Problems to Practice Next496. Next Greater Element I — Easy — monotonic stack pattern739. Daily Temperatures — Medium — next greater with index distance1047. Remove All Adjacent Duplicates In String — Easy — chain removal with stack84. Largest Rectangle in Histogram — Hard — advanced stack simulation503. Next Greater Element II — Medium — circular array with monotonic stackConclusionLeetCode 735 Asteroid Collision is a wonderful problem that takes the stack simulation pattern to the next level. The key insight is recognizing that only right-then-left asteroid pairs can collide, that chain collisions require a while loop not just an if statement, and that the survived flag keeps the logic clean across all cases.Work through every dry run in this article carefully — especially the [3, 5, -6, 2, -1, 4] example — because seeing chain collisions play out step by step is what makes this pattern click permanently.Once this problem makes sense, you are genuinely ready for the harder stack problems that follow. Keep going!

LeetCodeJavaStackArrayMedium

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

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

StringStackMediumLeetCode

LeetCode 3174: Clear Digits — Multiple Approaches Explained

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

StringStackString BuilderEasyLeetCode