Plus One

Problem

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.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

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

Solution

Approach 1: Right to Left with Carry

The key insight is to process digits from right to left, handling carry propagation.

Implementation

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)

        # Start from the rightmost digit
        for i in range(n - 1, -1, -1):
            # If digit is less than 9, just increment and return
            if digits[i] < 9:
                digits[i] += 1
                return digits

            # If digit is 9, set it to 0 and continue (carry)
            digits[i] = 0

        # If we're here, all digits were 9 (e.g., [9,9,9])
        # Result is [1,0,0,0]
        return [1] + digits

Approach 2: Explicit Carry Tracking

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        carry = 1

        for i in range(len(digits) - 1, -1, -1):
            total = digits[i] + carry
            digits[i] = total % 10
            carry = total // 10

            if carry == 0:
                break

        if carry:
            return [1] + digits

        return digits

Approach 3: Reverse and Process

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # Reverse for easier processing
        digits = digits[::-1]
        carry = 1

        for i in range(len(digits)):
            if carry:
                if digits[i] == 9:
                    digits[i] = 0
                else:
                    digits[i] += 1
                    carry = 0

        if carry:
            digits.append(1)

        return digits[::-1]

Approach 4: One-Liner (Pythonic)

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # Convert to int, add 1, convert back to list
        return [int(d) for d in str(int(''.join(map(str, digits))) + 1)]

Complexity Analysis

Time Complexity: O(n), where n is the length of digits. In worst case (all 9s), we process all digits.
Space Complexity: O(1) if we don’t count the output array. O(n) if we need to prepend a 1 (all 9s case).

Key Insights

Carry Propagation: The main challenge is handling carries when digit is 9.
Early Exit: If we find a digit less than 9, we can increment and return immediately.
All Nines Case: When all digits are 9 (e.g., [9,9,9]), result is [1,0,0,0] - one digit longer.
No Need for Full Array: Only need to prepend [1] if all original digits were 9.
Right-to-Left Processing: Natural direction for addition with carry.
Simple Logic: Each digit either increments (if < 9) or becomes 0 with carry (if = 9).
Edge Cases: Single digit [9] becomes [1,0]; single digit [0-8] just increments.