Nitinn S Kulkarni

Posted on Apr 3

🧮 Part 4: Hash Maps and Sets in Python – Lookups, Frequencies, and Fast Problem Solving

#python #dsa #interview #programming

🚀 Introduction

When it comes to efficient lookups, counting, grouping, and deduplication, nothing beats hash-based data structures like:

- dict (hash map)

- set

- defaultdict

- Counter

These are the go-to tools in Python for solving problems in O(1) average time, and they're heavily used in interviews and real-world systems.

In this post, we’ll explore:

✅ Hash map and set fundamentals

✅ Built-in Python tools: dict, set, defaultdict, and Counter

✅ Interview patterns and real-world use cases

✅ Clean, Pythonic solutions to classic problems

🔑 1️⃣ Hash Maps (dict)

A hash map is a key-value store with O(1) average time complexity for insertions, lookups, and deletions.


student_scores = {"Alice": 85, "Bob": 92}
student_scores["Charlie"] = 78
print(student_scores["Bob"])  # 92

🔹 Real Uses:
- Caching results
- Counting occurrences
- Mapping relationships (e.g., graph edges)

🧮 2️⃣ Frequency Counting with Counter


from collections import Counter

s = "mississippi"
freq = Counter(s)
print(freq['s'])  # 4

✅ Super useful for:

-   Anagrams

- Top K frequent elements

- Histogram problems

🧰 3️⃣ Grouping with defaultdict


from collections import defaultdict

grouped = defaultdict(list)
words = ["eat", "tea", "tan", "ate", "nat", "bat"]

for word in words:
    key = ''.join(sorted(word))
    grouped[key].append(word)

print(grouped.values())
# Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

✅ Avoids key errors and automatically initializes containers

🔎 4️⃣ Fast Lookups with Sets


seen = set()
seen.add(10)
print(10 in seen)  # True

Sets are unordered collections of unique items. Great for:

- Removing duplicates

- Fast existence checks

- Solving 2-sum-like problems efficiently

🧪 5️⃣ Common Interview Problems

✅ Two Sum (Leetcode #1)


def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

✅ Group Anagrams (Leetcode #49)


from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for word in strs:
        key = ''.join(sorted(word))
        groups[key].append(word)
    return list(groups.values())

✅ Longest Substring Without Repeating Characters (Leetcode #3)


def length_of_longest_substring(s):
    seen = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

✅ Top K Frequent Elements (Leetcode #347)


from collections import Counter
import heapq

def top_k_frequent(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

🧠 6️⃣ Hash Map Patterns You Must Know

Pattern	Use Case
Counting with Counter	Frequencies, modes, majority element
Index Mapping with dict	Fast access, graph edges
Sliding Window + Hash Map	Longest substring, minimum window substring
Set Membership	Fast lookup, detect duplicates
Reverse Mapping	Flip keys and values

🧪 7️⃣ Real-World Applications

Application	Data Structure
DNS caching	Hash map (cache domain/IP)
Spell-checking	Set (fast word lookup)
Chat usernames	Set (enforce uniqueness)
User login states	Dict (user_id → token)
Count words in logs	Counter or defaultdict(int)

✅ Best Practices

✔️ Use Counter for counting instead of manual loops
✔️ Use defaultdict to simplify grouping
✔️ Use sets when you only care about existence or uniqueness
✔️ Avoid using mutable types (like lists) as dict/set keys
❌ Don't use list.count() in loops – it's O(n)

🧠 Summary

✔️ Hash maps and sets are essential tools for solving problems efficiently
✔️ Python gives you dict, set, Counter, and defaultdict – power tools in your DSA arsenal
✔️ Know the patterns: counting, grouping, lookup, reverse mapping
✔️ Mastering these unlocks solutions to a ton of real-world and interview-style problems
🔜 Coming Up Next:

👉 Part 5: Recursion and Backtracking – Exploring Trees, Grids, and Puzzle Solvers

We’ll cover:

1. How recursion works under the hood
2. Recursive patterns
3. Backtracking templates (Sudoku, permutations)
4. Transitioning from recursion to DP

💬 Have a favorite Counter or defaultdict trick? Tried solving 2-sum with brute force before learning hash maps? Let’s chat in the comments! 🧠✨

DEV Community