NUHMAN.com

Introduction

LeetCode 66: Plus One is a simple yet common interview question. It involves incrementing a number represented by an array of digits, where the most significant digit is at the start. The challenge lies in handling carry-overs properly, especially when the digits contain trailing 9s.

This problem is a great example of array manipulation and understanding carry logic, similar to how you would do math by hand.

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.

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

Examples:

go

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

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

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

Constraints

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• The digits do not contain leading zeros, except for the number 0 itself.

Approach: Reverse Iteration with Carry Handling

We can treat this like regular addition:

1. Start from the last digit.
2. If it’s less than 9, simply add 1 and return the array.
3. If it’s 9, set it to 0 and continue the carry over to the next digit.
4. If all digits are 9 (e.g., [9,9,9]), we’ll need to add a new digit at the front ([1,0,0,0]).

Go Implementation

go

func plusOne(digits []int) []int {
    n := len(digits)

    for i := n - 1; i >= 0; i-- {
        if digits[i] < 9 {
            digits[i]++
            return digits
        }
        digits[i] = 0
    }

    // If we reach here, all digits were 9
    result := make([]int, n+1)
    result[0] = 1
    return result
}

Explanation

• The loop moves backward through the slice.
• If the current digit is less than 9, we can safely increment and return.
• If the digit is 9, it becomes 0 and we carry over to the next iteration.
• If all digits were 9 (like [9,9,9]), the result will be [1,0,0,0].

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n) (in worst case)

• Time is O(n) due to one backward traversal of the digits.
• Space is O(n+1) only when a new digit is added (e.g., all digits are 9).

Edge Cases

• [9] → [1,0]
• [9,9,9] → [1,0,0,0]
• [1,9,9] → [2,0,0]
• [0] → [1]

Conclusion

LeetCode 66 is a great warm-up question that’s often seen in interviews. It helps assess your understanding of how to manipulate arrays and carry values. It's also a good opportunity to write clean and efficient Go code for simple arithmetic logic.