66. Plus One (Easy)

Problem

You’re given an integer represented as a non-empty array of digits (most-significant first). Add 1 to it and return the resulting array.

Example

• digits = [1, 2, 3] → [1, 2, 4]
• digits = [9, 9, 9] → [1, 0, 0, 0]

LeetCode 66 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Convert to int, add, reconvert

Works in Python because int is arbitrary-precision.

Python

def plus_one(digits):
    n = int("".join(map(str, digits))) + 1  # L1: O(n) join + convert
    return [int(d) for d in str(n)]         # L2: O(n) convert back

TypeScript

function plusOne(digits: number[]): number[] {
    const n = BigInt(digits.join('')) + 1n;   // L1: O(n) join + convert
    return String(n).split('').map(Number);   // L2: O(n) convert back
}

Go

import (
    "strconv"
    "strings"
)

func plusOne(digits []int) []int {
    parts := make([]string, len(digits))
    for i, d := range digits { parts[i] = strconv.Itoa(d) }
    n, _ := strconv.ParseInt(strings.Join(parts, ""), 10, 64)  // L1: O(n)
    n++
    s := strconv.FormatInt(n, 10)
    result := make([]int, len(s))
    for i, ch := range s { result[i] = int(ch - '0') }        // L2: O(n)
    return result
}

Swift

final class Solution {
    func plusOne(_ digits: [Int]) -> [Int] {
        guard let value = Int(digits.map(String.init).joined()) else { return [] }
        return String(value + 1).utf8.map { Int($0 - 48) }
    }
}

Where the time goes, line by line

Variables: n = len(digits).

Line	Per-call cost	Times executed	Contribution
L1 (join + int convert)	$O(n)$	1	$O(n)$ ← dominates
L2 (str convert + list)	$O(n)$	1	$O(n)$

Complexity

• Time: $O(n)$, driven by L1/L2 (string conversion passes over all digits).
• Space: $O(n)$.

Fails in languages with fixed integer widths past ~10 digits.

Approach 2: Walk right to left with carry (canonical)

Standard grade-school addition, handling the all-nines case.

Python

def plus_one(digits):
    for i in range(len(digits) - 1, -1, -1):    # L1: walk right to left
        if digits[i] < 9:                        # L2: O(1)
            digits[i] += 1                       # L3: O(1), no carry needed
            return digits
        digits[i] = 0                            # L4: O(1), carry continues
    return [1] + digits                          # L5: O(n), all nines case

TypeScript

function plusOne(digits: number[]): number[] {
    for (let i = digits.length - 1; i >= 0; i--) {  // L1: walk right to left
        if (digits[i] < 9) {                          // L2: O(1)
            digits[i]++;                              // L3: O(1), no carry needed
            return digits;
        }
        digits[i] = 0;                               // L4: O(1), carry continues
    }
    return [1, ...digits];                           // L5: O(n), all nines case
}

Go

func plusOne(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {    // L1: walk right to left
        if digits[i] < 9 {                      // L2: O(1)
            digits[i]++                         // L3: O(1), no carry needed
            return digits
        }
        digits[i] = 0                           // L4: O(1), carry continues
    }
    return append([]int{1}, digits...)          // L5: O(n), all nines case
}

Swift

final class Solution {
    func plusOne(_ digits: [Int]) -> [Int] {
        var result = digits
        for index in result.indices.reversed() {
            if result[index] < 9 {
                result[index] += 1
                return result
            }
            result[index] = 0
        }
        result.insert(1, at: 0)
        return result
    }
}

Where the time goes, line by line

Variables: n = len(digits).

Line	Per-call cost	Times executed	Contribution
L1 (walk loop)	$O(1)$	up to n	$O(n)$ ← dominates
L2-L4 (carry logic)	$O(1)$	up to n	$O(n)$
L5 (prepend 1, all-nines)	$O(n)$	at most 1	$O(n)$

Best case: one step (last digit < 9). Worst case: all nines, walk all n digits then prepend.

Complexity

• Time: $O(n)$, driven by L1/L2/L3/L4 (right-to-left carry walk).
• Space: $O(1)$ extra (worst case one extra digit).

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Convert to int	$O(n)$	$O(n)$
Digit-by-digit carry	$O(n)$	$O(1)$

The digit-carry approach is language-agnostic and generalizes to problems like Add Binary (67) and Plus One Linked List (369).

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_066.py and run.
# Uses the canonical implementation (Approach 2: right-to-left carry).

def plus_one(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return [1] + digits

def _run_tests():
    assert plus_one([1, 2, 3]) == [1, 2, 4]
    assert plus_one([9, 9, 9]) == [1, 0, 0, 0]
    assert plus_one([0]) == [1]                   # single zero
    assert plus_one([9]) == [1, 0]                # single nine
    assert plus_one([1, 0, 9]) == [1, 1, 0]       # carry in middle
    assert plus_one([4, 3, 2, 1]) == [4, 3, 2, 2] # no carry
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function plusOne(digits: number[]): number[] {
    for (let i = digits.length - 1; i >= 0; i--) {
        if (digits[i] < 9) { digits[i]++; return digits; }
        digits[i] = 0;
    }
    return [1, ...digits];
}

console.assert(JSON.stringify(plusOne([1, 2, 3])) === JSON.stringify([1, 2, 4]));
console.assert(JSON.stringify(plusOne([9, 9, 9])) === JSON.stringify([1, 0, 0, 0]));
console.assert(JSON.stringify(plusOne([0])) === JSON.stringify([1]));
console.assert(JSON.stringify(plusOne([9])) === JSON.stringify([1, 0]));
console.assert(JSON.stringify(plusOne([1, 0, 9])) === JSON.stringify([1, 1, 0]));
console.assert(JSON.stringify(plusOne([4, 3, 2, 1])) === JSON.stringify([4, 3, 2, 2]));
console.log('all tests pass');

Related data structures

• Arrays, digit array; carry propagation

Related concepts

• Math and Number Theory, the arithmetic invariant behind digits, divisibility, modulo behavior, and identities.
• Simulation, the explicit state model for executing rules exactly while keeping cases organized.