Plus One (LeetCode 66)

The problem

A non-negative integer is stored as a list of its digits, most significant digit first, with no leading zeros (except the number 0 itself). Add one to the number and return the new digit list.

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

129 + 1 = 130: the last 9 rolls over to 0 and carries one into the 2.

How to think about it

Start with brute force. Join the digits into a string, convert to an integer, add one, and split it back into digits. In Python that works because integers never overflow. In Java or C++ a 100-digit array does not fit in any built-in type, so the interviewer will push you to work on the digits directly. The conversion also hides the one idea the question is testing.

The key insight: carrying only continues through 9s. Think about how you add one on paper. You touch the last digit. If it is less than 9, you bump it and you are done immediately; nothing to the left changes. If it is 9, it becomes 0 and the carry moves one place left. So the work is “turn trailing 9s into 0s, then bump the first non-9 digit”.

The only special case is all 9s. If every digit was 9 (999 → 1000), the loop turns them all into 0 and never finds a digit to bump. The answer is then a 1 followed by those zeros, so you prepend a 1.

Which pattern is this? Digit-by-digit arithmetic with a carry, from the math & geometry family. The tell is “a number stored as an array of digits”, which means “simulate the paper algorithm, don’t convert”.

Approach

1. Walk the indices from the last digit to the first.
2. If the current digit is less than 9, add one to it and return the list straight away.
3. Otherwise the digit is 9: set it to 0 and keep going left (the carry moves on).
4. If the loop finishes, every digit was 9 and is now 0. Return [1] + digits.

Solution

def plus_one(digits):
    for i in range(len(digits) - 1, -1, -1):   # least-significant digit first
        if digits[i] < 9:
            digits[i] += 1; return digits       # no carry left: done
        digits[i] = 0                           # 9 rolls over, carry continues
    return [1] + digits                         # all 9s: 999 -> 1000
# plus_one([1,2,9]) -> [1,3,0] ;  plus_one([9,9]) -> [1,0,0]

Dry run

On digits = [1, 2, 9]:

The loop stops at index 1, so index 0 is never touched. The answer is [1, 3, 0].

Complexity

• Time: O(n). In the worst case (all 9s) every digit is visited once. On average it is much faster, because the loop stops at the first digit below 9.
• Space: O(1) extra. The digits are updated in place. Only the all-9s case builds a new list of length n + 1, and that is the output itself.

Edge cases and pitfalls

• All 9s ([9], [9, 9, 9]) needs the extra leading 1. Forgetting the line after the loop is the most common bug.
• Single digit [0] gives [1]; [9] gives [1, 0].
• Don’t keep looping after the bump. Returning as soon as a digit is below 9 is both correct and what makes the average case fast.
• The input is mutated. If the caller needs the original list, copy it first.
• Converting to an int works in Python but misses the point and breaks in fixed-width languages; mention why you avoided it.

Related problems

• Add Two Numbers (LeetCode 2): the same carry logic, with two numbers stored as linked lists.
• Multiply Strings (LeetCode 43): digit-by-digit arithmetic again, with carries between positions.
• Reverse Integer (LeetCode 7): another digit-handling problem where overflow is the real question.