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.

---

Visualizing Carry Propagation

Watch how adding 1 propagates through the array when encountering 9s:

+ 1

Carry: 1

Starting from rightmost digit...

---

Approach & Explanation

This problem simulates the process of adding 1 to a number represented as an array of digits.

Key Insight

The key challenge is handling carry propagation. When we add 1 to the last digit:

• If it’s not 9, simply increment and return.
• If it’s 9, it becomes 0 and we carry the 1 to the next digit.
• If all digits are 9, we need to create a new array with an extra digit.

Algorithm

1. Iterate from right to left (least significant to most significant digit)
2. If current digit is not 9: increment it and return immediately
3. If current digit is 9: set it to 0 and continue (carry the 1)
4. If we exit the loop (all digits were 9): create a new array with length n+1 and set the first digit to 1

Example Walkthrough

For [9, 9, 9]:

Step 1: digits[2] = 9 → set to 0, carry = 1 → [9,9,0]
Step 2: digits[1] = 9 → set to 0, carry = 1 → [9,0,0]
Step 3: digits[0] = 9 → set to 0, carry = 1 → [0,0,0]
Step 4: All 9s, create new array [1,0,0,0]

Complexity Analysis

• Time: O(n) - single pass through the array
• Space: O(1) - or O(n) if all digits are 9 (worst case)

---

Solution

Java

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;

        for(int i = n-1 ; i >= 0 ; i--) {
            if(digits[i] != 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }

        int[] ans = new int[n+1];
        ans[0] = 1;

        return ans;
    }
}

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
    }

    ans := make([]int, n + 1)
    ans[0] = 1

    return ans
}

---

Key Insight

This problem teaches the fundamental concept of carry propagation in digit arithmetic. The elegant solution avoids unnecessary work by returning early when no carry is needed, and efficiently handles the edge case where all digits are 9.