Plus One
Add one to a number stored as an array of digits: walk from the end, turn trailing 9s into 0s, and grow the array only when every digit was 9.
Problem Understanding
Plus One: a non-negative integer is given as an array digits, most significant digit first, with no leading zeros. Return the array for that integer plus one.
Examples: [1,2,3] returns [1,2,4], [4,3,2,1] returns [4,3,2,2], and [9] returns [1,0].
The Intuition: The Carry Stops at the First Digit Below 9
Adding 1 by hand only changes digits from the right until a digit can absorb it:
- A digit below 9 takes the
+1and nothing else changes, so you can return immediately. - A 9 becomes 0 and the 1 carries one place left.
- If the carry runs off the front, every digit was 9; the answer is a 1 followed by that many zeros.
It is Add Strings with the second number fixed at 1, so the loop can stop early instead of always walking the whole array. The same right-to-left carry drives Add Binary and Multiply Strings.
Interactive Walkthrough
i marks where the carry is. 9s that rolled over to 0 are tinted, and the digit that took the +1 turns green. Try All nines to see the array grow.
Dry Run Table
Input: digits = [8, 9, 9, 9]
| i | digits[i] | Action | digits after |
|---|---|---|---|
| 3 | 9 | set 0, carry | [8, 9, 9, 0] |
| 2 | 9 | set 0, carry | [8, 9, 0, 0] |
| 1 | 9 | set 0, carry | [8, 0, 0, 0] |
| 0 | 8 | 8 + 1 = 9, return | [9, 0, 0, 0] |
Answer: [9, 0, 0, 0].
The Solution Template
One loop from the right that returns as soon as a digit absorbs the carry. C always returns a newly allocated array, because LeetCode frees the result.
Plus One Code
1var plusOne = function(digits) {2 for (let i = digits.length - 1; i >= 0; i--) {3 if (digits[i] < 9) {4 digits[i]++;5 return digits;6 }7 digits[i] = 0;8 }9 return [1, ...digits];10};
Edge Cases & Common Mistakes
- All 9s:
[9, 9]becomes[1, 0, 0]; remember to grow the array. - Single digit:
[0]becomes[1], and[9]becomes[1, 0]. - Continuing after the +1: once a digit below 9 is incremented the answer is final; keep looping and you add 1 again.
- Converting to an integer: up to 100 digits overflow 64-bit types.
- Building the grown array: only the leading 1 is set; every other digit is already 0.
Summary
Walk from the last digit. A digit below 9 takes the +1 and you return; a 9 becomes 0 and the carry moves left. If every digit was 9, return a 1 followed by zeros. O(n) time, O(1) extra space except when the array grows.
More practice: DSA interview questions with answers · patterns cheat sheet