Hash Map
The Hash Map Pattern
Remember what you have already seen so a later step can look it up in O(1) on average instead of rescanning. The everyday forms: look up a complement (Two Sum), count frequencies (Valid Anagram, Top K Frequent Elements), group items under a key they share (Group Anagrams), and test membership with a set when only presence matters (Longest Consecutive Sequence).
Interactive problems
Free to open
How do you recognise a hash map problem?
The brute force is a nested loop whose inner loop asks "have I seen X before?", "how many times?" or "which items share this?" — a hash map answers each.
What is the time complexity of the hash map pattern?
O(n) time on average for one pass with O(1) average lookups, paid for with O(n) extra space for the map — against O(n²) time and O(1) space for the nested loop.
Hash Map practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Hash Map problems by difficulty and complexity
The difficulty, running time and extra space of every hash map solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Two Sum | Easy | Ω(1) | Θ(n) | O(n) | O(n) |
| Valid Anagram | Easy | Ω(1) | Θ(n) | O(n) | O(k) |
| Group Anagrams | Medium | Ω(n · k log k) | Θ(n · k log k) | O(n · k log k) | O(n · k) |
| Top K Frequent Elements | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Longest Consecutive Sequence | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
Related patterns and concepts
The underlying technique is covered from first principles in the hash map lesson in the DSA visualizer curriculum. Hash Map is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 23 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree