LeetCode 66: Plus One Solution in Python Explained

Problem Statement

LeetCode 66, Plus One, is an easy-level problem where you’re given an array of digits digits representing a non-negative integer. Your task is to increment the integer by 1 and return the resulting array of digits. The digits are stored in big-endian order (most significant digit first), and there are no leading zeros in the input (except for the number 0 itself).

Constraints

1 <= digits.length <= 100: Array length is between 1 and 100.
0 <= digits[i] <= 9: Each digit is between 0 and 9.

Example

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

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

Input: digits = [9,9]
Output: [1,0,0]
Explanation: 99 + 1 = 100, carry creates new digit.

Understanding the Problem

How do you solve LeetCode 66: Plus One in Python? For digits = [1,2,3], increment the number 123 to 124, returning [1,2,4]. We need to handle digit-by-digit addition, accounting for carries (e.g., 99 + 1 = 100). We’ll explore two approaches: an Iterative Reverse Addition Solution (optimal and primary) and an Alternative with String Conversion (intuitive but less efficient). The reverse addition method runs in O(n) time with O(1) space, modifying the array in-place when possible.

Solution 1: Iterative Reverse Addition Approach (Primary)

Explanation

Iterate from the least significant digit (right end) to the most significant digit (left end), adding 1 and propagating any carry. If a carry remains after processing all digits, prepend a 1 to the array. This mimics manual addition without converting to an integer.

Here’s a flow for [9,9]:

Start: [9,9] + 1
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]

Start from Right.

Begin at the last digit.

Add with Carry.

Add 1 to the last digit, track carry.

Propagate Carry.

Move left, update digits with carry.

Handle Final Carry.

Prepend 1 if carry remains.

Return Result.

Step-by-Step Example

Example 1: digits = [1,2,3]

We need [1,2,4].

Goal: Increment [1,2,3] by 1.
Result for Reference: [1,2,4].
Start: digits = [1,2,3], i = 2, carry = 1.
Step 1: i = 2.

sum = digits[2] + carry = 3 + 1 = 4.
digits[2] = 4, carry = 0.

Step 2: i = 1, carry = 0.

sum = 2 + 0 = 2, digits[1] = 2.

Step 3: i = 0, carry = 0.

sum = 1 + 0 = 1, digits[0] = 1.

Step 4: carry = 0, no prepend.
Finish: Return [1,2,4].

Example 2: digits = [9,9]

We need [1,0,0].

Start: i = 1, carry = 1.
Step 1: i = 1.

sum = 9 + 1 = 10, digits[1] = 0, carry = 1.

Step 2: i = 0.

sum = 9 + 1 = 10, digits[0] = 0, carry = 1.

Step 3: carry = 1, prepend 1.

digits = [1,0,0].

Finish: Return [1,0,0].

How the Code Works (Iterative Reverse Addition)

Here’s the Python code with line-by-line explanation:

def plusOne(digits: list[int]) -> list[int]:
    # Line 1: Start from right with carry
    carry = 1
    for i in range(len(digits) - 1, -1, -1):
        # Line 2: Add carry to current digit
        total = digits[i] + carry
        digits[i] = total % 10
        carry = total // 10
        # Line 3: Early exit if no carry
        if carry == 0:
            return digits

    # Line 4: Handle remaining carry
    if carry:
        digits.insert(0, 1)

    # Line 5: Return result
    return digits

Alternative: String Conversion Approach

Explanation

Convert the digit array to a string, parse it as an integer, increment it, and convert back to a digit array. This is simpler but less efficient due to string operations and potential integer overflow for very large numbers (though constraints ensure it fits).

Convert to String.

Join digits into a string.

Increment Integer.

Parse to int, add 1.

Convert Back.

Split integer back to digits.

Return Result.

Step-by-Step Example (Alternative)

For [9,9]:

Start: digits = [9,9].
Step 1: Convert to string.

num_str = "99".

Step 2: Parse and increment.

num = int("99") = 99, num += 1 = 100.

Step 3: Convert back.

str(100) = "100", digits = [1,0,0].

Finish: Return [1,0,0].

How the Code Works (String Conversion)

def plusOneString(digits: list[int]) -> list[int]:
    # Line 1: Convert array to string
    num_str = ''.join(map(str, digits))

    # Line 2: Convert to integer and increment
    num = int(num_str) + 1

    # Line 3: Convert back to digit array
    return [int(d) for d in str(num)]

Complexity

Iterative Reverse Addition:

Time: O(n) – Single pass through array.
Space: O(1) – Modify in-place, O(n) worst case with prepend.

String Conversion:

Time: O(n) – String operations and conversion.
Space: O(n) – Store string and new array.

Efficiency Notes

Iterative Reverse Addition is O(n) time and O(1) space (excluding rare prepend), optimal for LeetCode 66 as it avoids conversions. String Conversion is O(n) time and O(n) space, simpler but less efficient and riskier for larger numbers outside constraints.

Key Insights

Tips to master LeetCode 66:

Reverse Start: Begin at least significant digit.
Carry Handling: Propagate carry leftward.
In-Place: Minimize memory with direct updates.

Additional Example

For digits = [1,9]:

Goal: [2,0].
Reverse: 9+1=10, [1,0], 1+1=2, [2,0].
Result: [2,0].

Edge Cases

Single Digit: [5] – Return [6].
All 9s: [9,9,9] – Return [1,0,0,0].
Large \(k\): Not applicable (k=1), but large arrays handled.

Final Thoughts

The Iterative Reverse Addition solution is a clean win for LeetCode 66 in Python—fast, space-efficient, and true to digit manipulation. For a related challenge, try LeetCode 65: Valid Number to switch to string parsing! Ready to increment? Solve LeetCode 66 on LeetCode now and test it with [1,2,3] or [9,9] to master plus-one addition. Dive in and bump it up!