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.
This approach involves checking from the last digit to the first and handling the carry manually. Start from the last digit and add one. If it results in 10, set that position to 0 and carry forward the 1 to the next significant digit. If any digit becomes less than 10 after addition, simply return the array as it is. If all digits end with a carry, insert an additional 1 at the beginning.
The Python function iterates over each digit from the back, checking and handling carry-forward. If the digit is less than 9, we increment it and return immediately. If it's 9, we turn it to 0 and continue. If all digits are 9, we handle it by adding a 1 at the front.
Time Complexity: O(n), where n is the length of the digits array.
Space Complexity: O(1), as we are modifying the digits array in place.
This approach involves converting the array of digits into a number, incrementing the number, and then converting it back into an array of digits. This is feasible due to built-in big integer support in several languages.
The function converts the digits to a string, then a number, increments it, and converts back to the digit list. Python's int handles big integers seamlessly.
Time Complexity: O(n) for conversion
Space Complexity: O(n) for storing the string.
We start traversing from the last element of the array, add one to the current element, and then take the modulus by 10. If the result is not 0, it means that there is no carry for the current element, and we can directly return the array. Otherwise, the current element is 0 and needs to be carried over. We continue to traverse the previous element and repeat the above operation. If we still haven't returned after traversing the array, it means that all elements in the array are 0, and we need to insert a 1 at the beginning of the array.
The time complexity is O(n), where n is the length of the array. Ignoring the space consumption of the answer, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Iterative Backtracking Approach | Time Complexity: O(n), where n is the length of the digits array. |
| Convert Array to Number Approach | Time Complexity: O(n) for conversion |
| Simulation | — |
| 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. |
Plus One - Leetcode 66 - Python • NeetCode • 78,420 views views
Watch 9 more video solutions →Practice Plus One with our built-in code editor and test cases.
Practice on FleetCode