LeetCode 66: Plus One — Step-by-Step Visual Trace

#leetcode #python #algorithms

Easy — Array | Math | Simulation

The Problem

Given a non-empty array of decimal digits representing a non-negative integer, increment the integer by one and return the resulting digits as an array.

Approach

Iterate through the digits array from right to left (least to most significant digit). If a digit is less than 9, increment it and return immediately. If it's 9, set it to 0 and continue. If all digits were 9, prepend a 1 to handle the overflow case.

Time: O(n) · Space: O(1)

Code

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