66. Plus One - Explanation

Problem Link

Description

You are given an integer array digits, where each digits[i] is the ith digit of a large integer. It is ordered from most significant to least significant digit, and it will not contain any leading zero.

Return the digits of the given integer after incrementing it by one.

Example 1:

Input: digits = [1,2,3,4]

Output: [1,2,3,5]

Explanation 1234 + 1 = 1235.

Example 2:

Input: digits = [9,9,9]

Output: [1,0,0,0]

Constraints:

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9


Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.


Hint 1

There are two cases when adding 1 to a number. If the rightmost digit is less than 9, we simply increment it. Otherwise, we set it to 0 and apply the same process to the preceding digit.


Hint 2

We iterate through the given digits from right to left using index i. If the current digit is less than 9, we increment it and return the array. Otherwise, we set the digit to 0 and continue. If the loop completes without returning, we insert 1 at the beginning of the array and return it.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Recursion

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        if not digits:
            return [1]

        if digits[-1] < 9:
            digits[-1] += 1
            return digits
        else:
            return self.plusOne(digits[:-1]) + [0]

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

2. Iteration - I

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        one = 1
        i = 0
        digits.reverse()

        while one:
            if i < len(digits):
                if digits[i] == 9:
                    digits[i] = 0
                else:
                    digits[i] += 1
                    one = 0
            else:
                digits.append(one)
                one = 0
            i += 1

        digits.reverse()
        return digits

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) or O(n)O(n) depending on the language.

3. Iteration - II

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

        return [1] + digits

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)