Two-sum

1 Problem statement and variants

1.1 Input/output specifications

Two-sum asks, given a collection of numbers and a target value, whether there exist two elements whose sum equals the target. In most presentations, the task is paired with a requirement to output a witness (the elements or their positions) when such a pair exists.

1.1.1 Decision version (existence of a pair)

The decision version is a yes/no question: given input list \(A\) of length \(n\) and target \(T\), determine whether there exist indices \(i \neq j\) such that \(A[i] + A[j] = T\). If duplicates are allowed in the input, the indices must refer to two (not necessarily distinct by value) positions in the list.

1.1.2 Constructive version (returning a pair)

The constructive version strengthens the requirement by asking for an explicit pair. A typical output is either the two values \((A[i], A[j])\) or their indices \((i, j)\) such that the sum condition holds. If no such pair exists, the output is commonly a sentinel such as “not found” or an empty result.

1.1.3 Index-based vs value-based output

Index-based output is often used to clarify which occurrences are chosen, especially when the list contains repeated numbers. Value-based output can be ambiguous when multiple index pairs yield the same values; it typically requires additional tie-breaking rules or accepts any valid witness. Index output also aligns naturally with algorithmic constraints such as whether reuse of the same element is allowed.

1.2 Constraints and assumptions

Correct algorithm design depends on clarifying what counts as a valid pair and how the input may contain repeated or special numeric values.

1.2.1 Distinct vs repeated elements

Most formulations permit repeated elements in the input list and treat each occurrence as separate. The constraint is then usually \(i \neq j\), not \(A[i] \neq A[j]\). In a set interpretation (no repeated elements), repeated values cannot occur; however, a multiset interpretation explicitly allows repetition and changes both counting arguments and edge-case handling.

1.2.2 Handling negative, zero, and large integers

The arithmetic does not restrict sign: negative numbers and zero are permitted in standard versions. Large integers also pose no conceptual difficulty for correctness, though they may influence practical concerns such as integer overflow in fixed-width machine arithmetic. In an abstract setting, calculations are assumed exact or the model accounts for sufficient precision.

1.2.3 Duplicate-pair interpretation rules

When duplicates exist, there may be multiple valid index pairs. Some tasks return any valid pair; others impose determinism such as the earliest pair in lexicographic index order. Proofs and algorithmic behavior must align with the chosen rule, especially for methods that scan in a particular order (for example, left-to-right passes or two-pointer sweeps).

1.3 Relationship to “k-sum” and generalizations

Two-sum is the base case for “k-sum,” which generalizes the question to whether \(k\) elements sum to a target. Many algorithmic strategies for k-sum—hashing, sorting, two-pointer techniques, and reductions—can be motivated by studying the two-sum case first. Complexity tends to grow rapidly with \(k\), making two-sum an important conceptual anchor.

2 Mathematical formulation

2.1 Pairwise-sum model

A clean way to express the problem is through pairwise sums and a target equation.

2.1.1 Using a target equation

Let \(A = \{A[0], A[1], \dots, A[n-1]\}\). The core requirement is existence of indices \(i \neq j\) such that \[ A[i] + A[j] = T. \] This equation defines the set of satisfying pairs and underpins both decision and constructive tasks.

2.1.2 Set versus multiset interpretations

If \(A\) is treated as a set, each value appears at most once and valid pairs correspond to two distinct elements by definition. If \(A\) is treated as a multiset (a list with possible repetition), then pairs can reuse values as long as they come from different occurrences. In practice, most computational formulations treat the input as a list (multiset by multiplicity).

2.2 Combinatorial perspective

Before choosing an algorithm, it is useful to consider how many candidate pairs could exist.

2.2.1 Counting candidate pairs

For a list of length \(n\), unordered index pairs correspond to choosing two distinct indices, yielding \(\binom{n}{2}\) candidates. If ordered pairs are considered, the count is \(n(n-1)\). This distinction affects constant factors in enumeration-based methods but not their overall quadratic growth.

2.2.2 Worst-case number of checks

A brute-force approach that tests each candidate pair performs a check per pair. In the worst case, no satisfying pair exists or the satisfying pair appears late, so essentially all pairs are tested. This yields the canonical \(O(n^2)\) time behavior.

2.3 Graph interpretation

Two-sum can also be framed in graph terms, which provides intuition for correctness and structure.

2.3.1 Constructing an auxiliary graph

One can build a graph whose vertices correspond to array positions. An edge between \(i\) and \(j\) exists when \(i \neq j\) and \(A[i] + A[j] = T\). The two-sum question then becomes: does this graph contain any edge?

2.3.2 Viewing solutions as edges

Under this view, the decision version asks whether the edge set is nonempty, and the constructive version asks for an explicit edge. Different algorithms can be seen as different ways to discover whether any edge exists without explicitly generating all edges.

3 Algorithmic approaches

3.1 Brute-force method

The simplest strategy is systematic enumeration.

3.1.1 Nested-loop enumeration

A common brute-force method uses two nested loops over indices \(i\) and \(j\) with \(i < j\). For each pair, it checks whether \(A[i] + A[j] = T\). If so, the algorithm returns the pair (or indices); otherwise it continues.

3.1.2 Time and space behavior

The method uses constant extra space beyond the input, aside from bookkeeping for indices and a return value. Time scales quadratically because it examines \(\binom{n}{2}\) candidates in the worst case.

3.2 Hash-based method

Hashing reduces redundant checks by remembering previously observed numbers.

3.2.1 Storing previously seen values

As the algorithm scans the list from left to right, it maintains a hash map from a number value to an index at which that value occurred. When processing a new element \(x = A[i]\), it determines the complement \(c = T - x\). If \(c\) has been seen already, then a valid pair exists: \((c, x)\) corresponds to indices stored for \(c\) and the current index \(i\).

3.2.2 Lookup of the needed complement

The key step is constant-time expected lookup in the hash map. The algorithm therefore avoids enumerating all future partners by using algebra: if the target must be reached by two terms, the second term is forced to be the complement of the first.

3.2.3 Average-case performance considerations

With a well-behaved hash function and typical assumptions (uniform hashing), insertion and lookup each take expected \(O(1)\) time, giving an expected \(O(n)\) runtime overall. In adversarial contexts or with poor hashing, performance can degrade, which motivates the more nuanced complexity discussion later.

3.3 Sorting and two-pointer method

Another classic approach relies on sorting and then exploiting order.

3.3.1 Sorting strategy and preprocessing

If the problem requires index output, sorting is done on pairs \((\text{value}, \text{original index})\) to preserve position information. After sorting values in nondecreasing order, the algorithm can consider sums of elements with predictable behavior as pointers move.

3.3.2 Two-pointer sweep logic

Maintain two indices \(l\) and \(r\) such that \(l < r\). Let \(s = A[l] + A[r]\). If \(s = T\), a valid pair is found. If \(s < T\), increasing \(l\) (moving to a larger value) can raise the sum toward the target, so the algorithm increments \(l\). If \(s > T\), decreasing \(r\) reduces the sum, so it decrements \(r\). This continues until pointers cross.

3.3.3 Managing duplicates while scanning

When duplicates exist, many pairs may satisfy the equation. The two-pointer method still terminates efficiently because each pointer moves monotonically. If a deterministic choice is needed (for example, returning the leftmost index pair under a specific ordering), the algorithm may require additional rules to control which duplicate combinations are considered first.

3.4 Balanced-search-tree method

Balanced trees provide ordered lookup with guaranteed logarithmic time.

3.4.1 Ordered lookup approach

Instead of hashing, the algorithm maintains an ordered map from seen values to indices. For each element \(x\), it queries for the complement \(c = T - x\). Ordered structures allow operations such as “find value equal to \(c\)” (and sometimes predecessor/successor queries, though equality suffices for two-sum).

3.4.2 Complexity trade-offs

Tree-based lookup and insertion take \(O(\log n)\) time per element, leading to \(O(n \log n)\) overall. Compared with hashing, trees provide stronger worst-case guarantees and avoid collision-based slowdowns, but often use more memory and more constant overhead.

4 Correctness and proof techniques

4.1 Loop invariants and reasoning

Correctness proofs often rely on identifying what information the algorithm has accumulated at each step and how that implies progress.

4.1.1 Invariant for the hash-based scan

For a left-to-right scan with a hash map, a typical invariant states: before processing index \(i\), the map contains exactly the values \(A[j]\) for all earlier indices \(j < i\) (with an associated index), and no later indices are included. If the algorithm finds that the complement \(T - A[i]\) is present in the map, then there exists a stored index \(j < i\) such that \(A[j] + A[i] = T\), yielding a valid pair. If the complement is absent, then no pair using \(A[i]\) as the second element can sum to \(T\) with an earlier occurrence, so the scan can safely continue.

4.1.2 Invariant for the two-pointer method

For the two-pointer approach on a sorted array, an invariant can express that all feasible solutions lie within the current window \([l, r]\) given the history of pointer movements. More concretely, when \(A[l] + A[r] < T\), any pair using the current \(l\) with an index smaller than \(r\) will have an even smaller sum (because the array is sorted and moving the right pointer left decreases the second term), so no solution is lost by incrementing \(l\). Symmetrically, when the sum exceeds \(T\), decrementing \(r\) cannot discard a valid pair.

4.2 Proof of existence/uniqueness conditions

Correctness also includes statements about what the algorithm returns when multiple answers exist.

4.2.1 When multiple valid pairs exist

All described constructive algorithms are designed to return at least one valid pair when it exists, not necessarily all. The proof therefore typically shows: if any satisfying pair exists, the algorithm’s logic will eventually encounter a point where it can output one. For example, the hash method outputs as soon as the first complement match is detected, while the two-pointer method outputs when pointers land on a satisfying pair.

4.2.2 Selecting a specific pair deterministically

If the task specifies which pair to return (such as earliest indices, or smallest lexicographic ordering), correctness must incorporate the tie-breaking mechanism. For hash-based scans, the selected pair often depends on scan order and whether the map stores the first or most recent occurrence of a value. For sorting-based methods, the returned pair depends on pointer movement order after sorting. Deterministic selection can require careful handling of duplicates and explicit comparison criteria.

4.3 Handling edge cases in proofs

A rigorous proof must address corner cases where naive reasoning might fail.

4.3.1 Minimal input sizes (fewer than two elements)

If \(n < 2\), no pair of distinct indices exists. Algorithms typically detect this implicitly by loop bounds: brute force and hash scans naturally fail to find a witness, while two-pointer methods start with invalid pointer positions and terminate without success.

4.3.2 Targets with no feasible solution

When no pair sums to the target, the algorithms must be shown to terminate without false positives. For hashing, this means that absence of the complement for each processed element implies no earlier index could form the target with that element, and since every pair uses some earlier element as its first member, no solution exists. For two pointers, pointer monotonicity and sortedness ensure that sums move systematically toward the target without skipping any candidate window that could contain a solution.

4.3.3 Cases involving duplicates

With duplicates, it is possible to form a valid sum using two equal values, such as when \(T = 2x\) and \(x\) occurs at least twice. Correctness proofs must confirm that the algorithms enforce distinct indices: hashing ensures the complement comes from an earlier position, and two pointers ensure \(l &lt; r\), which corresponds to using two different elements in the array.

5 Complexity analysis

5.1 Time complexity by method

Time complexity depends on both algorithm structure and assumptions about underlying operations.

5.1.1 Brute-force: O(n^2)

Nested-loop enumeration checks \(\binom{n}{2}\) pairs, yielding quadratic time. Even when a solution is found early, the worst-case time remains \(O(n^2)\).

5.1.2 Hashing: average O(n)

In expected analysis under typical hashing assumptions, each element requires one complement computation and one hash map lookup and insertion. Each operation is expected constant time, leading to expected \(O(n)\) runtime.

5.1.3 Sorting-based: O(n log n)

Sorting the array (or value-index pairs) dominates runtime with \(O(n \log n)\). The subsequent two-pointer scan is linear, so total time remains \(O(n \log n)\).

5.2 Space complexity by method

Space usage reflects auxiliary data structures needed beyond the input.

5.2.1 Extra memory in hashing

Hash maps store up to \(n\) entries in the worst case, so additional space is \(O(n)\). If the map stores only one index per distinct value, the space can be smaller in practice but remains \(O(n)\) in worst-case distinct inputs.

5.2.2 In-place considerations for two pointers

Two-pointer scanning after sorting can use extra memory depending on whether sorting is performed in place. If sorting is in place and only two indices are maintained, extra space can be \(O(1)\) beyond the sorting algorithm’s own space usage. When stable ordering and original indices are required, additional storage for (value, index) pairs may be necessary.

5.3 Average-case vs worst-case discussion

Complexity analysis often distinguishes idealized behavior from pathological cases.

5.3.1 Hash collision considerations

Worst-case hash performance can degrade if many inputs map to the same buckets or if an adversary selects keys to exploit weaknesses in the hash function. Under such scenarios, lookup and insertion can become linear, leading to worst-case time closer to \(O(n^2)\). Many systems mitigate this with randomized hashing or tree-based bucket structures.

5.3.2 Adversarial input effects

Sorting-based and tree-based solutions provide more predictable runtime under adversarial arrangements: comparisons and pointer moves do not depend on key distribution beyond ordering. Hash-based solutions are the primary candidates for input-sensitive variance.

6 Extensions and related problems

6.1 Variants with constraints on indices

Index-related constraints influence how algorithms must store and select information.

6.1.1 Returning the earliest/leftmost pair

If “earliest” is defined by minimal first index, or by lexicographic minimal \((i, j)\), the algorithm must align its scan direction and update policy accordingly. For hashing, storing the earliest index for each value can help ensure the output respects leftmost criteria. Sorting-based methods require careful mapping back to original indices and then applying the required comparison rule.

6.1.2 Enforcing i < j vs unordered pairs

Some specifications treat \((i, j)\) and \((j, i)\) as the same pair, while others treat them as distinct outputs. Enforcing \(i < j\) typically simplifies reasoning and avoids double-counting. Algorithm implementations usually achieve this naturally: brute force often loops with \(i < j\), and hashing commonly ensures that the stored complement comes from an earlier index, making \(j < i\) in the found pair.

6.2 Streaming and online settings

When data arrives incrementally and cannot be stored fully or revisited, the problem changes in practical terms.

6.2.1 One-pass processing with limited memory

In a streaming variant, the algorithm processes elements as they arrive and must decide whether a satisfying pair exists using limited memory. Hash-based one-pass scanning is well suited when memory can store previously seen values. Under tighter memory constraints, approximate or probabilistic techniques may be required, though exact two-sum in a strict streaming model generally needs space proportional to the number of distinct seen values.

6.2.2 Handling dynamic updates

If the list supports updates (insertions or deletions) while queries for different targets are made, static two-sum algorithms are insufficient. Data structure approaches may maintain auxiliary maps or balanced trees to support query-time lookups, trading update costs against query efficiency.

6.3 Two-sum over different domains

Changing the numeric domain can alter the meaning of “sum to target” even if the algorithmic skeleton remains similar.

6.3.1 Real numbers vs integers

With real numbers, equality checks may be complicated by floating-point representation errors. Algorithmic formulations may therefore assume exact arithmetic (symbolic reals) or incorporate tolerance-based comparisons. In an exact theoretical setting, the same complement logic applies.

6.3.2 Modular arithmetic (sum modulo m)

In modular variants, the condition becomes \((A[i] + A[j]) \bmod m = T\). The complement computation uses modular subtraction: a needed value is \(c \equiv T - x \pmod m\). Hashing or balanced lookup can still be applied over residue classes, and complexity depends on whether residues are treated as normalized values in \(\{0, 1, \dots, m-1\}\).

6.4 Connection to computational hardness in general k-sum

Two-sum is tractable with efficient methods; higher-order versions become substantially harder.

6.4.1 Growth of complexity with k

For k-sum, naive enumeration checks all combinations of \(k\) indices, leading to combinatorial explosion. Even when using sorting and recursive reduction strategies, runtime typically grows quickly with \(k\), though practical improvements exist for fixed small \(k\).

6.4.2 Parameterized perspectives

Parameterized complexity examines runtime as a function of parameters such as \(k\) (the number of elements to sum) and sometimes the target magnitude or constraints on the input structure. Two-sum corresponds to \(k=2\), where parameterized approaches yield efficient algorithms, motivating why the case is often used as a pedagogical starting point.