66. Plus One

This is a classic interview warm-up because it tests whether we can implement grade-school addition cleanly while handling tricky carry cases (lots of trailing 9s). It is a favorite among interviewers at companies like Google, Meta, and Amazon because the core pattern: carry propagation from right to left, shows up in many array and math problems. This problem teaches us how to solve it in a single backward pass without converting the whole array into an integer.

Problem statement

We are given a large non-negative integer as an array digits, where each element in digits[i] represents one digit of the integer. The digits are stored from most significant to least significant (left to right). Our task is to add 1 to this number and return the resulting digits as an array, preserving the same format and without introducing leading zeros.

Constraints

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits has no leading 0s

Examples

Optimized approach using carry propagation

Think of this like adding 1 to a number on paper. We start from the least significant digit (the end of the array). If the digit is less than 9, we simply increment it, and we are done. If it is 9, it becomes 0 and creates a carry that must be applied to the digit on the left. This carry may propagate across many digits, but it always moves in one direction: right to left.

Step-by-step algorithm

1. Store the length of digits in len_digits.
2. Iterate over the digits array from right to left.
   1. If digits[i] < 9,
      1. Increment it and return immediately (no carry).
   2. Otherwise,
      1. Set digits[i] = 0 and continue (carry persists).
   3. Decrement i as we move left.
3. If we successfully process the digits array, it means all digits were 9. So, create a new array with a leading 1 followed by n zeros, and return it.

Let’s look at the following illustration to better understand the solution.

1 / 5

Code implementation

from typing import List

def plusOne(digits):
    """
    Increment the integer represented by digits by one.
    We propagate carry from right to left, turning trailing 9s into 0s.
    """
    len_digits = len(digits)

    # Traverse from least significant digit to most significant.
    for i in range(len_digits - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits  # No carry needed beyond this point.
        digits[i] = 0  # 9 becomes 0 and carry continues.

    # If we finished the loop, all digits were 9 (e.g., 999 -> 1000).
    return [1] + digits


def main():
    test_cases = [
        [2, 5, 9],        # carry in last digit
        [7, 1, 3, 4],     # simple increment
        [9],              # single digit overflow
        [1, 9, 9],        # carry ripple
        [9, 9, 9, 9],     # full overflow
    ]

    for idx, digits in enumerate(test_cases, 1):
        # result = sol.plusOne(digits[:])  # copy to keep original intact
        # print(f"{idx}. Input: {digits} -> Output: {result}")
        result = plusOne(digits[:])
        print(f"{idx}. \t Input: {digits}")
        print(f" \t Output: {result}\n")
        print("-"*75)


if __name__ == "__main__":
    main()

Time complexity

The algorithm’s time complexity is O(N), as in the worst case, we scan the whole array from right to left once (all 9s) and touch every digit exactly once.

Space complexity

The algorithm’s space complexity is O(N), becuase in the worst case, when all digits are 9, we must allocate a new list of size N +1, as we need to add a new leading 1, which requires additional space proportional to the number of digits.

Common pitfalls and interview tips

1. Forgetting the “all 9s” case: If every digit becomes 0, you must prepend 1 (e.g., [9,9] -> [1,0,0]).
2. Converting digits to an integer: This may overflow in languages with fixed-width integers, and it misses the point of the problem’s constraints.
3. Not returning early: Once we increment a digit that is < 9, the carry stops, and continuing the loop risks incorrect extra modifications.