9. List & Dict Utilities for DSA

💡 Why this matters for DSA These are the Python standard library tools you'll reach for in almost every DSA problem. They're optimized, tested, and save you from reinventing the wheel.

9.1 Sorting with Custom Key

python

arr = [(1, "z"), (3, "a"), (2, "c")]

# Sort by second element
arr.sort(key=lambda x: x[1])
sorted(arr, key=lambda x: x[1])

# Sort by multiple criteria
sorted(students, key=lambda s: (-s.score, s.name))

# Sort indices by value (argsort pattern)
indexes = sorted(range(len(arr)), key=lambda i: arr[i])

✅ Tip — Key vs cmp: Python's sort uses a key function (not cmp). The key is computed once per element (decorate-sort-undecorate). This is efficient — O(n log n) comparisons of keys, not O(n log n) calls to key function.

9.2 defaultdict

Automatically creates a default value when a missing key is accessed.

python

from collections import defaultdict

# Default value 0 (counting)
freq = defaultdict(int)
for x in [1, 2, 2, 3]:
    freq[x] += 1
# freq = {1: 1, 2: 2, 3: 1}

# Default value [] (grouping)
groups = defaultdict(list)
for x in [1, 2, 3, 4, 5, 6]:
    groups[x % 2].append(x)
# groups = {1: [1, 3, 5], 0: [2, 4, 6]}

# Default value set()
adj = defaultdict(set)
adj[0].add(1)

✅ Tip — defaultdict vs regular dict:

python

# Without defaultdict
freq = {}
for x in arr:
    freq[x] = freq.get(x, 0) + 1

# With defaultdict
freq = defaultdict(int)
for x in arr:
    freq[x] += 1

9.3 Counter

python

from collections import Counter

arr = [1, 2, 2, 3, 3, 3, 1, 4]
c = Counter(arr)
# Counter({3: 3, 1: 2, 2: 2, 4: 1})

c[3]                    # 3
c.most_common(2)        # [(3, 3), (1, 2)]
list(c.elements())      # [1, 1, 2, 2, 3, 3, 3, 4]

# Counter arithmetic
c1 = Counter("hello")
c2 = Counter("world")
c1 + c2                 # {'l': 3, 'o': 2, 'h': 1, 'e': 1, 'w': 1, 'r': 1, 'd': 1}
c1 - c2                 # {'h': 1, 'e': 1}  (only positive counts)
c1 & c2                 # {'l': 1, 'o': 1}  (intersection)
c1 | c2                 # union (max counts)

✅ Tip — Counter is perfect for anagram / frequency problems:
python
def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

9.4 deque (Double-Ended Queue)

Optimized for O(1) append/pop from both ends.

python

from collections import deque

d = deque([1, 2, 3])

d.append(4)          # [1, 2, 3, 4]      O(1)
d.appendleft(0)      # [0, 1, 2, 3, 4]   O(1)
d.pop()              # 4                 O(1)
d.popleft()          # 0                 O(1)

# Rotate (useful for some problems)
d.rotate(1)          # [4, 1, 2, 3]
d.rotate(-1)         # [1, 2, 3, 4]

Using deque for BFS

python

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

✅ Tip — deque vs list as queue:

Operation list deque
append (right) O(1) O(1)
pop (right) O(1) O(1)
pop (left) O(n) ❌ O(1) ✅
append (left) O(n) ❌ O(1) ✅

Operation	list	deque
append (right)	O(1)	O(1)
pop (right)	O(1)	O(1)
pop (left)	O(n) ❌	O(1) ✅
append (left)	O(n) ❌	O(1) ✅

9.5 heapq (Priority Queue)

python

import heapq

arr = [3, 1, 4, 1, 5]
heapq.heapify(arr)          # convert to min-heap in-place O(n)
# arr = [1, 1, 4, 3, 5]

heapq.heappush(arr, 2)      # push O(log n)
smallest = heapq.heappop(arr)   # pop smallest O(log n)
smallest = arr[0]           # peek smallest O(1) (don't pop)

# k largest / smallest
heapq.nlargest(3, arr)      # [5, 4, 3]
heapq.nsmallest(3, arr)     # [1, 1, 2]

🔑 Key: heapq is a min-heap by default For max-heap, push negative values:
python
max_heap = []
heapq.heappush(max_heap, -x)
largest = -heapq.heappop(max_heap)

DSA patterns with heapq

python

# Merge k sorted lists
def merge_k(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
    return result

# Dijkstra / A* — use (distance, node) tuples

Practice Drill

python

# 1. Given words, group anagrams together (use defaultdict)
# 2. Sliding window maximum using deque
# 3. Find k largest elements in a list
# 4. Sort characters by frequency (use Counter + sorted)

💡 Click for Solutions

python

# 1. Group anagrams
from collections import defaultdict

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
groups = defaultdict(list)
for w in words:
    groups["".join(sorted(w))].append(w)
print(list(groups.values()))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

# 2. Sliding window maximum
from collections import deque

def max_sliding_window(nums, k):
    d = deque()
    result = []
    for i, n in enumerate(nums):
        while d and nums[d[-1]] < n:
            d.pop()
        d.append(i)
        if d[0] <= i - k:
            d.popleft()
        if i >= k - 1:
            result.append(nums[d[0]])
    return result

print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]

# 3. K largest elements
import heapq
arr = [3, 1, 5, 2, 7, 4]
k = 3
print(heapq.nlargest(k, arr))  # [7, 5, 4]

# 4. Sort characters by frequency
from collections import Counter
s = "tree"
freq = Counter(s)
sorted_chars = sorted(s, key=lambda c: (-freq[c], c))
print("".join(sorted_chars))  # "eetr" or "eert"

← Built-in Functions & Modules | Next → Time & Space Complexity