Plus One

Easy Arrays & Hashing Right to Left Traversal Original on LeetCode

Plus One is a easy arrays & hashing problem solved with the right to left traversal pattern. The best approach, optimal (in place, stop at the first non-9), runs in O(n) time and O(1) extra (O(n) only for the all-9s case) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (full carry pass into a new list) up.

Problem

A non-negative integer is stored as an array digits, one decimal digit per element, with the most significant digit first. Add 1 to the number and return the result in the same digit-array form.

The number can be much longer than any built-in integer type, so work with the digits directly.

Examples

Example 1

Input
digits = [3, 0, 7]
Output
[3, 0, 8]
Why
307 + 1 = 308; only the last digit changes.

Example 2

Input
digits = [2, 9, 9]
Output
[3, 0, 0]
Why
299 + 1 = 300; the carry ripples through both trailing 9s.

Example 3

Input
digits = [9, 9]
Output
[1, 0, 0]
Why
99 + 1 = 100, which needs one more digit than the input.

Constraints

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9
  • digits has no leading zeros, except for the number 0 itself ([0]).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (full carry pass into a new list)O(n)O(n)
Optimal (in place, stop at the first non-9)O(n)O(1) extra (O(n) only for the all-9s case)

1Brute force (full carry pass into a new list)

TimeO(n)Every digit is visited even when the carry dies out immediately.
SpaceO(n)A separate list holds all result digits.

Simulate schoolbook addition over every digit without stopping early: carry starts at 1, each digit becomes (d + carry) % 10, and the results are collected into a fresh list that is reversed at the end.

  1. carry = 1; walk i from n - 1 down to 0.
  2. sum = digits[i] + carry; append sum % 10 to a list; carry = sum / 10.
  3. If carry is still 1 after the loop, append 1.
  4. Reverse the list and copy it into an int array.
class Solution {
    public int[] plusOne(int[] digits) {
        List<Integer> out = new ArrayList<>();
        int carry = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            int sum = digits[i] + carry;
            out.add(sum % 10);
            carry = sum / 10;
        }
        if (carry == 1) out.add(1);
        int[] res = new int[out.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = out.get(out.size() - 1 - i);
        }
        return res;
    }
}

2Optimal (in place, stop at the first non-9)

TimeO(n)The loop stops at the first non-9 from the right; the worst case touches all n digits.
SpaceO(1) extra (O(n) only for the all-9s case)The input is updated in place; a new array is needed only when the length grows.

Walk from the right. A digit below 9 just gets incremented and the array is returned immediately. A 9 turns into 0 and the loop continues. Only when the loop finishes is every digit 9, so the answer is a new array of length n + 1 that starts with 1 and is zero elsewhere.

  1. For i from n - 1 down to 0: if digits[i] < 9, increment it and return digits.
  2. Otherwise set digits[i] = 0.
  3. After the loop, create res of length n + 1, set res[0] = 1, return res.
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[] res = new int[digits.length + 1];
        res[0] = 1;
        return res;
    }
}

Edge cases to test

  • All digits are 9: the answer is a 1 followed by n zeros
  • The single digit [0]
  • Trailing 9s inside a longer number, like [4, 9, 9]
  • Up to 100 digits, far beyond what a long can hold

Hints

Hint 1

Do it the way you add by hand: start at the last digit and carry to the left.

Hint 2

As soon as a digit is not 9, add 1 to it and you are done. A 9 becomes 0 and the carry moves on.

Hint 3

If the carry falls off the front, every digit was 9.

FAQ

What is the best time complexity for Plus One?

Optimal (in place, stop at the first non-9) runs in O(n) time and O(1) extra (O(n) only for the all-9s case) extra space. The loop stops at the first non-9 from the right; the worst case touches all n digits.

Which pattern does Plus One use?

It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.

Is there a brute force solution for Plus One?

Yes. Brute force (full carry pass into a new list) takes O(n) time and O(n) space. Simulate schoolbook addition over every digit without stopping early: carry starts at 1, each digit becomes (d + carry) % 10, and the results are collected into a fresh list that is reversed at the end.

Which edge cases should I test for Plus One?

All digits are 9: the answer is a 1 followed by n zeros; The single digit [0]; Trailing 9s inside a longer number, like [4, 9, 9]; Up to 100 digits, far beyond what a long can hold.