Problem Description

The Plus One problem from Leetcode asks you to increment an integer represented as an array of digits by one and return the resulting array. Each element in the input array digits contains a single digit, and the most significant digit is at the head of the list. For example, [1,2,3] represents the integer 123. The array does not contain any leading zeros except for the number 0 itself.

• Input: An array digits of length n (1 ≤ n ≤ 100), where each element is a digit (0-9).
• Output: An array representing the integer digits + 1, with no leading zeros.
• There is always exactly one valid solution for each input.

Thought Process

At first glance, this problem seems simple: just add one to the last digit. However, if the last digit is a 9, adding one causes a carry, which must be handled by incrementing the previous digit. This process may ripple all the way to the first digit (e.g., [9,9,9] becomes [1,0,0,0]).

The brute-force approach would be to convert the array to an integer, add one, and split it back into digits. However, this approach is not ideal, especially for very large numbers that can't be stored in standard integer types. Instead, we can process the array in-place, starting from the least significant digit (the end of the array), and handle the carry as we go.

This is similar to how you would add numbers by hand, starting from the rightmost digit and carrying over as needed.

Solution Approach

Here is the step-by-step algorithm to solve the problem efficiently:

1. Start at the last digit of the array (the least significant digit).
2. Add 1 to this digit.
3. If the sum is less than 10, set the digit and return the array (no carry needed).
4. If the sum is 10, set the digit to 0 and carry over 1 to the next digit to the left.
5. Repeat steps 2-4 for each digit moving leftward.
6. If you finish processing all digits and still have a carry (e.g., all digits were 9), insert a 1 at the beginning of the array.

This approach is efficient because:

• It operates in-place (except for the case where a new digit must be added at the front).
• It only traverses the array once, from right to left.

Example Walkthrough

Let's walk through an example with digits = [2, 9, 9]:

1. Start from the last digit (index 2): it's 9. Add 1 → 10. Set this digit to 0, carry = 1.
2. Move to index 1: it's 9. Add carry (1) → 10. Set this digit to 0, carry = 1.
3. Move to index 0: it's 2. Add carry (1) → 3. Set this digit to 3, carry = 0.
4. No more digits and carry is 0, so the process ends.
5. The final result is [3, 0, 0].

Another example: digits = [9, 9, 9]:

• All digits become 0 due to carry, and at the end, we insert 1 at the beginning: [1, 0, 0, 0].

Time and Space Complexity

Brute-force approach:

• Converting digits to an integer and back is O(n) time, but may fail for very large numbers due to integer overflow.
• Space complexity is O(n) for the resulting array.

• Time Complexity: O(n), since in the worst case (all digits are 9), we process every digit once.
• Space Complexity: O(1) extra space, except for the case where we must add a new digit at the front (then O(n) for the result array).

The optimized approach is both efficient and safe against integer overflow.

Summary

The Plus One problem is a classic example of digit-wise arithmetic, requiring careful handling of carry operations. By working from the least significant digit and carrying over as needed, we can efficiently increment the number in-place without worrying about integer overflow. This approach is elegant, efficient, and demonstrates a practical use of array manipulation for arithmetic operations.

Code Implementation

class Solution:
    def plusOne(self, digits):
        n = len(digits)
        for i in range(n - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0
        # If we are here, all digits were 9
        return [1] + digits
      

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        digits.insert(digits.begin(), 1);
        return digits;
    }
};
      

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        int[] result = new int[n + 1];
        result[0] = 1;
        return result;
    }
}
      

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