LeetCode #66. Plus One

Time Complexity: O(n)

• Best Case: O(1) - When the last digit is not 9 (e.g., [1,2,3] → [1,2,4])

We only check one digit and increment it

• Worst Case: O(n) - When all digits are 9 (e.g., [9,9,9] → [1,0,0,0])

We must iterate through all n digits to set them to 0

• Average Case: O(1) - Most numbers don't end in 9, so we typically only process one digit

Where n is the number of digits in the input array.

-

Space Complexity: O(1) or O(n)

• Best/Average Case: O(1) - When we can modify the input array in-place

No extra space needed except for variables

• Worst Case: O(n) - When all digits are 9

We create a new array of size n+1

-

class Solution {
    public int[] plusOne(int[] digits) {

        for (int i = digits.length -1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i] += 1;
                return digits;
            }
            digits[i] = 0;   
        }

        int[] newArray = new int[digits.length + 1];
        newArray[0] = 1;
        return newArray;
    }
}