Solution 1 - In-Place Reverse Traversal

Traverse the digits array from right to left. If the current digit is less than 9, increment it by one and return immediately. If the digit is 9, set it to 0 and continue to the next digit. If all digits were 9, prepend a 1 to the front of the array.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0066.1 - Plus One - Solution 1 - In-Place Reverse Traversal """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def plusOne(self, digits: List[int]) -> List[int]:
        """Plus One Function"""
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0

        return [1] + digits


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().plusOne([1, 2, 3]))       # [1, 2, 4]
    print(Solution().plusOne([4, 3, 2, 1]))    # [4, 3, 2, 2]
    print(Solution().plusOne([9]))              # [1, 0]
    print(Solution().plusOne([9, 9, 9]))        # [1, 0, 0, 0]


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Carry Propagation with While Loop

Use a carry variable starting at 1. Traverse the array from right to left, adding the carry to each digit. If the sum is 10, set the digit to 0 and keep the carry as 1. Otherwise, update the digit and set carry to 0. If carry remains after processing all digits, insert 1 at the beginning.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0066.2 - Plus One - Solution 2 - Carry Propagation with While Loop """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def plusOne(self, digits: List[int]) -> List[int]:
        """Plus One Function"""
        carry = 1
        i = len(digits) - 1

        while i >= 0 and carry:
            total = digits[i] + carry
            digits[i] = total % 10
            carry = total // 10
            i -= 1

        if carry:
            digits.insert(0, 1)

        return digits


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().plusOne([1, 2, 3]))       # [1, 2, 4]
    print(Solution().plusOne([4, 3, 2, 1]))    # [4, 3, 2, 2]
    print(Solution().plusOne([9]))              # [1, 0]
    print(Solution().plusOne([9, 9, 9]))        # [1, 0, 0, 0]


#####################################################################################
# Functions
#####################################################################################
if __name__ == "__main__":
    testcase()

0066 - Plus One

Solution 1 - In-Place Reverse Traversal

Solution 2 - Carry Propagation with While Loop