66. Plus One

Time: O(n)

Space: O(n)

Intuition

Simulate adding 1 from the rightmost digit. Carry propagates left. The only special case is all 9s (e.g., [9,9,9]) which becomes [1,0,0,0] - requiring a new leading digit.

Algorithm

1Traverse from the last index to 0.
2If digits[i] < 9: increment digits[i], return digits (no carry).
3Else set digits[i] = 0 (carry).
4If the loop completes (all 9s): create int[n+1] with [0]=1, rest 0. Return it.

Example Walkthrough

Input: [9,9,9]

1.i=2: 9->0, carry. i=1: 9->0, carry. i=0: 9->0, carry. Loop ends.
2.Return [1,0,0,0].

Output: [1,0,0,0]

Common Pitfalls

•Allocating a new array only for the all-9s case; otherwise modify in place.

66.cs

// Approach: Iterate from the last digit adding one with carry propagation.
// If all digits carry over, prepend 1 to a new array.
// Time: O(n) Space: O(n)

public 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[] ans = new int[digits.Length + 1];
        ans[0] = 1;
        return ans;
    }
}

Was this solution helpful?