Search Blogs

Showing results for "Carry Handling"

Found 5 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

LeetCode 17: Letter Combinations of a Phone Number — Java Solution and Backtracking Explained

IntroductionHave you ever wondered how a phone number can represent multiple possible words? On a traditional telephone keypad, each digit from 2 to 9 is associated with three or four letters. For example, 2 represents a, b, and c, while 3 represents d, e, and f.Now imagine entering the digits "23". For every letter represented by 2, we can combine it with every letter represented by 3. This produces nine possible combinations, including "ad", "ae", "af", "bd", and "cf".This is the central idea behind LeetCode 17: Letter Combinations of a Phone Number. The challenge is to generate every possible combination without missing any valid result.In this article, we will explore a recursive Java solution, understand how the keypad mapping is built, and trace how the recursive calls generate the final list.Problem link: LeetCode 17 — Letter Combinations of a Phone NumberUnderstanding the ProblemYou are given a string digits containing numbers from 2 to 9. Each digit corresponds to a group of letters on a telephone keypad.Your task is to return all possible strings that can be formed by choosing exactly one letter for each digit.For example, if the input is "23":Digit 2 can contribute a, b, or c.Digit 3 can contribute d, e, or f.Each letter selected from the first group must be paired with every letter in the second group.The resulting combinations are:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]The order of the returned combinations does not matter.One important detail is that the digits 0 and 1 are not included in the input constraints because they do not map to letters in this problem.Approach: Recursion with Phone Keypad MappingThe key observation is that each digit represents a choice, and recursion explores every available choice at the current position.For example, when processing "23", we first select a letter from digit 2. After that, we move to digit 3 and try all its letters. Once we have selected one letter for each digit, we have completed a valid combination.Our solution uses three main components.1. Build the digit-to-letter mappingWe create a list of character lists called arr.Each position represents a digit, and the corresponding list contains its letters. For instance:arr.get(2) contains a, b, c.arr.get(3) contains d, e, f.arr.get(7) contains p, q, r, s.arr.get(9) contains w, x, y, z.We begin with two empty lists at indices 0 and 1, so the mapping for a digit can be accessed directly using its numeric value.The variable charnum starts at 97, the ASCII value of lowercase a. We convert consecutive numeric values into characters and advance the counter by three or four letters, depending on the digit.This lets us construct the entire keypad mapping programmatically rather than writing each group manually.2. Recursively build each combinationThe helper method sol() receives four parameters:arr: the phone keypad mapping.ind: the current position in the input string.dig: the original digit string.sb: the combination constructed so far, represented as a string.At each recursive call, we examine the current digit and iterate over its available letters.For every letter, we make another recursive call with that letter appended to the current combination. This continues until every digit has contributed one letter.3. Stop when a complete combination is formedThe base condition is:if (sb.length() == dig.length())When the constructed string has the same length as the input digit string, we have selected one letter for every digit. We add that combination to the result list and return from the current call.The recursive process then continues exploring the remaining choices.This is the essential stopping condition that prevents the recursion from continuing beyond the number of input digits.Java SolutionHere is the recursive solution, preserving your approach while making two small improvements:Use a StringBuilder when adding a letter instead of repeatedly creating intermediate strings.Handle an empty input and keep the result list local to the method, so repeated calls do not accidentally reuse results from a previous invocation.import java.util.ArrayList;import java.util.List;class Solution {public void sol(List<List<Character>> arr,int ind,String digits,StringBuilder sb,List<String> lis) {if (ind == digits.length()) {lis.add(sb.toString());return;}int digit = digits.charAt(ind) - '0';for (char ch : arr.get(digit)) {sb.append(ch);sol(arr, ind + 1, digits, sb, lis);sb.deleteCharAt(sb.length() - 1);}}public List<String> letterCombinations(String digits) {List<String> lis = new ArrayList<>();if (digits.isEmpty()) {return lis;}List<List<Character>> arr = new ArrayList<>();arr.add(new ArrayList<>());arr.add(new ArrayList<>());int charnum = 97;for (int i = 0; i < 8; i++) {List<Character> li = new ArrayList<>();int count = (i == 5 || i == 7) ? 4 : 3;for (int j = 0; j < count; j++) {li.add((char) (charnum + j));}arr.add(li);charnum += count;}sol(arr, 0, digits, new StringBuilder(), lis);return lis;}}Why use StringBuilder and remove the last character?Your original code uses sb + arr.get(...).get(i) to create a new string for each recursive call. This is valid Java, but repeated string concatenation creates additional string objects.The improved version modifies a single StringBuilder:append(ch) adds the chosen letter.The recursive call explores the combinations that begin with that letter.deleteCharAt(sb.length() - 1) removes the letter after returning, allowing the next letter to be tried.This pattern is called backtracking. We make a choice, explore its consequences, and undo the choice before exploring another branch.It is especially useful when generating permutations, combinations, subsets, and other possible arrangements.Dry Run: digits = "23"Let's trace the recursion to see exactly how the combinations are generated.Initially, the current string is empty, and the current index is 0.Current choiceNext digit choiceCombination producedadadaeaeafafbdbdbebebfbfcdcdcececfcfThe process follows this sequence:Select a from digit 2.Explore all choices from digit 3, producing ad, ae, and af.Return to the first digit and replace a with b.Explore digit 3 again, producing bd, be, and bf.Repeat with c, producing cd, ce, and cf.The final result contains nine combinations.Why nine? The first digit has three choices, and the second digit also has three choices. Therefore, the total number of combinations is 3 × 3 = 9.Complexity AnalysisLet n be the length of the input string, and let R be the total number of generated combinations.Every digit has either three or four possible letters. The maximum number of combinations is therefore 4^n.Time complexity: O(n × R)There are R complete combinations, each containing n characters. Constructing and storing all these strings requires O(n × R) total time. Since R can be as large as 4^n, the worst-case time complexity is O(n × 4^n).Auxiliary space complexity: O(n)The recursion depth is at most n, and the StringBuilder holds at most n characters. The keypad mapping contains a fixed number of letters, so its space usage is constant with respect to the input length.Output space: O(n × R)The result list stores R strings, each of length n. This output memory is separate from the auxiliary space used by the algorithm.Because the constraints limit the input to at most four digits, the number of generated combinations remains small.Common Mistakes to Avoid1. Forgetting to advance to the next digitEvery recursive call must process the next position. If the index is not incremented, recursion will keep processing the same digit.2. Using an incorrect base conditionThe recursion should stop after processing all digits. Checking whether the current string has the same length as the input works, but checking ind == digits.length() directly makes the relationship between the index and the stopping condition clearer.3. Forgetting to undo a choiceWhen using a shared StringBuilder, remember to remove the character after the recursive call. Otherwise, letters from one branch may incorrectly carry over into another.4. Reusing a result list across separate callsIn your original implementation, lis is a class-level field. If the same Solution instance is used for multiple calls, previous results can remain in the list. Creating the result list inside letterCombinations() avoids this issue.5. Ignoring empty inputThe provided constraints guarantee at least one digit, but returning an empty list for an empty input is a useful defensive behavior. It also avoids accidentally treating the empty string as a valid result.Interview Tip: Recognize the Backtracking PatternWhenever a problem asks you to generate every possible arrangement from several groups of choices, consider recursion or backtracking.A useful way to design the solution is to ask:What choices are available at the current position?What state should be passed to the next recursive call?When is a complete answer formed?What needs to be undone before exploring the next choice?For this problem, the choices are the letters associated with the current digit, the state is the current combination and digit index, and a complete answer is reached after processing all digits.The same reasoning can help with problems such as generating subsets, permutations, combination sums, and other recursive search problems.ConclusionLeetCode 17, Letter Combinations of a Phone Number, is a useful introduction to recursive backtracking in Java. The phone keypad gives us a set of choices for every digit, and recursion explores every possible sequence of those choices.The most important part is not the keypad mapping itself. It is learning how to explore one choice completely, return to the previous state, and then try the next choice without mixing results between branches.Once this pattern becomes familiar, many combination-generation problems become easier to approach and explain in coding interviews.Key takeaway: Build the keypad mapping, choose one letter per digit, stop when every digit has been processed, and backtrack to explore the remaining possibilities.

LeetCodeJavaBacktrackingRecursionStringArrayListDSAMediumCombination

LeetCode 3963: Create Grid With Exactly One Path — The Simple Java Trick I Almost Overlooked

The First Question I Asked Myself: Do We Really Need a Complicated Path?Problem link: LeetCode 3963 — Create Grid With Exactly One PathWhen I first looked at this problem, I saw a grid with two types of cells:. means we can move through the cell.# means the cell is blocked.We have to construct a grid in which exactly one valid path exists from the top-left corner to the bottom-right corner.My first instinct was to think about movement. We can move right or down, so I started wondering how to arrange the cells to control these movements.But then I realized something important: the problem doesn't ask us to find a path in a given grid. It asks us to create the grid ourselves.That changes the problem completely.We are not trapped inside a grid someone else has designed. We are the ones deciding which cells are free and which cells are blocked.So instead of asking, "How do I search for exactly one path?", I started asking a simpler question:What is the easiest possible path I can create, and how can I prevent every other path?That question leads to a much simpler solution.Step 1: Stop Thinking That We Must Alternate Right and DownSuppose we have a grid with three rows and four columns.We need to travel from the top-left cell to the bottom-right cell.A valid path can move right or down. But there is no rule saying we must alternate between these movements.We can move right three times and then down twice. We can also move down twice first and then right three times.Both movement patterns are allowed, provided the cells we enter are free.This was the observation that made the problem easier for me.Instead of creating a complicated zigzag path, why not move right along the first row and then down along the last column?For example, with m = 3 and n = 4, we can create this grid:...####.###.Let's trace the intended path:(0,0) → (0,1) → (0,2)↓(1,3)↓(2,3)The first row is free until the final column, and the last column is free all the way to the bottom.Every other cell is blocked.There is only one way to reach the destination: move right across the top row, then move down along the last column.We don't need recursion, DFS, BFS, or dynamic programming. We only need to construct a grid that forces the movement we want.Step 2: Why Does This Grid Have Exactly One Path?Let's look at the structure rather than just the example.Our grid has three important parts:The top row is free, allowing movement to the right.The last column is free, allowing movement downward.Every other cell is blocked.Consider the starting cell (0,0).Since moving down immediately would enter a blocked cell, the only possible move is right.The same reasoning applies as we continue along the top row. Moving down is blocked until we reach the last column.Once we reach the last column, moving right is impossible because we are already at the rightmost boundary. The only available movement is down.We keep moving down until we reach the bottom-right cell.Therefore, every step is forced. There is no point along the path where we can choose between two valid directions.If every step has only one possible next move, there can be only one valid path.This is the central idea behind the construction.Step 3: Translate the Idea Into JavaNow that the pattern is clear, the code becomes straightforward.We create an array of strings, where each string represents one row of the grid.For every cell, we ask two questions:Is this cell in the first row?Is this cell in the last column?If either condition is true, we place a .. Otherwise, we place a #.In other words:if (i == 0 || j == n - 1) {// Free cell} else {// Obstacle}This creates the top-row-and-last-column corridor.Notice that we do not need to calculate all possible paths or count them. The construction itself guarantees that there is exactly one.Java SolutionHere is the complete implementation using the same constructive approach:class Solution {public String[] createGrid(int m, int n) {String[] ans = new String[m];for (int i = 0; i < m; i++) {StringBuilder row = new StringBuilder();for (int j = 0; j < n; j++) {if (i == 0 || j == n - 1) {row.append('.');} else {row.append('#');}}ans[i] = row.toString();}return ans;}}What is different from my original code?My original solution already had the right core idea: create free cells along the first column and the bottom row, blocking the other cells.That approach is also valid. It creates a path that moves down first and then right.The revised implementation uses the alternative pattern discussed above: move right along the top row, then down along the last column.Both constructions work because they create one continuous corridor and block all competing routes.I also used StringBuilder instead of repeatedly concatenating strings with ro += "." or ro += "#". This makes row construction clearer and avoids repeatedly creating intermediate strings.Step 4: Dry RunLet's use the example m = 3, n = 3.Initially, we have three rows and three columns.For each cell, we check whether it belongs to the first row or the last column.Row 0Every cell is in the first row, so every cell becomes free....Row 1The first two cells are neither in the first row nor in the last column, so they become obstacles. The last cell is in the last column, so it remains free.##.Row 2The same rule applies.##.The final grid is:...##.##.The only valid path is:(0,0) → (0,1) → (0,2)↓(1,2)↓(2,2)The answer is a valid grid because the path starts at (0,0), ends at (m - 1, n - 1), and contains no alternative route.Step 5: What About a Grid With Only One Row or One Column?This is where I initially added special cases to my code.For example, if m = 1, the grid contains only one row. We can make every cell free:....There is exactly one path: keep moving right.If n = 1, the grid contains only one column. We can make every cell free vertically:....There is exactly one path: keep moving down.The useful discovery is that our new construction already handles both cases. When m = 1, the first-row condition makes every cell free. When n = 1, the last-column condition makes every cell free.That means we don't need separate if (m == 1) or if (n == 1) blocks.Removing unnecessary special cases makes the code shorter and easier to reason about.Complexity AnalysisLet m be the number of rows and n be the number of columns.Time complexity: O(m × n)We visit every cell exactly once and decide whether it should be a free cell or an obstacle.Space complexity: O(m × n)The returned grid contains m × n characters, so the output itself requires O(m × n) space. The temporary StringBuilder for constructing a row uses O(n) space.What I Learned From This ProblemThe biggest lesson was that I was thinking too much about finding paths instead of designing one.When I saw the words "exactly one valid path," I could easily have started thinking about graph algorithms, counting paths, or checking every possible route.But we control the grid. That means we can make every decision along the route for the person moving through it.The moment I realized that we could move right as many times as needed before moving down, the problem became much simpler. I could create a straight corridor and block everything else.My original solution used the same principle in the opposite direction: move down first, then right. Both ideas are correct.This is a useful lesson for constructive problems in general: before reaching for a complicated algorithm, ask whether you can build an answer whose structure makes the required property inevitable.Final TakeawayLeetCode 3963 is not really about searching a grid. It is about constructing one that forces a unique route.Choose a simple path.Keep the cells along that path free.Block cells that could create alternative routes.Check that the construction still works for a single row or column.Sometimes the best solution isn't to explore every possibility. It's to design the situation so that only one possibility exists.That is the intuition worth carrying into the next constructive algorithm problem.

LeetCodeJavaMatrixEasy