Plus One

Adding one looks trivial until the last digit is 9. Then the problem becomes a compact state-tracking exercise: start where arithmetic begins, propagate a carry through trailing 9s, and stop as soon as one digit absorbs it.

Read the Digit Representation

The input stores one decimal digit per array element:

[1, 2, 3] represents 123

The leftmost element is the most significant digit. The rightmost element is the least significant digit, so that is where ordinary addition begins.

The output must remain the same kind of representation: a left-to-right array of single decimal digits with no leading zero. The only allowed new leading digit is the intentional 1 created when the carry overflows the entire array:

[9] -> [1, 0]

Do not return the integer 10, and do not pad the result with unnecessary zeroes. Preserve the digit-array contract.

The scan direction follows directly from the representation. A carry can move left only after the digit to its right has been processed, so starting from the left would make the dependency backward.

The Short Answer: Scan Right to Left

For each digit from right to left:

1. If the digit is 9, replace it with 0 and continue.
2. If the digit is below 9, increment it and return immediately.
3. If the scan finishes, every digit was 9; prepend 1.

Examples:

[1, 2, 3] -> [1, 2, 4]
[1, 2, 9] -> [1, 3, 0]
[9, 9, 9] -> [1, 0, 0, 0]

The first input stops immediately. The second carries through one position. The third carries through the entire representation.

That is the complete Plus One solution. The important work is understanding why those branches are sufficient.

Why Direct Digit Manipulation Is the Right Baseline

A tempting approach is:

1. Convert the digit array into an integer.
2. Add one.
3. Convert the result back into digits.

In a language with arbitrary-precision integers, that may produce the right value. But it is still the wrong derivation for this question.

The input already exposes the representation we are expected to manipulate. Converting it away hides positional addition, hides carry propagation, and may violate the intended operation on a digit array. The interview signal is not merely “can the language store this number?” It is “can you operate directly on the representation?”

Paper arithmetic gives us the needed algorithm:

• A digit below 9 absorbs the carry and increases by one.
• A digit equal to 9 becomes 0 and passes the carry left.
• Digits farther left remain unchanged once the carry is absorbed.
• If every digit is 9, the carry needs a new leading position.

No second array, hashing, or general-purpose big-integer conversion is needed.

Model the Carry Precisely

Conceptually, the algorithm starts with a carry of 1 at the least significant position.

A useful refinement makes the implementation easier to understand:

Whenever the loop reaches an index, the unresolved carry is exactly 1. Reaching the next iteration means the previous digit was 9 and passed that carry left. Returning means the current digit absorbed it.

So the implementation does not need a separate carry variable. Control flow encodes the carry:

• The 9 branch writes 0 and continues, so the carry remains active.
• The non-9 branch increments the digit and returns, so the carry terminates.
• Falling out of the loop means the carry survived every digit.

This is a small but reusable state-tracking pattern: store only the state that changes the next decision. Here, the loop index tells us where we are, and reaching that index tells us that the carry is still active.

Derive the Carry Transition

Let the current digit be d.

When d is below 9

The local sum is a valid decimal digit:

7 + 1 = 8

Increment d, and the carry disappears. Because no carry moves farther left, the prefix remains unchanged. The entire result is now complete, so return immediately.

When d is 9

The local sum is 10:

9 + 1 = 10

One array element can store only one decimal digit. Write 0 at the current position and pass a carry of 1 to the next position on the left.

9 -> 0, carry continues left

The transition is therefore mechanical:

if current digit == 9:
    write 0
    continue left
else:
    increment current digit
    return

The algorithm has three obligations:

1. Write the correct final digit at the current position.
2. Continue left only when the current position cannot absorb the carry.
3. Preserve every digit left of the carry until the carry is resolved.

The code follows those obligations directly.

Correctness Invariant

Use this invariant:

Before processing index i, every position to the right of i already contains its final digit after adding one, and the only unresolved effect is a carry of 1 into position i.

The invariant holds before the first iteration. No positions have been processed, and the initial carry belongs at the rightmost digit.

Now examine each transition.

The current digit is below 9

Incrementing it produces the correct digit after receiving the carry. The carry disappears, and the digits to the left remain unchanged. The processed suffix is already correct by the invariant, so the entire array is correct and the function can return.

The current digit is 9

Adding one produces 10. Replacing the current digit with 0 records the correct local digit. Moving left leaves exactly one unresolved carry for the next position. The processed suffix remains correct, so the invariant continues to hold.

The loop finishes

If the function reaches the end without returning, every digit was 9. Each position has correctly become 0, but the carry still has nowhere to go inside the original array.

Prepending 1 completes the result:

[9, 9, 9] -> [1, 0, 0, 0]

The all-9s case is not a separate algorithm. It is the same carry process surviving the entire representation.

Correctness condition: return early when the carry is absorbed; add a new leading 1 only when the carry survives every position.

Dry Runs

Ordinary increment: [1, 2, 3]

The final digit is below 9:

3 -> 4

Return:

[1, 2, 4]

The carry ends immediately.

One trailing 9: [1, 2, 9]

The carry moves left once:

9 -> 0
2 -> 3

Return:

[1, 3, 0]

Only the trailing 9 and the digit immediately before it change.

Several trailing 9s: [1, 9, 9]

The carry travels through both trailing 9s:

9 -> 0
9 -> 0
1 -> 2

Result:

[2, 0, 0]

All digits are 9: [9, 9, 9]

Every position passes the carry left:

9 -> 0
9 -> 0
9 -> 0

The carry survives the entire array, so prepend 1:

[1, 0, 0, 0]

Zero: [0]

Zero needs no special case:

0 -> 1

Result:

[1]

The most common mistake is handling a trailing carry correctly but forgetting the carry that survives the whole array. Test [9] and [9, 9, 9], not only inputs such as [1, 2, 9].

Implement Plus One in Python

This explicit-branch version makes the carry visible:

def plus_one(digits: list[int]) -> list[int]:
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] == 9:
            digits[i] = 0
        else:
            digits[i] += 1
            return digits

    # The carry survived every position.
    return [1] + digits

The reverse range is:

range(len(digits) - 1, -1, -1)

It starts at the last valid index, stops before -1, and moves left by one each time.

The early return matters. Once a digit below 9 absorbs the carry, scanning farther left would do unnecessary work and could incorrectly modify the prefix.

For ordinary inputs, the function mutates the existing list. When every digit is 9, [1] + digits creates a new list with one additional element. Both results satisfy the output contract.

A compact equivalent uses the value 10 as the carry signal:

def plus_one(digits: list[int]) -> list[int]:
    for i in range(len(digits) - 1, -1, -1):
        digits[i] += 1

        if digits[i] < 10:
            return digits

        digits[i] = 0

    return [1] + digits

Both implementations have the same behavior. For learning and interviews, I prefer the first version because the 9-to-0 transition states the carry rule directly.

Complexity and Interview Checks

Let n be the number of digits.

Time complexity

The worst-case time complexity is O(n). An input such as [9, 9, 9] forces the scan through every position.

Inputs that end in a digit below 9 return early, but worst-case analysis must account for the carry traversing the entire array.

Space complexity

The scan uses O(1) auxiliary space. It needs only the loop index and temporary scalar values.

When all digits are 9, the result has n + 1 elements, so Python allocates a longer returned list. That output size is separate from the constant working space used by the algorithm.

Check these cases before submitting:

[1, 2, 3] -> [1, 2, 4]
[1, 2, 9] -> [1, 3, 0]
[1, 9, 9] -> [2, 0, 0]
[9]       -> [1, 0]
[9, 9, 9] -> [1, 0, 0, 0]
[0]       -> [1]

Verify that:

• Every output element is between 0 and 9.
• The output remains a digit array, not an integer.
• The prefix left of the carry is preserved.
• The function returns as soon as the carry disappears.
• No leading zero is introduced.
• An all-9s input receives exactly one new leading 1.

The transferable rule is simple: when arithmetic is stored as positional digits, start where arithmetic starts—the least significant position. Let the control path carry the unresolved state. Turn 9 into 0, stop when a digit absorbs the carry, and treat a carry that survives the entire representation as proof that the result needs one new leading digit.