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 receive a non-empty array where each element represents a digit of a non‑negative integer. The digits are stored in order from most significant to least significant. The task is to add one to the integer and return the resulting array of digits without converting it into a built-in large integer type.
This problem mainly tests how you handle carry propagation in an array. When the last digit becomes 10 after adding one, the carry must move left across digits until a non‑9 digit is found or a new leading digit is created.
Approach 1: Iterative Backtracking Approach (Carry Propagation) (Time: O(n), Space: O(1))
This approach processes the digits from right to left, mimicking how addition works manually. Start at the last index and increment the digit. If the digit becomes less than 10, the operation is complete and the array can be returned immediately. When the digit becomes 10 (meaning the original value was 9), reset it to 0 and propagate the carry to the next digit on the left.
The key insight is that only trailing 9s require carry propagation. The moment a digit less than 9 is found, incrementing it resolves the entire operation. If the loop finishes and every digit was a 9 (for example [9,9,9]), create a new array with a leading 1 followed by zeros. This solution directly manipulates the array and avoids unnecessary conversions, making it the optimal approach for problems involving digit operations in math and array manipulation.
Approach 2: Convert Array to Number Approach (Time: O(n), Space: O(n))
This method first converts the array of digits into a numeric value or string representation, increments the number, and then converts the result back into an array of digits. In languages with arbitrary precision integers (like Python), this can be implemented in just a few lines.
The drawback is scalability. For very large arrays, converting the digits to a number may exceed integer limits in some languages or introduce unnecessary overhead. Additional memory is also required to rebuild the resulting array. While this approach works for small inputs and quick scripting tasks, it does not demonstrate control over digit-level operations.
Recommended for interviews: The iterative carry propagation approach is what interviewers expect. It demonstrates understanding of digit arithmetic, in-place array traversal, and edge cases such as sequences of trailing 9s. Mentioning the conversion approach shows awareness of simpler alternatives, but implementing the in-place carry logic proves stronger algorithmic thinking.
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.
C++
Java
C
C#
JavaScript
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.
Java
Time Complexity: O(n) for conversion
Space Complexity: O(n) for storing the string.
| 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 |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Backtracking (Carry Propagation) | O(n) | O(1) | Best for interviews and production logic where digits must be handled directly |
| Convert Array to Number | O(n) | O(n) | Quick scripting or languages with big integer support where input size is small |
Plus One - Leetcode 66 - Python • NeetCode • 62,651 views views
Watch 9 more video solutions →Practice Plus One with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor