Plus One: Handling Carry in Array Arithmetic

Plus One is LeetCode 66. You are given a large integer represented as an array of its digits, where digits[i] is the ith digit of the number. The digits are ordered from most significant to least significant (left to right). Increment the number by one and return the resulting array of digits.

Example: [1, 2, 3] becomes [1, 2, 4]. But [9, 9, 9] becomes [1, 0, 0, 0], because every digit overflows and a new leading 1 appears.

This problem looks trivial until you hit the carry case. When the last digit is not 9, you just add 1 and return. When it is 9, you need to propagate the carry left. And when every digit is 9, you need a longer array. The algorithm must handle all three cases cleanly.

The approach

The key insight is that you only ever add 1 to a number. That means the carry is always 0 or 1. You never need to handle arbitrary addition. This simplifies the logic significantly.

Walk the array from right to left:

1. If the current digit is 9, set it to 0 (it overflows) and continue to the next digit on the left. The carry propagates.
2. If the current digit is anything other than 9, increment it by 1 and return immediately. There is no further carry.
3. If you finish the loop without returning, every digit was 9. All of them are now 0. Prepend a 1 to the front of the array and return.

That is the entire algorithm. No separate carry variable needed, because the structure of the loop handles it implicitly. If you reach a non-9 digit, the carry dies there. If you exit the loop, the carry survived all the way through.

Visual walkthrough

Let's trace through two examples to see how carry propagation works in practice. First, [1, 2, 9] where the carry stops at the second digit. Then, [9, 9, 9] where the carry runs through every digit.

Notice the pattern: each 9 becomes a 0, and the carry moves left. The moment you hit a digit that is not 9, you increment it and stop. If every digit is 9, you exit the loop with all zeros and prepend a 1.

The solution

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

    return [1] + digits

Here is what each part does:

1. Right-to-left traversal. range(len(digits) - 1, -1, -1) iterates from the last index down to 0. This mirrors how you do addition by hand, starting from the ones place.
2. Carry on 9. If the digit is 9, setting it to 0 is equivalent to writing 10 % 10 = 0 and carrying the 1. You do not need a carry variable because continuing the loop is the carry.
3. Stop on non-9. If the digit is not 9, incrementing it absorbs the carry. You return immediately because no further changes are needed.
4. All 9s case. If the loop completes without returning, every digit was 9 and is now 0. The number grew by one digit, so you prepend 1. [1] + digits creates a new array [1, 0, 0, ..., 0].

Complexity analysis

Time: O(n) where n is the length of the digits array. In the worst case (all 9s), you visit every element once. In the best case (last digit is not 9), you visit only one element. But worst case is O(n).

Space: O(1) for the in-place modification. You do not allocate any extra data structures proportional to the input. The one exception is the all-9s case, where [1] + digits creates a new array of length n + 1. That makes the worst-case space O(n), but only in that single edge case.

The building blocks

This problem is built from one core building block:

Right-to-left carry propagation. Start at the rightmost digit and move left, propagating a carry until it is absorbed or you run out of digits. This is the same mechanic used in Add Two Numbers, Add Binary, and Multiply Strings. The difference here is simpler because you only add 1, so the carry is always exactly 1 until it stops.

This block shows up whenever you need to do arithmetic on numbers stored as arrays or strings. The direction is always right to left (least significant first), and the carry always propagates left until a digit can absorb it. Once you internalize this pattern, every "add one" or "add two numbers" problem becomes a variation of the same loop.

Edge cases

• No carry needed. [1, 2, 3] becomes [1, 2, 4]. The last digit is not 9, so you increment it and return on the first iteration.
• All 9s. [9, 9, 9] becomes [1, 0, 0, 0]. Every digit overflows, and you prepend a 1 at the front.
• Single digit 9. [9] becomes [1, 0]. A special case of the all-9s scenario with just one digit.
• Single digit, not 9. [5] becomes [6]. The simplest possible case, handled in one iteration.

From understanding to recall

This solution is short. Five lines of actual logic. But under time pressure, the details trip people up. Which direction does the loop go? What do you return after the loop? Is it [1] + digits or digits.insert(0, 1)?

The trick is that there is really only one thing to remember: walk right to left, turn 9s into 0s, and stop at the first non-9. If you exit the loop, prepend 1. That mental model is enough to reconstruct the code from scratch.

Spaced repetition locks it in. Type the solution from scratch today, again in a few days, again next week. After a handful of reps, the right-to-left carry pattern will be automatic, and it will transfer directly to harder problems like Add Two Numbers and Add Binary.

Related posts

• Add Two Numbers - The same carry propagation pattern applied to linked lists, where you add two multi-digit numbers digit by digit
• Reverse Integer - Another problem that manipulates individual digits of a number, building the result one digit at a time