Skip to content

Volume ITechnology

4.28.5 — Plus One ​

LeetCode 66 · Easy

The problem ​

A number is given as an array of digits, most significant first. Add one and return the result.

[1,2,3]     →  [1,2,4]
[4,3,2,1]   →  [4,3,2,2]
[9]         →  [1,0]
[9,9,9]     →  [1,0,0,0]

The pattern ​

Add one to the last digit and carry leftwards, exactly as you would on paper.

The only interesting input is all nines, because the result is one digit longer than the input. Everything else is a one-line change.

Here is the observation that makes the code short:

Walk from the right. If a digit is less than 9, add one and you are finished — there is no carry. If it is 9, set it to 0 and continue left.

The loop ends early on the first non-nine, so there is no carry variable at all.

If the loop finishes without returning, every digit was a 9. They are now all 0, and the answer is a 1 in front. That is the only case needing extra work.

The solution ​

python
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits) - 1, -1, -1):     # (1) right to left
            if digits[i] < 9:  # (2)
                digits[i] += 1  # (3)
                return digits                         # (4) no carry — done
            digits[i] = 0                             # (5) 9 becomes 0, carry continues

        return [1] + digits                           # (6) every digit was 9
ts
function plusOne(digits: number[]): number[] {
  for (let i = digits.length - 1; i >= 0; i--) {  // (1)
    if (digits[i] < 9) {  // (2)
      digits[i]++;  // (3)
      return digits;  // (4)
    }
    digits[i] = 0;  // (5)
  }

  return [1, ...digits];  // (6)
}

Line by line ​

(1) Walk the digits from right to left, from the ones digit upward. range(len(digits) - 1, -1, -1) counts down to 0.

(2) A digit below 9 can take the extra 1 without carrying.

(3) Add it, and

(4) we are finished. Nothing to the left changes.

(5) A 9 becomes 0, and the 1 carries to the next digit on the left. The loop moving left is the carry, so no separate carry variable is needed.

(6) The loop finished, so every digit was 9 and is now 0. The answer is a 1 followed by all those zeros, one digit longer than before.

Trace ​

Take [1, 2, 9].

iDigitActionDigits after
29becomes 0, carry left[1, 2, 0]
12below 9, add 1, return[1, 3, 0]

The answer is [1, 3, 0].

Edge cases ​

  • All nines, like [9, 9]. Every digit becomes 0, and line (6) returns [1, 0, 0].
  • Ends in a digit below 9. One step and done.
  • A single [0]. Returns [1].

No carry variable is needed. The early return replaces it — reaching the next iteration is the carry. That is what makes this five lines instead of ten.

[1] + digits after the loop works because every digit has already been set to 0 by then, so [9,9,9] becomes [0,0,0] and then [1,0,0,0].

Only one leading digit can ever be added, because adding 1 can never cause more than one extra digit.

Why not convert to an integer ​

The obvious approach is to build the number, add one, and split it back:

python
n = int(''.join(map(str, digits))) + 1
return [int(c) for c in str(n)]

It works in Python, where integers are unbounded. It fails in most other languages — the array can hold 100 digits, far beyond any 64-bit integer.

Say that out loud. Knowing that your language's convenience does not generalise is the point of this problem, and the array-based version is what a big-integer library actually does.

Complexity ​

O(n) time in the worst case — all nines. O(1) extra space when the input may be modified, or O(n) for the new array in the all-nines case.

Best case is O(1): a last digit below 9 returns immediately.

Where this goes next ​

  • Add Two Numbers — the same carry discipline on linked lists, and there the carry variable is needed because two inputs are being combined. 4.9.6.
  • Add Binary, Add Strings — same loop, different base.
  • Multiply Strings — carries in two dimensions. 4.28.7.
  • Big-integer arithmetic — Python's integers do this internally in base 2^{30} rather than base 10, because a bigger base means fewer digits and fewer carries. Every arbitrary-precision library is this loop.

What the interviewer will push on ​

"What is the interesting case?" All nines, where the result grows by one digit.

"Why is there no carry variable?" The early return replaces it; continuing the loop is the carry.

"Why not convert to an integer?" Overflow in any language with fixed-width integers, and 100 digits is far beyond 64 bits.

"What if you had to add an arbitrary number rather than 1?" Then you do need a carry variable, and the loop cannot exit early — that is Add Strings.

"Could the result ever grow by two digits?" No. Adding 1 to a number of n digits gives at most n + 1.

One thing to volunteer: name the all-nines case before writing anything, and mention that the integer conversion trick does not port to other languages. Both are one sentence and both are what the problem is testing.

Next: 4.28.6 Pow(x, n) — exponentiation in O(\log n), and a negative-number trap.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet