Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Adding one changes only the rightmost digit unless that digit is nine. Every trailing nine becomes zero and passes a carry to its left. The first digit below nine absorbs the carry, leaving all earlier digits unchanged.

Approach

Traverse digits from right to left, incrementing the current digit.
If it is now below ten, return the modified array immediately: there is no remaining carry.
Otherwise, replace the digit with zero and continue left.
If the loop finishes, every original digit was nine. Return a new leading one followed by the zeroed array, as in 999 -> 1000. Working directly with digits also avoids converting the full number into a fixed-width integer.

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # sarr = map(str, digits)
        # n = int("".join(sarr)) + 1
        # narr = list(str(n))
        # return list(map(int, narr))
        n = len(digits)

        for i in range(n - 1, -1, -1):
            digits[i] += 1
            if digits[i] < 10:
                return digits
            digits[i] %= 10

        return [1] + digits

Complexity analysis

Let n be the number of digits. The carry can traverse all digits, so time is O(n). The algorithm uses O(1) auxiliary space while mutating digits; only the overflow case allocates an O(n) returned array.