Love, Order, Progress

00

Problem Statement

You are given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

nums[0] + nums[1] is 2 + 7 = 9, returning [0, 1].

Example 2

Input: nums = [3,2,4], target = 6

Output: [1,2]

nums[1] + nums[2] is 2 + 4 = 6, returning [1, 2].

Example 3

Input: nums = [3,3], target = 6

Output: [0,1]

nums[0] + nums[1] is 3 + 3 = 6, returning [0, 1].

Constraints & Follow-up

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
-10⁹ ≤ target ≤ 10⁹
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than

\mathcal{O}(n^2)

time complexity?

Starting from the initial C++ template:

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
    }
};

01

Mathematical Representation & Index Mapping

Let the input array be modeled as a finite sequence of $n$ integers indexed over the discrete domain $I = \{0, 1, \dots, n - 1\}$ . We define a function $A : I \to \mathbb{Z}$ where $A(i) = a_i = \text{nums}[i]$ , and let $T \in \mathbb{Z}$ denote target.

DefinitionFormal Problem Specification

Given:

A = (a_0, a_1, \dots, a_{n-1}) \in \mathbb{Z}^n, \quad T \in \mathbb{Z}

Find:

\exists! (i, j) \in I \times I \quad \text{such that} \quad i < j \;\land\; a_i + a_j = T

Solution Set:

S = \left\{\, (i, j) \in I^2 \;\middle|\; 0 \le i < j < n, \; a_i + a_j = T \,\right\}, \quad |S| = 1

Visual · Sequence Mapping A : I → ℤ (Example 1: T = 9)

i = 0

↓

a₀ = 2

i = 1

↓

a₁ = 7

i = 2

↓

a₂ = 11

i = 3

↓

a₃ = 15

a₀ + a₁ = 2 + 7 = 9 = TValid Pair: (i, j) = (0, 1)

02

Combinatorial Search Space & The O(n²) Baseline

Because addition is commutative ( $a_i + a_j = a_j + a_i$ ) and self-pairing ( $i = j$ ) is forbidden, the naive search space consists of all strictly ordered index pairs $0 \le i < j < n$ . This corresponds to the strict upper triangle of the Cartesian product $I \times I$ .

CombinatoricsCardinality of the Pair Space

|\Omega| = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = (n - 1) + (n - 2) + \dots + 1 = \binom{n}{2} = \frac{n(n - 1)}{2} = \mathcal{O}(n^2)

For $n = 10^4$ : $|\Omega| = \frac{10{,}000 \times 9{,}999}{2} = 49{,}995{,}000$ pair evaluations.

Visual · Upper-Triangular Search Matrix (I × I for nums = [2, 7, 11, 15], T = 9)

i \ j	j = 0 (2)	j = 1 (7)	j = 2 (11)	j = 3 (15)
i = 0 (2)	i = j (skip)	2 + 7 = 9 ✓	2 + 11 = 13	2 + 15 = 17
i = 1 (7)	symmetric	i = j (skip)	7 + 11 = 18	7 + 15 = 22
i = 2 (11)	symmetric	symmetric	i = j (skip)	11 + 15 = 26
i = 3 (15)	symmetric	symmetric	symmetric	i = j (skip)

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();

        // Traverse the upper-triangular index space: 0 <= i < j < n
        // Evaluates C(n, 2) = n(n - 1) / 2 pairs -> O(n^2) time
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }

        return {};
    }
};

03

Algebraic Inversion & The Complement Operator

To break the $\mathcal{O}(n^2)$ barrier, we eliminate the inner loop by algebraically isolating $a_i$ . Instead of varying both $i$ and $j$ simultaneously, we fix the right endpoint $j$ and ask whether the unique additive complement $C(a_j) = T - a_j$ has already appeared in the prefix $P_j = \{a_0, a_1, \dots, a_{j-1}\}$ .

Algebraic TransformationComplement Formulation

a_i + a_j = T \iff a_i = T - a_j = C(a_j)

Decision Predicate at step $j$ : Does there exist $i \in \{0, \dots, j - 1\}$ such that $a_i = C(a_j)$ ?

ARCHITECTURE SCHEMA

Rendering diagram...

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();

        for (int j = 0; j < n; ++j) {
            // Algebraic reduction: a_i + a_j = T  <=>  a_i = T - a_j
            int complement = target - nums[j];

            // Instead of a second loop scanning i in {0, ..., j - 1},
            // we need an O(1) way to check if `complement` was already seen.
        }

        return {};
    }
};

04

Inverse Mapping via Hash Table (O(1) Lookup)

An array gives $\mathcal{O}(1)$ forward evaluation $i \mapsto a_i$ , but finding an index from a value requires inverting the function: $A^{-1}(v) = i$ . By maintaining a running hash table $M_j$ (std::unordered_map<int, int>) that maps each previously seen value $a_i$ to its index $i$ , each membership and index query takes amortized $\mathcal{O}(1)$ time.

Recurrence RelationPartial Inverse Map Invariant

M_0 = \emptyset

M_{j+1} = M_j \cup \{\, a_j \mapsto j \,\} \quad (\text{if } T - a_j \notin \operatorname{dom}(M_j))

Termination: When

T - a_j \in \operatorname{dom}(M_j)

, return

(M_j(T - a_j), j)

.

Visual Trace · Example 2: nums = [3, 2, 4], T = 6

Step j	a_j	Complement C(a_j) = 6 - a_j	Hash Map M_j (before insert)	Action
j = 0	3	6 - 3 = 3	{ }	3 ∉ M₀ → insert 3 &mapsto; 0
j = 1	2	6 - 2 = 4	{ 3: 0 }	4 ∉ M₁ → insert 2 &mapsto; 1
j = 2	4	6 - 4 = 2	{ 3: 0, 2: 1 }	2 ∈ M₂(index 1) → Return [1, 2] ✓

Why Query-Before-Insert Solves Duplicate Elements (Example 3: nums = [3, 3], T = 6)

At $j = 0$ , $M_0$ is empty, so $3 \mapsto 0$ is inserted. At $j = 1$ , we query $C(3) = 6 - 3 = 3$ before inserting nums[1], immediately finding $M_1(3) = 0$ and returning [0, 1] without ever colliding or using the same index twice.

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // Partial inverse map M_j : value (a_i) -> index (i)
        unordered_map<int, int> seen;

        for (int j = 0; j < nums.size(); ++j) {
            int complement = target - nums[j];

            // 1. O(1) membership query: is C(a_j) in dom(M_j)?
            if (seen.find(complement) != seen.end()) {
                return {seen[complement], j};
            }

            // 2. State transition: M_{j+1} = M_j U { a_j |-> j }
            seen[nums[j]] = j;
        }

        return {};
    }
};

05

Final Optimal C++ Solution — O(n) Time

Combining the single-pass prefix invariant with bucket pre-allocation (seen.reserve(nums.size())) eliminates rehash overhead and achieves optimal $\mathcal{O}(n)$ time complexity:

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> seen;
        seen.reserve(nums.size());

        for (int j = 0; j < nums.size(); ++j) {
            int complement = target - nums[j];

            if (auto it = seen.find(complement); it != seen.end()) {
                return {it->second, j};
            }

            seen[nums[j]] = j;
        }

        return {};
    }
};

Approach	Time Complexity	Space Complexity	Ops at n = 10⁴
Brute Force (Nested Loops)	O(n²)	O(1)	~5.0 × 10⁷
One-Pass Hash Table (Optimal)	O(n) amortized	O(n)	≤ 1.0 × 10⁴