Plus One

Problem in Plain English

Add one to a non-negative integer stored as an array of its decimal digits, most significant first, and return the resulting digit array.

Problem Statement

You are given a large non-negative integer as an array digits, where each entry holds one decimal digit ordered from most significant to least significant. Add one to the integer and return the resulting array of digits.

The integer can be too long for any native number type, so the addition must happen digit by digit. A trailing run of 9 digits rolls over to 0 and carries left, and an input of all 9 digits grows the array by one ([9] becomes [1, 0]).

Constraints

$1 \le \text{digits.length} \le 100$
$0 \le \text{digits[i]} \le 9$
The representation has no leading zero except the single-digit value [0].

Examples

Example 1

Input: digits = [1, 2, 3]
Output: [1, 2, 4]

The array represents 123. Adding one gives 124, so only the final digit changes and the result is [1, 2, 4].

Example 2

Input: digits = [4, 3, 2, 1]
Output: [4, 3, 2, 2]

The array represents 4321. Adding one gives 4322; the final 1 absorbs the increment without carrying left.

Example 3

Input: digits = [9]
Output: [1, 0]

Adding one to 9 produces 10. The original digit rolls over to 0, and the carry becomes a new leading 1.

Example 4

Input: digits = [1, 2, 9, 9]
Output: [1, 3, 0, 0]

The units and tens digits each roll from 9 to 0. Their carry reaches the hundreds digit, increasing 2 to 3; the leading 1 stays unchanged.

Intuition

Start at the units digit, where adding one first acts. A digit below 9 absorbs the increment and leaves everything to its left unchanged. A 9 becomes 0 and sends one carry left; for [1, 2, 9, 9] that changes the last two digits to zeros and the 2 to 3. Example 1 has no trailing 9, so only its 3 changes to 4. If every digit rolls over, a new leading 1 is required.

Approaches

Convert and Add

Solution Details

Reveal Convert and Add: intuition, complexity, and code

Intuition

Encode all decimal digits as a string, parse it using an arbitrary-precision integer, add one, and decode the result. Unlike a native Java int or JavaScript Number, this preserves all 100 permitted digits. It leaves the input unchanged and always returns a new array, but the big-integer conversion hides more arithmetic and storage than the direct carry approach.

Step-by-Step Logic

Join digits left to right into a decimal string; Example 1 appends 1, 2, 3 to obtain "123".
Parse that string as an arbitrary-precision integer, then add one: Example 1 becomes 124.
Format the sum in decimal, allocate a fresh output array, and convert each decimal character to one digit. For "124", build [1], [1, 2], then [1, 2, 4].
Return the new array; the original Example 1 input remains [1, 2, 3].

Why It Works

Joining the digits in their original order gives exactly their decimal representation. An arbitrary-precision integer parses that representation without overflow or rounding, and adding one produces the required mathematical value. Its decimal output string lists that value from most significant to least significant digit; converting each character back to a digit therefore gives the required array, including an extra leading 1 when all digits were 9. None of the operations writes into the input array.

Dry Run

Convert and Add: variable states at each step
Stage	Text / number before	Operation	Text / number after	Output built
Join digit 1	empty text	append 1	"1"	-
Join digit 2	"1"	append 2	"12"	-
Join digit 3	"12"	append 3	"123"	-
Parse	"123"	arbitrary-precision parse	123	-
Increment	123	add 1	124	-
Format	124	decimal formatting	"124"	[]
Decode index 0	"124"	character 1 to digit 1	"124"	[1]
Decode index 1	"124"	character 2 to digit 2	"124"	[1, 2]
Decode index 2	"124"	character 4 to digit 4	"124"	[1, 2, 4]
Return	input still [1, 2, 3]	return fresh array	-	[1, 2, 4]

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Let n be the number of decimal digits. Joining and decoding are O(n), but converting between decimal strings and a binary big integer is not a constant-time operation. O(n^2) is a conservative schoolbook-arithmetic bound for parsing/formatting; runtimes may use faster algorithms. The big integer, intermediate strings, Java StringBuilder or Python map output, and fresh returned array each use O(n) storage, so auxiliary and output space are both O(n). With the fixed 100-digit cap these costs are bounded, but n describes the input-size comparison.

Code

Solution.java

1import java.math.BigInteger;2class Solution {3    public int[] plusOne(int[] digits) {4        StringBuilder sb = new StringBuilder();5        for (int d : digits) {6            sb.append(d);7        }8        // BigInteger preserves inputs longer than any primitive integer.9        String s = new BigInteger(sb.toString()).add(BigInteger.ONE).toString();10        int[] res = new int[s.length()];11        for (int i = 0; i < s.length(); i++) {12            res[i] = s.charAt(i) - '0';13        }14        return res;15    }16}

Hints

Hint 1

Add one on paper to 129: only the trailing 9 flips, then the 2 absorbs the carry.

Hint 2

Scan from the last digit leftward: turn each 9 into 0 and stop at the first digit below 9 by adding one to it.

Hint 3

If every digit was 9, nothing absorbed the carry, so the answer is 1 followed by all 0 digits in a new array.

Edge Cases

[0] increments to [1] and retains the original object in the carry approach.
A single 9 becomes [1, 0]; an all-9 array of length 100 becomes a leading 1 followed by 100 zeros.
A suffix of nines, as in [1, 2, 9, 9], rolls over only until the first earlier non-9 digit absorbs the carry.
The conversion approach always allocates a fresh result and leaves the input unchanged. The carry approach returns the mutated input except for all nines, when it returns a new array and leaves the original all zeros.

Common Mistakes and Interview Tips

Folding the digits into a 32-bit int or 64-bit long and adding one, which overflows once the input passes 10 or 19 digits.
Returning the original array unchanged after an all-9 input instead of allocating the longer [1, 0, ..., 0] result.
Continuing the scan after a digit below 9 absorbs the increment, flipping earlier digits that should stay fixed.
Using JavaScript Number for conversion silently rounds long integers; BigInt is required for the conversion approach.
Interview tip: state whether mutation is allowed. A caller needing the original array must copy it before using the carry approach, adding O(n) storage.

Key Takeaway

Digit-array arithmetic runs right to left so carries flow naturally, and the all-max-digit input always needs its own branch.