Plus One LeetCode 66 — Complete Guide

LeetCode 66 Plus One gives you a large integer represented as an array of digits, where digits[0] is the most significant digit and digits[n-1] is the least significant digit. Your task: increment the integer by one and return the resulting digit array. The array never has leading zeros (except the number 0 itself, represented as [0]).

This is a straightforward simulation of how you add 1 by hand: start at the rightmost digit, add 1, and handle any carry that propagates left. The challenge is purely in the carry logic and the one edge case where carry propagates all the way past the leftmost digit — when every digit in the array is 9.

Despite its simplicity, Plus One tests your ability to simulate arithmetic correctly and handle boundary conditions cleanly. It is a foundational problem in the digit array family, alongside problems like Multiply Strings and Add Binary, and demonstrates that you can avoid integer overflow by operating digit by digit.

The overwhelmingly common case is that the last digit is not 9. When digits[n-1] < 9, simply increment it by 1 and return the array immediately. No carry occurs, no other digits change, and the array length stays the same. This single-line operation handles inputs like [1,2,3] → [1,2,4] and [9,8,7] → [9,8,8] without touching the rest of the array.

Even when the input has internal 9s — say [1,9,9] — the last digit rule still applies: if digits[n-1] < 9, return immediately. Only when the last digit is exactly 9 does carry become relevant. In practice, for random inputs, over 90% of increments terminate at the last digit, making this early-exit pattern both correct and performant.

The iteration strategy is to loop from the last index backward toward index 0, applying this logic at each position: if the current digit is less than 9, increment it and return. This backward loop naturally encodes the carry mechanic without any explicit carry variable — the loop itself is the carry propagation engine.

When the current digit is 9, adding 1 produces 10: the digit becomes 0 and a carry of 1 propagates to the next position to the left. Set digits[i] = 0 and continue the loop to the next iteration at index i-1. This precisely mirrors hand arithmetic: 9 + 1 = 10, write 0, carry 1.

Carry can chain through multiple consecutive 9s. Consider [1,2,9,9]: start at index 3 (digit 9), set to 0, carry left. Index 2 is also 9, set to 0, carry left. Index 1 is 2, which is less than 9 — increment to 3 and return [1,3,0,0]. The carry consumed both trailing 9s and absorbed into the first non-9 digit encountered.

The loop terminates as soon as it finds a digit less than 9. If the entire array is 9s, the loop runs through all indices setting each to 0, and exits the loop without ever returning early. That post-loop case is the all-9s edge case handled separately.

If the loop completes without triggering an early return, every digit in the array was 9. The loop has already set all of them to 0, leaving an array of all zeros. Now we need to prepend a 1 to represent the carry out of the most significant position. The result is [1, 0, 0, ..., 0] — one digit longer than the input.

For example, [9,9,9] + 1 = 1000. The loop sets all three digits to 0, yielding [0,0,0]. Then we prepend 1 to get [1,0,0,0]. Similarly [9] → [1,0], [9,9] → [1,0,0]. The new array always has exactly one more element than the input, and the first element is always 1.

This is the only case where the output array is longer than the input. All other inputs produce an array of the same length. In Python, the cleanest expression is [1] + digits (list concatenation). In Java, create a new int array of length digits.length + 1, set index 0 to 1, and leave the rest as 0 (default). Both are O(n) time and O(n) space.

For all inputs except the all-9s case, the algorithm modifies the input array in place and returns it. No new array allocation is needed; the output has the same length as the input. This is O(1) extra space. The early-return optimization in the simple case makes the common path extremely fast — one digit check, one increment, one return.

For the all-9s case, a new array of length n+1 must be created. You cannot extend the original array in place (at least not in Java/C++; Python lists are dynamic). In Python, [1] + digits is concise and idiomatic. In Java, int[] result = new int[digits.length + 1]; result[0] = 1; — the rest defaults to 0, which is correct since the loop already zeroed out digits (though we actually just need the new array since digits is now all zeros).

A common interview follow-up asks about space complexity. The answer is: O(1) extra space for the non-all-9s case (in-place modification), and O(n) for the all-9s case (new array). Since the all-9s case is the only one requiring new allocation, the amortized space cost is low — but worst-case space is O(n).

Python solution: def plusOne(digits): for i in range(len(digits) - 1, -1, -1): if digits[i] < 9: digits[i] += 1; return digits; digits[i] = 0; return [1] + digits. Eight lines including the function definition. The loop iterates from len-1 down to 0 (Python range with step -1). If a digit is less than 9, increment and return immediately. If 9, set to 0 and continue. After the loop, all digits are 0 — prepend 1.

Java solution: public int[] plusOne(int[] digits) { for (int i = digits.length - 1; i >= 0; i--) { if (digits[i] < 9) { digits[i]++; return digits; } digits[i] = 0; } int[] result = new int[digits.length + 1]; result[0] = 1; return result; } Identical logic — the loop condition i >= 0 mirrors Python's range down to 0. After the loop, allocate a new array of size n+1 and set the first element to 1.

Time complexity: O(n) worst case (all-9s input traverses the entire array). O(1) average case (terminates at the first non-9 from the right; for uniform random digits, expected position is near the end). Space complexity: O(1) for the non-all-9s case, O(n) for all-9s. Both Python and Java solutions are clean, readable, and handle all edge cases correctly.

Multiply Strings (LeetCode 43) extends the same digit-by-digit arithmetic to multiplication of two large numbers represented as strings. Instead of a single carry propagating left, you maintain a full result array and accumulate partial products. The inner loop structure mirrors Plus One's carry logic but applied across two operands.

Add Binary (LeetCode 67) is Plus One's closest relative: add two binary strings digit by digit from right to left, tracking carry. The only difference is the base (2 instead of 10) and that both operands are variable. Add to Array-Form of Integer (LeetCode 989) generalizes Plus One directly — add an arbitrary integer k to a digit array, propagating carry identically but for up to multiple carry steps.

Two Sum (LeetCode 1) and the broader math algorithms category share the digit array as a recurring data structure for representing large numbers without overflow. Mastering Plus One — especially the carry propagation pattern and the all-9s edge case — gives you the core intuition for the entire family. The backward iteration + early return + post-loop fallback is a reusable template across all digit array addition problems.