Algorithms
Hashing Techniques
Difficulty: Beginner
Two Sum was a hard problem in 2010. With a hash map it becomes a six-line interview warm-up: walk the array once, and for each value x ask whether target - x is already in the map. The same shape, single-pass plus complement lookup,...
Hashing Techniques
Two Sum was a hard problem in 2010. With a hash map it becomes a six-line interview warm-up: walk the array once, and for each value x ask whether target - x is already in the map. The same shape, single-pass plus complement lookup, solves "first duplicate," "contains nearby duplicate," "longest substring without repeats," and an entire family of trade-space-for-time problems.
Hashing Techniques catalogs those patterns. You will work through frequency counting (most/least frequent element, group anagrams via sorted-key trick), the two-sum complement template and its three-sum / four-sum extensions, existence checking and duplicate detection, index mapping where you store positions alongside values, and a first conceptual look at rolling hashes that prepare you for Rabin-Karp later. The lesson also discusses when a hash map is overkill versus when it is the obviously correct tool.
In Hash Map (Dictionary) Basics, you saw how hashing achieves expected O(1) insertion and lookup. This lesson is where that constant-time primitive turns into algorithmic leverage: brute-force O(n^2) scans collapse into a single pass that uses the map as an oracle.
From here you move into the paid track with Sorting (Advanced), which trades hash-map lookups for divide-and-conquer to break the O(n^2) sorting barrier.
Prerequisites:
Hash Map (Dictionary) BasicsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Use a hash map to count element frequencies and find the most/least frequent element.
Apply the two-sum complement lookup pattern to find pairs that satisfy a condition.
Use a hash map for O(1) existence checking (first duplicate, contains duplicate).
Use index mapping to track both values and their positions.
Recognize when a hash map is the right tool vs when simpler approaches suffice.
Analyze time and space trade-offs of hash-map-based solutions.
Why This Matters
01
Hash map patterns appear in roughly 30% of coding interview problems — mastering them is the single highest-ROI skill for interviews.
02
Frequency counting, two-sum, and duplicate detection are building blocks that combine with other techniques like sliding window and sorting.
03
Hash maps turn O(n^2) brute-force solutions into O(n) solutions by trading space for time.
04
These patterns are also fundamental in real-world applications: log analysis, deduplication, caching, and indexing.
Key Terms
6 terms you'll encounter in this lesson
Frequency counting
A pattern where a hash map records how many times each element appears. Keys are elements, values are counts.
Complement lookup
A technique where you compute what value is needed (the complement) and check if it exists in the hash map. Used in two-sum: complement = target - current.
Two-sum pattern
For each element, check if target - element exists in the hash map. If yes, you found a pair. If no, store the current element. Solves pair-finding in O(n).
Existence checking
Using a hash set for O(1) lookups to determine if an element has been seen before. Useful for duplicate detection.
Index mapping
Storing the index (position) of each element in a hash map, allowing O(1) lookup of where an element appears.
Anagram
Two strings that contain the same characters in different order. Grouping anagrams uses sorted characters as hash map keys.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Hash maps always use O(n) extra space, so they are wasteful"
The O(n) space is a deliberate trade-off for O(1) lookup time. Going from O(n^2) time to O(n) time is almost always worth O(n) extra space. In practice, the space is modest — a map of n integers uses roughly 8-16 bytes per entry.
"Two-sum requires sorting the array first"
Sorting works (with two pointers) but takes O(n log n) time and destroys original indices. The hash map approach is O(n) time and preserves indices. Use the hash map approach when you need indices; use sorting + two pointers when you only need values.
"A hash set and a hash map are the same thing"
A hash set stores only keys (for existence checking). A hash map stores key-value pairs (for associating data with keys). Use a set when you only need to check 'is X present?'. Use a map when you also need 'what is associated with X?'.