5. Dictionaries

💡 Why this matters for DSA Dicts are Python's most versatile DSA tool — frequency counters, memoization caches, graph adjacencies, and more. O(1) get/set makes them indispensable.

5.1 Key-Value Basics

python

d = {"apple": 5, "banana": 3, "cherry": 7}

d["apple"]        # 5       O(1)
d["grape"] = 2    # insert  O(1)
d["apple"] = 9    # update  O(1)

"apple" in d      # True    O(1)
len(d)            # 3       O(1)

⚠️ Warning: Keys must be hashable (strings, numbers, tuples — NOT lists or dicts).

5.2 Essential Methods

python

d = {"a": 1, "b": 2, "c": 3}

d.get("a")         # 1
d.get("z")         # None (no error!)
d.get("z", 0)      # 0  (default if missing)

d.keys()           # dict_keys(['a', 'b', 'c'])
d.values()         # dict_values([1, 2, 3])
d.items()          # dict_items([('a', 1), ('b', 2), ('c', 3)])

d.pop("b")         # removes & returns 2
d.pop("x", None)   # safe pop with default

d.update({"d": 4})  # add multiple key-value pairs

Iteration patterns

python

for key in d:                  # keys
for key, val in d.items():     # keys + values
for val in d.values():         # values

5.3 Dictionary Comprehension

python

# Squares
squares = {x: x**2 for x in range(5)}   # {0:0, 1:1, 2:4, 3:9, 4:16}

# Filter
evens = {x: x**2 for x in range(10) if x % 2 == 0}

# Swap keys and values
original = {"a": 1, "b": 2}
swapped = {v: k for k, v in original.items()}  # {1: 'a', 2: 'b'}

# From two lists
keys = ["name", "age", "city"]
vals = ["Manik", 25, "Pune"]
person = {k: v for k, v in zip(keys, vals)}

5.4 Frequency Counter Pattern ⭐

The most common DSA pattern with dicts.

python

# Count frequency of each element
arr = [1, 2, 2, 3, 3, 3, 1, 4]
freq = {}
for x in arr:
    freq[x] = freq.get(x, 0) + 1

# freq = {1: 2, 2: 2, 3: 3, 4: 1}

# Using collections.Counter (cleaner)
from collections import Counter
freq = Counter(arr)           # Counter({3: 3, 1: 2, 2: 2, 4: 1})
freq.most_common(1)           # [(3, 3)]

DSA problems that use this pattern

Two Sum
Valid Anagram
First non-repeating character
Subarray sum equals k
Character count matching

✅ Tip — defaultdict auto-initializes missing keys:

python

from collections import defaultdict

freq = defaultdict(int)      # default value 0
for x in arr:
    freq[x] += 1             # no KeyError!

groups = defaultdict(list)   # default value []
for x in arr:
    groups[x % 2].append(x)

5.5 Dict as a Lookup Table / Cache

python

# Memoization (Fibonacci)
cache = {}
def fib(n):
    if n <= 1:
        return n
    if n not in cache:
        cache[n] = fib(n-1) + fib(n-2)
    return cache[n]

# Graph adjacency list
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"]
}

Practice Drill

python

# 1. Count character frequencies in a string
# 2. Given two strings, check if they're anagrams
# 3. Find the first non-repeating character in a string
# 4. Two Sum: return indices of two numbers that add up to target

💡 Click for Solutions

python

# 1. Character frequencies
s = "hello"
freq = {}
for ch in s:
    freq[ch] = freq.get(ch, 0) + 1
print(freq)  # {'h':1, 'e':1, 'l':2, 'o':1}

# 2. Anagram check
def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

print(is_anagram("listen", "silent"))  # True

# 3. First non-repeating character
s = "swiss"
freq = Counter(s)
for ch in s:
    if freq[ch] == 1:
        print(ch)  # 'w'
        break

# 4. Two Sum
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
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

python

# Note: Counter needs import
from collections import Counter

← Tuples & Sets | Next → Conditionals & Loops