#66

Easy

LeetCode Problem Workspace

Plus One

Given a number as an array of digits, increment it by one and return the updated array of digits.

Problem Statement

You are given an array digits representing a large integer. The array contains digits of the number from most significant to least significant in left-to-right order. The integer does not contain leading zeros.

Your task is to increment the number by one and return the resulting array of digits. Handle any carry-over during the addition.

Examples

Example 1

Input: digits = [1,2,3]

Output: [1,2,4]

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]

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]

The array represents the integer 9. Incrementing by one gives 9 + 1 = 10. Thus, the result should be [1,0].

Constraints

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0's.

Solution Approach

Iterative Approach

Starting from the least significant digit, add one to it and check for any carry. If there is a carry, propagate it to the next digit until no carry is left. If the most significant digit has a carry, add a new digit at the beginning of the array.

In-place Modification

Modify the array in-place by updating the digits starting from the least significant digit. This approach avoids the need for additional space and can be faster for larger arrays.

Edge Case Handling

Consider edge cases such as when the number is a single-digit 9, which results in a carry and changes the array size, or when the number has a carry at multiple positions (e.g., 999 becomes 1000).

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the length of the digits array, as we may need to traverse the entire array in the worst case. Space complexity is O(1) if modified in-place, or O(n) if a new array is created.

What Interviewers Usually Probe

Can the candidate handle the carry and array resizing efficiently?
Does the candidate consider all edge cases, including the case of multiple carries?
How well does the candidate optimize the solution in terms of space and time complexity?

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle carry-over when incrementing digits.
Not properly adjusting the array length when a carry overflows the most significant digit.
Overcomplicating the solution by using extra data structures unnecessarily.

Follow-up variants

What if the array represents a negative number? Adjust the approach accordingly.
How would the solution change if the number represented more than one digit per element (e.g., two-digit numbers per array element)?
How do you handle cases where the array is empty?

FAQ

What is the pattern used in the Plus One problem?

The Plus One problem follows the 'array plus math' pattern, focusing on iterating through an array and applying basic arithmetic operations to manage carries and updates.

How should edge cases like a number ending in 9 be handled?

Edge cases like numbers ending in 9 should be handled by propagating the carry and resizing the array if necessary, e.g., 999 becomes 1000.

Is there a way to solve this problem in constant space?

Yes, solving the problem in-place with careful manipulation of the array ensures constant space complexity.

Can this problem be solved with recursion?

While recursion can be applied, an iterative solution is generally more efficient in terms of both time and space.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of the digits array, because we may need to iterate over the entire array to propagate carries.

terminal

Solution

Solution 1: Simulation

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.

1

2

3

4

5

6

7

8

9

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n - 1, -1, -1):
            digits[i] += 1
            digits[i] %= 10
            if digits[i] != 0:
                return digits
        return [1] + digits

Continue Practicing

#48 rotate image #149 max points on a line #150 evaluate reverse polish notation