22. Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant. Increment the large integer by one and return the resulting array of digits.

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents 123. 123 + 1 = 124.

Input: digits = [4,3,2,1]
Output: [4,3,2,2]

Input: digits = [9]
Output: [1,0]

Problem Breakdown:

1. Start from the last digit (rightmost) and work backwards, simulating manual addition with carry.

• for i in range(len(digits) - 1, -1, -1):

2. If the current digit is less than 9, simply increment it and return. No carry propagation needed.

•     if digits[i] < 9:
          digits[i] += 1
          return digits

3. If the current digit is 9, it becomes 0 (carry over). Continue to the next digit to the left.

•     digits[i] = 0

4. If we exit the loop, all digits were 9 (e.g., 999 becomes 1000). Prepend a 1.

• return [1] + digits

Summary:

Traverse digits from right to left. If a digit is less than 9, increment and return. If it is 9, set to 0 and continue (carry). If all digits are 9, prepend 1 to the array.

Time and Space Complexity:

Time Complexity: O(n) - worst case we traverse all digits.

Space Complexity: O(1) - we modify the array in place (O(n) only if all 9s require a new array).

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

JavaScript Solution:

var plusOne = function(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        digits[i] = 0;
    }
    digits.unshift(1);
    return digits;
};

Java Solution:

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