Plus One — Mastering Carry Propagation in Arrays (LeetCode 66)

Problem Statement

You are given a large integer represented as an integer array digits, where each digits[i] is the i-th digit of the integer. The digits are ordered from most significant to least significant (left to right). The large integer does not contain any leading zeros.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input:  digits = [1, 2, 3]
Output: [1, 2, 4]
Explanation: 123 + 1 = 124

Example 2:

Input:  digits = [4, 3, 2, 9]
Output: [4, 3, 3, 0]
Explanation: 4329 + 1 = 4330

Example 3 — The Tricky One:

Input:  digits = [9, 9, 9]
Output: [1, 0, 0, 0]
Explanation: 999 + 1 = 1000  ← array grows by one element

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits does not contain any leading zeros.

• Why This Problem Matters
• The Algorithm
• Why We Stop Early
• The All-9s Edge Case
• Visual Dry Run
• Case 1: [1, 2, 9]
• Case 2: [9, 9, 9]
• Common Mistakes
• Solutions
• Python
• JavaScript
• Complexity Analysis
• Follow-Up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

At first glance, Plus One seems almost insultingly simple. You might wonder why companies like Google and Amazon include it in their interview loops. The answer is not the algorithm — it is what the algorithm reveals about you as an engineer.

Carry propagation is everywhere. Adding numbers by hand, incrementing binary counters, implementing arbitrary-precision arithmetic, propagating signals in digital circuits — they all share the same cascading carry pattern. If you understand it deeply here, you recognize it instantly in harder problems like Add Binary (LC 67), Add Strings (LC 415), and Multiply Strings (LC 43).

The edge case is the whole point. Most inputs ([1,2,3], [4,5,6,7]) are trivially easy — you just bump the last digit and return. The interviewer is not watching to see if you can write that loop. They are watching to see if you spontaneously ask yourself: "What happens when every single digit is a 9?" Candidates who only handle the happy path write code that silently corrupts data in production. The all-9s case forces a result array one element larger than the input — and missing that is a real bug.

It signals clean code habits. A concise, correctly early-terminating solution tells the interviewer you understand why each line exists. The naïve approach (convert to integer, add one, split into digits) works for small inputs but breaks on 100-digit numbers that exceed 64-bit integer capacity. The in-place carry approach is both correct and efficient.

It is a warm-up that sets the tone. If you struggle here, the interviewer doubts your foundation. If you nail it quickly and explain your reasoning — including the all-9s case — you start the session with confidence and goodwill.

The Algorithm

The key insight: we are simulating elementary school addition from right to left. We only ever add 1 to the last digit, but if that digit was 9, it becomes 10, which means digit becomes 0 and carry moves left — and we repeat.

Step-by-step:

1. Walk the array from right to left (index n-1 down to 0).
2. Increment the current digit by 1.
3. If the result is less than 10 — no carry. Return immediately.
4. If the result equals 10 — set digit to 0, carry propagates left. Continue the loop.
5. If the loop finishes without returning — every digit was 9 and is now 0. Prepend a 1 to the array.

Algorithm sketch:

for i = n-1 down to 0:
    digits[i] += 1
    if digits[i] < 10:
        return digits       ← no carry, we're done
    digits[i] = 0           ← digit overflowed, carry continues

return [1] + digits         ← only reached if all digits were 9

The logic is clean because there is only one carry value: 1. We never add more than 1 to any digit, so the digit either stays below 10 (no carry) or becomes exactly 10 (set to 0, carry 1). The carry is implicit — we do not need a carry variable. The loop continuing is the carry.

Why We Stop Early

This is the elegance that separates a good solution from a great one.

When we increment a digit and get a result less than 10, no carry has been generated. The digit immediately to its left — and every digit further left — is completely unaffected. They stay exactly as they are. There is no reason to look at them.

So we return right there. Immediately. Without touching the rest of the array.

This means on the most common inputs — where only the last digit changes — our algorithm runs in O(1). We touch exactly one element. Even when the last few digits are 9s, we stop the moment we find a non-9. Only the pathological all-9s case requires visiting every element, giving us O(n) in the worst case.

This early-return pattern is not just an optimization — it is correct reasoning about what carry propagation means. If there is no carry, there is nothing left to do. An algorithm that keeps scanning anyway is doing unnecessary work and demonstrates a misunderstanding of the problem.

The All-9s Edge Case

This is the edge case that trips up most candidates who have not thought carefully.

Consider [9, 9, 9]:

• We visit index 2: digit 9 becomes 10, set to 0, continue.
• We visit index 1: digit 9 becomes 10, set to 0, continue.
• We visit index 0: digit 9 becomes 10, set to 0, continue.
• The loop ends. Every digit is now 0.

At this point, digits is [0, 0, 0]. We need to return [1, 0, 0, 0]. The result is one element longer than the input.

Why can we always just prepend a 1? Because the only way to exit the loop without returning is if every digit was 9 — meaning the input was 999...9 (n nines). And 999...9 + 1 = 1000...0 (1 followed by n zeros) — always. The array of zeros is already in digits. We just need to prepend 1.

In Python: return [1] + digits — creates a new list (O(n) space). In JavaScript: return [1, ...digits] — spreads into a new array (O(n) space).

This is the only case where we need O(n) extra space. In all other cases, the modification is in-place.

Visual Dry Run

Case 1: [1, 2, 9]

Initial state: [1, 2, 9]
               ^        ^
               0        i=2 (start here)

Step 1 — i=2:
  digits[2] = 9 + 1 = 10  → set to 0, continue carry
  State: [1, 2, 0]

Step 2 — i=1:
  digits[1] = 2 + 1 = 3   → 3 < 10, no carry!
  State: [1, 3, 0]
  RETURN [1, 3, 0]  ← done at i=1, never touched i=0

Result: [1, 3, 0] which represents 130 = 129 + 1. Correct.

Case 2: [9, 9, 9]

Initial state: [9, 9, 9]

Step 1 — i=2:
  digits[2] = 9 + 1 = 10  → set to 0, carry
  State: [9, 9, 0]

Step 2 — i=1:
  digits[1] = 9 + 1 = 10  → set to 0, carry
  State: [9, 0, 0]

Step 3 — i=0:
  digits[0] = 9 + 1 = 10  → set to 0, carry
  State: [0, 0, 0]

Loop exhausted — carry never resolved inside the array
Prepend 1: [1, 0, 0, 0]
RETURN [1, 0, 0, 0]

Result: [1, 0, 0, 0] which represents 1000 = 999 + 1. Correct.

Common Mistakes

Mistake 1 — Forgetting the all-9s case.

The most frequent bug. A candidate writes the loop correctly but then writes return digits after the loop, not realizing the loop only finishes when every digit has been zeroed out. The correct post-loop action is to prepend a 1. Test your solution against [9], [9,9], and [9,9,9] before claiming it is done.

Mistake 2 — Converting to integer and back.

# Do NOT do this:
def plusOne(digits):
    num = int("".join(map(str, digits)))
    return [int(d) for d in str(num + 1)]

This approach fails silently on large inputs. The problem states digits can have up to 100 elements — that is a number with 100 digits, which is astronomically larger than a 64-bit integer can hold. Python's arbitrary-precision integers happen to make this work in Python, but it is conceptually wrong, unmaintainable, and will fail in languages like Java, C++, or JavaScript where integer overflow is real. More importantly, it signals to the interviewer that you are pattern-matching rather than thinking about the problem. Do not do it.

Mistake 3 — Looping in the wrong direction.

Some candidates try to iterate from left to right, which breaks the carry model entirely. Carry propagates from least significant to most significant digit — right to left in our representation. Left-to-right traversal would require you to figure out where the carry starts before you begin, which is a harder problem. The right-to-left approach is natural: start where the change happens and follow the carry upstream until it dissipates.

Solutions

Python

from typing import List

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # Walk from the least significant digit (rightmost) to the most significant
        for i in range(len(digits) - 1, -1, -1):
            digits[i] += 1

            if digits[i] < 10:
                # No carry generated — everything to the left is unchanged
                # Return immediately without touching any other element
                return digits

            # digits[i] == 10: overflow. Set to 0 and let carry propagate left.
            digits[i] = 0

        # If we exit the loop, every digit was 9 and is now 0.
        # We need one more digit at the front. It's always 1.
        # Example: [9,9,9] → [0,0,0] → [1,0,0,0]
        return [1] + digits

JavaScript

/**
 * @param {number[]} digits
 * @return {number[]}
 */
function plusOne(digits) {
    // Start from the rightmost digit and work left
    for (let i = digits.length - 1; i >= 0; i--) {
        digits[i] += 1;

        if (digits[i] < 10) {
            // Digit incremented cleanly — no carry, stop here
            return digits;
        }

        // digits[i] === 10: set to 0 and carry 1 to the next position
        digits[i] = 0;
    }

    // All digits were 9. digits is now all zeros.
    // Prepend 1 to get [1, 0, 0, ..., 0]
    return [1, ...digits];
}

Complexity Analysis

The time complexity is O(n) in the worst case, but in practice the algorithm terminates very early for most inputs. The space complexity is O(1) for every case except all-9s, where we must allocate a new array of size n+1. There is no way to avoid this — the output is inherently one element larger than the input.

Follow-Up Questions

Once you solve Plus One cleanly, an interviewer may pivot to harder carry-propagation problems. Here is how they connect:

LC 67 — Add Binary (Medium) Given two binary strings, return their sum as a binary string. Same right-to-left carry model, but carry resets at 2 instead of 10. Use a pointer for each string and combine. Practice: simulate "1011" + "1101" by hand.

LC 415 — Add Strings (Medium) Given two non-negative integers as strings, add them without converting to integer. Identical to Add Binary but base 10. Uses two pointers walking right to left, accumulating carry. The output is built in reverse and flipped. This directly extends Plus One's pattern to two operands.

LC 43 — Multiply Strings (Medium) Given two numbers as strings, return their product as a string. Carry propagation still applies but now propagates from a 2D grid of partial products, not a single pass. Classic long multiplication. The carry can exceed 9, so you need carry = product // 10. Significantly harder, but you will recognize the DNA from Plus One.

All three problems reward candidates who understand why carry propagates — not just how to code it. Solve Plus One correctly and you have the foundation for all of them.

This Pattern Solves

The right-to-left carry propagation pattern you see in Plus One appears in:

• Arbitrary-precision arithmetic — adding, subtracting, multiplying integers stored as digit arrays or strings when they exceed native integer width.
• Binary counter increment — the same cascade applies in base 2; a ripple-carry adder in hardware is this exact algorithm in silicon.
• Date/time increment — adding one second that cascades through minutes, hours, days, months is structurally the same carry chain with non-uniform bases (60, 60, 24, 28-31, 12).
• Lexicographic enumeration — generating the "next" permutation or combination often involves a carry-like backward scan for the first position that can be incremented.
• Odometer simulation — rolling over rightmost digits with carry is the defining behavior of any odometer or counter.

Recognizing this pattern family means you never face a carry-propagation problem cold again.

Key Takeaway

Plus One is a deceptively simple problem whose value lies entirely in the all-9s edge case and the early-return optimization. A correct solution walks right to left, stops immediately when no carry is generated, and prepends a 1 only when every digit has overflowed — never allocating extra space otherwise. Master this and you have the intuition needed for a whole family of arithmetic simulation problems that appear regularly in technical interviews.