How do you solve Plus One?

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.

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 — Math & Geometry

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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate from the last digit to the first. If the digit is less than 9, increment it and return the list immediately…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

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

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

1 more step with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

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

See the answer with Pro.

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`