💬 Discord
Sign In
NeetCode #908LC-66EasyMath & GeometryNC 150NC 250
← Back to All Problems

#908 · #66 · Plus One(加一)

📌 Problem Statement & Constraints

Given a non-empty array digits of decimal digits representing a non-negative integer with the most significant digit first and no leading zeros, increment the integer by one and return the resulting digit array. Constraints: 1 <= digits.length <= 100, 0 <= digits[i] <= 9.

💡 Core Algorithmic Approaches

  1. Scan from the least significant digit, adding one.
  2. If the current digit is less than 9, increment it and return immediately -- no carry propagates further.
  3. If it is exactly 9, it becomes 0 and the carry moves to the next more significant digit.
  4. If the loop finishes, every digit was 9, so a new leading 1 must be prepended.

💻 Benchmark Python3 Implementation

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits          # no further carry
            digits[i] = 0              # this digit wraps, carry continues
        return [1] + digits            # every digit was 9

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): at most one pass over the digits.
💾 Space Complexity
O(1) beyond the input; O(n) only in the all-nines case for the new array.

⚠️ Interview Pitfalls & Follow-ups

  • Converting the array to an integer: unnecessary, and it overflows in fixed-width languages.
  • Forgetting the all-nines case: [9, 9] must become [1, 0, 0], which only the post-loop prepend produces.
  • Returning digits after the loop: the loop only exits when every digit was 9, so the prepend is mandatory.
  • Propagating the carry to the left before checking the digit: the digit must be tested first.