001. Two Sum

Quick Identifier

• Topic: arrays-hashing
• Pattern: Hash Map (Complement Lookup)
• Hint: Don't look forward for a matching pair; look backward. Store what you've seen in a map and ask, "Have I already seen the number I need?"
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Bloomberg, Apple
• LeetCode: 1

Quick Sights

• Time Complexity: O(n). We traverse the array exactly once. Hash map lookups and insertions are $O(1)$ amortized time.
• Space Complexity: O(n). In the worst case (the valid pair is at the very end of the array), we will store $n-1$ elements in the hash map.
• Core Mechanism: As we iterate through the array, we calculate the complement (i.e., target - current_number). We check if this complement already exists in our hash map of previously seen numbers. If it does, we have found our pair. If it doesn't, we add the current_number and its index to the hash map and continue.

Concept Explanation

As a senior engineer, the leap in logic for Two Sum is realizing that nested loops $O(n^2)$ are entirely redundant because they repeatedly check numbers you've already analyzed.

Instead of searching the array for a partner, we flip the logic: we maintain a registry (a Hash Map) of every number we've encountered so far.

1. The Registry: When you evaluate a number, you immediately know exactly what number you need to hit your target (need = target - current).
2. The Lookup: You simply ask the registry, "Hey, have you seen my need?"
3. The Guarantee: Because you are looking backward at numbers you've already processed, you guarantee that you never accidentally use the same index twice. If the registry says "Yes, I saw it at index i", you immediately return your current index and i.
4. The Update: If the registry says "No", you add your current number and its index to the registry so that future numbers can pair with you.

Diagram

This flowchart illustrates the single-pass $O(n)$ hash map logic.

Study Pattern (SDE3+)

• 0–3 min: This is the most famous algorithmic question. Immediately state the $O(n)$ time / $O(n)$ space hash map solution. Acknowledge that a two-pointer approach exists but would require sorting, which takes $O(n \log n)$ and ruins the original indices unless you map them first.
• Implementation pass: Use a Map in JS or map[int]int in Go. Be careful to check for existence in the map before adding the current number to the map. This prevents a number from accidentally pairing with itself if target = current * 2.
• 5 min extension: Discuss what happens if the array is absolutely massive (e.g., 100GB on disk) and cannot fit in memory. You would discuss external sorting algorithms (like merge sort chunks) and then applying the two-pointer approach on disk blocks, trading the impossible $O(n)$ RAM requirement for heavy disk I/O.

Approaches

• Brute force — Nested loops checking every pair $i$ and $j$. Time: $O(n^2)$, Space: $O(1)$.
• Two Pointers (Sorted) — Sort the array, place pointers at start and end. If sum is too big, move right pointer left. If too small, move left pointer right. Time: $O(n \log n)$, Space: $O(n)$ (to store original indices before sorting).
• One-Pass Hash Map — Time: $O(n)$, Space: $O(n)$. (Always pick this)

Optimal Solution

Go

func twoSum(nums []int, target int) []int {
	seen := make(map[int]int)

	for i := 0; i < len(nums); i++ {
		current := nums[i]
		need := target - current

		// Check if we've already seen the complement
		if priorIndex, exists := seen[need]; exists {
			return []int{priorIndex, i}
		}

		// If not, record the current number and its index
		seen[current] = i
	}

	return nil
}

JavaScript

function twoSum(nums, target) {
	const seen = new Map();

	for (let i = 0; i < nums.length; i++) {
		const current = nums[i];
		const need = target - current;

		// Check if we've already seen the complement
		if (seen.has(need)) {
			return [seen.get(need), i];
		}

		// If not, record the current number and its index
		seen.set(current, i);
	}

	return [];
}

Walkthrough

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

Output: [0, 1]

(If nums = [3, 2, 4], target = 6)

Edge Cases

• Duplicate numbers forming the target (e.g. [3,3], target 6). Because we check the map before inserting the current 3, the second 3 looks at the map, sees the first 3, and successfully pairs with it.
• Negative numbers and zero. Hash maps handle negative keys perfectly fine.

Pitfalls

• Storing all numbers in the hash map first in a separate loop. While this works, you have to write extra logic to ensure an element doesn't pair with itself if target == num * 2. The single-pass approach elegantly avoids this.
• Returning the values instead of the indices.

Similar Problems

• 167. Two Sum II — Input Array Is Sorted — The sorted variant where O(1) space is required using Two Pointers.
• 15. 3Sum — Harder variant combining sorting and Two Sum logic to find triplets.

Mind-Map Tags

#arrays #hashmap #two-sum #complement-lookup #indices