1. Two Sum

At a Glance

• Topic: arrays-hashing
• Pattern: Hash Map Lookup
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Bloomberg, Apple
• Frequency: Very High
• LeetCode: 1

Problem (one-liner)

Given an integer array numbers and an integer target, return the indices of the two distinct elements whose values sum to target. Exactly one valid pair exists.

Recognition Cues

• "Indices of two numbers such that they add up to target"
• "Return the answer as [index1, index2]" with order unspecified or ascending
• Unsorted array; pair sum constraint

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 — O(n²) time / O(1) space — try every unordered pair.
• Better — sort + two pointers — O(n log n) time / O(n) space — loses original indices unless you pair values with indices first.
• Optimal — O(n) time / O(n) space — one pass: map each value to index; for each current, look up target - current.

Optimal Solution

Go

package main

func twoSum(numbers []int, target int) []int {
	seen := make(map[int]int)
	for index := range numbers {
		current := numbers[index]
		need := target - current
		if priorIndex, exists := seen[need]; exists {
			return []int{priorIndex, index}
		}
		seen[current] = index
	}
	return nil
}

JavaScript

function twoSum(numbers, target) {
	const seen = new Map();
	for (let index = 0; index < numbers.length; index++) {
		const current = numbers[index];
		const need = target - current;
		if (seen.has(need)) {
			return [seen.get(need), index];
		}
		seen.set(current, index);
	}
	return [];
}

Walkthrough

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

Invariant: seen holds each value seen so far mapped to its index; complement lookup finds the partner in one step.

Edge Cases

• Pair uses same value twice only if two distinct indices exist (e.g. [3,3], target 6).
• Negative numbers and zero are fine with the hash map.
• Minimum length is 2 per problem guarantee.

Pitfalls

• Returning values instead of indices.
• Using sort + two pointers without preserving original indices.
• Assuming sorted input.

Similar Problems

• 167. Two Sum II — Input Array Is Sorted — sorted array, two pointers.
• 242. Valid Anagram — complementary counting / multiset idea.
• 217. Contains Duplicate — hash structure for membership.

Variants

• Count all pairs summing to target (with duplicates) → frequency map + combinatorics.
• Three sum → sort + fix one index + two pointers.
• k closest sum → sort + two pointers + track best diff.

Mind-Map Tags

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