Plus One — Solution

Problem

You have a non-negative integer stored as an array of its individual digits, with the most significant digit first. Add one to the number and return the updated array. The array is guaranteed not to contain any leading zeros, except for the number zero itself.

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

A trickier case — when the last digit is 9, a carry must ripple leftward:

• Input: digits = [9, 9, 9]
• Output: [1, 0, 0, 0]
• Explanation: 999 + 1 = 1000, carry propagates through every digit

Intuition

The only subtlety is carry propagation: if the last digit is less than 9, just increment it and you're done. If it is 9, it becomes 0 and you push a carry left — repeat until you find a digit below 9 or you've exhausted the array. The only case that requires a longer output array is when every digit was 9, and in that case the answer is always 1 followed by all zeros.

Solution — Single Pass

Walk the array from right to left. At each position, if the digit is below 9, increment it and return immediately — the carry stops here. Otherwise set the digit to 0 and continue carrying. If the loop finishes, all digits were 9 and the number grew by one digit.

1. Iterate from the last index toward 0.
2. If the current digit is less than 9, increment it and return the array.
3. Set the current digit to 0 (the 9 becomes 0 and the carry moves left).
4. If the loop completes without returning, every digit was 9.
5. Return a new array of length n + 1 with a leading 1 and all remaining digits 0.

1def plusOne(digits: list[int]) -> list[int]:
2    for i in range(len(digits) - 1, -1, -1):
3        if digits[i] < 9:
4            digits[i] += 1
5            return digits
6        digits[i] = 0  # this 9 becomes 0 and the carry moves left
7    # every digit was 9, so the number grew by one digit (e.g. 999 → 1000)
8    return [1] + digits

Time: O(n) — in the worst case (all nines) we touch every digit once.

Space: O(1) amortized — we modify in place; the only O(n) allocation is the rare all-nines case where the output must be one element longer than the input.

Complexity Summary

Common Mistakes

• Stopping at the last digit only — incrementing digits[-1] by 1 works for most inputs but breaks entirely for inputs like [2, 9] or [9] where carry must propagate.
• Forgetting the all-nines case — when every digit was 9, the array length must grow by one. Returning digits after zeroing everything out gives the wrong answer ([0, 0, 0] instead of [1, 0, 0, 0]).
• Converting to an integer — int(''.join(map(str, digits))) + 1 looks clean but silently breaks on inputs with hundreds of digits, which exceed integer precision in most languages.
• Off-by-one in the loop — iterating while i > 0 misses index 0, so a leading 9 (e.g. [9, 0]) is never zeroed and the carry is lost.
• Using the wrong comparison — checking digits[i] == 9 works, but checking digits[i] < 9 to decide when to stop is cleaner and handles any non-nine digit without a separate branch.

Related Problems

• add-binary — the same carry-propagation logic applied to binary strings instead of decimal digit arrays
• add-two-numbers — carry propagation through two linked lists, digit by digit
• multiply-strings — more complex digit-by-digit arithmetic on large numbers represented as strings
• reverse-integer — another problem that works with individual digits of an integer under overflow constraints
• missing-number — similarly short array problem where a single numeric insight resolves the whole question