Plus One Solution Explained – Step-by-Step

Data Structures / Array

Plus One

Easy

You are given a large integer represented as an integer array digits, where each digits[i] is the i^th 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, except for the number 0 itself.

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

Example

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123. Incrementing by one gives 124.

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9. Incrementing by one gives 10.

Explanation

The key insight for solving this problem is understanding how carry propagation works when adding numbers. When we add 1 to a digit, two things can happen:

If the digit is less than 9, we simply add 1 and we're done
If the digit is exactly 9, it becomes 0 and we need to carry 1 to the next digit

We process the array from right to left (least significant digit to most significant) because that's how addition works with carry. When we encounter a 9, we set it to 0 and continue moving left. If we reach the beginning of the array and still have a carry, we need to insert a 1 at the beginning.

This approach works in-place - we modify the original array without creating a new one, making it very space-efficient.

Idea Map

Start

Start from last index
(rightmost digit)

While i >= 0:

If digits[i] < 9:
digits[i]++, return

Else (digits[i] == 9):
digits[i] = 0, i--

If we exit loop:
Insert 1 at beginning
[1] + digits

End

Complexity Analysis

Time Complexity

O(n) - In the worst case (all 9s), we traverse the entire array once. For cases without carry propagation to the front, it's much faster.

Space Complexity

O(1) - We modify the array in-place. Only when all digits are 9 do we create a new array, which is still O(n) output space.

Code


def plusOne(digits):
Initializes the function `plusOne` which takes an array of digits as input.
    n = len(digits) - 1
Gets the index of the last digit (rightmost position).
    while n >= 0:
Starts a loop from the last digit, moving left (right to left traversal).
        if digits[n] < 9:
Checks if the current digit is less than 9 (no carry needed).
            digits[n] += 1
If digit is less than 9, simply add 1 to it.
            return digits
Return the modified array immediately - we're done!
        digits[n] = 0
If digit is 9, set it to 0 and carry 1 to the next digit.
        n -= 1
Move to the next digit on the left.
    return [1] + digits
If we exited the loop, all digits were 9. Insert 1 at the beginning (e.g., 999 → 1000).


public int[] plusOne(int[] digits) {
Initializes the function `plusOne` which takes an integer array as input.
    int n = digits.length - 1;
Gets the index of the last element in the array.
    while (n >= 0) {
Starts a loop from the last index, moving towards the front.
        if (digits[n] < 9) {
Checks if the current digit is less than 9 (no carry needed).
            digits[n]++;
If digit is less than 9, simply increment it by 1.
            return digits;
Return the modified array immediately - no more carry needed.
        }
End of if statement.
        digits[n] = 0;
If digit is 9, set it to 0 (carry 1 to next position).
        n--;
Move to the previous digit (to the left).
    }
End of while loop.
    int[] result = new int[digits.length + 1];
All digits were 9, so we need a new array with one extra position.
    result[0] = 1;
Set the first digit to 1 (e.g., 999 → 1000, the rest are already 0).
    return result;
Return the new array with the extra digit.
}
End of the function.


vector<int> plusOne(vector<int>& digits) {
Initializes the function `plusOne` which takes a reference to a vector of integers.
    int n = digits.size() - 1;
Gets the index of the last element in the vector.
    while (n >= 0) {
Starts a loop from the last index, moving towards the front.
        if (digits[n] < 9) {
Checks if the current digit is less than 9 (no carry needed).
            digits[n]++;
If digit is less than 9, simply increment it by 1.
            return digits;
Return the modified vector immediately - no more carry needed.
        }
End of if statement.
        digits[n] = 0;
If digit is 9, set it to 0 (carry 1 to next position).
        n--;
Move to the previous digit (to the left).
    }
End of while loop - all digits were 9.
    digits.insert(digits.begin(), 1);
Insert 1 at the beginning of the vector (e.g., 999 → 1999 → 1000 after loop sets all to 0).
    return digits;
Return the modified vector with the new leading 1.
}
End of the function.

Edge Cases & Common Mistakes

⚠️

Forgetting the all-9s case

When all digits are 9 (e.g., 999), after the loop you need to insert 1 at the beginning. The loop sets all digits to 0, so the result is 1000.

💡

Converting to integer won't work for large numbers

Don't convert the array to an integer and add 1. The array can represent numbers much larger than integer limits (e.g., 64-bit overflow). Work with digits directly.

✓

Single digit input

The algorithm handles single-digit inputs correctly: [0] → [1], [9] → [1,0]. No special cases needed.

Understanding Array Manipulation

Array manipulation involves modifying elements in-place, handling carry propagation, and understanding how data is laid out sequentially in memory. This problem is a practical example of working with digit arrays and handling edge cases in numerical operations.

Learn more about array manipulation →

data_array

Disclaimer: This problem is for educational purposes. Practice the 'Plus One' problem on LeetCode.

AlgoExplained.dev