LeetCode 66 - Plus One

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem gives us a non-empty array of digits that together represent a large integer. Each element in the array is a single decimal digit, and the digits are stored in left-to-right order from the most significant digit to the least significant digit.

For example:

[1,2,3] represents the number 123
[4,3,2,1] represents the number 4321
[9] represents the number 9

Our task is to add one to this integer and return the resulting digits as a new array representation.

The important detail is that the integer may be very large. The problem intentionally represents the number as an array instead of a standard integer type. In some languages, converting the array into an integer directly could overflow numeric limits for extremely large values. Even though the constraint here is only up to 100 digits, the intended solution is to manipulate the digits directly rather than relying on built-in big integer conversion.

The constraints tell us several useful things:

1 <= digits.length <= 100
The array is always non-empty.
The number can contain up to 100 digits, which is larger than many standard integer types can safely store.
0 <= digits[i] <= 9
Every element is guaranteed to be a valid decimal digit.
No leading zeros
Inputs like [0,1,2] will never appear.
The representation is always valid and normalized.

There are several important edge cases that can cause mistakes in naive implementations.

The first major edge case occurs when the last digit is not 9. In this situation, we can simply increment the final digit and stop immediately. For example, [1,2,3] becomes [1,2,4].

The second important edge case occurs when the number ends with one or more 9s. Adding one causes carry propagation. For example:

[1,2,9] becomes [1,3,0]
[1,9,9] becomes [2,0,0]

The most important edge case is when every digit is 9. In this situation, the number grows in length:

[9] becomes [1,0]
[9,9,9] becomes [1,0,0,0]

A correct solution must properly handle carry propagation across multiple digits and create a new leading digit when necessary.

Approaches

Brute Force Approach

A straightforward approach is to convert the digit array into an integer, add one, and then convert the result back into an array of digits.

For example:

Convert [1,2,3] into integer 123
Compute 123 + 1 = 124
Convert 124 back into [1,2,4]

This approach is conceptually simple and produces the correct answer because it directly simulates the arithmetic operation.

However, this method has important drawbacks. The represented number may become extremely large, potentially exceeding standard integer limits in many programming languages. Python supports arbitrary precision integers, but languages like Go do not natively support integers with 100 digits without special libraries.

Additionally, converting between representations introduces unnecessary overhead. The problem is specifically designed to encourage direct digit manipulation.

Optimal Approach

The better solution is to simulate elementary school addition directly on the digit array.

When adding one to a number:

Start from the least significant digit, the rightmost digit
If the digit is less than 9, increment it and stop
If the digit is 9, it becomes 0 and produces a carry into the next digit
Continue propagating the carry leftward until no carry remains
If all digits were 9, create a new array with leading 1

The key insight is that only the suffix of trailing 9s changes during the addition. Digits to the left remain unchanged once the carry stops.

For example:

[1,2,3]
Last digit becomes 4
Done immediately
[1,2,9]
9 becomes 0
Carry increments 2 to 3
[9,9,9]
Every digit becomes 0
Need a new leading 1

This solution avoids integer conversion entirely and works efficiently for arbitrarily large inputs.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Converts digits to integer and back
Optimal	O(n)	O(1) or O(n)	Direct digit manipulation with carry propagation

Algorithm Walkthrough

Start iterating from the last index of the array.

We begin from the least significant digit because addition proceeds from right to left. This mirrors how manual arithmetic works. 2. Check whether the current digit is less than 9.

If the digit is not 9, we can safely increment it by one without producing a carry.

Example:

[1,2,3]
Last digit 3 becomes 4
Result is [1,2,4]

At this point, the operation is complete, so we immediately return the array. 3. If the current digit is 9, set it to 0.

Adding one to 9 produces 10, which means:

Current position becomes 0
Carry moves to the next digit on the left

Example:

[1,2,9]
9 becomes 0
Carry continues leftward

Continue moving left while carries remain.

Every trailing 9 becomes 0 until we encounter a digit smaller than 9.

Example:

[1,9,9]
Rightmost 9 becomes 0
Next 9 becomes 0
1 becomes 2
Final result is [2,0,0]

Handle the all-9s case.

If the loop finishes without returning, then every digit was originally 9.

Example:

[9,9,9]
All digits become 0
We need an additional leading digit

Return:

[1,0,0,0]

Why it works

The algorithm works because decimal addition only affects digits involved in carry propagation. When a digit smaller than 9 is incremented, the carry stops immediately and all more significant digits remain unchanged. If a digit is 9, adding one forces it to become 0 and propagates the carry leftward. By processing digits from right to left, the algorithm exactly simulates standard base-10 addition, guaranteeing the correct result.

Python Solution

from typing import List

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # Traverse from right to left
        for index in range(len(digits) - 1, -1, -1):
            # If digit is less than 9, increment and return
            if digits[index] < 9:
                digits[index] += 1
                return digits

            # Otherwise, set current digit to 0 and continue carry
            digits[index] = 0

        # If all digits were 9, add leading 1
        return [1] + digits

The implementation follows the exact logic described in the algorithm walkthrough.

The loop starts at the last index and moves backward through the array. This direction is important because the least significant digit is the first place where addition occurs.

Inside the loop, the code checks whether the current digit is less than 9. If it is, we increment that digit and immediately return the updated array because no further carry propagation is needed.

If the digit equals 9, the digit becomes 0, and the carry continues to the next position on the left.

If the loop completes without returning, then every digit was originally 9. In that situation, the number increases in length, so we prepend a 1 to the modified array.

For example:

[9] becomes [0] during processing
Final return becomes [1,0]

This implementation is concise, efficient, and directly models arithmetic carry behavior.

Go Solution

func plusOne(digits []int) []int {
	for i := len(digits) - 1; i >= 0; i-- {
		// If digit is less than 9, increment and return
		if digits[i] < 9 {
			digits[i]++
			return digits
		}

		// Otherwise set current digit to 0
		digits[i] = 0
	}

	// All digits were 9
	result := make([]int, len(digits)+1)
	result[0] = 1

	return result
}

The Go implementation uses the same carry propagation logic as the Python version.

One notable difference is the handling of the all-9s case. In Python, we can simply return [1] + digits. In Go, slices cannot be concatenated that way, so we allocate a new slice with length len(digits) + 1.

The new slice is automatically initialized with zeros, so setting result[0] = 1 produces the desired output. For example:

Original: [9,9,9]
New slice: [1,0,0,0]

Go integers are easily sufficient because we never convert the entire number into a single integer value. We only manipulate individual digits.

Worked Examples

Example 1

Input:

digits = [1,2,3]

Step	Index	Current Digit	Action	Array State
Initial	-	-	Start traversal from right	[1,2,3]
1	2	3	Digit < 9, increment	[1,2,4]
Final	-	-	Return result	[1,2,4]

Final output:

[1,2,4]

Example 2

Input:

digits = [4,3,2,1]

Step	Index	Current Digit	Action	Array State
Initial	-	-	Start traversal from right	[4,3,2,1]
1	3	1	Digit < 9, increment	[4,3,2,2]
Final	-	-	Return result	[4,3,2,2]

Final output:

[4,3,2,2]

Example 3

Input:

digits = [9]

Step	Index	Current Digit	Action	Array State
Initial	-	-	Start traversal from right	[9]
1	0	9	Set to 0, carry continues	[0]
Final	-	-	Add leading 1	[1,0]

Final output:

[1,0]

Additional Example

Input:

digits = [1,9,9]

Step	Index	Current Digit	Action	Array State
Initial	-	-	Start traversal	[1,9,9]
1	2	9	Set to 0	[1,9,0]
2	1	9	Set to 0	[1,0,0]
3	0	1	Increment digit	[2,0,0]
Final	-	-	Return result	[2,0,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	In the worst case, every digit is processed once
Space	O(1) or O(n)	Usually in-place, but all-9 case requires a new array

The algorithm traverses the array from right to left at most once. Therefore, the running time is linear in the number of digits.

Most cases modify the input array directly and use constant extra space. However, when every digit is 9, we must allocate a new array with one additional digit. Because of this, the worst-case auxiliary space complexity is technically O(n).

Test Cases

from typing import List

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for index in range(len(digits) - 1, -1, -1):
            if digits[index] < 9:
                digits[index] += 1
                return digits

            digits[index] = 0

        return [1] + digits

solution = Solution()

assert solution.plusOne([1, 2, 3]) == [1, 2, 4]  # basic increment
assert solution.plusOne([4, 3, 2, 1]) == [4, 3, 2, 2]  # no carry propagation
assert solution.plusOne([9]) == [1, 0]  # single digit overflow
assert solution.plusOne([1, 2, 9]) == [1, 3, 0]  # single carry
assert solution.plusOne([1, 9, 9]) == [2, 0, 0]  # multiple carries
assert solution.plusOne([9, 9, 9]) == [1, 0, 0, 0]  # all digits are 9
assert solution.plusOne([0]) == [1]  # smallest valid number
assert solution.plusOne([8, 9, 9, 9]) == [9, 0, 0, 0]  # carry through suffix
assert solution.plusOne([2, 3, 4, 5]) == [2, 3, 4, 6]  # increment last digit only
assert solution.plusOne([9, 8, 9]) == [9, 9, 0]  # carry affects middle digit

Test	Why
`[1,2,3]`	Basic increment without carry
`[4,3,2,1]`	Standard non-overflow case
`[9]`	Single-digit overflow
`[1,2,9]`	Carry propagation through one digit
`[1,9,9]`	Carry propagation through multiple digits
`[9,9,9]`	Entire array overflows
`[0]`	Smallest possible valid input
`[8,9,9,9]`	Carry through long suffix of 9s
`[2,3,4,5]`	Last digit increment only
`[9,8,9]`	Carry affects middle position

Edge Cases

One important edge case occurs when the last digit is not 9. In this situation, the algorithm should stop immediately after incrementing the final digit. A buggy implementation might continue processing unnecessarily or accidentally modify earlier digits. The current implementation handles this correctly by returning immediately after incrementing a digit smaller than 9.

Another critical edge case occurs when the number ends with several consecutive 9s. Adding one causes carry propagation across multiple positions. For example, [1,9,9] must become [2,0,0]. Implementations that only handle a single carry would fail here. The loop-based carry propagation correctly processes every trailing 9.

The most significant edge case is when all digits are 9. In this case, the resulting number contains one extra digit. For example, [9,9,9] becomes [1,0,0,0]. Many incorrect solutions forget to expand the array length after all carries propagate. This implementation detects that situation when the loop completes without returning and creates a new array with a leading 1.

Another subtle edge case is a single-element array like [9] or [0]. Small arrays often expose indexing mistakes or off-by-one errors. Because the algorithm processes indices carefully from right to left and handles the all-9s case separately, these inputs work correctly.