Plus One

Problem Statement

You are given an integer array digits, where each digits[i] is the ith digit of a large integer. It is ordered from most significant to least significant digit, and it will not contain any leading zero.

Return the digits of the given integer after incrementing it by one.

Example 1:

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

Output: [1,2,3,5]

Explanation 1234 + 1 = 1235.

Example 2:

Input: digits = [9,9,9]

Output: [1,0,0,0]

Constraints:

• 1 <= len(digits) <= 100
• 0 <= digits[i] <= 9

Recommended Time and Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the number of digits.

Hint 1

Consider what happens when the last digit is 9.

Hint 2

Think about how to handle the case where all digits are 9.

Solution

Iteration (Optimal)

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

    return [1] + digits

Time complexity: O(n) Space complexity: O(1)