Search Blogs

Showing results for "One Pass Algorithm"

Found 11 results

Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

🚀 Try the ProblemPractice here:https://leetcode.com/problems/remove-nth-node-from-end-of-list/🤔 Let’s Think Differently…Imagine this list:1 → 2 → 3 → 4 → 5You are asked:👉 Remove the 2nd node from the endSo counting from end:5 (1st), 4 (2nd) ❌ remove thisFinal list:1 → 2 → 3 → 5🧠 Problem in Simple WordsYou are given:Head of a linked listA number n👉 Remove the nth node from the end👉 Return the updated list📦 Constraints1 <= number of nodes <= 300 <= Node.val <= 1001 <= n <= size of list🧩 First Thought (Counting Method)💡 IdeaCount total nodesFind position from start:position = total - nTraverse again and remove that node✅ Code (Counting Approach)class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(head == null) return head; // Step 1: Count nodes int co = 0; ListNode tempHead = head; while(tempHead != null){ co++; tempHead = tempHead.next; } // Step 2: If removing head if(co == n) return head.next; // Step 3: Find node before target int k = co - n; int con = 1; ListNode temp = head; while(con < k){ temp = temp.next; con++; } // Step 4: Remove node temp.next = temp.next.next; return head; }}⏱️ ComplexityTime ComplexityO(n) + O(n) = O(n)(two traversals)Space ComplexityO(1)⚠️ Limitation of This Approach👉 It requires two passesBut the problem asks:Can you solve it in one pass?🚀 Optimal Approach: Two Pointer Technique (One Pass)Now comes the interesting part 🔥🧠 Core IdeaWe use two pointers:fast pointerslow pointer🎯 Trick👉 Move fast pointer n steps aheadThen move both pointers together until:fast reaches endAt that moment:👉 slow will be at the node before the one to remove📌 Why This WorksBecause the gap between fast and slow is always n nodesSo when fast reaches end:👉 slow is exactly where we need it🔥 Step-by-Step VisualizationList:1 → 2 → 3 → 4 → 5n = 2Step 1: Move fast 2 stepsfast → 3slow → 1Step 2: Move both togetherfast → 4, slow → 2fast → 5, slow → 3fast → null, slow → 4👉 Now slow is at node before target🧼 Clean and Safe Approach (Using Dummy Node)Using dummy node avoids edge cases like removing head.💻 Code (Optimal One Pass Solution)class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // Dummy node to handle edge cases ListNode dummy = new ListNode(0, head); ListNode fast = dummy; ListNode slow = dummy; // Move fast pointer n steps ahead for(int i = 0; i < n; i++){ fast = fast.next; } // Move both pointers while(fast.next != null){ fast = fast.next; slow = slow.next; } // Remove nth node slow.next = slow.next.next; return dummy.next; }}⏱️ ComplexityTime ComplexityO(n)(single pass)Space ComplexityO(1)⚖️ Comparing ApproachesApproachPassesTimeSpaceDifficultyCounting2O(n)O(1)EasyTwo Pointer1O(n)O(1)Optimal❌ Common MistakesForgetting to handle removing head nodeNot using dummy nodeOff-by-one errors in pointer movementMoving fast incorrectly🔥 Interview InsightThis problem is a classic example of:Fast & Slow Pointer TechniqueUsed in many problems like:Cycle DetectionMiddle of Linked ListPalindrome Linked List🧠 Final ThoughtAt first, counting feels natural…But once you learn this trick:"Create a gap and move together"👉 You unlock a powerful pattern.🚀 ConclusionThe Remove Nth Node From End problem is not just about deletion…It teaches:Efficient traversalPointer coordinationOne-pass optimization👉 Tip: Whenever you see “from end”, think:"Can I use two pointers with a gap?"That’s your shortcut to solving these problems like a pro 🚀

Linked ListTwo PointersFast & Slow PointerOne Pass AlgorithmLeetCodeMedium

Master LeetCode 92: Reverse Linked List II | Detailed Java Solution & Explanation

If you are preparing for software engineering interviews, you already know that Linked Lists are a favourite topic among interviewers. While reversing an entire linked list is a standard beginner problem, reversing only a specific section of it requires a bit more pointer magic.In this blog post, we will tackle LeetCode 92. Reverse Linked List II. We will break down the problem in plain English, walk through a highly intuitive modular approach, and then look at an optimized one-pass technique.Let’s dive in!Understanding the ProblemQuestion Statement:Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.Example:Input: head = [1,2,3,4,5], left = 2, right = 4Output: [1,4,3,2,5]In Simple Words:Imagine a chain of connected boxes. You don't want to flip the whole chain backwards. You only want to flip a specific middle section (from the 2nd box to the 4th box), while keeping the first and last boxes exactly where they are.Approach 1: The Intuitive Modular Approach (Find, Reverse, Connect)When solving complex linked list problems, breaking the problem into smaller helper functions is an excellent software engineering practice.In this approach, we will:Use a Dummy Node. This is a lifesaver when left = 1 (meaning we have to reverse from the very first node).Traverse the list to find the exact boundaries: the node just before the reversal (slow), the start of the reversal (leftNode), and the end of the reversal (rightNode).Pass the sub-list to a helper function that reverses it.Reconnect the newly reversed sub-list back to the main list.Here is the Java code for this approach:/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { // Helper function to reverse a portion of the list public ListNode reverse(ListNode LeftHead, ListNode rightHead){ ListNode curr = LeftHead; ListNode prev = rightHead; // Standard linked list reversal logic while(curr != rightHead){ ListNode newnode = curr.next; curr.next = prev; prev = curr; curr = newnode; } return prev; } public ListNode reverseBetween(ListNode head, int left, int right) { if(left == 1 && right == 1) return head; // Dummy node helps handle edge cases easily ListNode dummy = new ListNode(-1); dummy.next = head; ListNode leftNode = null; ListNode rightNode = null; ListNode curr = head; int leftC = 1; int rightC = 1; ListNode slow = dummy; // Traverse to find the exact bounds of our sublist while(curr != null){ if(leftC == left - 1){ slow = curr; // 'slow' is the node just before the reversed section } if(leftC == left){ leftNode = curr; } if(rightC == right){ rightNode = curr; } if(leftC == left && rightC == right){ break; // We found both bounds, no need to traverse further } leftC++; rightC++; curr = curr.next; } // Reverse the sublist and connect it back ListNode rev = reverse(leftNode, rightNode.next); slow.next = rev; return dummy.next; }}🔍 Dry Run of Approach 1Let’s trace head = [1, 2, 3, 4, 5], left = 2, right = 4.Step 1: Initializationdummy = -1 -> 1 -> 2 -> 3 -> 4 -> 5slow = -1 (dummy node)Step 2: Finding Bounds (While Loop)We move curr through the list.When curr is at 1 (Position 1): left - 1 is 1, so slow becomes node 1.When curr is at 2 (Position 2): leftNode becomes node 2.When curr is at 4 (Position 4): rightNode becomes node 4. We break the loop.Step 3: The Helper ReversalWe call reverse(leftNode, rightNode.next), which means reverse(Node 2, Node 5).Inside the helper, we reverse the links for 2, 3, and 4.Because we initialized prev as rightHead (Node 5), Node 2's next becomes Node 5.The helper returns Node 4 as the new head of this reversed chunk. The chunk now looks like: 4 -> 3 -> 2 -> 5.Step 4: ReconnectionBack in the main function, slow (Node 1) is connected to the returned reversed list: slow.next = rev.Final List: dummy -> 1 -> 4 -> 3 -> 2 -> 5.Return dummy.next!Time & Space Complexity:Time Complexity: O(N). We traverse the list to find the pointers, and then the helper traverses the sub-list to reverse it. Since we visit nodes a maximum of two times, it is linear time.Space Complexity: O(1). We are only creating a few pointers (dummy, slow, curr, etc.), requiring no extra dynamic memory.Approach 2: The Optimized One-Pass SolutionLeetCode includes a follow-up challenge: "Could you do it in one pass?"While the first approach is incredibly readable, we can optimize it to reverse the nodes as we traverse them, eliminating the need for a separate helper function or a second sub-list traversal.In this approach, we:Move a prev pointer to the node just before left.Keep a curr pointer at left.Use a for loop to extract the node immediately after curr and move it to the front of the reversed sub-list. We do this exactly right - left times.class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { if (head == null || left == right) return head; ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; // Step 1: Reach the node just before 'left' for (int i = 0; i < left - 1; i++) { prev = prev.next; } // Step 2: Start the reversal process ListNode curr = prev.next; for (int i = 0; i < right - left; i++) { ListNode nextNode = curr.next; // Node to be moved to the front curr.next = nextNode.next; // Detach nextNode nextNode.next = prev.next; // Point nextNode to the current front of sublist prev.next = nextNode; // Make nextNode the new front of the sublist } return dummy.next; }}🔍 Why this works (The Pointer Magic)If we are reversing [1, 2, 3, 4, 5] from 2 to 4:prev is at 1. curr is at 2.Iteration 1: Grab 3, put it after 1. List: [1, 3, 2, 4, 5].Iteration 2: Grab 4, put it after 1. List: [1, 4, 3, 2, 5].Done! We achieved the reversal in a strict single pass.Time & Space Complexity:Time Complexity: O(N). We touch each node exactly once.Space Complexity: O(1). Done entirely in-place.ConclusionReversing a portion of a linked list is a fantastic way to test your understanding of pointer manipulation.Approach 1 is amazing for interviews because it shows you can modularize code and break big problems into smaller, testable functions.Approach 2 is the perfect "flex" to show the interviewer that you understand optimization and single-pass algorithms.I highly recommend writing down the dry run on a piece of paper and drawing arrows to see how the pointers shift. That is the secret to mastering Linked Lists!Happy Coding! 💻🚀

LeetCodeLinkedListJavaReverse LinkedList II

LeetCode 2095. Delete the Middle Node of a Linked List – Fast and Slow Pointer Approach

🔗 Try This Problemhttps://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/🎥 Video ExplanationProblem ExplanationYou are given the head of a singly linked list. The task is to remove the middle node and return the updated list.The middle node is defined using 0-based indexing:Middle Index = ⌊n / 2⌋Where n is the total number of nodes.ExampleInput: [1, 3, 4, 7, 1, 2, 6]Index: 0 1 2 3 4 5 6n = 7Middle index = 3Node to remove = 7Output: [1, 3, 4, 1, 2, 6]Approach 1: Brute Force (Two Traversals)IdeaTraverse the list to count total nodesCompute middle indexTraverse again to delete that nodeComplexityTime Complexity: O(n)Space Complexity: O(1)LimitationThis approach requires two passes, which is not optimal when a single traversal solution exists.Approach 2: Fast and Slow Pointer (Optimal)IntuitionUse two pointers:Slow pointer moves one step at a timeFast pointer moves two steps at a timeWhen the fast pointer reaches the end of the list:Slow pointer will be at the middle nodeImportant DetailTo remove the middle node, access to the previous node is required.Therefore, maintain an additional pointer:prev → tracks node before slowAlgorithm StepsInitialize:slow = headfast = headprev = nullTraverse:Move fast by 2 stepsMove slow by 1 stepUpdate prev = slow (before moving slow)When loop ends:slow points to middle nodeprev points to node before middleDelete node:prev.next = slow.nextDetailed Dry RunInput1 → 3 → 4 → 7 → 1 → 2 → 6Initial Stateslow = 1fast = 1prev = nullIteration 1fast → 4slow → 3prev → 1Iteration 2fast → 1slow → 4prev → 3Iteration 3fast → nullslow → 7prev → 4After Loopslow = 7 (middle node)prev = 4Deletionprev.next = slow.nextResult:1 → 3 → 4 → 1 → 2 → 6Optimized Code (Java)class Solution {public ListNode deleteMiddle(ListNode head) {// Edge case: single nodeif(head == null) return head;if(head.next == null) return null;ListNode slow = head;ListNode fast = head;ListNode prev = null;// Traverse using fast and slow pointerwhile(fast != null && fast.next != null){fast = fast.next.next;prev = slow;slow = slow.next;}// Remove middle nodeprev.next = slow.next;return head;}}Complexity AnalysisTime Complexity: O(n)Space Complexity: O(1)Only one traversal of the linked listNo extra data structures usedEdge CasesSingle NodeInput: [1]Output: []Two NodesInput: [2, 1]Output: [2]Even Length ListInput: [1, 2, 3, 4]n = 4Middle index = 2Node removed = 3Key TakeawaysFast and slow pointer reduces two-pass solution to one-passTracking the previous node is necessary for deletionWorks efficiently for large linked listsA fundamental pattern used in multiple linked list problemsConclusionThe fast and slow pointer technique provides an elegant and efficient way to identify and remove the middle node in a linked list. By leveraging different traversal speeds, the problem can be solved in a single pass with constant space, making it optimal for both interviews and practical implementations.

LeetCodeMediumLinked ListFast and Slow Pointer

LeetCode 1047: Remove All Adjacent Duplicates In String — Java Solution With All Approaches Explained

Introduction: What Is LeetCode 1047 Remove All Adjacent Duplicates In String?If you are grinding LeetCode for coding interviews at companies like Google, Amazon, or Microsoft, LeetCode 1047 Remove All Adjacent Duplicates In String is a problem you cannot skip. It is one of the most elegant examples of the stack simulation pattern and appears frequently as a warmup or follow-up question in technical rounds.In this article we will cover everything you need — plain English explanation, real life analogy, 3 Java approaches with dry runs, complexity analysis, common mistakes, FAQs, and similar problems to practice next.Here is the problem link-: Leetcode 1047 What Is the Problem Really Asking?You are given a string. Keep scanning it and whenever you find two same letters sitting next to each other, remove both of them. After removing, the letters around them might now become adjacent and form a new pair — so you keep doing this until no more adjacent duplicates exist.Example walkthrough for "abbaca":"abbaca" → bb are adjacent duplicates → remove → "aaca""aaca" → aa are adjacent duplicates → remove → "ca""ca" → no adjacent duplicates → done!✅ Output: "ca"Real Life Analogy — Think of Popping BubblesImagine a row of colored bubbles. Whenever two bubbles of the same color are next to each other, they pop and disappear. After they pop, the bubbles on either side might now touch each other — and if they are the same color, they pop too! You keep going until no two same-colored bubbles are touching.That chain reaction is exactly what this problem simulates. And the best tool to handle that chain reaction? A stack.Approach 1: Brute Force (Beginner Friendly)The IdeaScan the string repeatedly. Every time you find two adjacent equal characters, remove them. Keep doing this until a full pass finds nothing to remove.public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(s); boolean found = true; while (found) { found = false; for (int i = 0; i < sb.length() - 1; i++) { if (sb.charAt(i) == sb.charAt(i + 1)) { sb.deleteCharAt(i); sb.deleteCharAt(i); found = true; break; } } } return sb.toString();}This is easy to understand but very slow. For each pair found, you restart the entire scan. With n up to 100,000, this will get Time Limit Exceeded on LeetCode. Use it only to build intuition.Time Complexity: O(n²) — repeated passes over the string Space Complexity: O(n) — StringBuilder storageApproach 2: Stack Based Solution (Classic Interview Approach)The IdeaA stack is perfect here because of one key observation — when you remove a pair, the character that was before the pair is now adjacent to the character after the pair. That is a Last In First Out situation, which is exactly what a stack handles naturally.Algorithm:If the current character matches the top of the stack → pop (they cancel each other)Otherwise → push the current character onto the stackAt the end, the stack contains your final answerpublic String removeDuplicates(String s) { Stack<Character> st = new Stack<>(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (!st.empty() && c == st.peek()) { st.pop(); // adjacent duplicate found, cancel both } else { st.push(c); } } while (!st.empty()) { sb.append(st.pop()); } return sb.reverse().toString();}Dry Run — "abbaca"We go character by character and check against the top of the stack:a → stack empty, push → stack: [a]b → top is a, not equal, push → stack: [a, b]b → top is b, equal! pop → stack: [a]a → top is a, equal! pop → stack: []c → stack empty, push → stack: [c]a → top is c, not equal, push → stack: [c, a]Stack remaining: [c, a] → reverse → ✅ "ca"Notice how after removing bb, the two as automatically become adjacent and get caught — the stack handles this chain reaction naturally without any extra logic!Time Complexity: O(n) — single pass through the string Space Complexity: O(n) — stack holds up to n charactersApproach 3: StringBuilder as Stack (Optimal Solution) ✅The IdeaThis is your own solution and the best one! Instead of using a separate Stack<Character>, we use StringBuilder itself as a stack:sb.append(c) acts as pushsb.deleteCharAt(sb.length() - 1) acts as popsb.charAt(sb.length() - 1) acts as peekNo extra data structure, no boxing of char into Character objects, and no reversal needed at the end. Clean, fast, and minimal.public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (sb.length() != 0 && c == sb.charAt(sb.length() - 1)) { sb.deleteCharAt(sb.length() - 1); // adjacent duplicate, remove both } else { sb.append(c); } } return sb.toString();}Dry Run — "azxxzy"a → sb empty, append → "a"z → last char is a, not equal, append → "az"x → last char is z, not equal, append → "azx"x → last char is x, equal! delete → "az"z → last char is z, equal! delete → "a"y → last char is a, not equal, append → "ay"✅ Final Answer: "ay"Again, notice the chain reaction — after xx was removed, z and z became adjacent and got removed too. The StringBuilder handles this perfectly in a single pass!Time Complexity: O(n) — one pass, every character processed exactly once Space Complexity: O(n) — StringBuilder storageWhy StringBuilder Beats Stack in JavaWhen you use Stack<Character> in Java, every char primitive gets auto-boxed into a Character object. That means extra memory allocation for every single character. With StringBuilder, you work directly on the underlying char array — faster and leaner. Plus you skip the reversal step entirely.For an interview, the Stack approach is great for explaining your thought process clearly. But for the final submitted solution, StringBuilder is the way to go.Common Mistakes to AvoidNot checking sb.length() != 0 before peeking If the StringBuilder is empty and you call sb.charAt(sb.length() - 1), you will get a StringIndexOutOfBoundsException. Always guard this check — even if the problem guarantees valid input, it shows clean coding habits.Thinking you need multiple passes Many beginners think you need to scan the string multiple times because of chain reactions. The stack handles chain reactions automatically in a single pass. Trust the process!Forgetting to reverse when using Stack Since a stack gives you characters in reverse order when you pop them, you must call .reverse() at the end. With StringBuilder you do not need this.How This Fits Into the Stack Simulation PatternBy now you might be noticing a theme across multiple problems:LeetCode 3174 Clear Digits — digit acts as backspace, deletes closest left non-digit LeetCode 2390 Removing Stars — star acts as backspace, deletes closest left non-star LeetCode 1047 Remove Adjacent Duplicates — character cancels itself if it matches the top of stackAll three use the exact same StringBuilder-as-stack pattern. The only difference is the condition that triggers a deletion. This is why pattern recognition is the real skill — once you internalize this pattern, you can solve a whole family of problems in minutes.FAQs — People Also AskQ1. What is the best approach for LeetCode 1047 in Java? The StringBuilder approach is the best. It runs in O(n) time, uses O(n) space, requires no extra data structure, and avoids the reversal step needed with a Stack.Q2. Why does a stack work for removing adjacent duplicates? Because whenever you remove a pair, the characters around them become the new neighbors. A stack naturally keeps track of the most recently seen character, so it catches these chain reactions without any extra logic.Q3. What is the time complexity of LeetCode 1047? The optimal solution runs in O(n) time and O(n) space, where n is the length of the input string.Q4. Is LeetCode 1047 asked in coding interviews? Yes, it is commonly asked as a warmup problem or follow-up at companies like Google, Amazon, and Adobe. It tests your understanding of stack-based string manipulation.Q5. What is the difference between LeetCode 1047 and LeetCode 1209? LeetCode 1047 removes pairs of adjacent duplicates. LeetCode 1209 is the harder version — it removes groups of k adjacent duplicates, requiring you to store counts alongside characters in the stack.Similar LeetCode Problems to Practice Next2390. Removing Stars From a String — Medium — star as backspace3174. Clear Digits — Easy — digit as backspace844. Backspace String Compare — Easy — compare two strings after backspaces1209. Remove All Adjacent Duplicates in String II — Medium — harder version with k duplicates735. Asteroid Collision — Medium — stack simulation with collision logicConclusionLeetCode 1047 Remove All Adjacent Duplicates In String is a beautiful problem that teaches you one of the most powerful and reusable patterns in DSA — stack simulation. The moment you spot that a removal can cause a chain reaction of more removals, you know a stack is your best friend.The StringBuilder solution is clean, optimal, and interview-ready. Master it, understand why it works, and you will be able to tackle the entire family of stack simulation problems with confidence.Found this helpful? Share it with friends preparing for coding interviews

LeetCodeJavaStackStringEasy

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 121 — Best Time to Buy and Sell Stock I | Two Pointer / Sliding Window Explained

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

LeetCodeTwo PointersEasyJavaDSA

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

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

LeetCodeBinary SearchRotated Sorted ArrayJavaMedium

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

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

LeetcodeMediumRecursionBacktrackingJava

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

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

ArrayStackMonotonic StackHashMapEasyLeetCode

LeetCode 143 Reorder List - Java Solution Explained

IntroductionLeetCode 143 Reorder List is one of those problems that looks simple when you read it but immediately makes you wonder — where do I even start? There is no single trick that solves it. Instead it combines three separate linked list techniques into one clean solution. Mastering this problem means you have genuinely understood linked lists at an intermediate level.You can find the problem here — LeetCode 143 Reorder List.This article walks through everything — what the problem wants, the intuition behind each step, all three techniques used, a detailed dry run, complexity analysis, and common mistakes beginners make.What Is the Problem Really Asking?You have a linked list: L0 → L1 → L2 → ... → LnYou need to reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...In plain English — take one node from the front, then one from the back, then one from the front, then one from the back, and keep alternating until all nodes are used.Example:Input: 1 → 2 → 3 → 4 → 5Output: 1 → 5 → 2 → 4 → 3Node 1 from front, Node 5 from back, Node 2 from front, Node 4 from back, Node 3 stays in middle.Real Life Analogy — Dealing Cards From Both EndsImagine you have a deck of cards laid out in a line face up: 1, 2, 3, 4, 5. Now you deal them by alternately picking from the left end and the right end of the line:Pick 1 from left → placePick 5 from right → place after 1Pick 2 from left → place after 5Pick 4 from right → place after 2Pick 3 (only one left) → place after 4Result: 1, 5, 2, 4, 3That is exactly what the problem wants. The challenge is doing this efficiently on a singly linked list where you cannot just index from the back.Why This Problem Is Hard for BeginnersIn an array you can just use two pointers — one at the start and one at the end — and swap/interleave easily. But a singly linked list only goes forward. You cannot go backwards. You cannot easily access the last element.This is why the problem requires a three-step approach that cleverly works around the limitations of a singly linked list.The Three Step ApproachEvery experienced developer solves this problem in exactly three steps:Step 1 — Find the middle of the linked list using the Fast & Slow Pointer techniqueStep 2 — Reverse the second half of the linked listStep 3 — Merge the two halves by alternating nodes from eachLet us understand each step deeply before looking at code.Step 1: Finding the Middle — Fast & Slow PointerThe Fast & Slow Pointer technique (also called Floyd's algorithm) uses two pointers moving at different speeds through the list:slow moves one step at a timefast moves two steps at a timeWhen fast reaches the end, slow is exactly at the middle. This works because fast covers twice the distance of slow in the same number of steps.ListNode fast = head;ListNode slow = head;while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next;}// slow is now at the middleFor 1 → 2 → 3 → 4 → 5:Start: slow=1, fast=1Step 1: slow=2, fast=3Step 2: slow=3, fast=5 (fast.next is null, stop)Middle is node 3For 1 → 2 → 3 → 4:Start: slow=1, fast=1Step 1: slow=2, fast=3Step 2: fast.next.next is null, stopslow=2, middle is node 2After finding the middle, we cut the list in two by setting slow.next = null. This disconnects the first half from the second half.Step 2: Reversing the Second HalfOnce we have the second half starting from slow.next, we reverse it. After reversal, what was the last node becomes the first — giving us easy access to the back elements of the original list.public ListNode reverse(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode next = curr.next; // save next curr.next = prev; // reverse the link prev = curr; // move prev forward curr = next; // move curr forward } return prev; // prev is the new head}For second half 3 → 4 → 5 (from the first example):Reverse → 5 → 4 → 3Now we have:First half: 1 → 2 → 3 (but 3 is the end since we cut at slow)Wait — actually after cutting at slow=3: first half is 1 → 2 → 3, second half reversed is 5 → 4Let us be precise. For 1 → 2 → 3 → 4 → 5, slow stops at 3. slow.next = null cuts to give:First half: 1 → 2 → 3 → nullSecond half before reverse: 4 → 5Second half after reverse: 5 → 4Step 3: Merging Two HalvesNow we have two lists and we merge them by alternately taking one node from each:Take from first half, take from second half, take from first half, take from second half...ListNode orig = head; // pointer for first halfListNode newhead = second; // pointer for reversed second halfwhile (newhead != null) { ListNode temp1 = orig.next; // save next of first half ListNode temp2 = newhead.next; // save next of second half orig.next = newhead; // first → second newhead.next = temp1; // second → next of first orig = temp1; // advance first half pointer newhead = temp2; // advance second half pointer}Why do we loop on newhead != null and not orig != null? Because the second half is always equal to or shorter than the first half (we cut at middle). Once the second half is exhausted, the remaining first half nodes are already in the correct position.Complete Solutionclass Solution { public ListNode reverse(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } public void reorderList(ListNode head) { // Step 1: Find middle using fast & slow pointer ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } // Step 2: Reverse second half ListNode newhead = reverse(slow.next); slow.next = null; // cut the list into two halves // Step 3: Merge two halves alternately ListNode orig = head; while (newhead != null) { ListNode temp1 = orig.next; ListNode temp2 = newhead.next; orig.next = newhead; newhead.next = temp1; orig = temp1; newhead = temp2; } }}Complete Dry Run — head = [1, 2, 3, 4, 5]Step 1: Find MiddleList: 1 → 2 → 3 → 4 → 5Initial: slow=1, fast=1Iteration 1: slow=2, fast=3Iteration 2: fast.next=4, fast.next.next=5 → slow=3, fast=5fast.next is null → stopslow is at node 3Step 2: Cut and ReverseCut: slow.next = nullFirst half: 1 → 2 → 3 → nullSecond half: 4 → 5Reverse second half 4 → 5:prev=null, curr=4 → next=5, 4.next=null, prev=4, curr=5prev=4, curr=5 → next=null, 5.next=4, prev=5, curr=nullReturn prev=5Reversed second half: 5 → 4 → nullStep 3: Mergeorig=1, newhead=5Iteration 1:temp1 = orig.next = 2temp2 = newhead.next = 4orig.next = newhead → 1.next = 5newhead.next = temp1 → 5.next = 2orig = temp1 = 2newhead = temp2 = 4List so far: 1 → 5 → 2 → 3Iteration 2:temp1 = orig.next = 3temp2 = newhead.next = nullorig.next = newhead → 2.next = 4newhead.next = temp1 → 4.next = 3orig = temp1 = 3newhead = temp2 = nullList so far: 1 → 5 → 2 → 4 → 3newhead is null → loop endsFinal result: 1 → 5 → 2 → 4 → 3 ✅Dry Run — head = [1, 2, 3, 4]Step 1: Find MiddleInitial: slow=1, fast=1Iteration 1: slow=2, fast=3fast.next=4, fast.next.next=null → stopslow is at node 2Step 2: Cut and ReverseFirst half: 1 → 2 → nullSecond half: 3 → 4Reversed: 4 → 3 → nullStep 3: Mergeorig=1, newhead=4Iteration 1:temp1=2, temp2=31.next=4, 4.next=2orig=2, newhead=3List: 1 → 4 → 2 → 3Iteration 2:temp1=null (2.next was originally 3 but we cut at slow=2, so 2.next = null... wait)Actually after cutting at slow=2, first half is 1 → 2 → null, so orig when it becomes 2, orig.next = null.temp1 = orig.next = nulltemp2 = newhead.next = null2.next = 3, 3.next = nullorig = null, newhead = nullnewhead is null → stopFinal result: 1 → 4 → 2 → 3 ✅Why slow.next = null Must Come After Saving newheadThis is a subtle but critical ordering detail in the code. Look at this sequence:ListNode newhead = reverse(slow.next); // save reversed second half FIRSTslow.next = null; // THEN cut the listIf you cut first (slow.next = null) and then try to reverse, you lose the reference to the second half entirely because slow.next is already null. Always save the second half reference before cutting.Time and Space ComplexityTime Complexity: O(n) — each of the three steps (find middle, reverse, merge) makes a single pass through the list. Total is 3 passes = O(3n) = O(n).Space Complexity: O(1) — everything is done by rearranging pointers in place. No extra arrays, no recursion stack, no additional data structures. Just a handful of pointer variables.This is the optimal solution — linear time and constant space.Alternative Approach — Using ArrayList (Simpler but O(n) Space)If you find the three-step approach hard to implement under interview pressure, here is a simpler approach using extra space:public void reorderList(ListNode head) { // store all nodes in ArrayList for random access List<ListNode> nodes = new ArrayList<>(); ListNode curr = head; while (curr != null) { nodes.add(curr); curr = curr.next; } int left = 0; int right = nodes.size() - 1; while (left < right) { nodes.get(left).next = nodes.get(right); left++; if (left == right) break; // odd number of nodes nodes.get(right).next = nodes.get(left); right--; } nodes.get(left).next = null; // terminate the list}This is much easier to understand and code. Store all nodes in an ArrayList, use two pointers from both ends, and wire up the next pointers.Time Complexity: O(n) Space Complexity: O(n) — ArrayList stores all nodesThis is acceptable in most interviews. Mention the O(1) space approach as the optimal solution if asked.Common Mistakes to AvoidNot cutting the list before merging If you do not set slow.next = null after finding the middle, the first half still points into the second half. During merging, this creates cycles and infinite loops. Always cut before merging.Wrong loop condition for finding the middle The condition fast.next != null && fast.next.next != null ensures fast does not go out of bounds when jumping two steps. Using just fast != null && fast.next != null moves slow one step too far for even-length lists.Looping on orig instead of newhead The merge loop should run while newhead != null, not while orig != null. The second half is always shorter or equal to the first half. Once the second half is done, the remaining first half is already correctly placed.Forgetting to save both temp pointers before rewiring In the merge step, you must save both orig.next and newhead.next before changing any pointers. Changing orig.next first and then trying to access orig.next to save it gives you the wrong node.How This Problem Combines Multiple PatternsThis problem is special because it does not rely on a single technique. It is a combination of three fundamental linked list operations:Fast & Slow Pointer — you saw this concept in problems like finding the middle of a list and detecting cycles (LeetCode 141, 142).Reverse a Linked List — the most fundamental linked list operation, appears in LeetCode 206 and as a subtask in dozens of problems.Merge Two Lists — similar to merging two sorted lists (LeetCode 21) but here order is not sorted, it is alternating.Solving this problem proves you are comfortable with all three patterns individually and can combine them when needed.FAQs — People Also AskQ1. What is the most efficient approach for LeetCode 143 Reorder List? The three-step approach — find middle with fast/slow pointer, reverse second half, merge alternately — runs in O(n) time and O(1) space. It is the optimal solution. The ArrayList approach is O(n) time and O(n) space but simpler to code.Q2. Why use fast and slow pointer to find the middle? Because a singly linked list has no way to access elements by index. You cannot just do list[length/2]. The fast and slow pointer technique finds the middle in a single pass without knowing the length beforehand.Q3. Why reverse the second half instead of the first half? The problem wants front-to-back alternation. If you reverse the second half, its first node is the original last node — exactly what you need to interleave with the front of the first half. Reversing the first half would give the wrong order.Q4. What is the time complexity of LeetCode 143? O(n) time for three linear passes (find middle, reverse, merge). O(1) space since all operations are in-place pointer manipulations with no extra data structures.Q5. Is LeetCode 143 asked in coding interviews? Yes, frequently at companies like Amazon, Google, Facebook, and Microsoft. It is considered a benchmark problem for linked list mastery because it requires combining three separate techniques cleanly under pressure.Similar LeetCode Problems to Practice Next206. Reverse Linked List — Easy — foundation for step 2 of this problem876. Middle of the Linked List — Easy — fast & slow pointer isolated21. Merge Two Sorted Lists — Easy — merging technique foundation234. Palindrome Linked List — Easy — also uses find middle + reverse second half148. Sort List — Medium — merge sort on linked list, uses same split techniqueConclusionLeetCode 143 Reorder List is one of the best Medium linked list problems because it forces you to think in multiple steps and combine techniques rather than apply a single pattern. The fast/slow pointer finds the middle efficiently without knowing the length. Reversing the second half turns the "cannot go backwards" limitation of singly linked lists into a non-issue. And the alternating merge weaves everything together cleanly.Work through the dry runs carefully — especially the pointer saving step in the merge. Once you see why each step is necessary and how they connect, this problem will always feel approachable no matter when it shows up in an interview.

LeetCodeJavaLinked ListTwo PointerFast Slow PointerMedium

LeetCode 682 Baseball Game - Java Solution Explained

IntroductionLeetCode 682 Baseball Game is one of the cleanest and most beginner-friendly stack simulation problems on LeetCode. It does not require any fancy algorithm or deep insight — it purely tests whether you can carefully read the rules and simulate them faithfully using the right data structure.But do not let "Easy" fool you. This problem is a great place to practice thinking about which data structure fits best and why. We will solve it three different ways — Stack, ArrayList, and Deque — so you can see the tradeoffs and pick the one that makes most sense to you.You can find the problem here — LeetCode 682 Baseball Game.What Is the Problem Really Asking?You are keeping score for a baseball game with four special rules. You process a list of operations one by one and maintain a record of scores. At the end, return the total sum of all scores in the record.The four operations are:A number (like "5" or "-2") — just add that number as a new score to the record."C" — the last score was invalid, remove it from the record."D" — add a new score that is double the most recent score."+" — add a new score that is the sum of the two most recent scores.That is it. Four rules, simulate them in order, sum up what is left.Real Life Analogy — A Scoreboard With CorrectionsImagine a scoreboard operator at a sports event. They write scores on a whiteboard as the game progresses:A player scores 5 points → write 5Another player scores 2 → write 2Referee says last score was invalid → erase the last number (C)Special bonus rule kicks in → double the last valid score (D)Two scores combine → add the last two scores as one entry (+)At the end, add up everything on the whiteboard. The stack is your whiteboard — you write on top and erase from the top.Why Stack Is the Natural FitAll four operations only ever look at or modify the most recently added scores. C removes the last one. D doubles the last one. + uses the last two. This "most recent first" access pattern is the definition of LIFO — Last In First Out — which is exactly what a Stack provides.Any time a problem says "the previous score" or "the last two scores," your brain should immediately think Stack.Approach 1: Stack (Your Solution) ✅The IdeaUse a Stack of integers. For each operation:Number → parse and pushC → pop the topD → peek the top, push doubled value+ → pop top two, push both back, push their sumpublic int calPoints(String[] operations) { Stack<Integer> st = new Stack<>(); for (int i = 0; i < operations.length; i++) { String op = operations[i]; if (op.equals("C")) { st.pop(); // remove last score } else if (op.equals("D")) { st.push(st.peek() * 2); // double of last score } else if (op.equals("+")) { int prev1 = st.pop(); // most recent score int prev2 = st.pop(); // second most recent score int sum = prev1 + prev2; st.push(prev2); // put them back st.push(prev1); st.push(sum); // push the new score } else { st.push(Integer.parseInt(op)); // regular number } } // sum all remaining scores int total = 0; while (!st.empty()) { total += st.pop(); } return total;}One small improvement over your original solution — using op.equals("C") instead of op.charAt(0) == 'C'. This is cleaner and handles edge cases better since negative numbers like "-2" also start with - not a digit, so charAt(0) comparisons can get tricky. Using equals is always safer for string operations.Why the + Operation Needs Pop-Push-PopThe trickiest part is the + operation. You need the two most recent scores. Stack only lets you see the top. So you pop the first, then the second, compute the sum, then push both back before pushing the sum. This restores the record correctly — the previous two scores stay, and the new sum score is added on top.Detailed Dry Run — ops = ["5","2","C","D","+"]Let us trace every step carefully:"5" → number, parse and push Stack: [5]"2" → number, parse and push Stack: [5, 2]"C" → remove last score, pop Stack: [5]"D" → double last score, peek=5, push 10 Stack: [5, 10]"+" → sum of last two:pop prev1 = 10pop prev2 = 5sum = 15push prev2=5, push prev1=10, push sum=15 Stack: [5, 10, 15]Sum all: 5 + 10 + 15 = 30 ✅Detailed Dry Run — ops = ["5","-2","4","C","D","9","+","+"]"5" → push 5. Stack: [5]"-2" → push -2. Stack: [5, -2]"4" → push 4. Stack: [5, -2, 4]"C" → pop 4. Stack: [5, -2]"D" → peek=-2, push -4. Stack: [5, -2, -4]"9" → push 9. Stack: [5, -2, -4, 9]"+" → prev1=9, prev2=-4, sum=5. Push -4, 9, 5. Stack: [5, -2, -4, 9, 5]"+" → prev1=5, prev2=9, sum=14. Push 9, 5, 14. Stack: [5, -2, -4, 9, 5, 14]Sum: 5 + (-2) + (-4) + 9 + 5 + 14 = 27 ✅Approach 2: ArrayList (Most Readable)The IdeaArrayList gives you index-based access which makes the + operation much cleaner — no need to pop and push back. Just access the last two elements directly using size()-1 and size()-2.public int calPoints(String[] operations) { ArrayList<Integer> record = new ArrayList<>(); for (String op : operations) { int n = record.size(); if (op.equals("C")) { record.remove(n - 1); // remove last element } else if (op.equals("D")) { record.add(record.get(n - 1) * 2); // double last } else if (op.equals("+")) { // sum of last two — no need to remove and re-add! record.add(record.get(n - 1) + record.get(n - 2)); } else { record.add(Integer.parseInt(op)); } } int total = 0; for (int score : record) { total += score; } return total;}See how the + operation becomes a single line with ArrayList? record.get(n-1) + record.get(n-2) directly accesses the last two elements without any pop-push gymnastics.Dry Run — ops = ["5","2","C","D","+"]"5" → add 5. List: [5]"2" → add 2. List: [5, 2]"C" → remove last. List: [5]"D" → 5×2=10, add 10. List: [5, 10]"+" → get(0)+get(1) = 5+10=15, add 15. List: [5, 10, 15]Sum: 30 ✅Time Complexity: O(n) — single pass through operations Space Complexity: O(n) — ArrayList stores at most n scoresThe one tradeoff — remove(n-1) on an ArrayList is O(1) for the last element (no shifting needed). And get() is O(1). So this is fully O(n) overall and arguably the cleanest solution to read and understand.Approach 3: Deque (ArrayDeque — Fastest in Java)The IdeaArrayDeque is faster than Stack in Java because Stack is synchronized (thread-safe overhead) and ArrayDeque is not. For single-threaded LeetCode problems, ArrayDeque is always the better choice over Stack.public int calPoints(String[] operations) { Deque<Integer> deque = new ArrayDeque<>(); for (String op : operations) { if (op.equals("C")) { deque.pollLast(); // remove last } else if (op.equals("D")) { deque.offerLast(deque.peekLast() * 2); // double last } else if (op.equals("+")) { int prev1 = deque.pollLast(); int prev2 = deque.pollLast(); int sum = prev1 + prev2; deque.offerLast(prev2); // restore deque.offerLast(prev1); // restore deque.offerLast(sum); // new score } else { deque.offerLast(Integer.parseInt(op)); } } int total = 0; for (int score : deque) { total += score; } return total;}The logic is identical to the Stack approach. The only difference is the method names — offerLast instead of push, pollLast instead of pop, peekLast instead of peek.Time Complexity: O(n) Space Complexity: O(n)For iterating a Deque to sum, you can use a for-each loop directly — no need to pop everything out like with Stack.Approach ComparisonApproachTimeSpaceBest ForStackO(n)O(n)Classic interview answer, clear LIFO intentArrayListO(n)O(n)Cleanest code, easiest to readArrayDequeO(n)O(n)Best performance, preferred in productionAll three approaches have identical time and space complexity. The difference is purely in code style and readability. In an interview, any of these is perfectly acceptable. Mention that ArrayDeque is preferred over Stack in Java for performance if you want to impress.Why op.equals() Is Better Than op.charAt(0)Your original solution uses operations[i].charAt(0) == 'C' to check operations. This works but has a subtle risk — the + character check with charAt(0) is fine, but imagine if a future test had a number starting with C or D (it will not in this problem but defensive coding is a good habit). More importantly, "-2".charAt(0) is '-' which is fine, but using equals is semantically clearer — you are comparing the whole string, not just the first character. This shows cleaner coding habits in interviews.Edge Cases to KnowNegative numbers like "-2" Integer.parseInt("-2") handles negatives perfectly. The D operation on -2 gives -4. The + operation works correctly with negatives too. No special handling needed."C" after a "+" that added a score The problem guarantees C always has at least one score to remove. So after + adds a score, a C removes just that one new score — the previous two scores that + used remain intact. This is correct behavior and our solution handles it automatically.All scores removed If all operations are numbers followed by C operations removing every score, the stack ends up empty and the sum is 0. Our while loop handles this correctly — it simply never executes and returns 0.Only one operation A single number like ["5"] → push 5, sum is 5. Works fine.Common Mistakes to AvoidIn the + operation, forgetting to push both numbers back When you pop prev1 and prev2 to compute the sum, you must push them back onto the stack before pushing the sum. If you only push the sum without restoring prev1 and prev2, those scores disappear from the record permanently — which is wrong. The + operation only adds a new score, it does not remove the previous ones.Using charAt(0) comparison for detecting numbers Negative numbers start with -, not a digit. If you check charAt(0) >= '0' && charAt(0) <= '9' to detect numbers, you will miss negatives. The safest approach is to check for C, D, and + explicitly using equals, and fall through to the else for everything else (which covers both positive and negative numbers).Calling st.peek() or st.pop() without checking empty The problem guarantees valid operations — C always has something to remove, + always has two previous scores, D always has one. But in real code and defensive interview solutions, adding empty checks shows good habits even when the constraints guarantee safety.FAQs — People Also AskQ1. Why is Stack a good choice for LeetCode 682 Baseball Game? Because all four operations only access the most recently added scores — the last score for C and D, the last two for +. This "most recent first" access pattern is exactly what LIFO (Last In First Out) provides. Stack's push, pop, and peek all run in O(1) making it perfectly efficient.Q2. What is the time complexity of LeetCode 682? O(n) time where n is the number of operations. Each operation performs a constant number of stack operations (at most 3 pushes/pops for the + case). Space complexity is O(n) for storing scores.Q3. Why does the + operation need to pop and push back in the Stack approach? Stack only gives direct access to the top element. To get the second most recent score, you must pop the first one, peek/pop the second, then push the first one back. The ArrayList approach avoids this by using index-based access directly.Q4. What is the difference between Stack and ArrayDeque in Java for this problem? Both work correctly. ArrayDeque is faster because Stack is a legacy class that extends Vector and is synchronized (thread-safe), adding unnecessary overhead for single-threaded use. ArrayDeque has no synchronization overhead. For LeetCode and interviews, either is acceptable but ArrayDeque is technically better.Q5. Is LeetCode 682 asked in coding interviews? It appears occasionally as a warmup or screening problem. Its main value is testing whether you can carefully simulate rules without making logical errors — a skill that matters in systems programming, game development, and any domain with complex state management.Similar LeetCode Problems to Practice Next71. Simplify Path — Medium — stack simulation with path operations1047. Remove All Adjacent Duplicates In String — Easy — stack simulation735. Asteroid Collision — Medium — stack simulation with conditions150. Evaluate Reverse Polish Notation — Medium — stack with arithmetic operations, very similar pattern227. Basic Calculator II — Medium — stack with operator precedenceConclusionLeetCode 682 Baseball Game is a perfect problem to build confidence with stack simulation. The four operations are clearly defined, the rules are unambiguous, and the stack maps naturally to every operation. Once you understand why pop-push-back is needed for + in the stack approach and how ArrayList simplifies that with index access, you have genuinely understood the tradeoffs between these data structures.If you are newer to stacks, start with the ArrayList solution for clarity. Once that clicks, rewrite it with Stack to understand the LIFO mechanics. Then try ArrayDeque to understand why it is preferred in modern Java code.

LeetCodeJavaStackArrayListDequeEasy