Watch 10 video solutions for Plus One, a easy level problem involving Array, Math. This walkthrough by NeetCode has 78,420 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 in left-to-right order. The large integer does not contain any leading 0's.
Increment the large integer by one and return the resulting array of digits.
Example 1:
Input: digits = [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Incrementing by one gives 123 + 1 = 124. Thus, the result should be [1,2,4].
Example 2:
Input: digits = [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321. Incrementing by one gives 4321 + 1 = 4322. Thus, the result should be [4,3,2,2].
Example 3:
Input: digits = [9] Output: [1,0] Explanation: The array represents the integer 9. Incrementing by one gives 9 + 1 = 10. Thus, the result should be [1,0].
Constraints:
1 <= digits.length <= 1000 <= digits[i] <= 9digits does not contain any leading 0's.Problem Overview: You are given an integer array where each element represents a digit of a non‑negative number. The digits are stored from most significant to least significant. Add one to this number and return the updated array while handling carry correctly.
Approach 1: Iterative Backtracking (Carry Propagation) (Time: O(n), Space: O(1))
This approach processes the digits from right to left, exactly how manual addition works. Start from the last index and add 1. If the digit becomes 10, set it to 0 and propagate the carry to the previous digit. Continue moving left until a digit does not produce a carry. If all digits were 9, the array becomes all zeros and you allocate a new array with a leading 1 (for example [9,9,9] → [1,0,0,0]). The algorithm performs a single backward pass over the array, making it the optimal interview solution. It uses constant extra memory because operations are done in-place.
Approach 2: Convert Array to Number (Time: O(n), Space: O(n))
Another method converts the digit array into a numeric value, increments it, and converts the result back into digits. Iterate through the array, build the number using multiplication and addition, then add one. Finally split the number back into digits using repeated division or string conversion. While the logic is straightforward, it relies on large integer handling. For very large inputs the numeric value can exceed standard integer limits, making the approach less practical in languages without built-in big integers. This method still runs in linear time because each digit is processed a constant number of times, but it requires additional space for the reconstructed digits and depends on math conversions.
Recommended for interviews: Interviewers typically expect the carry-propagation solution. It demonstrates understanding of digit operations, in-place updates, and edge cases like trailing 9s or arrays consisting entirely of 9. The conversion approach shows conceptual correctness but is usually considered less robust because it depends on large integer support rather than direct digit manipulation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Backtracking (Carry Propagation) | O(n) | O(1) | Best general solution. Works in-place and handles large digit arrays efficiently. |
| Convert Array to Number | O(n) | O(n) | Useful when language supports big integers and simplicity matters more than memory usage. |