66. Plus One

At a Glance

• Topic: math-geometry
• Pattern: Math simulation (grade-school carry)
• Difficulty: Easy
• Companies: Google, Amazon, Microsoft, Apple, Meta
• Frequency: High
• LeetCode: 66

Problem (one-liner)

Given a non-empty array of digits representing a non-negative integer (most significant digit first), return the digits of that integer plus one, also as a digit array.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• "Digits of large integer" without bigint
• Single increment — propagate carry from the right
• All 9s causes length increase

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — parse to big integer — disallowed / awkward in many languages.
• Better — carry from least significant (last index) leftward — O(digits) time / O(1) extra if in-place allowed or O(digits) for new slice.

Optimal Solution

Go

package main

func plusOne(digits []int) []int {
	carry := 1
	for index := len(digits) - 1; index >= 0 && carry > 0; index-- {
		sum := digits[index] + carry
		digits[index] = sum % 10
		carry = sum / 10
	}
	if carry > 0 {
		return append([]int{carry}, digits...)
	}
	return digits
}

JavaScript

function plusOne(digits) {
	const result = [...digits];
	let carry = 1;
	for (let index = result.length - 1; index >= 0 && carry > 0; index--) {
		const sum = result[index] + carry;
		result[index] = sum % 10;
		carry = Math.floor(sum / 10);
	}
	if (carry > 0) {
		result.unshift(carry);
	}
	return result;
}

Walkthrough

Input: digits = [1, 2, 9]

Result: [1, 3, 0].

Edge Cases

• [9] → [1, 0]
• [0] → [1] per definition (no leading zeros except zero itself)

Pitfalls

• Prepending new digit when carry survives past index 0
• Mutating shared input when tests expect copy

Similar Problems

• 43. Multiply Strings — multi-digit arithmetic.
• 50. Pow(x, n) — repeated scaling / construction (math topic cluster).

Variants

• Add arbitrary small integer k with carry.
• Big-endian binary increment.

Mind-Map Tags

#carry #digits #simulation #array #math