Search Blogs

Showing results for "Pointer Manipulation"

Found 12 results

LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/odd-even-linked-list/Problem Description (In Very Simple Words)You are given the head of a linked list.Your task is:👉 Rearrange the list such that:All nodes at odd positions come firstFollowed by all nodes at even positionsImportant Clarification❗ This problem is about positions (indices), NOT values.1st node → Odd2nd node → Even3rd node → Odd4th node → EvenExample WalkthroughExample 1Input:[1,2,3,4,5]Positions:1(odd), 2(even), 3(odd), 4(even), 5(odd)Output:[1,3,5,2,4]Example 2Input:[2,1,3,5,6,4,7]Output:[2,3,6,7,1,5,4]Constraints0 <= number of nodes <= 10^4-10^6 <= Node.val <= 10^6Core Idea of the ProblemWe need to:Separate nodes into two groups:Odd index nodesEven index nodesMaintain their original orderFinally:👉 Attach even list after odd listThinking About Different ApproachesWhen solving this problem, multiple approaches may come to mind:Approach 1: Create New ListsIdeaTraverse the listCreate new nodes for odd and even positionsBuild two separate listsMerge themProblem with This Approach❌ Uses extra space❌ Not optimal (violates O(1) space requirement)❌ Code becomes messy and harder to maintainYour approach is logically correct, but:👉 It is not optimal and can be simplified a lot.Approach 2: Brute Force Using Array/ListIdeaStore nodes in an arrayRearrange based on indicesRebuild linked listComplexityTime: O(n)Space: O(n) ❌ (Not allowed)Approach 3: Optimal In-Place Approach (Best Solution)This is the cleanest and most important approach.Optimal Approach: Two Pointer Technique (In-Place)IdeaInstead of creating new nodes:👉 We rearrange the existing nodesWe maintain:odd → points to odd nodeseven → points to even nodesevenHead → stores start of even listVisualizationInput:1 → 2 → 3 → 4 → 5We separate into:Odd: 1 → 3 → 5Even: 2 → 4Final:1 → 3 → 5 → 2 → 4Step-by-Step LogicStep 1: Initialize pointersodd = headeven = head.nextevenHead = head.nextStep 2: Traverse the listWhile:even != null && even.next != nullUpdate:odd.next = odd.next.nexteven.next = even.next.nextMove pointers forward:odd = odd.nexteven = even.nextStep 3: Mergeodd.next = evenHeadClean Java Implementation (Optimal)class Solution { public ListNode oddEvenList(ListNode head) { // Edge case if(head == null || head.next == null) return head; // Initialize pointers ListNode odd = head; ListNode even = head.next; ListNode evenHead = even; // Rearranging nodes while(even != null && even.next != null){ odd.next = odd.next.next; // Link next odd even.next = even.next.next; // Link next even odd = odd.next; even = even.next; } // Attach even list after odd list odd.next = evenHead; return head; }}Dry Run (Important)Input:1 → 2 → 3 → 4 → 5Steps:Iteration 1:odd → 1, even → 2Link:1 → 32 → 4Iteration 2:odd → 3, even → 4Link:3 → 54 → nullFinal connection:5 → 2Result:1 → 3 → 5 → 2 → 4Time ComplexityO(n)We traverse the list once.Space ComplexityO(1)No extra space used.Why This Approach is BestFeatureResultExtra Space❌ NoneClean Code✅ YesEfficient✅ O(n)Interview Friendly✅ HighlyCommon Mistakes❌ Confusing values with positions❌ Creating new nodes unnecessarily❌ Forgetting to connect even list at the end❌ Breaking the list accidentallyKey LearningThis problem teaches:In-place linked list manipulationPointer handlingList partitioningFinal ThoughtsThe Odd Even Linked List problem is a classic example of how powerful pointer manipulation can be.Even though creating new nodes might seem easier at first, the in-place approach is:👉 Faster👉 Cleaner👉 Interview optimized👉 Tip: Whenever you are asked to rearrange a linked list, always think:"Can I solve this by just changing pointers instead of creating new nodes?"That’s the key to mastering linked list problems 🚀

Linked ListPointer ManipulationIn-Place AlgorithmTwo PointersLeetCode Medium

Reverse LinkedList (LeetCode 206) – The One Trick That Changes Everything

🚀 Try the ProblemPractice here:https://leetcode.com/problems/reverse-linked-list/🤔 Let’s Start With a Simple Question…What happens if you take this:1 → 2 → 3 → 4 → 5…and try to reverse it?You want:5 → 4 → 3 → 2 → 1Sounds easy, right?But here’s the catch:👉 You can only move forward in a linked list👉 There is no backward pointerSo how do we reverse something that only goes one way?🧠 The Core Problem (In Simple Words)You are given the head of a linked list.👉 Reverse the list👉 Return the new head📦 Constraints0 <= number of nodes <= 5000-5000 <= Node.val <= 5000🔍 Before Jumping to Code — Think Like ThisWhen solving this, your brain might go:Can I store values somewhere and reverse? ❌ (extra space)Can I rebuild the list? ❌ (unnecessary)Can I just change links? ✅ (YES, THIS IS THE KEY)⚡ The Breakthrough Idea👉 Instead of moving nodes👉 We reverse the direction of pointers🎯 Visual Intuition (Very Important)Let’s take:1 → 2 → 3 → 4 → nullWe want:null ← 1 ← 2 ← 3 ← 4But how?🧩 The 3-Pointer Magic TrickWe use 3 pointers:prev → stores previous nodecurr → current nodenext → stores next node🔄 Step-by-Step TransformationInitial State:prev = nullcurr = 1 → 2 → 3 → 4Step 1:Save next nodeReverse linkf = 21 → nullMove pointers:prev = 1curr = 2Step 2:f = 32 → 1Move:prev = 2curr = 3Continue…Eventually:4 → 3 → 2 → 1 → null💡 Final Insight👉 Each step reverses one link👉 At the end, prev becomes the new head✅ Clean Java Code (Iterative Approach)class Solution {public ListNode reverseList(ListNode head) {// Previous pointer starts as nullListNode prev = null;// Current pointer starts from headListNode curr = head;while (curr != null) {// Store next nodeListNode f = curr.next;// Reverse the linkcurr.next = prev;// Move prev forwardprev = curr;// Move curr forwardcurr = f;}// New head is prevreturn prev;}}⏱️ ComplexityTime ComplexityO(n)We traverse the list once.Space ComplexityO(1)No extra space used.🔁 Another Way: Recursive ApproachNow let’s think differently…👉 What if we reverse the rest of the list first, then fix the current node?🧠 Recursive IdeaFor:1 → 2 → 3 → 4We:Reverse from 2 → 3 → 4Then fix 1💻 Recursive Codeclass Solution {public ListNode reverseList(ListNode head) {// Base caseif(head == null || head.next == null)return head;// Reverse restListNode newHead = reverseList(head.next);// Fix current nodehead.next.next = head;head.next = null;return newHead;}}⚖️ Iterative vs RecursiveApproachProsConsIterativeFast, O(1) spaceSlightly tricky to understandRecursiveElegant, clean logicUses stack (O(n) space)❌ Common MistakesForgetting to store next nodeLosing reference to rest of listNot updating pointers correctlyReturning wrong node🔥 Real Interview InsightThis problem is not just about reversing a list.It teaches:👉 Pointer manipulation👉 In-place updates👉 Thinking in steps👉 Breaking problems into small operations🧠 Final ThoughtAt first, this problem feels tricky…But once you understand this line:curr.next = prev👉 Everything clicks.🚀 ConclusionThe Reverse Linked List problem is one of the most important foundational problems in DSA.Mastering it will:Boost your confidenceStrengthen pointer logicHelp in many advanced problems👉 Tip: Practice this until you can visualize pointer movement in your head — that’s when you truly master linked lists.

Linked ListPointer ManipulationIterative ApproachRecursionLeetCodeEasy

LeetCode 203: Remove Linked List Elements – Step-by-Step Guide for Beginners

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/remove-linked-list-elements/Problem Description (In Very Simple Words)You are given:The head of a linked listAn integer value valYour task is:👉 Remove all nodes from the linked list whose value is equal to val.👉 Return the updated head of the linked list.What is a Linked List? (Quick Recap)A linked list is a chain of nodes where each node contains:value + pointer to next nodeExample:1 → 2 → 6 → 3 → 4 → 5 → 6 → nullExample WalkthroughExample 1Input:head = [1,2,6,3,4,5,6]val = 6Output:[1,2,3,4,5]ExplanationWe remove all nodes with value 6.1 → 2 → ❌6 → 3 → 4 → 5 → ❌6Final list:1 → 2 → 3 → 4 → 5Example 2Input:head = []val = 1Output:[]Example 3Input:head = [7,7,7,7]val = 7Output:[]All nodes are removed.Constraints0 <= number of nodes <= 10^41 <= Node.val <= 500 <= val <= 50Understanding the Problem DeeplyThe tricky part is:👉 Nodes can appear anywhere:At the beginningIn the middleAt the endOr all nodes👉 Linked list does NOT allow backward traversalSo we must carefully handle pointers.Thinking About the SolutionWhen solving this problem, multiple approaches may come to mind:Possible ApproachesTraverse the list and remove nodes manually.Handle head separately, then process the rest.Use a dummy node to simplify logic.Use recursion (less preferred for beginners).Approach 1: Without Dummy Node (Manual Handling)IdeaFirst, remove nodes from the start (head) if they match val.Then traverse the list using two pointers:prev → previous nodecurr → current nodeKey ChallengeHandling head separately makes code more complex.Codeclass Solution { public ListNode removeElements(ListNode head, int val) { // Step 1: Remove matching nodes from the beginning while(head != null && head.val == val){ head = head.next; } // If list becomes empty if(head == null) return null; ListNode prev = head; ListNode curr = head.next; while(curr != null){ if(curr.val == val){ // Skip the node prev.next = curr.next; } else { // Move prev only when node is not removed prev = curr; } curr = curr.next; } return head; }}Why This WorksWe ensure prev always points to the last valid nodeWhen we find a node to delete:prev.next = curr.nextThis skips the unwanted nodeProblem With This Approach👉 Too many edge cases:Removing head nodesEmpty listAll nodes equalApproach 2: Dummy Node (Best & Clean Approach)IdeaWe create a fake node (dummy) before the head.dummy → head → rest of listThis helps us:👉 Treat head like a normal node👉 Avoid special casesVisualizationOriginal:1 → 2 → 6 → 3After dummy:-1 → 1 → 2 → 6 → 3Java Implementation (Best Approach)class Solution { public ListNode removeElements(ListNode head, int val) { // Step 1: Create dummy node ListNode dumm = new ListNode(-1, head); // Step 2: Start from dummy ListNode curr = dumm; while(curr.next != null){ // If next node needs to be removed if(curr.next.val == val){ // Skip that node curr.next = curr.next.next; } else { // Move forward only when no deletion curr = curr.next; } } // Step 3: Return new head return dumm.next; }}Step-by-Step Dry RunInput:1 → 2 → 6 → 3 → 4 → 5 → 6val = 6After dummy:-1 → 1 → 2 → 6 → 3 → 4 → 5 → 6Traversal:curr = -1 → 1 (keep)curr = 1 → 2 (keep)curr = 2 → 6 (remove)curr = 2 → 3 (keep)curr = 3 → 4 (keep)curr = 4 → 5 (keep)curr = 5 → 6 (remove)Final:1 → 2 → 3 → 4 → 5Time ComplexityO(n)We traverse the list once.Space ComplexityO(1)No extra space used.Why Dummy Node is PreferredWithout DummyWith DummyComplex edge casesClean logicSpecial handling for headNo special handlingError-proneSafe and readableApproach 3: Recursive Solution (Conceptual)IdeaWe process one node at a time and recursively solve for the rest.Codeclass Solution { public ListNode removeElements(ListNode head, int val) { if(head == null) return null; head.next = removeElements(head.next, val); if(head.val == val){ return head.next; } else { return head; } }}Time ComplexityO(n)Space ComplexityO(n)(due to recursion stack)Key TakeawaysLinked list problems are all about pointer manipulationAlways think about edge cases (especially head)Dummy node simplifies almost every linked list problemConclusionThe Remove Linked List Elements problem is perfect for understanding how linked lists work in real scenarios.While the manual approach works, the dummy node technique provides a much cleaner and safer solution.If you master this pattern, you will be able to solve many linked list problems easily in interviews.👉 Tip: Whenever you feel stuck in linked list problems, try adding a dummy node — it often simplifies everything!

Linked ListIterationDummy NodePointer ManipulationLeetCodeEasy

Reverse Only Letters – Two Pointer Strategy Explained (LeetCode 917)

🔗 Problem LinkLeetCode 917 – Reverse Only Letters 👉 https://leetcode.com/problems/reverse-only-letters/IntroductionThis is a very clean two-pointer problem.The challenge is not just reversing a string — it’s reversing only the letters while keeping all non-letter characters in their original positions.This problem strengthens:Two pointer techniqueCharacter validation logicIn-place string manipulationLet’s break it down.📌 Problem UnderstandingYou are given a string s.Rules:All non-English letters must remain at the same index.Only English letters (uppercase or lowercase) should be reversed.Return the modified string.Example 1Input: "ab-cd"Output: "dc-ba"Only letters are reversed. Hyphen stays at same position.Example 2Input: "a-bC-dEf-ghIj"Output: "j-Ih-gfE-dCba"Example 3Input: "Test1ng-Leet=code-Q!"Output: "Qedo1ct-eeLg=ntse-T!"Notice:Numbers, -, =, ! stay fixed.Only letters move.🧠 IntuitionThe first thought might be:Extract all lettersReverse themPut them backBut that would require extra space.Instead, we can solve this efficiently using Two Pointers.🚀 Two Pointer ApproachWe use:i → starting from leftj → starting from rightSteps:Convert string into char array.Move i forward until it points to a letter.Move j backward until it points to a letter.Swap letters.Continue until i < j.💻 Your Codeclass Solution { public String reverseOnlyLetters(String s) { int i = 0; int j = s.length() - 1; char arr[] = s.toCharArray(); while(i < j){ boolean l = ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') || ('a' <= s.charAt(i) && s.charAt(i) <= 'z'); boolean r = ('A' <= s.charAt(j) && s.charAt(j) <= 'Z') || ('a' <= s.charAt(j) && s.charAt(j) <= 'z'); if(l && r){ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; }else if(l){ j--; }else if(r){ i++; }else{ i++; j--; } } return new String(arr); }}🔍 Step-by-Step Explanation1️⃣ Convert to Character Arraychar arr[] = s.toCharArray();Strings are immutable in Java. So we convert to char array to modify it.2️⃣ Initialize Two Pointersint i = 0;int j = s.length() - 1;We start from both ends.3️⃣ Check If Characters Are Lettersboolean l = ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') || ('a' <= s.charAt(i) && s.charAt(i) <= 'z');You manually check ASCII ranges for uppercase and lowercase letters.Same logic for r.4️⃣ Swap When Both Are Lettersif(l && r){ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--;}Only swap letters.5️⃣ Move Pointers When One Is Not LetterIf left is letter but right is not → move jIf right is letter but left is not → move iIf both are not letters → move bothThis ensures:Non-letter characters remain in their positions.🎯 Why This WorksWe never move non-letter characters.We only swap valid letters.Since we use two pointers:Time complexity stays linear.No extra array needed for letters.⏱ Complexity AnalysisTime Complexity: O(n)Each character is visited at most once.Space Complexity: O(n)Because we convert string to char array.(If considering output string creation, still O(n))🔥 Cleaner OptimizationInstead of manually checking ASCII ranges, Java provides:Character.isLetter(c)Cleaner version:class Solution { public String reverseOnlyLetters(String s) { int i = 0, j = s.length() - 1; char[] arr = s.toCharArray(); while(i < j){ if(!Character.isLetter(arr[i])){ i++; }else if(!Character.isLetter(arr[j])){ j--; }else{ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } return new String(arr); }}Much cleaner and readable.🏁 Final ThoughtsThis problem teaches:Two pointer patternIn-place string reversalCharacter validation logicClean pointer movement strategyIt’s a simple but powerful pattern that appears often in interviews.If you master this, you can easily solve:Reverse Vowels of a StringValid PalindromeReverse String IIPalindrome with One Removal

Two PointersString ManipulationLeetCodeEasy

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

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

Two PointersString ManipulationHashMapLeetCodeEasy

LeetCode 2: Add Two Numbers – Step-by-Step Linked List Addition Explained Clearly

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/add-two-numbers/Problem Description (In Simple Words)You are given two linked lists, where:Each node contains a single digit (0–9)The digits are stored in reverse order👉 That means:[2,4,3] represents 342[5,6,4] represents 465Your task is:👉 Add these two numbers👉 Return the result as a linked list (also in reverse order)Important Points to UnderstandEach node contains only one digitNumbers are stored in reverse orderYou must return the answer as a linked listYou must handle carry just like normal additionExample WalkthroughExample 1Input:l1 = [2,4,3]l2 = [5,6,4]Interpretation:342 + 465 = 807Output:[7,0,8]Example 2Input:l1 = [0]l2 = [0]Output:[0]Example 3Input:l1 = [9,9,9,9,9,9,9]l2 = [9,9,9,9]Output:[8,9,9,9,0,0,0,1]Constraints1 <= number of nodes <= 1000 <= Node.val <= 9No leading zeros except the number 0Understanding the Core IdeaThis problem is essentially:👉 Adding two numbers digit by digitBut instead of arrays or integers, the digits are stored in linked lists.How Addition Works (Real-Life Analogy)Let’s add:342 + 465We normally add from right to left:2 + 5 = 74 + 6 = 10 → write 0, carry 13 + 4 + 1 = 8Now notice something important:👉 Linked list is already in reverse order👉 So we can directly process from left to rightThinking About the SolutionBefore coding, let’s think of possible approaches:Possible Ways to SolveConvert linked lists into numbers → add → convert back (Not safe due to overflow)Store digits in arrays and simulate additionTraverse both lists and simulate addition directly (best approach)Optimal Approach: Simulate Addition (Digit by Digit)Key IdeaWe traverse both linked lists and:Add corresponding digitsMaintain a carryCreate a new node for each digit of resultStep-by-Step LogicStep 1: InitializeCreate a dummy node (to simplify result building)Create a pointer curr to build the result listInitialize carry = 0Step 2: Traverse Both ListsContinue while:l1 != null OR l2 != nullAt each step:Start with carry:sum = carryAdd value from l1 (if exists)Add value from l2 (if exists)Step 3: Create New NodeDigit to store:sum % 10New carry:sum / 10Step 4: Move ForwardMove l1 and l2 if they existMove curr forwardStep 5: Handle Remaining CarryIf carry is not zero after loop:👉 Add one more nodeStep 6: Return ResultReturn:dummy.nextCode Implementation (With Explanation)class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // Dummy node to simplify result construction ListNode dumm = new ListNode(-1); ListNode curr = dumm; int sum = 0; int carr = 0; // Traverse both lists while(l1 != null || l2 != null){ // Start with carry sum = carr; // Add l1 value if exists if(l1 != null){ sum += l1.val; l1 = l1.next; } // Add l2 value if exists if(l2 != null){ sum += l2.val; l2 = l2.next; } // Create new node with digit ListNode newNode = new ListNode(sum % 10); // Update carry carr = sum / 10; // Attach node curr.next = newNode; curr = curr.next; } // If carry remains if(carr != 0){ curr.next = new ListNode(carr); } return dumm.next; }}Dry Run (Important for Understanding)Input:l1 = [2,4,3]l2 = [5,6,4]Step-by-step:Step 1:2 + 5 = 7 → node(7), carry = 0Step 2:4 + 6 = 10 → node(0), carry = 1Step 3:3 + 4 + 1 = 8 → node(8), carry = 0Final:7 → 0 → 8Time ComplexityO(max(n, m))Where:n = length of l1m = length of l2Space ComplexityO(max(n, m))For storing the result linked list.Why Dummy Node is ImportantWithout dummy node:You need to handle first node separatelyWith dummy node:Code becomes clean and consistentNo special cases requiredCommon Mistakes to Avoid❌ Forgetting to handle carry❌ Not checking if l1 or l2 is null❌ Missing last carry node❌ Incorrect pointer movementKey TakeawaysThis is a simulation problemLinked list problems become easier with dummy nodesAlways think in terms of real-world analogy (addition)ConclusionThe Add Two Numbers problem is one of the most important linked list problems for interviews.It teaches:Pointer manipulationCarry handlingIterative traversalClean code using dummy nodesOnce you understand this pattern, many other linked list problems become much easier to solve.👉 Tip: Whenever you see problems involving numbers in linked lists, think of digit-by-digit simulation with carry.

Linked ListMathSimulationCarry HandlingDummy NodeLeetCode Medium

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

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 844: Backspace String Compare — Java Solution With All Approaches Explained

IntroductionLeetCode 844 Backspace String Compare is a fantastic problem that shows up frequently in coding interviews. It combines string manipulation, stack simulation, and even has a follow-up that challenges you to solve it in O(1) space — which is what separates a good candidate from a great one.Here is the Link of Question -: LeetCode 844In this article we cover a plain English explanation, real life analogy, 3 Java approaches including the O(1) space two pointer solution, dry runs, complexity analysis, common mistakes, and FAQs.What Is the Problem Really Asking?You are given two strings s and t. Both contain lowercase letters and # characters. Think of # as the backspace key on your keyboard — it deletes the character just before it. If there is nothing to delete, it does nothing.Process both strings through these backspace operations and check if the resulting strings are equal. Return true if equal, false otherwise.Quick Example:s = "ab#c" → # deletes b → becomes "ac"t = "ad#c" → # deletes d → becomes "ac"Both equal "ac" → return true ✅Real Life Analogy — The Keyboard TypoYou are typing a message. You type "ab", realize you made a typo, hit backspace, and type "c". Your friend types "ad", hits backspace, and types "c". Even though you both typed differently, the final message on screen is the same — "ac".That is exactly what this problem is about. Two people typing differently but ending up with the same result.Approach 1: StringBuilder as Stack (Optimal & Clean) ✅The IdeaThis is your own solution and the best O(n) approach. Process each string independently using a StringBuilder as a stack:Letter → append to StringBuilder (push)# → delete last character if StringBuilder is not empty (pop)Then simply compare the two resulting StringBuilders.public boolean backspaceCompare(String s, String t) { return process(s).equals(process(t));}private String process(String str) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (c == '#') { if (sb.length() > 0) { sb.deleteCharAt(sb.length() - 1); } } else { sb.append(c); } } return sb.toString();}Notice how extracting a process() helper method makes the code cleaner and avoids repeating the same loop twice — a great habit to show in interviews!Dry Run — s = "ab##", t = "c#d#"Processing s = "ab##":a → append → "a"b → append → "ab"# → delete last → "a"# → delete last → ""Processing t = "c#d#":c → append → "c"# → delete last → ""d → append → "d"# → delete last → ""Both result in "" → return true ✅Time Complexity: O(n + m) — where n and m are lengths of s and t Space Complexity: O(n + m) — two StringBuilders storing processed stringsApproach 2: Stack Based Solution (Interview Classic)The IdeaSame logic as above but using explicit Stack<Character> objects. Great for explaining your thought process clearly in an interview even though StringBuilder is cleaner.public boolean backspaceCompare(String s, String t) { return processStack(s).equals(processStack(t));}private String processStack(String str) { Stack<Character> st = new Stack<>(); for (int i = 0; i < str.length(); i++) { char c = str.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();}Dry Run — s = "a#c", t = "b"Processing s = "a#c":a → push → stack: [a]# → pop → stack: []c → push → stack: [c]Result: "c"Processing t = "b":b → push → stack: [b]Result: "b""c" does not equal "b" → return false ✅Time Complexity: O(n + m) Space Complexity: O(n + m)Approach 3: Two Pointer — O(1) Space (Follow-Up Solution) 🔥This is the follow-up the problem asks about — can you solve it in O(n) time and O(1) space? This means no extra StringBuilder or Stack allowed.The IdeaInstead of building processed strings, traverse both strings from right to left simultaneously. Keep a count of pending backspaces. Skip characters that would be deleted and compare characters that survive.Why right to left? Because # affects characters to its left, so processing from the end lets us know upfront how many characters to skip.public boolean backspaceCompare(String s, String t) { int i = s.length() - 1; int j = t.length() - 1; int skipS = 0, skipT = 0; while (i >= 0 || j >= 0) { // Find next valid character in s while (i >= 0) { if (s.charAt(i) == '#') { skipS++; i--; } else if (skipS > 0) { skipS--; i--; } else { break; } } // Find next valid character in t while (j >= 0) { if (t.charAt(j) == '#') { skipT++; j--; } else if (skipT > 0) { skipT--; j--; } else { break; } } // Compare the valid characters if (i >= 0 && j >= 0) { if (s.charAt(i) != t.charAt(j)) { return false; } } else if (i >= 0 || j >= 0) { return false; // one string still has chars, other doesn't } i--; j--; } return true;}Dry Run — s = "ab#c", t = "ad#c"Starting from the right end of both strings:Round 1:s[3] = 'c' → valid, no skips → stopt[3] = 'c' → valid, no skips → stopCompare 'c' == 'c' ✅ → move both pointers leftRound 2:s[2] = '#' → skipS = 1, move lefts[1] = 'b' → skipS > 0, skipS = 0, move lefts[0] = 'a' → valid, stopt[2] = '#' → skipT = 1, move leftt[1] = 'd' → skipT > 0, skipT = 0, move leftt[0] = 'a' → valid, stopCompare 'a' == 'a' ✅ → move both pointers leftBoth pointers exhausted → return true ✅Time Complexity: O(n + m) — each character visited at most once Space Complexity: O(1) — only pointer and counter variables, no extra storage!Approach ComparisonThe StringBuilder approach is the easiest to write and explain. The Stack approach is slightly more verbose but shows clear intent. The Two Pointer approach is the hardest to code but the most impressive — it solves the follow-up and uses zero extra space.In an interview, start with the StringBuilder solution, explain it clearly, then mention the Two Pointer approach as the O(1) space optimization if asked.How This Fits the Stack Simulation PatternYou have now seen this same pattern across four problems:3174 Clear Digits — digit deletes closest left non-digit 2390 Removing Stars — star deletes closest left non-star 1047 Remove Adjacent Duplicates — character cancels matching top of stack 844 Backspace String Compare — # deletes closest left character, then compare two stringsAll four use the same StringBuilder-as-stack core. The only differences are the trigger character and what you do with the result. This is the power of pattern recognition in DSA.Common Mistakes to AvoidNot handling backspace on empty string When # appears but the StringBuilder is already empty, do nothing. Always guard with sb.length() > 0 before calling deleteCharAt. The problem explicitly states backspace on empty text keeps it empty.Using Stack and forgetting to handle # when stack is empty In the Stack approach, only pop if the stack is not empty. Pushing # onto the stack when it is empty is a common bug that gives wrong answers.In Two Pointer, comparing before both pointers find valid characters Make sure both inner while loops fully complete before comparing. Comparing too early is the most common mistake in the O(1) space solution.FAQs — People Also AskQ1. What is the best approach for LeetCode 844 in Java? For most interviews, the StringBuilder approach is the best — clean, readable, and O(n) time. If the interviewer asks for O(1) space, switch to the Two Pointer approach traversing from right to left.Q2. How does the O(1) space solution work for LeetCode 844? It uses two pointers starting from the end of both strings, keeping a skip counter to track pending backspaces. Characters that would be deleted are skipped, and only surviving characters are compared.Q3. What is the time complexity of LeetCode 844? All three approaches run in O(n + m) time where n and m are the lengths of the two strings. The Two Pointer approach achieves this with O(1) space instead of O(n + m).Q4. Why traverse from right to left in the Two Pointer approach? Because # affects characters to its left. Scanning from the right lets you know upfront how many characters to skip before you reach them, avoiding the need to store anything.Q5. Is LeetCode 844 asked in Google interviews? Yes, it is commonly used as a warmup or screening problem. The follow-up O(1) space solution is what makes it interesting for senior-level interviews.Similar LeetCode Problems to Practice Next1047. Remove All Adjacent Duplicates In String — Easy — same stack pattern2390. Removing Stars From a String — Medium — star as backspace3174. Clear Digits — Easy — digit as backspace1209. Remove All Adjacent Duplicates in String II — Medium — k adjacent duplicates678. Valid Parenthesis String — Medium — stack with wildcardsConclusionLeetCode 844 Backspace String Compare is a well-rounded problem that tests string manipulation, stack simulation, and space optimization all in one. The StringBuilder solution is your go-to for interviews. But always be ready to explain the Two Pointer O(1) space follow-up — that is what shows real depth of understanding.Check out these problems alongside 1047, 2390, and 3174 and you will have the entire stack simulation pattern locked down for any coding interview.

StringStackTwo PointerString Builder

LeetCode 462: Minimum Moves to Equal Array Elements II | Java Solution Explained (Median Approach)

IntroductionLeetCode 462 is a classic mathematical and greedy problem.We are given an integer array where each operation allows us to:Increment an element by 1Decrement an element by 1Our task is to make all numbers equal while using the minimum number of moves.At first glance, this may look like a simple array problem.But the hidden concept behind this question is:Median propertyGreedy optimizationAbsolute difference minimizationThis problem is extremely popular in coding interviews because it tests logical thinking more than coding complexity.# Problem LinkProblem StatementYou are given an integer array nums.In one move:You can increase an element by 1Or decrease an element by 1You must make all array elements equal.Return the minimum number of operations required.Example 1Input:nums = [1,2,3]Output:2Explanation:[1,2,3]→ [2,2,3]→ [2,2,2]Total operations = 2Example 2Input:nums = [1,10,2,9]Output:16Key ObservationWe need to choose one target value such that all numbers move toward it.Question:Which target gives minimum total moves?Answer:MedianMedian minimizes the sum of absolute differences.Why Median Works?Suppose:nums = [1,2,3,10]If target = 2|1-2| + |2-2| + |3-2| + |10-2|= 1 + 0 + 1 + 8= 10If target = 5|1-5| + |2-5| + |3-5| + |10-5|= 4 + 3 + 2 + 5= 14Median gives minimum moves.Approach 1: Brute ForceIn this approach, we try every possible value as target.For each target:Calculate total operations neededStore minimum answerAlgorithmFind minimum and maximum elementTry every value between themCompute total movesReturn minimumJava Code (Brute Force)class Solution {public int minMoves2(int[] nums) {int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;for (int num : nums) {min = Math.min(min, num);max = Math.max(max, num);}int result = Integer.MAX_VALUE;for (int target = min; target <= max; target++) {int moves = 0;for (int num : nums) {moves += Math.abs(num - target);}result = Math.min(result, moves);}return result;}}Time ComplexityO(N × Range)Very slow for large values.Approach 2: Sorting + Median (Optimal)This is the best and most commonly used approach.IdeaSort arrayPick median elementCalculate total absolute differenceStepsStep 1: Sort ArraySorting helps us easily find median.Step 2: Pick MedianMedian index = n / 2Step 3: Calculate MovesFor every element:moves += abs(median - value)Optimal Java Solutionclass Solution {public int minMoves2(int[] nums) {Arrays.sort(nums);int mid = nums.length / 2;int ans = 0;for (int i = 0; i < nums.length; i++) {int diff = Math.abs(nums[mid] - nums[i]);ans += diff;}return ans;}}Code ExplanationStep 1: Sort ArrayArrays.sort(nums);Sorting allows median calculation.Step 2: Get Medianint mid = nums.length / 2;Middle element becomes target.Step 3: Compute DifferenceMath.abs(nums[mid] - nums[i])Find distance from median.Step 4: Add All Movesans += diff;Store total moves.Approach 3: Two Pointer OptimizationAfter sorting, we can use two pointers.Instead of calculating absolute difference manually, we can pair smallest and largest values.IdeaAfter sorting:moves += nums[right] - nums[left]Because both numbers will meet toward median.Java Code (Two Pointer)class Solution {public int minMoves2(int[] nums) {Arrays.sort(nums);int left = 0;int right = nums.length - 1;int moves = 0;while (left < right) {moves += nums[right] - nums[left];left++;right--;}return moves;}}Why Two Pointer Works?Because:Median minimizes total distancePairing smallest and largest values gives direct movement cost.Dry RunInput:nums = [1,10,2,9]Sort:[1,2,9,10]Median:9Operations:|1-9| = 8|2-9| = 7|9-9| = 0|10-9| = 1Total:16Time ComplexitySortingO(N log N)TraversingO(N)TotalO(N log N)Space ComplexityO(1)Ignoring sorting stack.Common Mistakes1. Using Average Instead of MedianMany people think average gives minimum.Wrong.Average minimizes squared difference.Median minimizes absolute difference.2. Forgetting SortingMedian requires sorted order.3. Overflow IssueValues can be large.Sometimes use:long ansfor safer calculation.4. Using Wrong Median IndexCorrect:n / 2Edge CasesCase 1Single element array.Answer = 0Case 2All elements already equal.Answer = 0Case 3Negative numbers.Algorithm still works.FAQsQ1. Why median gives minimum moves?Median minimizes total absolute difference.Q2. Can average work?No.Average does not minimize absolute distance.Q3. Is sorting necessary?Yes.Sorting helps us easily find median.Q4. Which approach is best?Sorting + median approach.Interview InsightInterviewers ask this problem to test:Median property understandingGreedy optimizationMathematical thinkingArray manipulationConclusionLeetCode 462 is one of the most important median-based interview questions.The major learning is:Median minimizes total absolute differenceSorting makes finding median easySum of distances gives answerOnce you understand why median works, this question becomes very simple.

MathMedianMediumLeetCodeJavaArrayTwo PointerSorting

Max Consecutive Ones III – Sliding Window with Limited Flips

IntroductionLeetCode 1004: Max Consecutive Ones III is a classic sliding window problem that challenges your understanding of arrays, window manipulation, and frequency counting.The goal is to find the longest subarray of consecutive 1's in a binary array if you are allowed to flip at most K zeros to 1’s.This problem is an excellent example of transforming a brute-force solution into a linear-time efficient approach using the sliding window pattern.If you’d like to try solving the problem first, you can attempt it here: Try the problem on LeetCode: https://leetcode.com/problems/max-consecutive-ones-iii/Problem UnderstandingYou are given:A binary array nums containing only 0's and 1'sAn integer k representing the maximum number of zeros you can flipYou need to return the length of the longest contiguous subarray of 1's after flipping at most k zeros.Examples:Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2Output: 6Explanation: Flip two zeros to get [1,1,1,0,0,1,1,1,1,1,1].Longest consecutive ones = 6.Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3Output: 10Explanation: Flip three zeros to get longest consecutive ones of length 10.A naive approach would check every possible subarray, flip zeros, and count consecutive ones:Time Complexity: O(n²) → too slow for large arraysInefficient for constraints up to 10⁵ elementsKey Idea: Sliding Window with Zero CountInstead of brute-force, notice that:We only care about how many zeros are in the current windowWe can maintain a sliding window [i, j]Keep a counter z for zeros in the windowExpand the window by moving jIf z exceeds k, shrink the window from the left by moving i and decrementing z for each zero removedIntuition:The window always contains at most k zerosThe length of the window gives the maximum consecutive ones achievable with flipsThis allows linear traversal of the array with O(1) space, making it optimal.Approach (Step-by-Step)Initialize pointers: i = 0, j = 0Initialize z = 0 (zeros count in current window) and co = 0 (max length)Iterate j from 0 to nums.length - 1:If nums[j] == 0, increment zCheck z:If z <= k: window is valid → update co = max(co, j - i + 1)Else: shrink window by moving i until z <= k, decrement z for zeros leaving windowContinue expanding window with jReturn co as the maximum consecutive onesOptimization:Only need one variable for zeros countAvoids recomputing sums or scanning subarrays repeatedlyImplementation (Java)class Solution { public int longestOnes(int[] nums, int k) { int co = 0; // maximum length of valid window int i = 0, j = 0; // window pointers int z = 0; // count of zeros in current window while (j < nums.length) { if (nums[j] == 0) { z++; // increment zeros count } if (z <= k) { co = Math.max(co, j - i + 1); // valid window j++; } else { // shrink window until zeros <= k while (z > k) { if (nums[i] == 0) { z--; } i++; } co = Math.max(co, j - i + 1); j++; } } return co; }}Dry Run ExampleInput:nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2Execution:Window [i, j]Zeros zValid?Max length co[0,0] → [1]0Yes1[0,2] → [1,1,1]0Yes3[0,3] → [1,1,1,0]1Yes4[0,4] → [1,1,1,0,0]2Yes5[0,5] → [1,1,1,0,0,0]3No → shrink i5[3,8] → [0,0,1,1,1,1]2Yes6Output:6Complexity AnalysisTime Complexity: O(n) → Each element is visited at most twice (once when j moves, once when i moves)Space Complexity: O(1) → Only counters and pointers usedEdge Cases Consideredk = 0 → cannot flip any zeros, just count consecutive onesArray with all 1’s → return full lengthArray with all 0’s → return min(k, length)Single element arrays → works correctlySliding Window Pattern ImportanceThis problem is a perfect example of the sliding window pattern:Use a window to track a condition (max zeros allowed)Expand and shrink dynamically based on constraintsEfficiently computes maximum/minimum contiguous subarray lengthsIt also demonstrates counting with limited violations – a key interview concept.ConclusionBy tracking zeros with a sliding window, we convert a naive O(n²) problem into O(n) linear time.Understanding this pattern allows you to solve:Max consecutive ones/zeros problemsLongest substring/subarray with constraintsSubarray problems with limited replacements or violationsOnce mastered, this approach applies to many binary array and string problems efficiently.

SlidingWindowBinaryArrayLeetCodeMedium

Longest Substring with K Unique Characters – Efficient Sliding Window Solution

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

SlidingWindowHashMapStringsGFG