Plus One

Problem

You are given a non-negative integer represented as a list of its decimal digits digits, most-significant digit first. The number has no leading zeros (except the number 0 itself, given as [0]). Add one to the number and return the resulting list of digits.

Examples

• digits = [1, 2, 3] → [1, 2, 4] — 123 + 1 = 124.
• digits = [4, 3, 9] → [4, 4, 0] — 439 + 1 = 440; the trailing 9 rolls over and carries.
• digits = [9, 9] → [1, 0, 0] — 99 + 1 = 100; the carry propagates off the front, growing the array.

Constraints

• 1 <= len(digits) <= 100
• 0 <= digits[i] <= 9
• digits has no leading zeros (aside from [0]).

Think about it first

TL;DR

Walk right-to-left, incrementing the first non-9 and zeroing the trailing 9s — O(n) time, O(1) extra space.

Approach 1 — Brute force (convert to an integer)

The obvious route: join the digits into an integer, add one, and split the result back into digits.

from typing import List


def plusOne(digits: List[int]) -> List[int]:
    num = int("".join(map(str, digits))) + 1
    return [int(c) for c in str(num)]

Complexity: O(n) time, O(n) space. It works, but it detours through string/int conversions and, in fixed-width-integer languages, would overflow for large inputs — the whole point of representing the number as digits is to avoid that.

Approach 2 — In-place carry from the right

The insight: adding one propagates a carry leftward only through consecutive trailing 9s. The first digit from the right that is less than 9 absorbs the carry — increment it and return immediately, since nothing to its right or left changes. If every digit is 9, they all become 0 and a single leading 1 is prepended.

from typing import List


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

Walkthrough with digits = [4, 3, 9]:

• i = 2: digits[2] = 9, not < 9, so set it to 0 → [4, 3, 0].
• i = 1: digits[1] = 3 < 9, so increment → [4, 4, 0] and return.

With digits = [9, 9]:

• i = 1: 9 → 0 → [9, 0].
• i = 0: 9 → 0 → [0, 0].
• Loop ends without returning, so prepend 1 → [1, 0, 0].

Complexity: O(n) time worst case (all nines), often O(1) when the last digit isn’t 9; O(1) extra space apart from the one new cell prepended in the all-nines case.

Common pitfalls

• Handling the all-nines case by mutating in place and forgetting to prepend the leading 1.
• Iterating left-to-right and trying to track a carry forward — right-to-left is far simpler because the carry naturally flows toward the most-significant end.
• Returning after zeroing a 9 instead of continuing the loop; you only return once you’ve found a digit to increment.

Pattern takeaway

Grade-school addition on a digit array runs right-to-left with a carry. Recognize that “+1” is the cheapest form of this: it stops at the first non-9 digit, and only the all-nines input changes the array’s length. Working on the digit list directly avoids any integer-overflow concerns.