Hash Map Interview Patterns and Problems
How hash maps appear in coding interviews — frequency counting, two-sum patterns, grouping, and collision handling.
The most useful data structure in interviews
Hash maps (dictionaries, objects, unordered maps — whatever your language calls them) appear in more interview solutions than any other data structure. They provide O(1) average-time lookups, making them the go-to tool for reducing brute-force O(n²) solutions to O(n). If you are stuck on an interview problem, ask yourself: "Would a hash map help here?" The answer is often yes.
Pattern 1: Complement lookup (Two Sum family)
The classic Two Sum (LeetCode 1) asks: given an array and a target, find two numbers that add up to the target. The brute-force approach checks every pair in O(n²). With a hash map, you iterate once: for each number, check if target - num exists in the map. If yes, you found the pair. If no, store the current number and its index.
Extensions
"Two Sum II" (sorted input) uses two pointers instead, but the hash map approach still works. "Three Sum" (LeetCode 15) reduces to Two Sum by fixing one element and finding a pair among the rest. "Four Sum" (LeetCode 18) adds another layer. The hash map pattern scales to any k-sum problem.
"Subarray Sum Equals K" (LeetCode 560) applies the same idea with prefix sums: store prefix sums in a hash map and check if currentSum - k exists. This is a favorite among interviewers because it combines two concepts.
Pattern 2: Frequency counting
Counting occurrences is the simplest hash map pattern but appears in dozens of problems.
Character frequency
"Valid Anagram" (LeetCode 242) counts character frequencies in two strings and compares. "First Unique Character" (LeetCode 387) finds the first character with count 1. "Top K Frequent Elements" (LeetCode 347) counts element frequencies, then extracts the k most common using a heap or bucket sort.
Majority element
LeetCode 169 asks for the element appearing more than n/2 times. A hash map solution counts frequencies and returns the winner. Boyer-Moore voting algorithm does it in O(1) space, but the hash map approach is often sufficient and easier to explain under interview pressure.
Pattern 3: Grouping by key
Hash maps naturally group elements that share a property. "Group Anagrams" (LeetCode 49) groups strings by their sorted form: the sorted string becomes the key, and all anagrams map to the same bucket.
This pattern extends broadly. Group intervals by overlap, group points by slope (for "Max Points on a Line"), or group nodes by level in a tree. Whenever you need to partition data by some equivalence, a hash map is the right tool.
Pattern 4: Seen-before tracking
"Contains Duplicate" (LeetCode 217) checks if any value appears twice. Add each element to a set (a hash map with only keys); if the element already exists, return true. This is O(n) time and O(n) space.
Longest consecutive sequence
LeetCode 128 asks for the longest consecutive sequence in an unsorted array. Put all elements in a set. For each element, check if it is the start of a sequence (i.e., num - 1 is not in the set). If so, count how many consecutive elements follow. This is O(n) because each element is visited at most twice.
Happy number
LeetCode 202 asks if repeatedly summing the squares of digits eventually reaches 1. Use a set to track seen numbers. If you see a number again before reaching 1, you are in a cycle and the number is not happy. Alternatively, use Floyd's cycle detection with fast and slow pointers.
Pattern 5: Index tracking
Sometimes you need to know not just whether an element exists, but where it is. Hash maps that store indices enable this.
"Contains Duplicate II" (LeetCode 219) asks if any duplicate is within k positions. Store each element's most recent index. When you see an element again, check if the distance is at most k. This is O(n) time.
The LRU Cache (LeetCode 146) combines a hash map for O(1) lookups with a doubly linked list for O(1) eviction. The hash map stores keys mapped to linked list nodes. On access, move the node to the front. On insertion when full, evict the tail. This is one of the most commonly asked design problems.
Pattern 6: Prefix sums with hash maps
Prefix sums paired with hash maps solve "count subarrays with sum k" problems efficiently. Maintain a running sum and a hash map of how many times each sum has appeared. For each new prefix sum, the number of subarrays ending here with sum k equals the count of prefixSum - k in the map.
This pattern appears in "Subarray Sum Equals K" (LeetCode 560), "Continuous Subarray Sum" (LeetCode 523), and "Count Number of Nice Subarrays" (LeetCode 1248).
When not to use a hash map
Hash maps use O(n) space. If the problem constraints suggest O(1) space, consider sorting (O(n log n) time but O(1) extra space) or bit manipulation. If the keys are small integers, a fixed-size array is faster and simpler. If ordering matters, use a tree map or sorted structure instead.
For interview practice, building hash map intuition is one of the highest-leverage investments you can make. Tools like Phantom Coder can help you spot when a hash map applies to a problem you are working on.
Ready to ace your next interview?
Phantom Coder gives you real-time AI assistance, invisible to screen sharing.
Download for macOS — $99/mo