Plus One
Last Updated: March 28, 2026
Understanding the Problem
We have a number split across an array, one digit per slot, with the most significant digit at index 0. Our job is to add 1 to this number and return the updated array. Sounds simple, and for most cases it is: just bump the last digit by one.
But what happens when the last digit is 9? Adding 1 to 9 gives 10, which means we need to set that digit to 0 and carry 1 to the next position. And if that next position is also 9, we carry again. The tricky edge case is a number like 999: adding 1 gives 1000, which requires a longer array than the input.
So the real challenge here is handling the carry propagation correctly. The key observation is that we only need to keep carrying as long as the current digit is 9. The moment we hit a digit less than 9, we increment it, and we're done, no further changes needed.
Key Constraints:
1 <= digits.length <= 100→ The array can have up to 100 digits, representing a number far beyond what any primitive integer type can hold. This rules out converting to a number, adding 1, and converting back.0 <= digits[i] <= 9→ Each element is a single digit. After adding 1, any digit that reaches 10 must roll over to 0 with a carry.No leading zeroes→ The input is well-formed. But our output might need an extra leading digit (e.g., 999 becomes 1000).
Approach 1: Carry Simulation (Full Loop)
Intuition
The most natural way to think about this is to simulate grade-school addition. Start from the last digit, add 1 (or the carry), and propagate left. We maintain a carry variable and process every digit from right to left, just like you would on paper.
This approach processes every digit regardless of whether the carry has already been resolved. It's straightforward and easy to get right.
Algorithm
- Initialize
carry = 1(since we're adding one). - Loop from the last digit to the first.
- At each position, compute
sum = digits[i] + carry. - Set
digits[i] = sum % 10(the digit to keep). - Set
carry = sum / 10(the carry for the next position). - After the loop, if
carryis still 1, create a new array of sizen + 1, set the first element to 1, and return it.
Example Walkthrough
Code
- Time Complexity: O(n). We always iterate through all n digits, even if the carry resolves after the first step.
- Space Complexity: O(1) amortized, O(n) worst case. We modify the input in place. Only when all digits are 9 do we allocate a new array.
This approach works correctly but always processes every digit. What if we stopped the moment the carry resolved?
Approach 2: Early Return (Optimal)
Intuition
The carry can only ever be 0 or 1 in this problem (since the max single-digit sum is 9 + 1 = 10). The moment we add 1 to a digit that's less than 9, the result is at most 9, so there's no carry to propagate. We can return immediately.
This means we only need to keep going when the current digit is 9. In that case, it becomes 0 and we carry 1 to the next digit. If we make it through the entire array without returning, every digit was 9, and we need to create a new array starting with 1.
Algorithm
- Loop from the last digit to the first.
- If
digits[i] < 9, increment it by 1 and return the array immediately. - If
digits[i] == 9, set it to 0 and continue to the next digit (carry propagates). - If the loop finishes without returning, all digits were 9. Create a new array of size
n + 1, set the first element to 1, and return it.
Example Walkthrough
Code
- Time Complexity: O(n) worst case, O(1) best case. Worst case: all digits are 9, we process all n digits. Best case: the last digit is not 9, we return after one step.
- Space Complexity: O(1) amortized, O(n) worst case. We modify the input in place. Only when all digits are 9 do we allocate a new array.