Algorithms from zero
The ''''seen'''' pattern
Imagine you are given an array [5, 2, 9, 11] and asked: do any two numbers add up to 14? A naive approach: for each number, scan the rest of the array to see if its complement is there. That is O(n²). But here is the key: as you traverse the array once, keep a set of numbers you have already seen. For each new number x, check whether (target - x) is in the set. If yes, you found the pair. If no, add x to the set. One pass, O(n) time. This is the seen pattern, and it transforms many O(n²) scans into one O(n) journey.
After this lesson you can build and use a “seen” hash set to solve two-sum on an unsorted array in O(n) time, understand why the seen pattern turns nested loops into single passes, detect duplicates using a seen set, find the intersection of two arrays, detect cycles in a linked list by remembering visited nodes, and recognize the shape: “have I seen something that completes the answer?” — store as you go, check as you go.
The problem we are solving:
You are given an array [5, 2, 11, 9] and a target sum of 14. Find two numbers that add up to 14.
One approach: nested loops.
function twoSumNaive(arr, target) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === target) {
return [i, j]; // Return indices
}
}
}
return null; // No pair found
}This is O(n²): for each element, you scan the rest of the array. For large inputs, this is slow.
The seen pattern idea:
Instead, traverse the array once. As you go, keep a hash set of numbers you have seen so far. For each number x, ask: is (target - x) in the set? If yes, you found the pair and you are done. If no, add x to the set and move on.
function twoSumSeen(arr, target) {
const seen = new Set();
for (let num of arr) {
const complement = target - num;
// Have I seen the complement before?
if (seen.has(complement)) {
return [complement, num]; // Found the pair
}
// No, so add this number to the set and continue
seen.add(num);
}
return null; // No pair found
}One loop, O(n) time. One set, O(n) space. The set lets you check “have I seen X?” in O(1).
Why it works:
- First element: add it to the set.
- Second element: check if its complement is in the set. If yes, done. If no, add it.
- Third element, onwards: same logic.
Because the set stores all elements seen so far, and set membership is O(1), the total time is O(n) with one pass.
The seen pattern shape:
The pattern is: store as you go, check as you go.
- Iterate through the data.
- For each element, ask: “have I seen something that completes the answer?”
- If yes, you found it.
- If no, remember this element and continue.
This shape works for:
- Two-sum: have I seen the complement?
- Duplicate detection: have I seen this value before?
- Intersection: have I seen this element in the first array?
- First duplicate: have I seen this value before (return it)?
- Cycle detection: have I visited this node before?
Two-sum tradeoff: hash map vs. two-pointer.
If the array is unsorted, the seen pattern (hash map) is O(n) time, O(n) space.
If the array is sorted, the two-pointer pattern is O(n) time, O(1) space — no extra memory. But sorting an unsorted array takes O(n log n), which is slower than hashing.
Choose the seen pattern for unsorted data. Choose two-pointer for sorted data.
1. Two-sum with a hash map (return indices):
function twoSum(nums, target) {
const map = new Map(); // value → index
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
// Have I seen the complement before?
if (map.has(complement)) {
return [map.get(complement), i]; // Return the two indices
}
// No, so store this number and its index
map.set(nums[i], i);
}
return null; // No pair found
}
const result = twoSum([2, 11, 15, 3], 9);
console.log(result); // [0, 1] — indices of 2 and 7? No, wait...
// Actually: 2+11=13, 2+15=17, 2+3=5, 11+15=26, 11+3=14, 15+3=18
// Hmm, no pair sums to 9. Try [2, 7, 11, 15], target 9:
// 2+7=9 ✓
const result2 = twoSum([2, 7, 11, 15], 9);
console.log(result2); // [0, 1]2. Detect the first duplicate using a seen set:
function findFirstDuplicate(arr) {
const seen = new Set();
for (let num of arr) {
if (seen.has(num)) {
return num; // Found the first duplicate
}
seen.add(num);
}
return null; // No duplicates
}
console.log(findFirstDuplicate([1, 2, 3, 2, 4])); // 2
console.log(findFirstDuplicate([1, 2, 3, 4])); // null3. Find the intersection of two arrays:
function intersection(arr1, arr2) {
const set1 = new Set(arr1);
const result = new Set();
// For each element in arr2, check if it was in arr1
for (let num of arr2) {
if (set1.has(num)) {
result.add(num); // Add to result (avoid duplicates with a set)
}
}
return Array.from(result);
}
console.log(intersection([1, 2, 2, 1], [2, 2])); // [2]
console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4])); // [9, 4] or [4, 9]Try the two-sum example:
Let us trace the two-sum seen pattern on [2, 7, 11, 15] with target 9:
1
function twoSum(nums, target) {
2
const map = new Map();
3
for (let i = 0; i < nums.length; i++) {
4
const complement = target - nums[i];
5
if (map.has(complement)) {
6
return [map.get(complement), i];
7
}
8
map.set(nums[i], i);
9
}
10
return null;
11
}
Notice: we found the pair on the second element, without looping back. The map stores the first element’s index, and we check it instantly via O(1) lookup.
The seen pattern:
| Operation | Time | Space |
|---|---|---|
| Two-sum (hash map) | O(n) | O(n) |
| Detect first duplicate | O(n) | O(n) |
| Find intersection | O(n + m) | O(n) |
| Detect cycle (linked list) | O(n) | O(n) |
Where n and m are the sizes of the input(s).
Comparison: nested loops vs. seen pattern:
- Nested loops: for each element, scan the rest. n × n = O(n²).
- Seen pattern: one loop, O(1) lookups. O(n).
For n = 1000, nested loops: 1,000,000 operations. Seen pattern: 1,000. The difference grows fast.
Why O(1) lookup matters:
In the two-sum problem, the complement check must be instant. If you searched linearly (O(n) per check), the total would be O(n²) again. Hash maps give O(1) lookup, which is essential.
Why does the seen pattern solve two-sum in O(n) time instead of O(n²)?
In two-sum, why do we store the value and its index in the map, not just add it to a set?
If you use the seen pattern to find the first duplicate in [1, 2, 3, 2, 4], which number is returned?
For unsorted data, is the seen pattern (hash map) or two-pointer better, and why?
If you check for duplicates in an array of 5000 elements using the seen pattern, how many hash operations (add/check) do you perform (approximately)?
lesson.inset.misconception
“The seen pattern is just for two-sum.” Not true. The seen pattern works for any problem where you ask “have I seen something before?” — duplicate detection, intersection, cycle detection, finding the first repeating element, and many more. The shape is universal: store as you go, check as you go.
Edge cases
Empty or single-element input: An empty array has no pairs, so return null. A single-element array cannot have a pair with another element, so return null. Always test these.
Target not reachable: If no pair sums to the target, the loop completes and you return null. The set contains all elements, but none form a pair.
Why is the seen pattern O(n) while a nested loop is O(n²)?
The seen pattern is the practice of storing values you have encountered in a hash set or map as you traverse data, then checking instantly whether you have seen something before.
Key facts:
- Store as you go, check as you go: for each element, check if it (or its complement) is in the set. If yes, you found your answer. If no, add it and continue.
- Time complexity: O(n) because you iterate once and each check is O(1).
- Space complexity: O(n) because the set stores up to n values.
- Common uses:
- Two-sum: have I seen the complement?
- Duplicate detection: have I seen this value?
- Intersection: have I seen this in the first array?
- First duplicate: have I seen this before?
- Cycle detection: have I visited this node?
- Replaces O(n²): the naive approach of nested loops. Seen pattern solves it in one pass.
- Trade memory for speed: O(n) space buys O(n) time instead of O(n²).
You now have a powerful pattern that applies to many real problems. Next, you will explore how collisions in hash functions affect performance, and dive deeper into hash function design.