What pattern does Plus One use?

The Pattern: Math & Geometry (Digit-by-Digit Simulation) The Heuristic: When incrementing a number represented as digits, simulate addition from least significant digit upwards, stopping early when no carry is needed, and handle the all-9s edge case by prepending 1.

Plus One - LeetCode Solution & Explanation

Q: What is the time complexity of Plus One?

O(n). The algorithm iterates through the digits at most once from right to left, where n is the number of digits.

Problem

Given a list of digits representing a non-negative integer, return the list of digits representing the integer plus one.

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits does not contain leading zeros except for the number 0 itself

Example

Input: digits = [1, 2, 3]

Output: [1, 2, 4]

Starting from the least significant digit (rightmost), the algorithm adds one. Since 3 is less than 9, it increments to 4 and returns immediately, resulting in [1, 2, 4]. If the input were [1, 2, 9], the algorithm would set the last digit to 0 and carry the increment to the next digit. It would then increment 2 to 3, resulting in [1, 3, 0]. For [9, 9, 9], all digits become 0, and a new leading 1 is added, resulting in [1, 0, 0, 0].

Approach

Straightforward Solution

A naive approach converts the digit array to an integer, adds one, and converts back to a digit array. This is inefficient and may cause overflow for large inputs.

Core Observation

Adding one to a number represented as an array of digits requires handling carry propagation from the least significant digit upwards. If a digit is less than 9, incrementing it completes the operation without carry. If a digit is 9, it resets to 0 and the carry moves to the next more significant digit.

Path to Optimal

The key insight is to simulate the addition directly on the digit array from right to left, avoiding integer conversion. By iterating backwards, the algorithm increments the first digit that is less than 9 and returns immediately. If all digits are 9, it resets all to 0 and prepends 1 to the list.

Optimal Approach

Iterate from the last digit to the first. If the digit is less than 9, increment it and return the list immediately. If the digit is 9, set it to 0 and continue to the next digit. If the loop completes, all digits were 9, so return a new list with 1 followed by zeros.

Time

O(n)

The algorithm iterates through the digits at most once from right to left, where n is the number of digits.

Space

O(n)

In the worst case (all digits are 9), a new list of length n+1 is created to accommodate the carry, otherwise the operation is done in-place.

Solution

1class 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

Step-by-Step Solution

1

Iterate Backwards to Increment Digits and Handle Carry

3n = len(digits)
5for i in range(n - 1, -1, -1):
6    if digits[i] < 9:
7        digits[i] += 1
8        return digits
9    digits[i] = 0

Objective

To simulate adding one to the number by processing digits from least significant to most significant, handling carry propagation.

Key Insight

By iterating from the end, the algorithm can increment the first digit that is less than 9 and return immediately, avoiding unnecessary work. If a digit is 9, it resets to 0 and the carry moves left. This approach efficiently simulates addition without converting to an integer.

Interview Quick-Check

Core Logic

Increment digits from right to left, returning immediately when a digit less than 9 is incremented, otherwise set digit to 0 and continue.

State & Boundaries

Loop runs from last index to first index inclusive, ensuring all digits are processed for carry.

Common Pitfalls & Bugs

Failing to return immediately after incrementing a digit less than 9 leads to incorrect carry propagation.

2

Handle All-Nines Edge Case by Prepending One

11	`return [1] + digits`

Objective

To handle the special case where all digits are 9, resulting in an overflow that requires increasing the number's length.

Key Insight

If the loop completes without returning, it means every digit was 9 and has been reset to 0. The number now represents zero with an extra digit needed. Prepending 1 to the list correctly represents the incremented number (e.g., 999 + 1 = 1000).

Interview Quick-Check

Core Logic

Return a new list with 1 followed by zeros when all digits are 9, representing the carry overflow.

Common Pitfalls & Bugs

Forgetting to handle the all-9s case leads to incorrect results or index errors.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 8 Critical

return digits

Return the updated digits list immediately after increment.

This immediate return is critical because it stops the carry propagation once a digit less than 9 is incremented, guaranteeing correctness and optimal performance by avoiding needless processing.

Line 11 Critical

return [1] + digits

Return a new list with 1 prepended to the digits list.

Prepending 1 after resetting all digits to 0 is the only way to correctly represent the incremented number when all digits are 9, ensuring correctness for this special but critical edge case.

Line 6 Core

if digits[i] < 9:

Check if the current digit is less than 9.

If the digit is less than 9, incrementing it will not cause a carry, allowing the algorithm to finish early.

Line 9 Core

digits[i] = 0

Set the current digit to 0 when it is 9.

Resetting a 9 to 0 simulates the carry-over effect in addition, requiring the next more significant digit to be incremented.

Line 5 Core

for i in range(n - 1, -1, -1):

Iterate backwards through the digits from last to first.

Processing digits from right to left simulates addition starting from the least significant digit, enabling correct carry propagation.

Line 7 Core

digits[i] += 1

Increment the current digit by one.

Incrementing the digit directly simulates adding one to the number at this position without carry.

Line 3 Standard

n = len(digits)

Calculate the length of the digits list.

Knowing the number of digits allows iteration from the least significant digit backwards, which is essential for simulating addition with carry.

Test Your Understanding

Why does the algorithm return immediately after incrementing a digit less than 9?

Because incrementing a digit less than 9 does not produce a carry, so no further digits need to be changed, making the operation complete.

Don't just read it. Drill it.

Reconstruct Plus One from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Plus One drill

or drill a free problem

1	`class Solution:`
2	`def plusOne(self, digits: list[int]) -> list[int]:`
3	`n = len(digits)`
4
5	`for i in range(n - 1, -1, -1):`
6	`if digits[i] < 9:`
7	`digits[i] += 1`
8	`return digits`
9	`digits[i] = 0`
10
11	`return [1] + digits`

3	`n = len(digits)`
5	`for i in range(n - 1, -1, -1):`
6	`if digits[i] < 9:`
7	`digits[i] += 1`
8	`return digits`
9	`digits[i] = 0`