LeetCode 66: Plus One - All Approaches Explained

Problem Statement

The Plus One problem, LeetCode 66, is an easy-difficulty challenge where you’re given a non-empty array of digits digits representing a non-negative integer. Each element is a single digit (0-9), and the most significant digit is at the start (no leading zeros except for the number 0 itself). Your task is to increment the integer by 1 and return the resulting array of digits.

Constraints

• 1 ≤ digits.length ≤ 100.
• 0 ≤ digits[i] ≤ 9.

Example

Copy codeInput: digits = [1,2,3]
Output: [1,2,4]
Explanation: 123 + 1 = 124.

Copy codeInput: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: 4321 + 1 = 4322.

Copy codeInput: digits = [9]
Output: [1,0]
Explanation: 9 + 1 = 10.

Copy codeInput: digits = [9,9]
Output: [1,0,0]
Explanation: 99 + 1 = 100.

Understanding the Problem

We need to increment a number represented as an array of digits by 1, handling carry-over when digits become 10. Key points:

• Start from the least significant digit (end of array).
• If a digit becomes 10, set it to 0 and carry 1 to the next digit.
• If carry propagates to the front, prepend a 1.
• The problem mimics basic arithmetic addition. Let’s explore two approaches:

1. Iterative Carry : Process digits with carry tracking.
2. Reverse Traversal : Simplified carry handling (best approach).

Approach 1: Iterative Carry

Intuition

Simulate addition by iterating from the end, adding 1 to the last digit, and propagating any carry to the left until no carry remains or a new digit is needed.

How It Works

• Start from the last digit, add 1.
• If result is 10, set digit to 0, carry = 1, move left.
• If result < 10, update digit and stop.
• If carry remains after the first digit, prepend 1.

Step-by-Step Example

For digits = [1,2,3]:

• i=2: 3 + 1 = 4 < 10, digits[2] = 4, stop.
• Result: [1,2,4].

For digits = [9,9]:

• i=1: 9 + 1 = 10, digits[1] = 0, carry = 1.
• i=0: 9 + 1 = 10, digits[0] = 0, carry = 1.
• Carry = 1: Prepend 1.
• Result: [1,0,0].
004aad

Python Code

Copy codedef plusOne_iterative(digits):
    n = len(digits)
    carry = 1
    
    for i in range(n-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

# Test cases
print(plusOne_iterative([1,2,3]))  # Output: [1,2,4]
print(plusOne_iterative([4,3,2,1]))  # Output: [4,3,2,2]
print(plusOne_iterative([9]))      # Output: [1,0]
print(plusOne_iterative([9,9]))    # Output: [1,0,0]

Detailed Walkthrough

• Carry : Tracks overflow (1 or 0).
• Modulo/Division : Extracts digit and carry.
• For [9]: Carry prepends 1, becomes [1,0].

Complexity

• Time Complexity : O(n). Single pass through digits.
• Space Complexity : O(1) or O(n) if prepending (output space).

Pros and Cons

• Pros : Mimics arithmetic, straightforward.
• Cons : Slightly verbose with carry check.

Approach 2: Reverse Traversal (Best Approach)

Intuition

Traverse the array from right to left, incrementing the first digit less than 9 and resetting subsequent 9s to 0, or prepending 1 if all digits are 9. This is the best approach because it’s concise, efficient, and interview-preferred.

How It Works

• Iterate from end to start.
• If digit < 9, increment and return.
• If digit = 9, set to 0 and continue.
• If all digits processed (all 9s), prepend 1.

Step-by-Step Example

For digits = [1,2,3]:

• 004aad i=2: 3 < 9, digits[2] = 4, return [1,2,4].

For digits = [9,9]:

• i=1: 9 = 9, digits[1] = 0.
• i=0: 9 = 9, digits[0] = 0.
• All processed: Prepend 1.
• Result: [1,0,0].

Python Code (Best Approach)

Copy codedef plusOne(digits):
    for i in range(len(digits)-1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    
    return [1] + digits

# Test cases
print(plusOne([1,2,3]))    # Output: [1,2,4]
print(plusOne([4,3,2,1]))  # Output: [4,3,2,2]
print(plusOne([9]))        # Output: [1,0]
print(plusOne([9,9]))      # Output: [1,0,0]

Detailed Walkthrough

• Early Return : Stops when no carry needed.
• All 9s : Falls through loop, prepends 1.
• For [4,3,2,1]: Increments 1 to 2, returns immediately.

Complexity

• Time Complexity : O(n). Single pass.
• Space Complexity : O(1) or O(n) if prepending (output space).

Why It’s the Best

• Simplest and most concise solution.
• Efficient with early termination.
• Interview-preferred for elegance.

Comparison of Approaches

Edge Cases to Consider

1. Single digit : [9] → [1,0].
2. All 9s : [9,9,9] → [1,0,0,0].
3. No carry : [1] → [2].
4. Max length : 100 digits, still fits constraints.

Final Thoughts

• Iterative Carry : Correct but slightly verbose.
• Reverse Traversal : The best approach —fast, simple, and optimal. Master this reverse traversal technique for its clarity and interview appeal. Try adding two numbers in array form as a follow-up challenge!