Plus One

1. Problem & Core Objective

A non-negative integer is given as an array of decimal digits, most significant first, with no leading zeros. Increment it by one and return the resulting digit array.

[1,2,3]      →  [1,2,4]
[4,3,2,1]    →  [4,3,2,2]
[9]          →  [1,0]
[9,9,9]      →  [1,0,0,0]

Constraints: 1 <= digits.length <= 100, 0 <= digits[i] <= 9, no leading zeros except for the single-element array [0].

What's actually being tested: noticing that the output can be longer than the input, and that this happens in exactly one case. The loop is four lines; the interview content is knowing that all-nines is the only input where the array must grow, and why.

2. First-Principles Thought Process

Why the array can't just be modified in place

Adding 1 to a decimal number changes only a suffix of its digits: everything after the last non-9 is unaffected, the last non-9 increments, and the trailing nines become zeros.

1 2 3       →  1 2 4        touch one digit
1 2 9       →  1 3 0        touch two
1 9 9       →  2 0 0        touch three
9 9 9       →  1 0 0 0      no non-9 exists — the number gains a digit

So the mutation is local except when there is no non-9 digit at all. That single exception is why the return type is a new array rather than void.

The loop follows directly

Walk from the right. The first digit below 9 can absorb the carry, so increment it and return immediately — everything to its left is untouched, and everything to its right has already been set to 0:

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

Falling out of the loop means every digit was 9, so the array is now all zeros and the answer is a leading 1 followed by those zeros.

The all-nines case has a shape worth noticing

int[] res = new int[digits.length + 1];
res[0] = 1;
return res;

new int[] is zero-filled, so only res[0] needs setting. That's not a golf trick — 10^k genuinely is a 1 followed by k zeros, and the zero-fill is the array expressing that.

This is also the only case that allocates. Every other input is handled in place with an early return, which is worth stating: the function is O(1) extra space on all but one input class.

Why this isn't just BigInteger

Converting to a number, adding 1, and converting back is O(n) too, but it allocates a String, a BigInteger, and another String. More importantly it hides the carry logic, which is the thing being asked about. It's the right production answer and the wrong interview answer — and it's exactly what I used as the reference implementation for testing.

3. Solution Paths

Approach 1 — Convert, add, convert back

public int[] plusOne(int[] digits) {
    StringBuilder sb = new StringBuilder();
    for (int d : digits) sb.append(d);
    String s = new BigInteger(sb.toString()).add(BigInteger.ONE).toString();
    int[] res = new int[s.length()];
    for (int i = 0; i < s.length(); i++) res[i] = s.charAt(i) - '0';
    return res;
}

• Time O(n) · Space O(n)

The reference the in-place version was checked against, on 20,000 random inputs.

Counter-questions on this approach

⭐ "Why BigInteger rather than long?"

Because the input can be 100 digits, and long tops out around 19. Using long would pass on small tests and silently wrap on anything longer — the kind of bug that survives casual testing.

int would fail at 10 digits. The constraint of 100 is there precisely to rule out both.

"What's wrong with it beyond the allocations?"

It answers a different question. The problem is asking about carry propagation on a digit array; this delegates that to a library and demonstrates nothing.

I'd write it in twenty seconds to fix the expected behaviour, say it's what I'd ship if the input were already a number, and then write the real one.

"Is s.charAt(i) - '0' safe?"

Yes for ASCII digits — '0' through '9' are contiguous in Unicode, so subtraction gives 0..9. It breaks for non-ASCII digit characters, which don't arise here.

Approach 2 — Carry propagation with early return (optimal)

public int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;
            return digits;                       // carry absorbed — everything left is untouched
        }
        digits[i] = 0;                           // 9 + 1 = 10: write 0, carry on
    }
    int[] res = new int[digits.length + 1];      // every digit was 9
    res[0] = 1;                                  // the rest are already 0
    return res;
}

• Time O(n) worst case, O(1) typically · Space O(1) except for all-nines

Counter-questions on this approach

⭐ "Why is the early return correct — don't you need to finish the loop?"

No. Once a digit below 9 has absorbed the carry, there is nothing left to propagate, and every digit to its left is unchanged by definition. The digits to its right were already set to 0 on the way in.

That's also why the typical case is O(1): only one in ten random numbers ends in 9, so the loop usually exits on the first iteration.

⭐ "When does the function allocate?"

Only when every digit is 9. Every other input is mutated in place and returned. So the space is O(1) for all but one input class, and O(n) for that one — worth stating precisely rather than as a flat O(n).

⭐ "Why is res[0] = 1 enough?"

new int[n+1] is zero-filled by the JVM, and all-nines plus one is 10^n — a 1 followed by n zeros. The default initialisation is the answer for every other position.

This is one of the few places where relying on Java's zero-fill is expressing the mathematics rather than saving typing.

"Does mutating the input matter?"

It's observable: the caller's array is modified even in the non-carrying case. LeetCode doesn't care, but in real code I'd clone first, or document it. Worth raising because the function sometimes returns the same object and sometimes a new one, which is an awkward contract either way.

"Can you do it without mutating and still in O(1) extra?"

No — producing a new array is O(n) by definition. The choice is between mutating the input and allocating always; the current version mutates and allocates only when it must.

"What about [0]?"

digits[0] = 0 < 9, so it increments to [1] and returns. The "no leading zeros except [0]" clause exists so that this single input is well defined, and it needs no special case.

Approach 3 — Explicit carry variable

public int[] plusOne(int[] digits) {
    int carry = 1;
    for (int i = digits.length - 1; i >= 0 && carry > 0; i--) {
        int sum = digits[i] + carry;
        digits[i] = sum % 10;
        carry = sum / 10;
    }
    if (carry == 0) return digits;
    int[] res = new int[digits.length + 1];
    res[0] = carry;
    System.arraycopy(digits, 0, res, 1, digits.length);
    return res;
}

• Time O(n) · Space O(1) except for the carry-out case

Counter-questions on this approach

⭐ "Why write it this way if it's longer?"

Because it generalises. Replace carry = 1 with the second operand's digits and it becomes full multi-digit addition; the % 10 and / 10 are the general carry rules rather than a +1 special case.

For this problem Approach 2 is tighter. For "add two digit arrays" this is the skeleton.

"The System.arraycopy looks redundant — the digits are all 0 anyway."

In the all-nines case, yes — digits is all zeros and the copy is copying zeros over zeros. It's there because this version doesn't know it only carries out from all-nines; it handles the general carry-out.

That's exactly the cost of the more general formulation, and worth naming rather than leaving as unexplained work.

"Is carry > 0 in the loop condition an optimisation or a requirement?"

An optimisation — without it the loop would run to the end doing sum = digits[i] + 0, which is harmless. It's what makes the typical case O(1) rather than O(n), matching Approach 2's early return.

4. Why the Optimal Solution Wins

O(n) worst case is a lower bound — all-nines forces every digit to change.

Write Approach 2. Lead with the observation that the array grows in exactly one case, because that's what decides the return type and it's the thing a wrong solution gets wrong.

5. Java Prerequisites

Arrays are zero-filled

int[] res = new int[n + 1];
res[0] = 1;                    // the remaining n entries are already 0 — which IS the answer

Right-to-left iteration

for (int i = digits.length - 1; i >= 0; i--)

System.arraycopy signature

System.arraycopy(src, srcPos, dest, destPos, length);
System.arraycopy(digits, 0, res, 1, digits.length);     // shift right by one

BigInteger for arbitrary precision

new BigInteger("999...9").add(BigInteger.ONE).toString();

long holds 19 digits, int holds 10, and the constraint here is 100 — so both primitives are out. That's the constraint doing deliberate work.

Char-to-digit conversion

s.charAt(i) - '0'          // 0..9
(char) (d + '0')           // back again

Returning the input array is legal and means the function sometimes returns its argument and sometimes a fresh object. Not a bug, but a contract worth stating.

6. Interview Communication Guide

Clarifying questions: Can the input have leading zeros (no, except [0] itself)? May I mutate the input array (I will unless you'd rather I didn't)? Can the input be empty (no, length ≥ 1)? Could the digits represent a negative number (no, non-negative)?

The pitch

"The thing that decides the shape of this function is that the output can be longer than the input — and that happens in exactly one case.

Adding 1 only changes a suffix: everything after the last non-9 digit becomes 0, the last non-9 increments, and everything to its left is untouched. So I walk from the right. The first digit below 9 absorbs the carry — increment it and return immediately, because nothing further can propagate. A 9 becomes 0 and I keep going.

If I fall out of the loop, every digit was a 9, the array is now all zeros, and the answer is 10^n — a 1 followed by n zeros. So I allocate n+1 entries, set the first to 1, and Java's zero-fill supplies the rest. That's not a shortcut; the zeros are the mathematics.

That's also the only input that allocates. Everything else is handled in place with an early return, so the typical case is O(1) time and space — only one in ten random numbers even ends in a 9.

One thing worth noting: the constraint of up to 100 digits is deliberate. long holds 19 and int holds 10, so converting to a number and back needs BigInteger — which works and is what I'd ship if the input arrived as a number, but it delegates exactly the carry logic being asked about.

And I'd mention that the function mutates its argument in the common case and returns a fresh array in the rare one. That's an awkward contract; I'd clone up front if the caller's array matters."

Edge cases to volunteer:

Lead with [9]. It's the smallest input that forces a longer output, and a solution that returns void or mutates in place is wrong on it and only on it.

7. Follow-Up Questions — Modified Constraints

⭐ "Add an arbitrary integer k instead of 1."

Same loop with carry = k: sum = digits[i] + carry; digits[i] = sum % 10; carry = sum / 10;. The carry can now exceed 1 and can propagate further, and the result may grow by several digits rather than one — so the new array's length is n + digits(carry).

The carry > 0 loop condition stops being a mere optimisation and becomes the termination condition.

⭐ "Add two digit arrays together."

Walk both from the right with a shared carry, padding the shorter with zeros. That's Approach 3's skeleton with a second operand — and it's Add Two Numbers in array form rather than linked-list form.

The list version is arguably easier, because lists are stored least-significant-first and need no reverse iteration.

"Subtract one instead."

The mirror: the first digit above 0 decrements, and trailing zeros become 9s. The interesting difference is that the result can shrink — [1,0,0] − 1 is [9,9], not [0,9,9] — so leading zeros must be stripped, and [0] − 1 is undefined for non-negative input.

Shrinking is fiddlier than growing, because "how many leading zeros to strip" is a scan rather than a single case.

"What if the digits were stored least-significant-first?"

Strictly easier: iterate forwards, and append to the end on carry-out instead of reallocating with a shift. That's why arbitrary-precision libraries store digits in that order.

"What if the base weren't 10?"

Replace 9 with base − 1 and % 10 / / 10 with % base / / base. Nothing structural changes, which is a good sign the solution is about carry rather than about decimal.

"What if the array were 10^8 digits and stored on disk?"

The early return does almost all the work — the expected number of digits touched is about 10/9, since a carry propagates past a digit only if it's a 9. So you'd read from the end and stop, touching a couple of bytes in the overwhelming majority of cases.

Only all-nines forces a full rewrite, and that's the one input where an in-place update is impossible anyway.

"How would you test it?"

Differentially against BigInteger on random digit arrays, with all-nines deliberately over-represented — I used one in five, across lengths 1 to 12, 20,000 cases. Uniform random inputs would produce an all-nines array roughly never, which is precisely the case that matters.