Sets & the two-sum trick
How a hash set turns an O(n²) search into a single O(n) pass. · 6 min read
A hash set is a hash table that stores only keys — membership in O(1). That single power collapses a lot of brute-force scans.
The classic is two-sum: find two numbers that add up to a target. Brute force checks every pair — O(n²). With a set you do it in one pass: for each number, ask whether its complement has already been seen.
def two_sum(nums, target):
seen = set()
for x in nums:
if target - x in seen: # O(1)
return True
seen.add(x)
return FalseThe same idea in C++ uses unordered_set, which is the standard-library hash set:
bool twoSum(vector<int>& nums, int target) {
unordered_set<int> seen;
for (int x : nums) {
int need = target - x;
if (seen.count(need)) return true;
seen.insert(x);
}
return false;
}Interactive visualization: Each lookup hashes straight to a bucket — step through it frame by frame on this page.
brute force: every pair— Two nested loops → n(n−1)/2 checks.⟹ O(n²)— Quadratic.hash set: one pass, O(1) lookups— Trade O(n) memory for speed.⟹ O(n) time— Linear.
Result: O(n²) → O(n)
Practice: Two Sum (Easy) — Find the two indices whose values add up to a target.
Practice: Contains Duplicate (Easy) — Does any value appear at least twice?
Practice: Group Anagrams (Hard) — Bucket words by their sorted-letter signature.