Intuition — real-life analogies

Map / dict

Phonebook

Name (key) → Phone number (value). You look up a name, instantly get the number. No scanning through all entries — jump straight to it.

Key insight: pairs of (key, value). Every key is unique. Values can repeat.

Set

Guest list

A list of unique attendees. You care only about membership — is this person invited? No duplicates. No order matters.

Key insight: uniqueness only. No values, no order, just existence.

When to use which?

Question	Use	Why
"Does X exist?"	Set	O(1) membership check
"What is the value for X?"	Dict	Key → value lookup
"How many times does X appear?"	Dict	Frequency counting
"Find duplicates / unique items"	Set	Auto-deduplication
"Group items by category"	Dict	Key = category, val = list
"Common items between two groups"	Set	intersection()

The core rule: if you need to associate a value with a key → dict. If you only need to know presence/absence → set.

Definitions

Map (Python: dict)

A collection of key-value pairs where each key is unique. Implemented internally as a hash table.

# Python dict = HashMap phonebook = {"Alice": 9876, "Bob": 1234} # key="Alice", value=9876

Property	dict
Keys unique?	Yes — duplicate key overwrites
Values unique?	No — duplicates allowed
Ordered?	Yes (insertion order, Python 3.7+)
Mutable?	Yes — add, update, delete freely
Key type requirement	Must be hashable (immutable)

Set (Python: set)

An unordered collection of unique elements. Internally, it's a hash table that only stores keys (no values).

guests = {"Alice", "Bob", "Alice"} print(guests) # {'Alice', 'Bob'} — deduped

Property	set
Elements unique?	Yes — automatically
Ordered?	No — no guaranteed order
Mutable?	Yes (use frozenset for immutable)
Element type	Must be hashable

HashMap

Conceptual name used in CS/Java. In Python, dict IS the HashMap. Same O(1) operations, same hash table internals.

HashSet

Conceptual name used in CS/Java. In Python, set IS the HashSet. A hash table storing only keys.

Java/C++ say HashMap/HashSet. Python says dict/set. They're the same concept — tell interviewers you know both.

Hashing — interactive visualizer

How it works (high-level)

A hash function converts any key into an integer index. That index tells Python exactly which bucket to put/find the value — no searching needed.

# Python internally does something like: index = hash(key) % num_buckets table[index] = value # O(1) — direct placement

Try it — hash visualizer

hash(key)

—

bucket (hash % 8)

—

items stored

0

Collision: two keys land in the same bucket. Python handles this via open addressing — it finds the next free slot.

Hashable vs unhashable

Type	Hashable?	Can be a dict key / set element?
int, float, str, tuple	Yes	Yes
bool, None	Yes	Yes
list	No	No — TypeError
dict	No	No — TypeError
set	No	No (use frozenset)

# This FAILS: d = {[1,2]: "value"} # TypeError: unhashable type: 'list' # Fix: use tuple as key d = {(1,2): "value"} # OK

Map vs Set vs List vs Tuple

Feature	dict	set	list	tuple
Stores	key-value pairs	unique elements	ordered elements	ordered elements
Ordered?	Yes (3.7+)	No	Yes	Yes
Duplicates?	Values yes, keys no	No	Yes	Yes
Mutable?	Yes	Yes	Yes	No
Lookup	O(1) by key	O(1) membership	O(n) search	O(n) search
Index access?	By key only	No	Yes (d[i])	Yes (d[i])
Use when	key→value map	unique items	ordered sequence	immutable sequence
Memory	High	Medium-high	Low	Lowest

Literal syntax

d = {"a": 1, "b": 2} # dict s = {1, 2, 3} # set l = [1, 2, 3] # list t = (1, 2, 3) # tuple e = {} # EMPTY DICT, not set! es = set() # empty set (must use set())

Common mistake: {} creates an empty dict, NOT a set. Always use set() for an empty set.

Python API — dict and set

dict methods

Method	What it does	Returns
d.get(k, default)	Get value, no KeyError if missing	value or default
d.keys()	All keys	dict_keys view
d.values()	All values	dict_values view
d.items()	All (key, value) pairs	dict_items view
d.update(other)	Merge another dict in	None
d.pop(k, default)	Remove key, return value	value or default
d.setdefault(k, v)	Get key; insert v if missing	existing or new value
k in d	Membership test O(1)	bool

# get() vs direct access d = {"a": 1} d["b"] # KeyError! d.get("b", 0) # 0 — safe default # setdefault — very useful for grouping d = {} d.setdefault("fruits", []).append("apple") d.setdefault("fruits", []).append("mango") # d = {"fruits": ["apple", "mango"]} # items() iteration (most common pattern) for k, v in d.items(): print(k, v)

set methods

Method	What it does	Alt syntax
s.add(x)	Add element	—
s.remove(x)	Remove — KeyError if missing	—
s.discard(x)	Remove — no error if missing	—
s.union(t)	All elements from both	s \| t
s.intersection(t)	Elements in both	s & t
s.difference(t)	In s but not in t	s - t
s.issubset(t)	All of s in t?	s <= t
x in s	Membership O(1)	—

a = {1, 2, 3, 4} b = {3, 4, 5, 6} a | b # {1,2,3,4,5,6} union a & b # {3,4} intersection a - b # {1,2} difference a ^ b # {1,2,5,6} symmetric difference # discard vs remove a.discard(99) # silent — no error a.remove(99) # KeyError!

Useful extras

from collections import defaultdict, Counter # defaultdict — no KeyError on missing keys freq = defaultdict(int) freq["a"] += 1 # no init needed # Counter — frequency dict in one line c = Counter("banana") # Counter({'a':3,'n':2,'b':1}) c.most_common(2) # [('a',3),('n',2)]

Operations — step through

dict operations walkthrough

Press Next to begin

Current dict: {}

All operations — quick reference

# ── INSERT / UPDATE ───────────────────── d = {} d["key"] = "value" # O(1) d.update({"a":1,"b":2}) # O(k) — k items # ── DELETE ────────────────────────────── del d["key"] # O(1), KeyError if missing d.pop("key", None) # O(1), safe d.clear() # O(n) wipes all # ── SEARCH / LOOKUP ───────────────────── "key" in d # O(1) key check d.get("key", 0) # O(1) safe get "val" in d.values() # O(n) value scan! # ── ITERATION ─────────────────────────── for k in d: # O(n) keys for v in d.values(): # O(n) values for k,v in d.items(): # O(n) pairs ← most common # ── SET OPERATIONS ────────────────────── s = {1,2,3} s.add(4) # O(1) s.discard(99) # O(1), safe 2 in s # O(1) ← beats list!

Complexity table

Operation	dict avg	dict worst	set avg	set worst
Insert / Add	O(1)	O(n)	O(1)	O(n)
Delete / Remove	O(1)	O(n)	O(1)	O(n)
Lookup / Membership	O(1)	O(n)	O(1)	O(n)
Iteration	O(n)	O(n)	O(n)	O(n)
union / intersection	—	—	O(m+n)	O(m+n)
Space	O(n)	O(n)	O(n)	O(n)

Worst case O(n) happens on many hash collisions (all keys in one bucket). In practice with Python's dict, this is extremely rare.

Dict vs List — why O(1) matters

dict lookup n=1M

O(1)

list scan n=1M

O(n)

speedup factor

~1,000,000x

O(1) average comes from the hash function mapping directly to the bucket. No iteration needed. This is why x in my_set beats x in my_list for large n.

Patterns and use cases

Frequency counting — interactive

# Pattern: freq map freq = {} for ch in word: freq[ch] = freq.get(ch, 0) + 1 # OR: Counter(word)

5 essential patterns

# 1. Duplicate detection seen = set() def has_dup(lst): for x in lst: if x in seen: return True seen.add(x) return False # 2. Two-sum pattern def two_sum(nums, target): seen = {} # val → index for i, n in enumerate(nums): if target - n in seen: return [seen[target-n], i] seen[n] = i # 3. Grouping by key from collections import defaultdict groups = defaultdict(list) for word in words: groups[sorted(word)].append(word) # anagrams # 4. Sliding window with set def longest_unique(s): seen, l, res = set(), 0, 0 for r, ch in enumerate(s): while ch in seen: seen.discard(s[l]); l += 1 seen.add(ch) res = max(res, r - l + 1) return res # 5. Indexing for O(1) access idx = {v: i for i, v in enumerate(arr)}

Practice problems

Two Sum

Easy

Given nums and target, return indices of two numbers that add to target.

def twoSum(nums, target): seen = {} # {value: index} for i, n in enumerate(nums): complement = target - n if complement in seen: # O(1) lookup return [seen[complement], i] seen[n] = i return [] # Dry run: nums=[2,7,11,15], target=9 # i=0: n=2, comp=7, seen={} → add {2:0} # i=1: n=7, comp=2, seen={2:0} → FOUND! return [0,1]

Time: O(n) — Space: O(n)

First non-repeating character

Medium

def firstUniqChar(s): freq = Counter(s) # O(n) for i, ch in enumerate(s): # O(n) if freq[ch] == 1: return i return -1 # Dry run: s="leetcode" # freq={'l':1,'e':3,'t':1,'c':1,'o':1,'d':1} # i=0: 'l' → freq=1 → return 0 ✓

Time: O(n) — Space: O(1) since at most 26 chars

Longest substring without repeating characters

Medium

def lengthOfLongestSubstring(s): seen = {} # char → last seen index l, res = 0, 0 for r, ch in enumerate(s): if ch in seen and seen[ch] >= l: l = seen[ch] + 1 # shrink window seen[ch] = r res = max(res, r - l + 1) return res # Dry run: s="abcabcbb" # r=0:'a' l=0 seen={a:0} res=1 # r=1:'b' l=0 seen={a:0,b:1} res=2 # r=2:'c' l=0 res=3 # r=3:'a' → dup! l=1, seen={a:3,...} res=3 # ... final res=3 ✓

Time: O(n) — Space: O(min(n, alphabet))

Top K frequent elements

Interview

import heapq from collections import Counter def topKFrequent(nums, k): freq = Counter(nums) # {num: count} # min-heap of size k return heapq.nlargest(k, freq.keys(), key=freq.get) # nums=[1,1,1,2,2,3], k=2 # freq={1:3,2:2,3:1} # nlargest(2,...) → [1,2] ✓ # Time: O(n log k) Space: O(n) # Bucket sort approach → O(n) def topKFrequent_On(nums, k): freq = Counter(nums) buckets = [[] for _ in range(len(nums)+1)] for num, cnt in freq.items(): buckets[cnt].append(num) res = [] for b in reversed(buckets): res.extend(b) if len(res) >= k: return res[:k]

Concept check

Score0 / 0

Interview tips and mistakes

Pattern recognition — reach for dict/set when you see:

counting occurrences find pair with sum X detect duplicates O(1) lookup needed grouping/anagrams sliding window unique first/last seen index common elements

Common mistakes

Mistake	Problem	Fix
Using list as dict key	TypeError: unhashable	Convert to tuple first
d["k"] on missing key	KeyError	d.get("k", 0)
{} for empty set	Creates dict, not set	set()
Mutating dict during iteration	RuntimeError	Iterate over list(d.keys())
x in d.values()	O(n) not O(1)	Restructure — key lookup instead
Assuming set is ordered	Wrong output	Use list + sort if order matters

Optimization insights

Prefer defaultdict(int) over d.get(k, 0) — cleaner for frequency counting.

Use Counter for frequency — it has built-in .most_common(k).

Convert a list to set for O(1) membership: lookup = set(my_list) then x in lookup.

dict consumes ~8x more memory than a list of same size. Avoid for memory-critical applications.

In interviews: always mention O(1) average lookup as the key reason for choosing dict/set. Interviewers love hearing this explicitly.

Interview language bridge

CS / Java / C++	Python equivalent
HashMap	dict
HashSet	set
LinkedHashMap	dict (ordered since 3.7)
TreeMap (sorted)	sortedcontainers.SortedDict
Map.getOrDefault(k, v)	d.get(k, v)
map.containsKey(k)	k in d
set.contains(x)	x in s