Plus One — Carry Propagation Done Right

The Problem

You are given a non-empty array digits representing a non-negative integer, where digits[0] is the most significant digit. Add one to the integer and return the resulting digit array. The integer has no leading zeros except the number 0 itself.

The challenge is the carry. If you add 1 to [1, 2, 9], the rightmost digit becomes 10, which doesn’t fit in a single slot. You have to propagate the carry leftward, possibly extending the array if every digit is 9.

Intuition

Walk the array from the back. If the current digit is less than 9, increment it and return immediately — no further carry can propagate. Otherwise set it to 0 and continue leftward. If you walk past index 0 with every slot now 0, the result has one more digit than the input: prepend a 1.

The early return is the optimization. It collapses the average case to O(1) because most inputs do not have a chain of trailing nines.

Explanation with Example

Take digits = [1, 2, 9]. Loop from i = 2.

• digits[2] = 9. Set to 0. Carry continues. Array: [1, 2, 0].
• digits[1] = 2 < 9. Set to 3. Return. Array: [1, 3, 0].

For digits = [9, 9, 9] the loop sets every slot to 0, falls through, and we return [1, 0, 0, 0].

step 1: digits[2]=9 -> set 0, carry on
      digits = [1,2,0]
step 2: digits[1]=2 -> 2 < 9, set to 3, return
      digits = [1,3,0]

Code

def plusOne(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return [1] + digits

public int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        digits[i] = 0;
    }
    int[] result = new int[digits.length + 1];
    result[0] = 1;
    return result;
}

vector<int> plusOne(vector<int>& digits) {
    for (int i = digits.size() - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        digits[i] = 0;
    }
    digits.insert(digits.begin(), 1);
    return digits;
}

Edge Cases

A single digit [0] returns [1]. A single digit [9] returns [1, 0]. An array of all nines extends in length by one. An array whose last digit is less than 9 returns after a single increment, never touching the rest.

There are no overflow concerns in Python; the algorithm only does single-digit arithmetic. In other languages, the same single-digit arithmetic still fits in a byte, so the algorithm is safe.

If the problem allowed leading zeros in input, you would have to skip them, but the spec rules that out.

Complexity Analysis

Time is O(n) in the worst case (all nines), but most inputs run in O(1) because the carry dies at the first non-nine digit. Amortized over random inputs the cost is constant.

Space is O(1) if we mutate in place and return the same list. The all-nines case allocates a new list of length n + 1, which is O(n) extra. That allocation is unavoidable since the result simply doesn’t fit in the original array.

How to Explain It in an Interview

Start with: “I’ll process digits from the back, propagating a carry. The carry stops the moment I find a digit less than 9, so I can return early. If every digit was 9, I prepend a 1 at the end.” Then write the code, run through [1, 2, 9] and [9, 9]. Mention the int-conversion shortcut as a Python-only trick that wouldn’t survive a code review in Java.

If the interviewer asks about “add two numbers represented as arrays” (Add Strings), point out the same carry-propagation pattern with two input pointers instead of one. Same idea, more bookkeeping.

Related Problems

• Add Binary — carry propagation with base 2.
• Add Strings — two big-integer arrays added.
• Plus One Linked List — same logic with a linked list.
• Add to Array-Form of Integer — adds an integer to a digit array.