Skip to content

170 — Plus One

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

170 — Plus One

LeetCode 66 · Easy. You're given an array of digits digits representing a large non-negative integer, most significant digit first (no leading zeroes, except the number 0 itself). Increment the number by one and return the resulting array of digits.

🍽️ Intuition

This is exactly the "carry the one" arithmetic you learned doing addition by hand, just applied to a single array instead of two. Start from the rightmost digit and add 1. If it doesn't roll over past 9, you're done — just bump that digit and stop. If it does roll over (a 9 becomes a 10), that digit becomes 0 and the carry moves one place to the left, where the same question repeats: does this digit roll over too? The only genuinely new situation is when every digit was a 9 — 999 -> 1000 — where the carry runs off the front of the number entirely and the array needs to grow by one digit.

[1, 2, 9]  ->  add 1 to rightmost digit (9+1=10, carries) -> [1, 2, 0], carry
           ->  add carry to next digit (2+1=3, no carry)   -> [1, 3, 0]   done

[9, 9, 9]  ->  9+1=10, carries -> [9, 9, 0]
           ->  9+1=10, carries -> [9, 0, 0]
           ->  9+1=10, carries -> [0, 0, 0], carry runs off the front
           ->  prepend the final carry                     -> [1, 0, 0, 0]

🚩 Pattern-Recognition Cue

"Increment this array-of-digits number by one, handling carry" is the right-to-left carry-propagation signal: process the array from the last index backward, stop the moment a digit absorbs the increment without rolling over, and only in the all-9s edge case does the result need an extra leading digit.

🐢 Brute Force

Rebuild the number by combining every digit into a single integer, add one, then split the result back into digits. This is the natural first instinct — and it works, but only as long as the number fits inside a fixed-width integer type; a digits array long enough to represent a number bigger than Int.max would silently overflow.

func plusOneBruteForce(_ digits: [Int]) -> [Int] {
    var number = 0
    for digit in digits {
        number = number * 10 + digit
    }
    number += 1

    var result: [Int] = []
    while number > 0 {
        result.insert(number % 10, at: 0)
        number /= 10
    }
    return result.isEmpty ? [0] : result
}

// smoke test
print(plusOneBruteForce([1, 2, 3]))   // [1, 2, 4]
print(plusOneBruteForce([4, 3, 2, 1])) // [4, 3, 2, 2]
print(plusOneBruteForce([9, 9, 9]))   // [1, 0, 0, 0]
print(plusOneBruteForce([0]))         // [1]

Big-O: O(n) time to rebuild the number and split it back apart, where n is the digit count — but with a hidden ceiling: it silently breaks once the number exceeds what Int can hold. O(n) space for the result.

🚀 Optimal

Walk the array from the last digit backward, propagating the carry directly on the digits themselves — no intermediate integer, so there's no overflow ceiling no matter how long digits is.

func plusOne(_ digits: [Int]) -> [Int] {
    var digits = digits

    for i in stride(from: digits.count - 1, through: 0, by: -1) {
        if digits[i] < 9 {
            digits[i] += 1
            return digits
        }
        digits[i] = 0
    }

    // every digit was a 9 and rolled over to 0 -- the carry ran off the front
    return [1] + digits
}

// smoke test — same cases as the brute force
print(plusOne([1, 2, 3]))    // [1, 2, 4]
print(plusOne([4, 3, 2, 1])) // [4, 3, 2, 2]
print(plusOne([9, 9, 9]))    // [1, 0, 0, 0]
print(plusOne([0]))          // [1]

Big-O: O(n) time — at most one full pass over the digits, stopping early the moment a digit doesn't roll over. O(n) space for the returned array (O(1) extra beyond it).

🔑 The Key Insight

The brute force's trip through a native integer is really just a detour — it converts to a representation that already knows how to "add one with carrying" for free, then converts back. But digit arrays can represent numbers of unbounded length, and native integers can't, so that detour has a ceiling the array itself doesn't have. Propagating the carry directly on the array reimplements exactly the same "add one, carry if you roll past 9" logic the CPU does internally, at the same O(n) cost, but without ever needing the whole number to fit in one machine word.

🔗 Related Chapters

  • Arrays and Strings — the digit array being scanned and mutated directly; this is the only genuine Data Structure fit for a problem this close to raw array manipulation.
  • Prefix Sum — disclosed as a loose fit, not a natural one: there's no running sum or prefix array being built here. The only thing this problem shares with that chapter is the shape of a single right-to-left accumulation pass — a carry propagating backward is a distant cousin of a sum propagating forward, but Plus One is really just a self-contained carry loop, not an instance of the Prefix Sum pattern.

🧸 Memory Sentence

Plus One is grade-school "carry the one" — walk from the last digit backward, stop the instant a digit absorbs the bump without rolling over, and only grow the array when every digit was a 9.

✅ Check Your Understanding

  1. Why does the optimal solution return immediately the moment it finds a digit less than 9, instead of finishing the loop over the whole array?
  2. What specifically breaks in the brute-force approach if digits represents a 25-digit number, and why doesn't the optimal approach have that same problem?
  3. Trace plusOne([8, 9, 9]) step by step. Which digits get set to 0, and which one absorbs the final +1?
  4. Why is [1] + digits — prepending a 1 to an array that's now all zeroes — the correct way to handle the all-9s case, rather than, say, appending a 0 at the end?

⬅️ Previous: Happy Number · Next: Pow(x, n) ➡️

Clone this wiki locally