Domain 1EasyCORE

Plus One

The problem requires us to increment a non-negative integer represented by an array of its digits. The most significant digit is at the head of the list, and each element in the array contains a single digit. We need to return the new array representing the incremented integer.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

66. Plus One

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 42.2%


Problem Breakdown

The problem requires us to increment a non-negative integer represented by an array of its digits. The most significant digit is at the head of the list, and each element in the array contains a single digit. We need to return the new array representing the incremented integer.

Inputs:

  • A non-empty array of decimal digits (digits), where 1 <= len(digits) <= 100 and 0 <= digits[i] <= 9.

Outputs:

  • An array of decimal digits representing the integer after incrementing by one.

Implicit Constraints or Tricky Edge Cases:

  • The input array does not contain leading zeros, except for the number zero itself.
  • Handling cases where the last digit is a nine (e.g., [9, 9, 9]) which results in carrying over to additional digits.

Intuition

A brute-force approach would involve converting the entire array into an integer, adding one, and then converting it back into an array of digits. However, this approach has high time complexity due to conversions and is not optimal for large arrays.

The key insight is to simulate the addition process manually from right to left (least significant digit to most significant digit). This way, we can handle carry-overs efficiently without needing to convert the entire number.

Approach

  1. Start by iterating through the array from the last element to the first.
  2. For each digit:
    • If it is less than 9, simply increment it and return the array as no further carry-over is needed.
    • If it is 9, set it to 0 (since 9 + 1 = 10) and continue to the next digit.
  3. If all digits were 9 (e.g., [9, 9, 9]), after processing all digits, we will have an array of zeros. In this case, prepend a 1 to the array to account for the carry-over.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input array. We iterate through each digit at most once.
  • Space Complexity: O(1) (excluding the space required for the output). The algorithm modifies the input array in place and uses a constant amount of extra space.

Solution

def plusOne(digits):
    n = len(digits)
    
    # Traverse from the last element to the first
    for i in range(n - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    
    # If all digits were 9, we need an additional digit at the beginning
    return [1] + digits

Edge Cases Handled

  • Single-digit numbers: The function correctly handles cases like [0] and [9].
  • Numbers with trailing nines: For example, [9, 9, 9] becomes [1, 0, 0, 0].
  • General case: Any valid input array of digits is handled by the algorithm.