63. Plus One

Add one at the least-significant digit and let the carry ripple left. Any digit below 9 absorbs the +1 and we're done; a 9 rolls over to 0 and passes the carry on. If every digit was 9, prepend a leading 1.

Idea

Adding one only ever affects a run of trailing 9s. Walking from the rightmost digit:

• If the digit is less than 9, incrementing it absorbs the whole +1. No further digit changes — return immediately.
• If the digit is 9, it becomes 0 and carries the +1 one place to the left.

If we fall off the left edge (the number was all 9s, like 999), the result grows by one digit: prepend a 1 in front of the now-all-zeros array (1000).

Algorithm

1. Loop i from the last index down to 0:
   • If digits[i] < 9: set digits[i] += 1 and return digits.
   • Else set digits[i] = 0 (carry continues).
2. If the loop finishes without returning, return [1] + digits.

Worked example: [1,2,9]

• i = 2: digit is 9 → set to 0, carry left. Array: [1,2,0].
• i = 1: digit is 2 < 9 → set to 3, return. Array: [1,3,0].

Result [1,3,0] = 129 + 1 = 130. ✓

Contrast [9,9]: both become 0, loop ends, prepend 1 → [1,0,0] = 100.

Complexity

• Time: O(n) worst case (all 9s).
• Space: O(1) extra (O(n) only in the all-9s case that grows the array).

class 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;
    }
}