Notes
All notes

Two Sum: the hash map that remembers

Problem. Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution and you may not use the same element twice.

Input:  nums = [1, 3, 5, 7, 9], target = 10
Output: [1, 3]        # nums[1] + nums[3] = 3 + 7 = 10

The brute-force baseline

The obvious solution is a pair of nested loops: for every i, scan every j > i and test nums[i] + nums[j] == target.

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

That is \(O(n^2)\) time and \(O(1)\) extra space. For a 10-element array it is fine; for a million elements it is a trillion comparisons. We can do better, because the inner loop is asking a question a dictionary answers in \(O(1)\).

The key idea

Fix the current element \(x = \texttt{nums}[i]\). The only partner that can complete the pair is

\[ \text{complement} = \texttt{target} - x \]

So instead of scanning the rest of the array, we ask one question: have I already seen the complement? If we keep a hash map from value → index of everything to the left of i, that question is a single lookup.

The algorithm is one pass:

  1. seen = {} — a map from value to the index where we saw it.
  2. For each index i with value x:
    • compute complement = target - x;
    • if complement is in seen, we are done — its stored index plus i is the answer;
    • otherwise record seen[x] = i and move on.

The elegant part is the ordering: we look before we store, so an element can never be paired with itself — even when target = 2 * x.

Dry run

Take nums = [1, 3, 5, 7, 9] and target = 10. In every diagram the current element is shaded orange with an arrow below it, and the map built so far is printed underneath.

Step 1 — i = 0, x = 1. The map is empty, so the complement 9 cannot be in it. Store 1 → 0.

\begin{tikzpicture}[
  c/.style={draw,thick,minimum size=0.95cm,font=\large\bfseries},
  cur/.style={c,fill=orange!45,very thick},
  hit/.style={c,fill=green!40,very thick},
  lbl/.style={font=\scriptsize\ttfamily}
]
  \node[anchor=south west,font=\small] at (-0.75,0.55) {\texttt{nums}};
  \node[anchor=south east,font=\small] at (5.35,0.55) {\texttt{target} $=10$};
  \foreach \v [count=\i from 0] in {1,3,5,7,9} {
    \ifnum\i=0 \node[cur] at (\i*1.15,0) {\v}; \else \node[c] at (\i*1.15,0) {\v}; \fi
    \node[lbl] at (\i*1.15,-0.72) {\i};
  }
  \draw[->,very thick] (0,-1.5) -- (0,-0.6);
  \node[font=\small,anchor=west] at (0.12,-1.4) {$i=0,\ x=1$};
  \node[font=\small,anchor=north west,align=left] at (-0.75,-2.0)
    {complement $=10-1=9$, not in \texttt{seen}; store $1\mapsto0$};
\end{tikzpicture}

Step 2 — i = 1, x = 3. The complement 7 is not in the map (which holds {1: 0}), so store 3 → 1.

\begin{tikzpicture}[
  c/.style={draw,thick,minimum size=0.95cm,font=\large\bfseries},
  cur/.style={c,fill=orange!45,very thick},
  hit/.style={c,fill=green!40,very thick},
  lbl/.style={font=\scriptsize\ttfamily}
]
  \node[anchor=south west,font=\small] at (-0.75,0.55) {\texttt{nums}};
  \node[anchor=south east,font=\small] at (5.35,0.55) {\texttt{target} $=10$};
  \foreach \v [count=\i from 0] in {1,3,5,7,9} {
    \ifnum\i=1 \node[cur] at (\i*1.15,0) {\v}; \else \node[c] at (\i*1.15,0) {\v}; \fi
    \node[lbl] at (\i*1.15,-0.72) {\i};
  }
  \draw[->,very thick] (1.15,-1.5) -- (1.15,-0.6);
  \node[font=\small,anchor=west] at (1.27,-1.4) {$i=1,\ x=3$};
  \node[font=\small,anchor=north west,align=left] at (-0.75,-2.0)
    {complement $=10-3=7$, not in \texttt{seen}; store $3\mapsto1$};
\end{tikzpicture}

Step 3 — i = 2, x = 5. Something interesting happens: the complement is 5 itself. But 5 is not yet in the map, because we have not stored the current element yet. This is exactly why we check first and store after — the element is never allowed to match itself. Store 5 → 2.

\begin{tikzpicture}[
  c/.style={draw,thick,minimum size=0.95cm,font=\large\bfseries},
  cur/.style={c,fill=orange!45,very thick},
  hit/.style={c,fill=green!40,very thick},
  lbl/.style={font=\scriptsize\ttfamily}
]
  \node[anchor=south west,font=\small] at (-0.75,0.55) {\texttt{nums}};
  \node[anchor=south east,font=\small] at (5.35,0.55) {\texttt{target} $=10$};
  \foreach \v [count=\i from 0] in {1,3,5,7,9} {
    \ifnum\i=2 \node[cur] at (\i*1.15,0) {\v}; \else \node[c] at (\i*1.15,0) {\v}; \fi
    \node[lbl] at (\i*1.15,-0.72) {\i};
  }
  \draw[->,very thick] (2.3,-1.5) -- (2.3,-0.6);
  \node[font=\small,anchor=west] at (2.42,-1.4) {$i=2,\ x=5$};
  \node[font=\small,anchor=north west,align=left] at (-0.75,-2.0)
    {complement $=10-5=5$, not in \texttt{seen} yet; store $5\mapsto2$};
\end{tikzpicture}

Step 4 — i = 3, x = 7. The complement is 3, and 3 is in the map at index 1. Both positions are highlighted: the current element in orange, its partner in green. Return [1, 3].

\begin{tikzpicture}[
  c/.style={draw,thick,minimum size=0.95cm,font=\large\bfseries},
  cur/.style={c,fill=orange!45,very thick},
  hit/.style={c,fill=green!40,very thick},
  lbl/.style={font=\scriptsize\ttfamily}
]
  \node[anchor=south west,font=\small] at (-0.75,0.55) {\texttt{nums}};
  \node[anchor=south east,font=\small] at (5.35,0.55) {\texttt{target} $=10$};
  \foreach \v [count=\i from 0] in {1,3,5,7,9} {
    \ifnum\i=1 \node[hit] at (\i*1.15,0) {\v};
    \else\ifnum\i=3 \node[cur] at (\i*1.15,0) {\v};
    \else \node[c] at (\i*1.15,0) {\v};
    \fi\fi
    \node[lbl] at (\i*1.15,-0.72) {\i};
  }
  \draw[->,very thick] (3.45,-1.5) -- (3.45,-0.6);
  \node[font=\small,anchor=west] at (3.57,-1.4) {$i=3,\ x=7$};
  \node[font=\small,anchor=north west,align=left] at (-0.75,-2.0)
    {complement $=10-7=3$ is in \texttt{seen} at index $1$; return $[1,3]$};
\end{tikzpicture}

Four elements inspected, one lookup each — the array was never scanned twice.

The code

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []                      # no pair (not expected by the problem)

The same idea in Go, using a map[int]int:

func twoSum(nums []int, target int) []int {
	seen := make(map[int]int) // value -> index
	for i, x := range nums {
		if j, ok := seen[target-x]; ok {
			return []int{j, i}
		}
		seen[x] = i
	}
	return nil
}

Complexity

Approach Time Extra space
Brute force \(O(n^2)\) \(O(1)\)
Hash map \(O(n)\) \(O(n)\)

The hash map spends memory to remove the inner loop: each element costs one insert and at most one lookup, both amortised \(O(1)\).

Edge cases worth remembering