Pattern Recognition for Algorithms
This guide starts from two questions I want answered for every problem on NeetCode 250. First, given a problem, how do I map it to the algorithm it actually needs, which means understanding when that algorithm is useful in the first place, not just what it does. Second, once I know which algorithm fits, what shape does the code for it usually take.
So for every pattern, hashing, two pointers, sliding window, whatever comes next, I am not just recording the code that solves a category of problems. I am trying to write down the specific signal in a problem statement that should make a pattern come to mind before any code gets written.
Each pattern gets split into three files, and the split maps onto three separate questions.
intro.md answers what the tool actually is, stripped of any problem attached to it. For hashing, that means starting with the plainest possible definition, a hash map is key-value storage, and only then getting into how it behaves in memory and what shape it takes in a specific language.
intuition.md answers when the tool applies. This is the file I care about most, since recognition is the harder half once the syntax is memorized. Rather than one broad rule, each pattern gets broken into a small number of plain questions a problem might secretly be asking, seen before, how many times, does something else complete this, which things belong together, for hashing specifically. Each question comes with one real problem worked through in full, no code, just the reasoning for why that problem is that question in disguise.
implementation.md answers how the code looks once we already know which question we are answering. These are the skeletons worth knowing from memory, so that recognizing the pattern is the only hard part left, writing it becomes mechanical.
Hashing is finished first, working through Contains Duplicate as the walked example under its matching question. More patterns follow the same three-file shape as they get written.
Hashing
What a hash map actually is
A hash map is key-value storage. That’s it. You give it a key, it gives you back the value stored under that key.
Say we have an array [2, 4, 2, 5, 4, 4] and we want to store the frequency of each element. A hash map can hold this as an element-to-frequency store, where the key is the element and the value is how many times it showed up.
4 -> 3
5 -> 1
2 -> 2
Read or write to any key, and the cost is the same regardless of how many keys are already in the map.
Hash maps in JavaScript
JavaScript gives us three structures that are really this same key-value idea, just shaped for different needs.
Object is the plain version, keys are coerced to strings, and it is what most people reach for first without thinking of it as a hash map.
Map is the general-purpose version, any value can be a key, insertion order is preserved, and it has a proper .has(), .get(), .set() interface. Use it whenever we need both a key and a value attached to it, like the frequency counts earlier in this chapter.
Set is a hash map with the value dropped, it only stores keys and answers one question, .has(key). Use it whenever the value we would store is meaningless and all we care about is whether the key exists at all, which is exactly the “Seen Before” bucket.
Intuition
Thinking about it in terms of memory
Underneath, a hash map is still an array. The map keeps a plain array in memory, and a hash function converts each key into an index into that array. Writing map[key] = value really means: compute hash(key), land on a slot in the underlying array, store the value there. Reading map[key] runs the same computation and jumps straight to that slot.
That jump is the whole trick. There is no scanning. Whether the map holds ten entries or ten million, computing hash(key) and landing on a slot costs the same. That is where the O(1) average lookup comes from, it is one array access after one computation, not a search through the array.
A hash map trades the searching step for a computing step. Without one, checking “have I seen this value” means walking every element already visited, a search whose cost grows with how much we have stored. With one, checking the same thing means running the value through hash() and looking at one slot, a cost that stays flat no matter how much we have stored. The map does not get faster at searching, it removes the need to search at all.
This is the thing to internalize before looking at any specific problem. Every hashing problem is a disguised version of “I need to search for something, repeatedly, as I go.” The hash map is what turns that repeated search into a repeated computation instead.
When to reach for a hash map
I am going to throw some hints for identifying the usage of maps, but they won’t be understandable at first glance. Which is why I’ll walk you through examples for each of these intuitions.
- Seen Before: have I run into this value already?
- Frequency: how many times has this value shown up?
- Pairing: is there another value out there that completes this one?
- Grouping: which values belong together?
Whenever a problem’s brute force reads as “for each element, scan the rest to check something,” that “something” is the candidate for going into a map first.
Each of these four questions gets a full worked problem in the Examples chapter that follows, reasoning and code together.
Implementation
Once a problem is recognized as one of the four buckets from the intuition chapter, the code follows a fixed shape. These are the four skeletons, one per bucket, worth knowing from memory rather than re-derived each time.
Seen Before
function seenBefore(items) {
const seen = new Set();
for (const item of items) {
if (seen.has(item)) return true; // already ran into this one
seen.add(item);
}
return false;
}
Frequency
function frequency(items) {
const counts = new Map();
for (const item of items) {
counts.set(item, (counts.get(item) || 0) + 1);
}
return counts;
}
Pairing
function pairing(nums, target) {
const seen = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) return [seen.get(complement), i];
seen.set(nums[i], i);
}
return [];
}
The check happens before the insert, not after. That order matters, it is what stops a value from pairing with itself.
Grouping
function grouping(items, keyFn) {
const groups = new Map();
for (const item of items) {
const key = keyFn(item);
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(item);
}
return [...groups.values()];
}
keyFn is whatever computed property decides which bucket an item belongs to, a sorted string for anagrams, a row or column index for a grid, whatever the problem defines as “belongs together.”
Intuition in Action
Worked problems from the intuition chapter, reasoning and code together, one bucket at a time.
Seen Before
Contains Duplicate hands us an array and asks a single question, does any value in it show up more than once. Nothing about order matters, nothing about position matters, the only thing that matters is whether a value repeats anywhere in the array.
The naive way to answer that is to pick a value and check it against every other value in the array, then move to the next value and do the same thing again. That works, but it means for every single element we are re-reading the whole array to answer one yes-or-no question. The work we redo on every step is identical in shape, “is this value present among the ones I have already looked at.”
That repeated shape is the tell. If the question we keep re-asking is always “have I already looked at this value,” we do not need to re-read anything, we just need to remember what we have already looked at. That is exactly what a hash map gives us, a place to record every value the moment we look at it, and a way to check that record in one step instead of a scan.
So the approach becomes: walk the array once, and for each value, first ask the map if it already holds this value. If it does, we have our duplicate and we are done, no need to look further. If it does not, we record it in the map and move to the next value. By the time we reach any given element, the map contains every element that came before it, so checking the map is the same as checking the whole array up to that point, except it costs one lookup instead of a scan. That is why the seen-before question maps directly onto this problem, and why the fix for the repeated O(n) scan is a single hash map built as we go.
// Contains Duplicate
// https://leetcode.com/problems/contains-duplicate/description/
//
// Problem: given an array of integers, return true if any value
// appears at least twice, and false if every element is distinct.
//
// The hint toward a hash map is "appears at least twice" itself,
// that phrase is really asking, for each value: have I run into
// this value already? That is the "Seen Before" intuition, so a
// hash set is the fit, one lookup instead of re-scanning the array.
function containsDuplicate(nums) {
// A Set, not a Map, because we never need a value attached to
// the key. All we ever ask is "does this key exist," so a Map
// here would just be storing a throwaway value like true next
// to every key. Set is the key-only shape of a hash map.
const seen = new Set();
for (const n of nums) {
// Ask the set first. If it already holds this value,
// we found our duplicate, no need to look any further.
if (seen.has(n)) return true;
// Otherwise this is the first time we've seen n.
// Record it so future values can check against it.
seen.add(n);
}
// Walked the whole array, every value was new when we reached it.
return false;
}
module.exports = { containsDuplicate };
Contains Duplicate II asks the same seen-before question with one more condition attached, a repeat only counts if the two indices are within k of each other. So “have I seen this value” is not enough on its own anymore, we also need to know where we saw it.
That changes what the map has to hold. Instead of a set that only answers yes or no, we need a map from value to the index it last appeared at. The check on each element becomes two parts, has this value shown up before, and if so, is the gap between here and there small enough to count.
The map still gets written to on every element, whether or not that element triggers a match, because a value seen too far back to count now might still be close enough to count against a later index. Overwriting the last-seen index each time keeps the stored position as recent as possible, which is exactly what the distance check needs.
// Contains Duplicate II
// https://leetcode.com/problems/contains-duplicate-ii/description/
//
// Problem: given an array of integers and an integer k, return true
// if there are two distinct indices i and j such that nums[i] ==
// nums[j] and the distance between i and j is at most k.
//
// Strip away the k constraint for a moment and this is just Contains
// Duplicate again, does any value repeat (that's what nums[i] == nums[j] means right?) , answered by remembering
// every value we pass. The k constraint doesn't change that core
// question, it only restricts which repeats are allowed to count.
// A far-apart repeat is not a match here, so knowing a value repeated
// is no longer enough, we also need to know how far apart the two
// occurrences are. That means the map can't just record "seen or
// not," it has to record the index each value was last seen at, so
// the distance can actually be checked when a repeat shows up.
function containsNearbyDuplicate(nums, k) {
const lastSeenAt = new Map(); // value -> most recent index
for (let i = 0; i < nums.length; i++) {
const n = nums[i];
if (lastSeenAt.has(n) && i - lastSeenAt.get(n) <= k) {
return true;
}
// Record (or overwrite) this value's most recent position,
// so the next repeat only measures distance from here.
lastSeenAt.set(n, i);
}
return false;
}
module.exports = { containsNearbyDuplicate };
Longest Consecutive Sequence gives an unsorted array and asks for the length of the longest run of consecutive integers hiding inside it, in O(n) time. “Consecutive” here means back to back on the number line, not back to back in the array. Take [100, 4, 200, 1, 3, 2], scattered in that order, but 1, 2, 3, 4 sit next to each other once we think in terms of value rather than position, and no longer run in the array beats that, so the answer is 4.
Sorting first would make the run easy to spot, [1, 2, 3, 4, 100, 200] has the run sitting right next to itself, but sorting itself already costs O(n log n), which rules it out before we even get to the counting.
Without sorting, we still have to figure out which numbers keep the consecutive sequnce going, and the only tool we start with is the raw array. Take 1 from our example array. To know the run keeps going, we need to know whether 2 shows up anywhere in [100, 4, 200, 1, 3, 2], which means scanning the array looking for it. It does, so we check for 3 the same way, another full scan, then 4, another scan, then 5, one more scan that comes back empty and stops the run there.
That is four scans just to measure the run starting at 1. Now consider that we do not know in advance where a run starts, so in the worst case this same scan-for-the-next-number step gets repeated starting from every single number in the array. Each of those scans costs O(n) on its own, and we potentially do one for every element, which multiplies out to O(n^2) overall, the exact cost we were trying to avoid by skipping the sort.
Look at what actually got repeated across all those scans: the same question, is this specific number present in the array, asked over and over with a different number each time. Answering it by scanning costs O(n) per question, and we are asking it many times, which is where the O(n^2) comes from. What we need instead is a way to answer that same question in one step, not a scan.
That means recording every number somewhere we can check instantly, before doing any counting. A set does exactly that, so put every number in the array into a set first. After that, asking “is n + 1 present” is a single lookup, not a search across the array, the same fix that turned Contains Duplicate from a scan into a seen-before check.
This puts the solution in two separate passes. The first pass walks the original array once, just to load every number into the set. The second pass walks the set, not the array, doing the actual counting. Iterating the set instead of the array also means a number that appears more than once in the input only gets processed once, since the set already collapsed it to a single entry.
That alone still leaves a second problem, counting from every number would recount the same run many times, once from each of its members. Take 1, 2, 3, 4 from the example, if we counted forward from 1, then again from 2, then again from 3, we would redo the same run three extra times.
The fix is to make each number disappear from the set the moment it gets counted. Walk the set, and for a number still there, delete it, then expand outward from it, right first, then left, deleting every neighbor as it gets pulled into the run. A number that already got absorbed into an earlier run is already gone from the set by the time the outer walk would have reached it, and a set’s iterator skips entries that were already deleted, so it is simply never visited a second time. Every number gets deleted exactly once, and every deletion happens during exactly one expansion, so the total work across every run put together is still O(n).
// Longest Consecutive Sequence
// https://leetcode.com/problems/longest-consecutive-sequence/description/
//
// Problem: given an unsorted array of integers, return the length of
// the longest run of consecutive integers, in any order in the input,
// solved in O(n) time.
//
// The seen-before question here is "is this value present in the
// array at all," asked over and over as we try to extend a run.
// A set answers that in one lookup instead of a scan, which is what
// keeps the whole thing linear.
function longestConsecutive(nums) {
// This is the first pass, even though there's no visible loop.
// Set(nums) walks nums once internally to load every value in.
const present = new Set(nums);
let longest = 0;
// Second pass, over the set, not nums, so a value repeated in
// the input only gets processed once here.
for (const n of present) {
// No need to check whether n was already claimed by an
// earlier run. If it was, it was deleted below before this
// loop reached it, and a Set's iterator skips entries that
// were already deleted, so n simply never shows up here.
present.delete(n);
let length = 1;
// Expand right, deleting each number as it joins this run so
// no later iteration step processes it again.
let right = n + 1;
while (present.has(right)) {
present.delete(right);
length++;
right++;
}
// Expand left the same way.
let left = n - 1;
while (present.has(left)) {
present.delete(left);
length++;
left--;
}
longest = Math.max(longest, length);
}
return longest;
}
module.exports = { longestConsecutive };