Math & Geometry crash course ↗ · 128

66. Plus One

A number is stored as an array of digits; add 1 to it. The key insight is handling carry propagation: scan right to left, increment if the digit is under 9, otherwise set it to 0 and continue. The only tricky case — all 9s — resolves in one line.

● EasyArray In-PlaceCarry PropagationMathTypeScript

PROBLEM What we're solving

Given a non-empty array of digits representing a non-negative integer — most-significant digit first, no leading zeros — return the array after adding 1. For example: [1, 2, 9] → [1, 3, 0] (the 9 carries into the 2). The tricky edge case: [9, 9, 9] → [1, 0, 0, 0] — the result has one more digit.

KEY IDEA Increment from the right; stop at the first non-9

Insight → adding 1 can only propagate carry through consecutive 9s at the tail. As soon as you hit a digit that is < 9, increment it and return — carry is absorbed. If all digits are 9, every digit becomes 0 and you prepend a 1. No integer conversion needed; work directly on the array.

RECIPE Right-to-left carry walk

  • 1 · Walk from the last digit backward. Start at index digits.length - 1 and move left; we add 1 to the least-significant position first, exactly as we would on paper.
  • 2 · If the current digit is less than 9, increment and return.Adding 1 produces no carry — we are done immediately. This short-circuit handles every "easy" case (no 9s at the tail) in O(1).
  • 3 · If the digit is 9, set it to 0 and continue left. A 9 + 1 = 10; write the 0 and carry the 1 to the next position. The loop propagates this carry automatically.
  • 4 · After the loop, prepend 1. Reaching here means every digit was 9. The array is now all zeros; return [1, ...digits] (spread into a new array).
Classic confusion → forgetting the all-9s case. After the loop the array is full of zeros — return digits would give the wrong answer. Always have the return [1, ...digits] guard after the loop, not inside it.

COST Complexity & alternatives

Convert to BigInt, add, convert back
O(n)
Correct but fragile — large inputs exceed safe integer range; relies on string conversions.
In-place carry walk
O(n)
O(n) worst case (all 9s), O(1) average; O(1) extra space.

Both are O(n) worst-case, but the in-place walk exits early and uses no extra space except in the all-9s edge case (where a new array is unavoidable). The BigInt path is rarely acceptable in interviews.

Pattern transfer → carry propagation appears in Add Binary (LC 67 — two bit strings), Add Strings (LC 415 — two numeric strings), Multiply Strings (LC 43 — digit-by-digit carry grid), and Add Two Numbers (LC 2 — carry on a linked list). The same right-to-left carry loop is the backbone of all of them.

RUN IT Add 1 from the right, carry left

step 0 / 3
STARTInput: [1, 2, 9]. We add 1 from the rightmost digit, propagating carry left.
1▶function plusOne(digits: number[]): number[] {
2▶  for (let i = digits.length - 1; i >= 0; i--) {
3    if (digits[i] < 9) {
4      digits[i]++;      // no carry — we're done
5      return digits;
6    }
7    digits[i] = 0;      // digit was 9: write 0, carry continues
8  }
9  // All digits were 9 (e.g. [9,9,9] → [1,0,0,0])
10  return [1, ...digits];
11}
digits102192
State
[1, 2, 9]
digits
1
carry
active digit / carry presentnewly written / prependedfinal answer
slowfast

TYPESCRIPT The solution, annotated

plusOne.ts
function plusOne(digits: number[]): number[] {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
      digits[i]++;      // no carry — we're done
      return digits;
    }
    digits[i] = 0;      // digit was 9: write 0, carry continues
  }
  // All digits were 9 (e.g. [9,9,9] → [1,0,0,0])
  return [1, ...digits];
}

Reading it block by block

Lines 2–6 — the main loop. We iterate from the last index down to 0. If the digit is < 9, a simple increment absorbs the carry and we return immediately — no further work needed. This is the common case.
Line 7 — handle the 9. A digit of 9 plus 1 yields 10; we write the 0 and let the loop carry the 1 leftward implicitly (the loop continues to the next iteration).
Line 10 — all-9s fallback. If we exit the loop without returning, every digit was set to 0 (e.g. [9,9,9] → [0,0,0]). Prepending a 1 gives the correct result [1,0,0,0]. The spread syntax creates a new array; mutating digits in-place is fine for the 0s but we need one extra slot.
Complexity → O(n) worst case when all digits are 9 (carry propagates the full length). O(1) average — the last digit is not a 9 most of the time and we return after one step. Extra space is O(1) except for the all-9s case, which allocates a new length-(n+1) array.

INTERVIEWFollow-ups they'll ask

  • "What if the array can have leading zeros?"Strip them first, or handle them in the carry loop (a leading 0 never causes a carry, so it's a no-op pass). The problem guarantees no leading zeros, so this is a good edge-case conversation.
  • "Can you do it without mutating the input?" Clone the array first with digits = [...digits] before the loop. Same O(n) time, O(n) space.
  • "Extend to adding an arbitrary integer k, not just 1?" Seed carry with k and change the loop to sum = digits[i] + carry; digits[i] = sum % 10; carry = Math.floor(sum / 10). This is exactly the Add Strings / Add Two Numbers pattern.
  • "What's the brute force?" Parse to BigInt, add 1, stringify, split. Works but is O(n) allocation-heavy and fails for very large arrays in JS without BigInt.
  • "Linked-list version?" Same carry logic, but you need to either reverse the list first or use a recursive call that unwinds — this leads directly to LC 2 Add Two Numbers.

MNEMONIC The one-liner

"Walk right to left: under 9 → bump and bail; 9 → zero it out and keep walking. Fall off the left? Stick a 1 on front."

TRIGGERS When you see ___ → reach for ___

"increment a number stored as digit array"right-to-left carry walk
a 9 in the ones (or tens, hundreds) placeset to 0, propagate carry
all digits are 9prepend 1 after the loop
"add two numbers / add binary"same carry loop, two sources

SKELETON The reusable shape

skeleton.ts
function plusOne(digits: number[]): number[] {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
      digits[i]++;
      return digits;
    }
    digits[i] = 0;
  }
  return [1, ...digits];
}

FLASHCARDS Tap to flip

What direction do we scan, and why?
Right to left — addition starts at the least-significant digit and carry flows toward the most-significant.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What does [1, 2, 9] return?
QUESTION 02
What does [9, 9, 9] return?
QUESTION 03
When does the loop exit early (before reaching index 0)?
QUESTION 04
Worst-case time complexity of the carry-walk approach?
QUESTION 05
Why is converting to BigInt then adding 1 considered a worse solution in an interview?
QUESTION 06
After the loop, why is return [1, ...digits] correct rather than digits.unshift(1); return digits?
QUESTION 07
Trace [2, 9, 9]: how many iterations does the loop execute?
QUESTION 08
#66 · Plus OneAdd one to the number represented as a digit array by propagating carry from the last digit forward. If carry survives past the first digit, prepend a 1 to the array.Which algorithmic approach does this primarily use?
QUESTION 09
#66 · Plus OneAdd one to the number represented as a digit array by propagating carry from the last digit forward. If carry survives past the first digit, prepend a 1 to the array.Which implementation correctly solves it?