Plus One — Carry Propagation in Arrays

Problem Statement#

Given a non-empty array of decimal digits representing a non-negative integer, increment the integer by one. The most significant digit is at the head of the array, and each element holds a single digit.

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• The number does not contain leading zeros except for the number 0 itself

Input:  digits = [1, 2, 3]
Output: [1, 2, 4]

Input:  digits = [9, 9, 9]
Output: [1, 0, 0, 0]

Why This Problem Matters#

Plus One looks trivial but is actually a careful array interview question that Google and Amazon use to filter candidates who do not handle edge cases. Add one to nine carries to the next digit. Add one to nine, nine, nine and the array grows.

This string FAANG warmup tests whether you can write loops that walk arrays from the end, manipulate carries, and conditionally allocate a new array. The same arithmetic pattern appears in Add Binary, Add Two Numbers, Multiply Strings, and Plus One Linked List.

The Core Insight#

Walk from the least significant digit, which is the last index. If the digit is less than nine, increment and return. If it is nine, set to zero and continue carrying. If we exit the loop, every digit was nine — prepend a leading one.

The clever optimization is that we never need a separate carry variable. Once we increment a digit successfully, we are done. Once we set to zero, the carry is implicit in the next iteration.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    def plusOne(self, 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

var plusOne = function(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i] += 1;
            return digits;
        }
        digits[i] = 0;
    }
    return [1, ...digits];
};

Time: O(n) — worst case all nines. Space: O(1) extra in normal case, O(n) when we prepend on overflow.

Common Mistakes#

• Converting the array to an integer, which fails for digits longer than 64 bits.
• Forgetting to prepend a leading one when every digit is nine.
• Using digits[i] equal to 9 plus 1 as a check; you should compare strictly less than 9.
• Iterating from index zero instead of the end, requiring a reverse later.

Interview Tips#

• Confirm whether the integer can exceed 64 bits, which forces array arithmetic.
• Walk the all-nines case explicitly before coding.
• Mention the early-return optimization to avoid scanning unchanged prefixes.
• Note this generalizes to plus k by tracking a carry variable.

Follow-up Questions#

• What if you must add k instead of one? Hint: maintain a carry variable.
• What about Add Binary? Hint: same pattern with mod 2.
• What if the integer is in a linked list? Hint: reverse, walk, reverse back.
• Multiply Strings? Hint: nested loops with carry into a result array.
• Subtract one? Hint: borrow propagates similarly.

Key Takeaways#

• LeetCode 66 is solved with a reverse walk and early return on non-nine digits.
• All-nines is the only case that grows the array; prepend a leading one.
• Time is O(n) worst case, O(1) extra space normally.
• Pattern generalizes to Add Binary and Add Two Numbers.
• Avoid converting to integer; arrays are needed for arbitrary precision.
• Walk from least significant to most significant digit.
• Common Google and Amazon array warmup question.