Plus One LeetCode Solution: Carry Propagation Explained

Plus one leetcode (#66) is one of the first problems most people solve when learning array manipulation. The task sounds trivial — take a number represented as an array of digits and add one to it. But the moment you encounter an input like [9, 9, 9], you realize this problem is really about understanding carry propagation.

Carry propagation is the same digit-by-digit logic you used in grade school arithmetic. When a digit overflows past 9, you set it to 0 and carry 1 to the next position. This exact pattern appears in harder problems like Add Two Numbers (#2) and Add Binary (#67), making Plus One the perfect entry point.

In this walkthrough, you will learn the clean right-to-left approach that solves Plus One in O(n) time and O(1) extra space — plus how to handle the tricky edge case where every digit is 9.

You are given a non-empty array of digits representing a non-negative integer. The most significant digit is at the head of the array, and each element contains a single digit from 0 to 9. Your job is to increment the number by one and return the result as a new digit array.

For example, [1, 2, 3] represents the number 123. Adding one gives 124, so you return [1, 2, 4]. The straightforward case is simple — just bump the last digit. The challenge comes when adding one causes a cascade of carries.

Consider [9, 9, 9] which represents 999. Adding one gives 1000, but that requires four digits instead of three. Your output must be [1, 0, 0, 0]. The leetcode 66 solution must handle this array length change gracefully.

The key insight is that you do not need to convert the array to a number, add one, and convert back. That approach breaks for very large numbers that overflow integer limits. Instead, you simulate addition digit by digit, starting from the rightmost position — exactly how you would add on paper.

Start at the last index. Add 1 to that digit. If the result is less than 10, you are done — no carry needed, return the array immediately. If the result equals 10, set that digit to 0 and move one position left to add the carry. Repeat until either a digit absorbs the carry or you run out of digits.

If you process every digit and still have a carry, it means every digit was 9. The result has one more digit than the input, and it always looks like [1, 0, 0, ..., 0]. This is the only case where the output array is longer than the input.

The implementation is remarkably concise once you understand the pattern. You iterate from the last index to the first. At each position, check whether the digit is less than 9. If it is, increment it by one and return the array — no further processing needed. If the digit equals 9, set it to 0 and let the loop continue to carry the one.

If the loop completes without returning, every digit was 9 and every digit is now 0. You need to prepend a 1 to the front of the array. In most languages, you create a new array of length n+1, set the first element to 1, and return it (the rest are already 0).

This approach runs in O(n) time in the worst case where all digits are 9, but in practice it often returns after checking just one or two digits. The space complexity is O(1) extra space for the common case, or O(n) when you need to create a new longer array for the all-nines case.

Let us trace through two examples to see the plus one carry pattern in action. First, consider [1, 2, 3]. We start at index 2 where the digit is 3. Since 3 is less than 9, we increment it to 4 and return [1, 2, 4]. The function touches exactly one digit — no carry needed.

Now consider [9, 9, 9]. At index 2, the digit is 9 so we set it to 0 and continue. At index 1, the digit is 9 so we set it to 0 and continue. At index 0, the digit is 9 so we set it to 0 and continue. The loop ends without returning, so we prepend 1 to get [1, 0, 0, 0]. Every digit cascaded.

A middle-ground example is [1, 2, 9]. At index 2, digit is 9 — set to 0, continue. At index 1, digit is 2 — less than 9, increment to 3, return [1, 3, 0]. The carry propagated exactly one position before stopping. This demonstrates how the algorithm naturally handles partial carries.

Single digit inputs are worth testing explicitly. The input [9] should return [1, 0] — the simplest all-nines case. The input [0] should return [1] — just increment. And [5] should return [6] — straightforward, no carry.

Multi-digit inputs where only some trailing digits are 9 test partial carry propagation. The input [2, 9, 9] should return [3, 0, 0] — carry propagates through two positions before the 2 absorbs it. The input [8, 9, 9, 9] becomes [9, 0, 0, 0] — the carry reaches the leading digit without overflowing.

These edge cases confirm that the increment digit array approach handles every scenario: no carry, partial carry, and full carry with array expansion. Once you internalize this pattern, you can apply the same logic to Add Two Numbers (#2) where two linked lists carry simultaneously.

Plus One (#66) teaches the carry propagation pattern in its purest form. There is no second number to track, no linked list pointers to manage, and no base conversion to worry about. It is just one number, one increment, and a clean right-to-left sweep. This makes it the ideal starting point before you tackle Add Two Numbers (#2) or Add Binary (#67).

The plus one explained approach — iterate from right, handle the carry, expand if needed — is a template you will reuse across multiple LeetCode problems. In Add Two Numbers, you apply the same carry logic but process two linked lists simultaneously. In Add Binary, you do the same but in base 2 instead of base 10.

If you are building your pattern library for coding interviews, add Plus One to your array digit addition category in YeetCode. Review it alongside Two Sum and other array fundamentals. The carry propagation pattern is simple to learn, easy to forget, and guaranteed to appear in interviews — spaced repetition with YeetCode flashcards keeps it sharp.