#66 Plus One

frequently reported atIntuit Google Amazon Microsoft

the problem

In plain words

A large non-negative number is stored as an array of digits, most significant digit first, with no leading zeros. Add one to it and return the digits of the result.

in digits = [1,2,3]

out [1,2,4]

123 + 1 = 124.

in digits = [4,3,2,1]

out [4,3,2,2]

in digits = [9]

out [1,0]

9 + 1 = 10: the array grows.

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
No leading zeros

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternSimulation

Adding 1 only changes the trailing run of 9s (they become 0) and the digit just before it. If every digit is 9, the answer is 1 followed by zeros — one digit longer.

solutions

From brute force to optimal

Treat +1 as an addition that starts with carry = 1, collect digits in a list, reverse at the end.

carry = 1.
From the right: sum = digit + carry, keep sum % 10, carry = sum / 10.
Append a final carry, reverse, convert to int[].

timeO(n)

Visits every digit even when the carry dies at the first one.

spaceO(n)

A boxed List<Integer> copy of the number.

javajava.util.*

1class Solution {2    public int[] plusOne(int[] digits) {3        List<Integer> out = new ArrayList<>();4        int carry = 1;                                   // "+1" is just an addition that starts with carry = 15        for (int i = digits.length - 1; i >= 0; i--) {6            int sum = digits[i] + carry;7            out.add(sum % 10);8            carry = sum / 10;9        }10        if (carry > 0) out.add(carry);11        Collections.reverse(out);12        return out.stream().mapToInt(Integer::intValue).toArray();13    }14}

From the right, turn 9s into 0s; the first digit below 9 just increments and you return.

For i from n−1 down to 0: if digits[i] < 9, increment and return.
Otherwise set digits[i] = 0 and continue.
All 9s: return [1, 0, 0, …].

timeO(n)

Worst case is all 9s; usually it stops after one digit.

spaceO(1)

In place — except the all-9s case, where the answer itself needs n + 1 digits.

javajava.util.*

1class Solution {2    public int[] plusOne(int[] digits) {3        for (int i = digits.length - 1; i >= 0; i--) {4            if (digits[i] < 9) {5                digits[i]++;                             // no carry: we are done6                return digits;7            }8            digits[i] = 0;                               // 9 + 1 = 10: write 0, carry 1 to the left9        }10        int[] result = new int[digits.length + 1];       // only for 9, 99, 999, ...11        result[0] = 1;                                   // the rest are already 012        return result;13    }14}

in the room

How to say it in the interview

talk track

Say why you won't convert to a number: 100 digits is far beyond long.
Describe the two cases (digit < 9 → done; digit 9 → 0 and carry) before writing code.

traps

Converting the array to a long and back — it overflows after 18 digits.
Forgetting the all-9s case, which needs a longer array.

what they ask next

Follow-ups

Add two such digit arrays?

Same carry loop from the right over both arrays (that's Add Strings, LC 415, and Add Two Numbers on linked lists, LC 2).

before you submit

Edge cases to test

[9] and [9, 9, 9] grow by one digit
[0] → [1]
100 digits — far beyond a long, so never convert to a number

practise next