Problem Statement

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Additional information

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits does not contain any leading 0's.

Example 1:

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

Explanation: The array represents the integer 123. Incrementing by one gives 124, so the result is [1, 2, 4].

Example 2:

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

Explanation: The array represents the integer 129. Incrementing by one gives 130, so the result is [1, 3, 0].

Example 3:

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

Explanation: The array represents the integer 999. Incrementing by one gives 1000, so the result is [1, 0, 0, 0].

Reverse Iteration with Carry

Intuition

This problem is about simulating elementary school addition with a "carry" operation.

1. The Logic:
We need to add 1 to the last digit.

• Case A (No Carry): If the last digit is less than 9 (e.g., 123), we just increment it (124) and we are done.
• Case B (Carry): If the last digit is 9 (e.g., 129), adding 1 makes it 10. We set the current digit to 0 and "carry over" the 1 to the next digit to the left.
• Case C (All Nines): If all digits are 9 (e.g., 999), the loop finishes and we are left with [0, 0, 0]. We must manually insert a 1 at the beginning to get [1, 0, 0, 0].

2. The Iteration:
We loop through the array backwards (from the last index to the first).

Algorithm

Step 1: Start a loop from the last index (len(digits) - 1) down to 0.

Step 2: Check if the current digit is 9.

• If it is not 9: Increment it by 1 and return the array immediately. (We are done).
• If it is 9: Set the current digit to 0 and continue the loop (carrying the 1 to the next left position).

Step 3: If the loop finishes without returning, it means all digits were 9 (e.g., input was 99 and is now 00).

Step 4: Return a new array [1] concatenated with the current digits. (Result: [1, 0, 0]).

def plus_one(digits: list[int]) -> list[int]:
    n = len(digits)
    
    # Iterate backwards
    for i in range(n - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
        
    # If we are here, it means all digits were 9 (e.g., 999 -> 000)
    return [1] + digits

Time & Space Complexity

• Time Complexity: O(n). In the worst case (all 9s), we visit every digit.
• Space Complexity: O(1) generally, or O(n) in the worst case where we need to create a new array with an extra digit.