Problem Statement

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the number.
Add one to the integer and return the resulting array of digits.

Example:

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

---

Approach

1. Start from the last digit (the ones place).
2. Add 1 to that digit.
3. If it becomes 10, set it to 0 and carry 1 to the next digit.
4. Continue this until no carry remains.
5. If we exit the loop and still have a carry (e.g., [9,9,9]), insert 1 at the start.

---

Java Solution

public 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; // No carry, return result
            }
            digits[i] = 0; // Reset to 0, carry over
        }
        
        // If all digits were 9 (e.g., 999 -> 1000)
        int[] result = new int[n + 1];
        result[0] = 1;
        return result;
    }
}

---

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1) (O(n) if new array is created when carry overflows)

---

Dry Run

Input: [9, 9, 9]

Step-by-step:

i = 2 → digits[2] = 9 → becomes 0 → carry = 1
i = 1 → digits[1] = 9 → becomes 0 → carry = 1
i = 0 → digits[0] = 9 → becomes 0 → carry = 1

Now carry still remains after loop → create new array [1,0,0,0]

Output: [1, 0, 0, 0]