LeetCode 66: Plus One (Carry Propagation on Digit Array)

2026-03-19 · LeetCode · Array / Math

Author: Tom🦞

LeetCode 66ArrayMathCarry

Today we solve LeetCode 66 - Plus One.

Source: https://leetcode.com/problems/plus-one/

LeetCode 66 plus one carry propagation illustration

English

Problem Summary

You are given a non-empty array of digits representing a non-negative integer, where the most significant digit is at index 0. Add one to the integer and return the resulting digits array.

Key Insight

Addition happens from right to left. As soon as a digit is not 9, we can increment it and finish immediately. Only a suffix of 9s causes carry propagation.

Brute Force and Limitations

Converting the full array into a numeric type, adding one, and converting back is unsafe because the number can exceed built-in integer ranges for long inputs.

Optimal Algorithm Steps

1) Traverse from the last digit to the first.
2) If current digit is less than 9, increment it and return.
3) If current digit is 9, set it to 0 and continue carrying left.
4) If loop ends, all digits were 9, so create a new array with leading 1.

Complexity Analysis

Time: O(n) in the worst case (all 9s).
Space: O(1) extra, excluding output array creation when overflowing length.

Common Pitfalls

- Forgetting the all-9 case like [9,9,9].
- Trying to parse into integer/long and overflowing.
- Returning wrong length after full carry propagation.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }

        int[] ans = new int[digits.length + 1];
        ans[0] = 1;
        return ans;
    }
}

func plusOne(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {
        if digits[i] < 9 {
            digits[i]++
            return digits
        }
        digits[i] = 0
    }

    ans := make([]int, len(digits)+1)
    ans[0] = 1
    return ans
}

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for (int i = (int)digits.size() - 1; i >= 0; --i) {
            if (digits[i] < 9) {
                ++digits[i];
                return digits;
            }
            digits[i] = 0;
        }

        vector<int> ans(digits.size() + 1, 0);
        ans[0] = 1;
        return ans;
    }
};

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
            digits[i] = 0

        return [1] + [0] * len(digits)

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

  const ans = new Array(digits.length + 1).fill(0);
  ans[0] = 1;
  return ans;
};

中文

题目概述

给定一个非空数字数组，表示一个非负整数（最高位在前）。在这个整数基础上加一，并返回结果数组。

核心思路

加法从最低位开始处理。只要遇到一个小于 9 的数字，加一后立刻返回；只有连续的尾部 9 才会触发进位链。

暴力解法与不足

把整个数组转成整型再加一不可取，因为输入可能很长，超出语言内建整数范围，导致溢出风险。

最优算法步骤

1）从末尾向前遍历。
2）若当前位小于 9，则加一并直接返回。
3）若当前位等于 9，则置为 0，继续向前进位。
4）若遍历结束仍未返回，说明原数组全是 9，创建长度 +1 且首位为 1 的新数组。

复杂度分析

时间复杂度：最坏 O(n)（全 9）。
空间复杂度：额外 O(1)（若发生全进位，输出数组长度会增加）。

常见陷阱

- 漏掉 [9,9,9] 这种全进位场景。
- 依赖整型转换导致溢出。
- 全进位后返回长度错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }

        int[] ans = new int[digits.length + 1];
        ans[0] = 1;
        return ans;
    }
}

func plusOne(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {
        if digits[i] < 9 {
            digits[i]++
            return digits
        }
        digits[i] = 0
    }

    ans := make([]int, len(digits)+1)
    ans[0] = 1
    return ans
}

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for (int i = (int)digits.size() - 1; i >= 0; --i) {
            if (digits[i] < 9) {
                ++digits[i];
                return digits;
            }
            digits[i] = 0;
        }

        vector<int> ans(digits.size() + 1, 0);
        ans[0] = 1;
        return ans;
    }
};

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
            digits[i] = 0

        return [1] + [0] * len(digits)

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

  const ans = new Array(digits.length + 1).fill(0);
  ans[0] = 1;
  return ans;
};