Search Blogs

Showing results for "Carry Handling"

Found 3 results

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 402: Remove K Digits — Java Solution Explained

IntroductionLeetCode 402 Remove K Digits is one of those problems where the brute force solution feels obvious but completely falls apart at scale — and the optimal solution requires a genuinely clever insight that, once you see it, feels like magic.This problem sits at the intersection of two powerful techniques — Greedy thinking and Monotonic Stack. If you have already solved Next Greater Element and Asteroid Collision, you have all the building blocks you need. This is where those patterns level up.You can find the problem here — LeetCode 402 Remove K Digits.What Is the Problem Really Asking?You are given a number as a string and an integer k. Remove exactly k digits from the number such that the resulting number is as small as possible. Return it as a string without leading zeros.Example:num = "1432219", k = 3We want to remove 3 digits to make the number as small as possibleRemove 4, 3, 2 → remaining is "1219"Output: "1219"Simple goal — smallest possible number after exactly k removals.Real Life Analogy — Choosing the Best Price TagImagine you are reading a price tag digit by digit from left to right. Every time you see a digit that is bigger than the next one coming, you have a chance to remove it and make the price smaller. You have a limited number of removals — use them wisely on the biggest offenders from the left side, because leftmost digits have the most impact on the overall value.Removing a 9 from the front of a number shrinks it far more than removing a 9 from the end. This left-to-right priority with greedy removal is the entire insight of this problem.The Core Greedy InsightHere is the key question — which digit should we remove first to make the number as small as possible?Think about it this way. In the number "1432219", which digit is hurting us the most? It is 4 — because it is large and sits early in the number. After removing 4 we get "132219". Now 3 is the biggest early offender. And so on.More precisely — whenever you see a digit that is greater than the digit immediately after it, removing it makes the number smaller. This is because a larger digit sitting before a smaller digit inflates the overall value.This is the Greedy rule: scan left to right, and whenever the current digit on the stack is greater than the incoming digit, remove it (if we still have removals left).A Monotonic Increasing Stack enforces exactly this — it keeps digits in non-decreasing order, automatically kicking out any digit that is larger than what comes next.The Solution — Monotonic Stackpublic String removeKdigits(String num, int k) { Stack<Character> st = new Stack<>(); // build monotonic increasing stack for (int i = 0; i < num.length(); i++) { // while stack top is greater than current digit and we still have removals while (!st.empty() && k != 0 && st.peek() > num.charAt(i)) { st.pop(); // remove the larger digit — greedy choice k--; } st.push(num.charAt(i)); } // if k removals still remaining, remove from the end (largest digits are at top) while (k != 0) { st.pop(); k--; } // build result string from stack StringBuilder sb = new StringBuilder(); while (!st.empty()) { sb.append(st.pop()); } sb.reverse(); // stack gives reverse order // remove leading zeros while (sb.length() > 0 && sb.charAt(0) == '0') { sb.deleteCharAt(0); } // if nothing left, return "0" return sb.length() == 0 ? "0" : sb.toString();}Step-by-Step Dry Run — num = "1432219", k = 3Processing 1: Stack empty → push. Stack: [1]Processing 4: Stack top 1 < 4 → no pop. Push 4. Stack: [1, 4]Processing 3: Stack top 4 > 3 and k=3 → pop 4, k=2. Stack: [1] Stack top 1 < 3 → stop. Push 3. Stack: [1, 3]Processing 2: Stack top 3 > 2 and k=2 → pop 3, k=1. Stack: [1] Stack top 1 < 2 → stop. Push 2. Stack: [1, 2]Processing 2: Stack top 2 == 2 → not greater, stop. Push 2. Stack: [1, 2, 2]Processing 1: Stack top 2 > 1 and k=1 → pop 2, k=0. Stack: [1, 2] k=0, stop. Push 1. Stack: [1, 2, 1]Processing 9: k=0, no more removals. Push 9. Stack: [1, 2, 1, 9]k is now 0, skip the cleanup loop.Build result: pop all → "9121" → reverse → "1219" No leading zeros. Return "1219" ✅Step-by-Step Dry Run — num = "10200", k = 1Processing 1: stack empty → push. Stack: [1]Processing 0: Stack top 1 > 0 and k=1 → pop 1, k=0. Stack: [] Push 0. Stack: [0]Processing 2: k=0, no removals. Push. Stack: [0, 2]Processing 0: k=0. Push. Stack: [0, 2, 0]Processing 0: k=0. Push. Stack: [0, 2, 0, 0]k=0, skip cleanup.Build result: "0020" → reverse → "0200" Remove leading zero → "200" Return "200" ✅Step-by-Step Dry Run — num = "10", k = 2Processing 1: push. Stack: [1]Processing 0: Stack top 1 > 0 and k=2 → pop 1, k=1. Stack: [] Push 0. Stack: [0]k=1 remaining → cleanup loop → pop 0, k=0. Stack: []Build result: empty string. Remove leading zeros: nothing to remove. Length is 0 → return "0" ✅The Three Tricky Cases You Must HandleCase 1 — k is not fully used after the loop This happens with a non-decreasing number like "12345" with k=2. No element ever gets popped during the loop because no digit is greater than the next one. The stack ends up as [1,2,3,4,5] with k still = 2. The solution is to pop from the top of the stack — which holds the largest digits — until k hits 0.Case 2 — Leading zeros After removing digits, the remaining number might start with zeros. "10200" becomes "0200" after removing 1. We strip leading zeros with a while loop. But we must be careful not to strip the only zero — that is why we check length > 0 before each removal.Case 3 — Empty result If all digits are removed (like "10" with k=2), the StringBuilder ends up empty. We return "0" because an empty number is represented as zero.Why Remaining k Gets Removed From the EndAfter the main loop, if k is still greater than 0, why do we remove from the top of the stack (which corresponds to the end of the number)?Because the stack at this point holds a non-decreasing sequence. In a non-decreasing sequence, the largest values are at the end. Removing from the end removes the largest remaining digits — which is exactly the greedy choice to minimize the number.For example in "12345" with k=2: the stack is [1,2,3,4,5]. Pop top twice → remove 5 and 4 → [1,2,3] → result is "123". Correct!Time and Space ComplexityTime Complexity: O(n) — each digit is pushed onto the stack exactly once and popped at most once. Even with the while loop inside the for loop, total push and pop operations across the entire run never exceed 2n. The leading zero removal is also O(n) in the worst case. Overall stays linear.Space Complexity: O(n) — the stack holds at most n digits in the worst case when no removals happen during the main loop.Common Mistakes to AvoidNot handling remaining k after the loop This is the most common mistake. If the number is already non-decreasing, the loop never pops anything. Forgetting the cleanup loop gives the wrong answer for inputs like "12345" with k=2.Not removing leading zeros After removals, the result might start with zeros. "0200" should be returned as "200". Skipping this step gives wrong output.Returning empty string instead of "0" When all digits are removed, return "0" not "". An empty string is not a valid number representation.Using >= instead of > in the pop condition If you pop on equal digits too, you remove more than necessary and might get wrong results. Only pop when strictly greater — equal digits in sequence are fine to keep.How This Connects to the Monotonic Stack SeriesLooking at the stack problems you have been solving:496 Next Greater Element — monotonic decreasing stack, find first bigger to the right 735 Asteroid Collision — stack simulation, chain reactions 402 Remove K Digits — monotonic increasing stack, greedy removal for minimum numberThe direction of the monotonic stack flips based on what you are optimizing. For "next greater" you keep a decreasing stack. For "smallest number" you keep an increasing stack. Recognizing which direction to go is the skill that connects all these problems.FAQs — People Also AskQ1. Why does a Monotonic Stack give the smallest number in LeetCode 402? A monotonic increasing stack ensures that at every point, the digits we have kept so far are in the smallest possible order. Whenever a smaller digit arrives and the stack top is larger, removing that larger digit can only make the number smaller — this greedy choice is always optimal.Q2. What happens if k is not fully used after the main loop in LeetCode 402? The number is already in non-decreasing order so no removals happened during the loop. The remaining removals should be made from the end of the number (top of stack) since those are the largest values in a non-decreasing sequence.Q3. How are leading zeros handled in LeetCode 402? After building the result string, strip any leading zeros with a while loop. If stripping leaves an empty string, return "0" because the empty case represents zero.Q4. What is the time complexity of LeetCode 402? O(n) time because each digit is pushed and popped at most once across the entire algorithm. Space complexity is O(n) for the stack.Q5. Is LeetCode 402 asked in coding interviews? Yes, it is frequently asked at companies like Google, Amazon, and Microsoft. It tests greedy thinking combined with monotonic stack — two patterns that interviewers love because they require genuine insight rather than memorization.Similar LeetCode Problems to Practice Next496. Next Greater Element I — Easy — monotonic decreasing stack739. Daily Temperatures — Medium — next greater with distances316. Remove Duplicate Letters — Medium — similar greedy stack with constraints1081. Smallest Subsequence of Distinct Characters — Medium — same approach as 31684. Largest Rectangle in Histogram — Hard — advanced monotonic stackConclusionLeetCode 402 Remove K Digits is a beautiful problem that rewards clear thinking. The greedy insight — always remove a digit when a smaller digit comes after it — naturally leads to the monotonic stack solution. The three edge cases (remaining k, leading zeros, empty result) are what separate a buggy solution from a clean, accepted one.Work through all three dry runs carefully. Once you see how the stack stays increasing and how each pop directly corresponds to a greedy removal decision, this pattern will click permanently and carry you through harder stack problems ahead.

LeetCodeJavaStackMonotonic StackGreedyStringMedium

LeetCode 258 — Add Digits | Brute Force to O(1) Digital Root Trick Explained in Java

IntroductionSome problems on LeetCode look too simple to teach you anything meaningful. LeetCode 258 — Add Digits is one of those problems that tricks you with its simplicity. The simulation is beginner-friendly and easy to code in five minutes, but hiding right underneath the surface is a beautiful piece of number theory that lets you solve the entire thing in a single arithmetic expression — no loops, no recursion, pure O(1) math.Whether you are just starting your DSA journey or preparing for coding interviews, this problem is worth understanding deeply. Not just for the answer, but for the mathematical intuition that produces it. By the end of this article, you will not just know the formula — you will understand exactly why it works, where it comes from, and how to derive it yourself even if you forget it during an interview.Problem LinkLeetCode 258 — Add Digits https://leetcode.com/problems/add-digits/Problem StatementGiven an integer num, repeatedly add all its digits until the result has only one digit, and return it.The follow-up asks: can you solve this in O(1) time without any loop or recursion?Approach 1 — Simulation (The Intuitive Way)IntuitionThe problem statement itself tells you exactly what to do. Keep summing the digits of the number until you are left with a single digit. You simulate this literally using nested loops.To extract digits from any integer, two operations do all the work:num % 10 isolates the rightmost digit. For 38, that gives 8.num / 10 removes the rightmost digit. For 38, that leaves 3.You accumulate the digits into a sum, replace num with that sum, and repeat the whole process until num drops below 10.Dry Runnum = 38Outer loop iteration 1:38 % 10 = 8 → sum = 8, num = 33 % 10 = 3 → sum = 11, num = 0Inner loop ends. num = 11Outer loop iteration 2:11 % 10 = 1 → sum = 1, num = 11 % 10 = 1 → sum = 2, num = 0Inner loop ends. num = 2num < 10 → outer loop exits → return 2 ✅Codeclass Solution { public int addDigits(int num) { // If already a single digit, return immediately — no work needed if (num < 10) return num; // Keep repeating the digit sum process until num becomes single digit while (num >= 10) { int sum = 0; // Extract each digit from right to left using modulo and division while (num > 0) { int dig = num % 10; // isolate the last digit num = num / 10; // strip the last digit off sum = sum + dig; // accumulate into running sum } // Replace num with the sum of its digits and check again num = sum; } return num; }}ComplexityTime Complexity: O(log n) — Each iteration reduces the number to the sum of its digits, shrinking it dramatically. The number of passes is very small even for large inputs.Space Complexity: O(1) — Only a handful of integer variables. No extra memory allocated.This passes all test cases cleanly. But the follow-up challenges you to eliminate the loop entirely. That is where things get genuinely interesting.Approach 2 — O(1) Digital Root Formula (The Mathematical Way)Starting With ObservationBefore jumping to the formula, let us build the intuition from scratch the way a mathematician would — by looking at small cases and hunting for a pattern.Let us compute the result for every number from 0 to 27 manually:num → result0 → 01 → 12 → 23 → 34 → 45 → 56 → 67 → 78 → 89 → 910 → 1 (1+0)11 → 2 (1+1)12 → 3 (1+2)13 → 4 (1+3)14 → 5 (1+4)15 → 6 (1+5)16 → 7 (1+6)17 → 8 (1+7)18 → 9 (1+8)19 → 1 (1+9=10, then 1+0=1)20 → 2 (2+0)21 → 3 (2+1)22 → 4 (2+2)23 → 5 (2+3)24 → 6 (2+4)25 → 7 (2+5)26 → 8 (2+6)27 → 9 (2+7)The pattern is impossible to miss. After 0, the results cycle through 1, 2, 3, 4, 5, 6, 7, 8, 9 and then repeat, endlessly, with a period of exactly 9.Now the question is — why? Why does the digit sum cycle with period 9? To understand that, we need to talk about what happens to a number modulo 9.The Core Mathematical Property — Why Digits and Modulo 9 Are ConnectedHere is the fundamental theorem that powers this entire solution:Any positive integer is congruent to the sum of its digits modulo 9.In plain English: if you take a number, divide it by 9, and note the remainder — that remainder is the same as the remainder you get when you divide the sum of its digits by 9.Let us prove this properly so it actually makes sense rather than just being a thing you memorize.Take any two-digit number. You can write it as:num = 10a + bWhere a is the tens digit and b is the units digit. For example, 38 = 10(3) + 8.Now notice that 10 = 9 + 1, so:num = (9 + 1)a + b = 9a + a + bWhen you compute num % 9:num % 9 = (9a + a + b) % 9 = (9a % 9) + (a + b) % 9 = 0 + (a + b) % 9 = (a + b) % 9And a + b is exactly the digit sum. So num % 9 = digitSum % 9. They share the same remainder modulo 9.This same logic extends to three-digit numbers. Write num = 100a + 10b + c. Since 100 = 99 + 1 and 10 = 9 + 1:num = (99 + 1)a + (9 + 1)b + c = 99a + 9b + a + b + cWhen you take % 9, the 99a and 9b parts vanish because they are divisible by 9, and you are left with (a + b + c) % 9 — which is again just the digit sum modulo 9.This pattern holds for numbers of any length. Every power of 10 is just 1 more than a multiple of 9 — 10 = 9+1, 100 = 99+1, 1000 = 999+1 — so all the place-value multipliers disappear modulo 9, leaving only the digit sum behind.This is the reason the digit sum process produces the same final result as the original number modulo 9. The digit sum operation preserves the residue modulo 9 at every step.Why the Cycle Has Period 9Now that we know num ≡ digitSum (mod 9), the cycling pattern makes total sense.Every time you apply the digit sum operation, the result changes but the residue modulo 9 stays the same. You keep applying it until you hit a single digit. The single-digit numbers are 0 through 9. Among those, the residue modulo 9 of each single digit is just the digit itself — except 9, whose residue is 0.So the final single digit you land on is determined entirely by what num % 9 is:num % 9 == 0 → result is 9 (for any positive num)num % 9 == 1 → result is 1num % 9 == 2 → result is 2...num % 9 == 8 → result is 8The only exception is num = 0 itself, which is a genuine zero, not a nine.Translating This Into a FormulaIf we tried to write this directly as num % 9, there is one problem: multiples of 9 like 9, 18, 27 give a remainder of 0, but the correct answer for all of them is 9, not 0.We need a formula that maps every positive integer to a value in 1..9 cyclically, rather than 0..8.The standard trick for shifting a zero-indexed cycle to a one-indexed cycle is to subtract 1 before taking the modulo and add 1 after:result = 1 + (num - 1) % 9Let us verify this on a few cases:num = 9: 1 + (9-1) % 9 = 1 + 8 % 9 = 1 + 8 = 9 ✅num = 18: 1 + (18-1) % 9 = 1 + 17 % 9 = 1 + 8 = 9 ✅num = 1: 1 + (1-1) % 9 = 1 + 0 = 1 ✅num = 10: 1 + (10-1) % 9 = 1 + 9 % 9 = 1 + 0 = 1 ✅num = 38: 1 + (38-1) % 9 = 1 + 37 % 9 = 1 + 1 = 2 ✅The only number this formula does not cover is num = 0, which is a special case handled separately since 0 has no digit sum cycle — it simply returns 0.Connecting It Back to the ObservationNow look at the table we built earlier through the lens of this formula. Numbers 1 through 9 map to themselves. Then 10 gives 1 + 0 = 1, same as 1. Numbers 10 through 18 are just 1 through 9 offset by 9. Then 19 wraps back to 1. The cycle length of 9 follows directly from the modulo-9 arithmetic. It is not a coincidence at all — it is the inevitable consequence of how place-value and modular arithmetic interact.Codeclass Solution { public int addDigits(int num) { // Special case: 0 is not part of the 1-9 cycle, it simply returns 0 if (num == 0) return 0; // Digital root formula derived from the congruence property modulo 9. // (num - 1) % 9 maps the range to 0..8 instead of the raw 0..8 cycle // that would make multiples of 9 return 0 incorrectly. // Adding 1 at the end shifts it back to the correct 1..9 range. return 1 + (num - 1) % 9; }}ComplexityTime Complexity: O(1) — A fixed number of arithmetic operations regardless of the size of num.Space Complexity: O(1) — No variables, no data structures, nothing allocated.Approach ComparisonApproachTimeSpaceLoop / RecursionSimulationO(log n)O(1)YesDigital Root FormulaO(1)O(1)NoBoth approaches are entirely correct and both pass all test cases. The simulation is more readable and immediately obvious to anyone reading the code. The digital root formula is what an interviewer is hoping you know when they ask the follow-up — and more importantly, if you understand the modulo-9 proof above, you can derive it on the spot rather than hoping you remembered it.Key TakeawaysThe most important thing this problem teaches you is not the formula itself. It is the habit of asking a deeper question when you see a repeated process: is there a closed-form mathematical pattern hiding inside this repetition?The digit sum operation looks like pure computation at first glance. But underneath it is modular arithmetic, and modular arithmetic has structure that can often be collapsed into a direct formula. That same insight — that repeated digit operations connect to modulo 9 — shows up in divisibility rules you learned in school. A number is divisible by 9 if and only if its digit sum is divisible by 9. A number is divisible by 3 if and only if its digit sum is divisible by 3. Both of those rules are the exact same theorem we used to derive the digital root formula here.Once you internalize this connection between digit sums and modulo 9, you will recognize it surfacing in other problems across number theory, checksum algorithms, and competitive programming. The formula is a one-liner. The understanding behind it is something you carry with you permanently.

Digital RootLeetCode EasyJavaNumber TheoryMath