The collections Module: Python's Supercharged Data Structures

Counter, defaultdict, deque, namedtuple — four ready-made containers that turn ten lines of fiddly dictionary code into one.

Learning Objectives

After this lesson, you will be able to:

Use Counter to count hashable objects and perform arithmetic on frequency data
Use defaultdict to eliminate 'key not found' boilerplate in grouping patterns
Use namedtuple to create lightweight, readable, immutable records
Use deque for O(1) append and pop from both ends — including sliding windows
Apply heapq for priority queues and top-K problems
Use bisect for O(log n) search and insertion in sorted lists

Prerequisites

Before You Start

Review

#Why the collections Module Exists

Python's built-in list, dict, and set are excellent general-purpose containers. But for specific use cases, they make you write repetitive boilerplate. The collections module provides specialized containers that eliminate that boilerplate and often run faster.

pythonrunnable cell

# The full import (pick what you need)
from collections import (
    Counter,       # counting hashable objects
    defaultdict,   # dict with auto-created missing values
    OrderedDict,   # dict with order-sensitive operations
    namedtuple,    # immutable tuple with named fields
    deque,         # double-ended queue with O(1) both-end ops
    ChainMap,      # layered dict views
)
import heapq   # heap operations on lists
import bisect  # binary search on sorted lists

Data Structure Explorer — Stack, Queue, BST & Hash TableInteractive

See how Python's built-in structures work under the hood before we layer the collections module on top. Insert, remove, and search elements with animated step-by-step visualization.

Loading visualization...

#Counter: Counting Made Effortless

Counter is a dict subclass where missing keys default to zero, purpose-built for counting hashable objects.

pythonrunnable cell

from collections import Counter

# Count characters in a string
char_count = Counter("banana")
print(char_count)
# Counter({'a': 3, 'n': 2, 'b': 1})

# Count words in a list
words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
word_count = Counter(words)
print(word_count)
# Counter({'apple': 3, 'banana': 2, 'cherry': 1})

# Count words from a text
text = "to be or not to be that is the question to be"
token_counts = Counter(text.split())
print(token_counts)
# Counter({'to': 3, 'be': 3, 'or': 1, 'not': 1, ...})

#.most_common(n)

pythonreference · read-only

vocab = Counter("the cat sat on the mat the cat sat".split())

# Top 3 most frequent
print(vocab.most_common(3))
# [('the', 3), ('cat', 2), ('sat', 2)]

# All items, most common first
print(vocab.most_common())
# [('the', 3), ('cat', 2), ('sat', 2), ('on', 1), ('mat', 1)]

# Access a missing key -- returns 0, not KeyError
print(vocab["elephant"])   # 0

#Counter Arithmetic

Counter supports set-like arithmetic that makes combining frequency tables elegant.

pythonreference · read-only

c1 = Counter({"apple": 5, "banana": 3, "cherry": 1})
c2 = Counter({"banana": 2, "cherry": 4, "date": 6})

# Addition: combine counts
print(c1 + c2)
# Counter({'date': 6, 'apple': 5, 'cherry': 5, 'banana': 5})

# Subtraction: keep only positive results
print(c1 - c2)
# Counter({'apple': 5, 'banana': 1})
# 'cherry' becomes -3, dropped (only positives kept)

# Intersection: minimum of each count
print(c1 & c2)
# Counter({'banana': 2, 'cherry': 1})

# Union: maximum of each count
print(c1 | c2)
# Counter({'date': 6, 'apple': 5, 'cherry': 4, 'banana': 3})

#Use Case: Finding the Most Common Words

pythonrunnable cell

from collections import Counter

sentences = [
    "the cat sat on the mat",
    "the dog ran in the park",
    "the cat and the dog played",
]

# Count every word across all the sentences
all_words = []
for line in sentences:
    all_words.extend(line.split())

word_counter = Counter(all_words)

# The most frequent words are almost always the boring ones
print("Top 5 words:", word_counter.most_common(5))

# Give each common word a number, so you can refer to it by index
how_many = 10
numbered = {word: idx for idx, (word, _) in enumerate(word_counter.most_common(how_many))}
print("Numbered:", numbered)
# {'the': 0, 'cat': 1, 'dog': 2, ...}

# Encode a sentence
def encode(sentence: str, vocab: dict[str, int]) -> list[int]:
    """Convert words to vocab ids, unknown words get -1."""
    return [vocab.get(w, -1) for w in sentence.split()]

print(encode("the cat ran", vocab))   # [0, 1, ?]

What Do You Think?

You have Counter({'a': 3, 'b': 1}) - Counter({'a': 2, 'b': 5}). What is the result?

The result is Counter({'a': 1}). Counter subtraction keeps only positive results and drops zeros and negatives. b becomes 1 - 5 = -4, which is dropped.

#defaultdict: Eliminate Missing-Key Boilerplate

defaultdict is a dict subclass that automatically creates a default value for missing keys instead of raising KeyError.

pythonrunnable cell

from collections import defaultdict

# Without defaultdict -- classic verbose pattern
groups = {}
words = [("fruit", "apple"), ("veggie", "carrot"), ("fruit", "banana"), ("veggie", "broccoli")]
for category, item in words:
    if category not in groups:      # boilerplate check
        groups[category] = []       # boilerplate initialization
    groups[category].append(item)

print(groups)
# {'fruit': ['apple', 'banana'], 'veggie': ['carrot', 'broccoli']}


# With defaultdict(list) -- missing keys auto-get an empty list
groups_v2 = defaultdict(list)
for category, item in words:
    groups_v2[category].append(item)    # no check needed!

print(dict(groups_v2))
# {'fruit': ['apple', 'banana'], 'veggie': ['carrot', 'broccoli']}

#Common Default Factories

pythonreference · read-only

# defaultdict(int) -- missing keys default to 0
word_count = defaultdict(int)
text = "the quick brown fox jumps over the lazy dog the fox"
for word in text.split():
    word_count[word] += 1   # no .get() or check needed
print(dict(word_count))

# defaultdict(set) -- missing keys default to empty set
# Use case: building an inverted index
inverted_index: defaultdict = defaultdict(set)
documents = {
    "doc1": "python beginner tutorial",
    "doc2": "python web development flask",
    "doc3": "beginner tutorial for flask",
}
for doc_id, content in documents.items():
    for word in content.split():
        inverted_index[word].add(doc_id)

# Which docs contain "python"?
print(inverted_index["python"])   # {'doc1', 'doc2'}
# Which docs contain "machine"? None of them --
# and this lookup just CREATED the key. See the question below.
print(inverted_index["machine"])  # set()
print(len(inverted_index))        # 8 -- "machine" is now stored

# defaultdict with a lambda -- custom defaults
config = defaultdict(lambda: "NOT_SET")
config["debug"] = True
print(config["debug"])       # True
print(config["log_level"])   # "NOT_SET" (auto-created)

What Do You Think?

inverted_index has 7 words in it. You read inverted_index['machine'], a word in none of the documents. What is the dict's length afterwards?

#Building a Graph with defaultdict

pythonreference · read-only

# Adjacency list graph -- a perfect use case for defaultdict(list)
graph: defaultdict = defaultdict(list)

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]
for src, dst in edges:
    graph[src].append(dst)
    graph[dst].append(src)   # undirected

# BFS from A
from collections import deque

def bfs(graph: dict, start: str) -> list[str]:
    visited: set[str] = set()
    queue: deque[str] = deque([start])
    order: list[str] = []
    visited.add(start)

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

    return order

print(bfs(graph, "A"))   # ['A', 'B', 'C', 'D', 'E']

#OrderedDict: Order-Sensitive Operations

In Python 3.7+, regular dicts maintain insertion order. So when do you still need OrderedDict?

pythonrunnable cell

from collections import OrderedDict

# OrderedDict has .move_to_end() which regular dicts lack
od = OrderedDict([("a", 1), ("b", 2), ("c", 3)])
od.move_to_end("a")          # move "a" to the end
print(list(od.keys()))       # ['b', 'c', 'a']

od.move_to_end("a", last=False)  # move "a" to the front
print(list(od.keys()))           # ['a', 'b', 'c']

# OrderedDict equality considers order; regular dict equality does not
d1 = OrderedDict([("a", 1), ("b", 2)])
d2 = OrderedDict([("b", 2), ("a", 1)])
print(d1 == d2)    # False -- order matters for OrderedDict

r1 = {"a": 1, "b": 2}
r2 = {"b": 2, "a": 1}
print(r1 == r2)    # True -- order does NOT matter for regular dict

#LRU Cache with OrderedDict

pythonrunnable cell

from collections import OrderedDict

class LRUCache:
    """Least Recently Used cache using OrderedDict.

    The most recently used item moves to the end.
    When capacity is exceeded, the front (least recently used) is evicted.
    """

    def __init__(self, capacity: int) -> None:
        self._cache: OrderedDict = OrderedDict()
        self._capacity = capacity

    def get(self, key: str) -> object:
        if key not in self._cache:
            return -1
        self._cache.move_to_end(key)   # mark as recently used
        return self._cache[key]

    def put(self, key: str, value: object) -> None:
        if key in self._cache:
            self._cache.move_to_end(key)
        self._cache[key] = value
        if len(self._cache) > self._capacity:
            self._cache.popitem(last=False)  # evict least recently used (front)

    def __repr__(self) -> str:
        return f"LRUCache({dict(self._cache)})"


cache = LRUCache(capacity=3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
print(cache.get("a"))   # 1 -- "a" is now most recently used
cache.put("d", 4)       # capacity exceeded, "b" is evicted (LRU)
print(cache.get("b"))   # -1 -- "b" was evicted
print(cache)            # LRUCache({'c': 3, 'a': 1, 'd': 4})

Quick check

Capacity is 3 and 'a', 'b', 'c' are all in. `get('a')` runs, then `put('d', 4)`. Why is 'b' evicted rather than 'a'?

#namedtuple: Readable, Memory-Efficient Records

namedtuple creates tuple subclasses with named fields. Access by name instead of index — clearer code, same memory footprint as a plain tuple.

pythonrunnable cell

from collections import namedtuple

# Define a namedtuple type
Point = namedtuple("Point", ["x", "y"])
Color = namedtuple("Color", ["r", "g", "b"])
Employee = namedtuple("Employee", ["name", "department", "salary"])

# Create instances
p = Point(x=3, y=7)
c = Color(255, 128, 0)
emp = Employee("Alice", "Engineering", 95000)

# Named access (much clearer than p[0], p[1])
print(f"Point: ({p.x}, {p.y})")
print(f"Color: rgb({c.r}, {c.g}, {c.b})")
print(f"{emp.name} in {emp.department} earns ${emp.salary:,}")

# Still a tuple -- index access and unpacking work
print(p[0])                  # 3
x, y = p                     # unpacking
print(x, y)                  # 3, 7

# Immutable -- cannot modify fields
# p.x = 10    # AttributeError: can't set attribute

# _replace() creates a NEW namedtuple with one field changed
p2 = p._replace(x=10)
print(p2)   # Point(x=10, y=7)
print(p)    # Point(x=3, y=7) -- original unchanged

# _asdict() converts to a regular dict
print(emp._asdict())
# {'name': 'Alice', 'department': 'Engineering', 'salary': 95000}

#Memory Comparison: namedtuple vs dict vs class

pythonreference · read-only

import sys

# Representing the same data three ways
Point_nt   = namedtuple("Point_nt", ["x", "y", "z"])
p_namedtuple = Point_nt(1.0, 2.0, 3.0)
p_dict       = {"x": 1.0, "y": 2.0, "z": 3.0}

class PointClass:
    def __init__(self, x, y, z):
        self.x = x; self.y = y; self.z = z

p_class = PointClass(1.0, 2.0, 3.0)

print(f"namedtuple: {sys.getsizeof(p_namedtuple)} bytes")
# namedtuple: ~80 bytes  (small fixed size — like a plain tuple)
print(f"dict:       {sys.getsizeof(p_dict)} bytes")
# dict:       ~184 bytes (hash table overhead, even with compact dicts)
print(f"class:      {sys.getsizeof(p_class) + sys.getsizeof(p_class.__dict__)} bytes")
# class:      object header + __dict__ — typically 2-3x a namedtuple

Exact byte numbers depend on your Python build (3.12 / 3.13 / free-threaded), platform, and any pointer-tagging or shared-key optimization. The relative ranking holds: namedtuple < dict < class with dict. To shrink the class to namedtuple-level, declare __slots__ (covered in oop-advanced).

namedtuples are ideal for representing database rows, coordinates, config snapshots, or any read-only record where you want attribute access without the overhead of a full class.

What Do You Think?

p = Point(x=3, y=7). You write p._replace(x=10) on its own line and then print p. What do you see?

#deque: O(1) Operations on Both Ends

Python list is implemented as a dynamic array. Inserting or removing at the left end (insert(0, x), pop(0)) is O(n) because every element must shift. deque uses a different internal structure that makes both-end operations O(1).

pythonrunnable cell

from collections import deque
import time

# Demonstrate the performance gap
n = 100_000

# list.insert(0) is O(n) -- shifts every element
lst = []
start = time.time()
for i in range(n):
    lst.insert(0, i)
list_time = time.time() - start

# deque.appendleft() is O(1) -- no shifting
dq = deque()
start = time.time()
for i in range(n):
    dq.appendleft(i)
deque_time = time.time() - start

print(f"list.insert(0): {list_time:.3f}s")
print(f"deque.appendleft: {deque_time:.4f}s")
# list is typically 100-1000x slower for large n

#Core deque Operations

pythonreference · read-only

dq = deque([1, 2, 3, 4, 5])

# Append / pop from both ends -- all O(1)
dq.append(6)           # [1, 2, 3, 4, 5, 6]  (right end)
dq.appendleft(0)       # [0, 1, 2, 3, 4, 5, 6]  (left end)
right = dq.pop()       # 6  (from right)
left  = dq.popleft()   # 0  (from left)
print(list(dq))        # [1, 2, 3, 4, 5]

# Rotate -- move n elements from one end to the other
dq.rotate(2)           # move 2 from right to left
print(list(dq))        # [4, 5, 1, 2, 3]
dq.rotate(-1)          # move 1 from left to right
print(list(dq))        # [5, 1, 2, 3, 4]

#Fixed-Size deque: The Sliding Window Pattern

pythonrunnable cell

from collections import deque

# maxlen: when full, adding to one end auto-discards from the other
history = deque(maxlen=5)
for i in range(10):
    history.append(i)
    print(f"Added {i}: {list(history)}")
# Added 0: [0]
# Added 1: [0, 1]
# ...
# Added 5: [1, 2, 3, 4, 5]  -- 0 was auto-discarded
# Added 9: [5, 6, 7, 8, 9]  -- always the last 5

# Sliding window average (useful for time-series smoothing)
def moving_average(data: list[float], window: int) -> list[float]:
    """Compute moving average using a deque window."""
    window_data: deque[float] = deque(maxlen=window)
    averages: list[float] = []

    for value in data:
        window_data.append(value)
        if len(window_data) == window:
            averages.append(sum(window_data) / window)

    return averages


prices = [10, 12, 11, 14, 15, 13, 16, 18, 17, 20]
ma = moving_average(prices, window=3)
print("Moving average (window=3):", [round(x, 2) for x in ma])
# [11.0, 12.33, 13.33, 14.0, 14.67, 15.67, 17.0, 18.33]

#BFS with deque

pythonrunnable cell

from collections import deque

def bfs_shortest_path(graph: dict, start: str, end: str) -> list[str] | None:
    """Find shortest path using BFS with deque."""
    if start == end:
        return [start]

    visited: set[str] = {start}
    # Each item in queue is a path so far
    queue: deque[list[str]] = deque([[start]])

    while queue:
        path = queue.popleft()
        current = path[-1]

        for neighbor in graph.get(current, []):
            if neighbor not in visited:
                new_path = path + [neighbor]
                if neighbor == end:
                    return new_path
                visited.add(neighbor)
                queue.append(new_path)

    return None   # no path found


graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print(bfs_shortest_path(graph, "A", "F"))   # ['A', 'C', 'F']

Quick check

Change the single line `path = queue.popleft()` to `path = queue.pop()`. What does the function still do, and what does it stop doing?

#ChainMap: Layered Dict Lookups

ChainMap groups multiple dicts into a single logical view. Lookups search each map in order. Writes go to the first map.

pythonrunnable cell

from collections import ChainMap

# Classic use case: layered configuration
defaults = {
    "timeout": 30,
    "retries": 3,
    "debug": False,
    "log_level": "INFO",
}
env_vars = {
    "timeout": 60,
    "debug": True,
}
cli_args = {
    "log_level": "DEBUG",
}

# Priority: CLI > env vars > defaults
config = ChainMap(cli_args, env_vars, defaults)

print(config["timeout"])     # 60  (from env_vars)
print(config["retries"])     # 3   (from defaults)
print(config["log_level"])   # "DEBUG"  (from cli_args)
print(config["debug"])       # True  (from env_vars)

# Writes go to the first map only
config["new_key"] = "hello"
print(cli_args)   # {'log_level': 'DEBUG', 'new_key': 'hello'}
print(defaults)   # unchanged

# .maps gives access to the underlying list of dicts
print(config.maps)   # [cli_args, env_vars, defaults]

# Create a child context (adds a new layer at the front)
child = config.new_child({"timeout": 5})
print(child["timeout"])   # 5 (child override)
print(config["timeout"])  # 60 (parent unchanged)

What Do You Think?

config = ChainMap(cli_args, env_vars, defaults) and config['timeout'] reads 60 from env_vars. You then assign config['timeout'] = 99. Which dict changes?

#heapq: Priority Queues

Python's heapq module implements a min-heap on top of a regular Python list. The smallest element is always at index 0. Push and pop are O(log n).

pythonrunnable cell

import heapq

# heapq operates on a regular list
heap: list[int] = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

print(heap)               # [1, 3, 7, 10, 5] (heap-ordered, not sorted)
print(heapq.heappop(heap))  # 1 (smallest always pops first)
print(heapq.heappop(heap))  # 3
print(heapq.heappop(heap))  # 5

# heapify: convert an existing list to a heap in O(n)
data = [8, 2, 6, 4, 1, 9, 3]
heapq.heapify(data)
print(data)               # [1, 2, 3, 4, 8, 9, 6] (heap property satisfied)

# nlargest / nsmallest: efficiently find top-K elements
scores = [45, 92, 78, 55, 88, 91, 63, 71, 84, 97]
print(heapq.nlargest(3, scores))   # [97, 92, 91]
print(heapq.nsmallest(3, scores))  # [45, 55, 63]

#Max-Heap Trick

Python only has min-heap. To simulate a max-heap, negate your values.

pythonrunnable cell

import heapq

max_heap: list[int] = []
for value in [5, 1, 8, 3, 7]:
    heapq.heappush(max_heap, -value)   # store negated

print(-heapq.heappop(max_heap))  # 8 (largest)
print(-heapq.heappop(max_heap))  # 7
print(-heapq.heappop(max_heap))  # 5

#Priority Queue with Tasks

pythonrunnable cell

import heapq
from dataclasses import dataclass, field

@dataclass(order=True)
class Task:
    """A task with a priority and name."""
    priority: int
    name: str = field(compare=False)

task_queue: list[Task] = []
heapq.heappush(task_queue, Task(priority=3, name="Send report"))
heapq.heappush(task_queue, Task(priority=1, name="Fix critical bug"))
heapq.heappush(task_queue, Task(priority=2, name="Code review"))
heapq.heappush(task_queue, Task(priority=1, name="Deploy hotfix"))

# Process in priority order (lowest number = highest priority)
while task_queue:
    task = heapq.heappop(task_queue)
    print(f"  [{task.priority}] {task.name}")
# [1] Fix critical bug
# [1] Deploy hotfix
# [2] Code review
# [3] Send report

#K Closest Points to Origin

pythonrunnable cell

import heapq
import math

def k_closest(points: list[tuple[int, int]], k: int) -> list[tuple[int, int]]:
    """Return k points closest to the origin using a heap."""
    # Use a min-heap keyed by distance squared (avoid sqrt for speed)
    heap = [(p[0]**2 + p[1]**2, p) for p in points]
    heapq.heapify(heap)
    return [heapq.heappop(heap)[1] for _ in range(k)]


points = [(1, 3), (-2, 2), (5, 8), (0, 1), (3, -2)]
print(k_closest(points, k=2))   # [(0, 1), (-2, 2)]

Quick check

Pushing 10, 3, 7, 1, 5 gives the list `[1, 3, 7, 10, 5]`. Why is it not `[1, 3, 5, 7, 10]`?

#bisect: Binary Search on Sorted Lists

The bisect module provides binary search on already-sorted lists. Search is O(log n), but insertion maintains sort order at O(n) due to shifting.

pythonrunnable cell

import bisect

sorted_list = [1, 3, 5, 7, 9, 11, 15]

# bisect_left: index of leftmost position where x can be inserted
# (also the index where x would be if it already exists)
print(bisect.bisect_left(sorted_list, 7))    # 3 (7 is at index 3)
print(bisect.bisect_left(sorted_list, 6))    # 3 (6 would go at index 3)
print(bisect.bisect_left(sorted_list, 1))    # 0

# bisect_right (same as bisect.bisect): index AFTER any existing occurrences
sorted_with_dups = [1, 3, 3, 3, 5, 7]
print(bisect.bisect_left(sorted_with_dups, 3))    # 1 (before the 3s)
print(bisect.bisect_right(sorted_with_dups, 3))   # 4 (after the 3s)

# insort: insert while maintaining sorted order
data = [1, 3, 5, 7]
bisect.insort(data, 4)
print(data)   # [1, 3, 4, 5, 7]
bisect.insort(data, 6)
print(data)   # [1, 3, 4, 5, 6, 7]

#Grade Lookup with bisect

pythonrunnable cell

import bisect

def grade(score: int) -> str:
    """Assign a letter grade using binary search."""
    breakpoints = [60, 70, 80, 90]
    grades      = ["F", "D", "C", "B", "A"]
    return grades[bisect.bisect(breakpoints, score)]


test_scores = [45, 62, 75, 83, 91, 100]
for s in test_scores:
    print(f"  {s} -> {grade(s)}")
# 45 -> F
# 62 -> D
# 75 -> C
# 83 -> B
# 91 -> A
# 100 -> A

#Range Query with bisect

pythonrunnable cell

import bisect

def count_in_range(sorted_data: list[int], lo: int, hi: int) -> int:
    """Count elements in [lo, hi] using binary search. O(log n)."""
    left  = bisect.bisect_left(sorted_data, lo)
    right = bisect.bisect_right(sorted_data, hi)
    return right - left

data = sorted([12, 5, 19, 3, 8, 15, 7, 22, 11, 4])
print(data)   # [3, 4, 5, 7, 8, 11, 12, 15, 19, 22]
print(count_in_range(data, 5, 15))   # 6 (values: 5, 7, 8, 11, 12, 15)
print(count_in_range(data, 10, 20))  # 4 (values: 11, 12, 15, 19)

What Do You Think?

grade() uses bisect([60, 70, 80, 90], score). A student scores exactly 60. What grade comes back?

#Code Playground

pythonplayground.py · Pyodide

# Streaming word frequency analyzer
# Combine Counter + deque to analyze text in a sliding window
from collections import Counter, deque

# A streaming text processor that:
# 1. Maintains a sliding window of the last N words
# 2. Shows the most common words in the current window
# 3. Updates as each new word arrives

class StreamingAnalyzer:
  """Analyze word frequency in a sliding window of text."""

def __init__(self, window_size: int = 10) -> None:
      self.window_size = window_size
      self.window: deque[str] = deque(maxlen=window_size)
      self.counts: Counter = Counter()

def add_word(self, word: str) -> None:
      """Add a word to the window, evicting the oldest if full."""
      # If window is full, the oldest word will be auto-evicted
      # We must update counts BEFORE appending (deque auto-evicts on append)
      if len(self.window) == self.window_size:
          oldest = self.window[0]   # will be evicted
          self.counts[oldest] -= 1
          if self.counts[oldest] == 0:
              del self.counts[oldest]

self.window.append(word)
      self.counts[word] += 1

def top_words(self, n: int = 3) -> list[tuple[str, int]]:
      """Return the top n most common words in the current window."""
      # YOUR CODE HERE
      # Hint: self.counts is a Counter -- it has .most_common(n)
      pass

def snapshot(self) -> str:
      """Return a readable snapshot of the current window state."""
      return f"Window: {list(self.window)} | Top: {self.top_words(3)}"

# Test with a stream of words
text = "the cat sat on the mat the cat and the dog sat on the mat too"
words = text.split()

analyzer = StreamingAnalyzer(window_size=6)

print("Processing word stream (window=6):")
for i, word in enumerate(words):
  analyzer.add_word(word)
  if i >= 5:   # only show once window is full
      print(f"  Word {i+1} ('{word}'): {analyzer.snapshot()}")

# CHALLENGE: Use heapq to find the top-3 most frequent words
# across the ENTIRE text (not just the window)
import heapq
full_counts = Counter(text.split())
top3 = None  # use heapq.nlargest to find top-3 (word, count) pairs
print(f"\nTop 3 words overall: {top3}")

Tests · Build a streaming word frequency analyzer with Counter and deque!

#Key Takeaways

Counter is a specialized dict for counting — Counter(iterable) counts frequencies automatically, supports arithmetic between counters, and .most_common(n) retrieves top-N in one call
defaultdict eliminates missing-key boilerplate — pass a factory (list, int, set, or a lambda) and missing keys are auto-initialized. Essential for grouping, graph adjacency lists, and inverted indexes
namedtuple creates readable, memory-efficient records — access by name (p.x) instead of index (p[0]), fully immutable and hashable, uses far less memory than a dict or class
deque gives O(1) both-end operations — appendleft/popleft are O(1) vs list's O(n). Use maxlen for sliding windows and fixed-size buffers. Always prefer deque over list for queues
heapq provides a priority queue on a regular list — min-heap by default; negate values for max-heap. nlargest/nsmallest find top-K efficiently without sorting the whole collection
bisect enables O(log n) search in sorted lists — bisect_left/bisect_right find insertion points, insort maintains order. Use for range queries, grade lookups, and anywhere you maintain a sorted structure

Quick Check1 / 5

What does Counter({'a': 3, 'b': 1}) - Counter({'a': 2, 'b': 5}) produce?

The collections Module: Python's Supercharged Data Structures

Counter, defaultdict, deque, namedtuple — four ready-made containers that turn ten lines of fiddly dictionary code into one.

Learning Objectives

After this lesson, you will be able to:

Use Counter to count hashable objects and perform arithmetic on frequency data
Use defaultdict to eliminate 'key not found' boilerplate in grouping patterns
Use namedtuple to create lightweight, readable, immutable records
Use deque for O(1) append and pop from both ends — including sliding windows
Apply heapq for priority queues and top-K problems
Use bisect for O(log n) search and insertion in sorted lists

Prerequisites

Before You Start

Review

#Why the collections Module Exists

pythonrunnable cell

# The full import (pick what you need)
from collections import (
    Counter,       # counting hashable objects
    defaultdict,   # dict with auto-created missing values
    OrderedDict,   # dict with order-sensitive operations
    namedtuple,    # immutable tuple with named fields
    deque,         # double-ended queue with O(1) both-end ops
    ChainMap,      # layered dict views
)
import heapq   # heap operations on lists
import bisect  # binary search on sorted lists

Data Structure Explorer — Stack, Queue, BST & Hash TableInteractive

See how Python's built-in structures work under the hood before we layer the collections module on top. Insert, remove, and search elements with animated step-by-step visualization.

Loading visualization...

#Counter: Counting Made Effortless

Counter is a dict subclass where missing keys default to zero, purpose-built for counting hashable objects.

pythonrunnable cell

from collections import Counter

# Count characters in a string
char_count = Counter("banana")
print(char_count)
# Counter({'a': 3, 'n': 2, 'b': 1})

# Count words in a list
words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
word_count = Counter(words)
print(word_count)
# Counter({'apple': 3, 'banana': 2, 'cherry': 1})

# Count words from a text
text = "to be or not to be that is the question to be"
token_counts = Counter(text.split())
print(token_counts)
# Counter({'to': 3, 'be': 3, 'or': 1, 'not': 1, ...})

#.most_common(n)

pythonreference · read-only

vocab = Counter("the cat sat on the mat the cat sat".split())

# Top 3 most frequent
print(vocab.most_common(3))
# [('the', 3), ('cat', 2), ('sat', 2)]

# All items, most common first
print(vocab.most_common())
# [('the', 3), ('cat', 2), ('sat', 2), ('on', 1), ('mat', 1)]

# Access a missing key -- returns 0, not KeyError
print(vocab["elephant"])   # 0

#Counter Arithmetic

Counter supports set-like arithmetic that makes combining frequency tables elegant.

pythonreference · read-only

c1 = Counter({"apple": 5, "banana": 3, "cherry": 1})
c2 = Counter({"banana": 2, "cherry": 4, "date": 6})

# Addition: combine counts
print(c1 + c2)
# Counter({'date': 6, 'apple': 5, 'cherry': 5, 'banana': 5})

# Subtraction: keep only positive results
print(c1 - c2)
# Counter({'apple': 5, 'banana': 1})
# 'cherry' becomes -3, dropped (only positives kept)

# Intersection: minimum of each count
print(c1 & c2)
# Counter({'banana': 2, 'cherry': 1})

# Union: maximum of each count
print(c1 | c2)
# Counter({'date': 6, 'apple': 5, 'cherry': 4, 'banana': 3})

#Use Case: Finding the Most Common Words

pythonrunnable cell

from collections import Counter

sentences = [
    "the cat sat on the mat",
    "the dog ran in the park",
    "the cat and the dog played",
]

# Count every word across all the sentences
all_words = []
for line in sentences:
    all_words.extend(line.split())

word_counter = Counter(all_words)

# The most frequent words are almost always the boring ones
print("Top 5 words:", word_counter.most_common(5))

# Give each common word a number, so you can refer to it by index
how_many = 10
numbered = {word: idx for idx, (word, _) in enumerate(word_counter.most_common(how_many))}
print("Numbered:", numbered)
# {'the': 0, 'cat': 1, 'dog': 2, ...}

# Encode a sentence
def encode(sentence: str, vocab: dict[str, int]) -> list[int]:
    """Convert words to vocab ids, unknown words get -1."""
    return [vocab.get(w, -1) for w in sentence.split()]

print(encode("the cat ran", vocab))   # [0, 1, ?]

What Do You Think?

You have Counter({'a': 3, 'b': 1}) - Counter({'a': 2, 'b': 5}). What is the result?

The result is Counter({'a': 1}). Counter subtraction keeps only positive results and drops zeros and negatives. b becomes 1 - 5 = -4, which is dropped.

#defaultdict: Eliminate Missing-Key Boilerplate

defaultdict is a dict subclass that automatically creates a default value for missing keys instead of raising KeyError.

pythonrunnable cell

from collections import defaultdict

# Without defaultdict -- classic verbose pattern
groups = {}
words = [("fruit", "apple"), ("veggie", "carrot"), ("fruit", "banana"), ("veggie", "broccoli")]
for category, item in words:
    if category not in groups:      # boilerplate check
        groups[category] = []       # boilerplate initialization
    groups[category].append(item)

print(groups)
# {'fruit': ['apple', 'banana'], 'veggie': ['carrot', 'broccoli']}


# With defaultdict(list) -- missing keys auto-get an empty list
groups_v2 = defaultdict(list)
for category, item in words:
    groups_v2[category].append(item)    # no check needed!

print(dict(groups_v2))
# {'fruit': ['apple', 'banana'], 'veggie': ['carrot', 'broccoli']}

#Common Default Factories

pythonreference · read-only

# defaultdict(int) -- missing keys default to 0
word_count = defaultdict(int)
text = "the quick brown fox jumps over the lazy dog the fox"
for word in text.split():
    word_count[word] += 1   # no .get() or check needed
print(dict(word_count))

# defaultdict(set) -- missing keys default to empty set
# Use case: building an inverted index
inverted_index: defaultdict = defaultdict(set)
documents = {
    "doc1": "python beginner tutorial",
    "doc2": "python web development flask",
    "doc3": "beginner tutorial for flask",
}
for doc_id, content in documents.items():
    for word in content.split():
        inverted_index[word].add(doc_id)

# Which docs contain "python"?
print(inverted_index["python"])   # {'doc1', 'doc2'}
# Which docs contain "machine"? None of them --
# and this lookup just CREATED the key. See the question below.
print(inverted_index["machine"])  # set()
print(len(inverted_index))        # 8 -- "machine" is now stored

# defaultdict with a lambda -- custom defaults
config = defaultdict(lambda: "NOT_SET")
config["debug"] = True
print(config["debug"])       # True
print(config["log_level"])   # "NOT_SET" (auto-created)

What Do You Think?

inverted_index has 7 words in it. You read inverted_index['machine'], a word in none of the documents. What is the dict's length afterwards?

#Building a Graph with defaultdict

pythonreference · read-only

# Adjacency list graph -- a perfect use case for defaultdict(list)
graph: defaultdict = defaultdict(list)

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]
for src, dst in edges:
    graph[src].append(dst)
    graph[dst].append(src)   # undirected

# BFS from A
from collections import deque

def bfs(graph: dict, start: str) -> list[str]:
    visited: set[str] = set()
    queue: deque[str] = deque([start])
    order: list[str] = []
    visited.add(start)

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

    return order

print(bfs(graph, "A"))   # ['A', 'B', 'C', 'D', 'E']

#OrderedDict: Order-Sensitive Operations

In Python 3.7+, regular dicts maintain insertion order. So when do you still need OrderedDict?

pythonrunnable cell

from collections import OrderedDict

# OrderedDict has .move_to_end() which regular dicts lack
od = OrderedDict([("a", 1), ("b", 2), ("c", 3)])
od.move_to_end("a")          # move "a" to the end
print(list(od.keys()))       # ['b', 'c', 'a']

od.move_to_end("a", last=False)  # move "a" to the front
print(list(od.keys()))           # ['a', 'b', 'c']

# OrderedDict equality considers order; regular dict equality does not
d1 = OrderedDict([("a", 1), ("b", 2)])
d2 = OrderedDict([("b", 2), ("a", 1)])
print(d1 == d2)    # False -- order matters for OrderedDict

r1 = {"a": 1, "b": 2}
r2 = {"b": 2, "a": 1}
print(r1 == r2)    # True -- order does NOT matter for regular dict

#LRU Cache with OrderedDict

pythonrunnable cell

from collections import OrderedDict

class LRUCache:
    """Least Recently Used cache using OrderedDict.

    The most recently used item moves to the end.
    When capacity is exceeded, the front (least recently used) is evicted.
    """

    def __init__(self, capacity: int) -> None:
        self._cache: OrderedDict = OrderedDict()
        self._capacity = capacity

    def get(self, key: str) -> object:
        if key not in self._cache:
            return -1
        self._cache.move_to_end(key)   # mark as recently used
        return self._cache[key]

    def put(self, key: str, value: object) -> None:
        if key in self._cache:
            self._cache.move_to_end(key)
        self._cache[key] = value
        if len(self._cache) > self._capacity:
            self._cache.popitem(last=False)  # evict least recently used (front)

    def __repr__(self) -> str:
        return f"LRUCache({dict(self._cache)})"


cache = LRUCache(capacity=3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
print(cache.get("a"))   # 1 -- "a" is now most recently used
cache.put("d", 4)       # capacity exceeded, "b" is evicted (LRU)
print(cache.get("b"))   # -1 -- "b" was evicted
print(cache)            # LRUCache({'c': 3, 'a': 1, 'd': 4})

Quick check

Capacity is 3 and 'a', 'b', 'c' are all in. `get('a')` runs, then `put('d', 4)`. Why is 'b' evicted rather than 'a'?

#namedtuple: Readable, Memory-Efficient Records

namedtuple creates tuple subclasses with named fields. Access by name instead of index — clearer code, same memory footprint as a plain tuple.

pythonrunnable cell

from collections import namedtuple

# Define a namedtuple type
Point = namedtuple("Point", ["x", "y"])
Color = namedtuple("Color", ["r", "g", "b"])
Employee = namedtuple("Employee", ["name", "department", "salary"])

# Create instances
p = Point(x=3, y=7)
c = Color(255, 128, 0)
emp = Employee("Alice", "Engineering", 95000)

# Named access (much clearer than p[0], p[1])
print(f"Point: ({p.x}, {p.y})")
print(f"Color: rgb({c.r}, {c.g}, {c.b})")
print(f"{emp.name} in {emp.department} earns ${emp.salary:,}")

# Still a tuple -- index access and unpacking work
print(p[0])                  # 3
x, y = p                     # unpacking
print(x, y)                  # 3, 7

# Immutable -- cannot modify fields
# p.x = 10    # AttributeError: can't set attribute

# _replace() creates a NEW namedtuple with one field changed
p2 = p._replace(x=10)
print(p2)   # Point(x=10, y=7)
print(p)    # Point(x=3, y=7) -- original unchanged

# _asdict() converts to a regular dict
print(emp._asdict())
# {'name': 'Alice', 'department': 'Engineering', 'salary': 95000}

#Memory Comparison: namedtuple vs dict vs class

pythonreference · read-only

import sys

# Representing the same data three ways
Point_nt   = namedtuple("Point_nt", ["x", "y", "z"])
p_namedtuple = Point_nt(1.0, 2.0, 3.0)
p_dict       = {"x": 1.0, "y": 2.0, "z": 3.0}

class PointClass:
    def __init__(self, x, y, z):
        self.x = x; self.y = y; self.z = z

p_class = PointClass(1.0, 2.0, 3.0)

print(f"namedtuple: {sys.getsizeof(p_namedtuple)} bytes")
# namedtuple: ~80 bytes  (small fixed size — like a plain tuple)
print(f"dict:       {sys.getsizeof(p_dict)} bytes")
# dict:       ~184 bytes (hash table overhead, even with compact dicts)
print(f"class:      {sys.getsizeof(p_class) + sys.getsizeof(p_class.__dict__)} bytes")
# class:      object header + __dict__ — typically 2-3x a namedtuple

Exact byte numbers depend on your Python build (3.12 / 3.13 / free-threaded), platform, and any pointer-tagging or shared-key optimization. The relative ranking holds: namedtuple < dict < class with dict. To shrink the class to namedtuple-level, declare __slots__ (covered in oop-advanced).

namedtuples are ideal for representing database rows, coordinates, config snapshots, or any read-only record where you want attribute access without the overhead of a full class.

What Do You Think?

p = Point(x=3, y=7). You write p._replace(x=10) on its own line and then print p. What do you see?

#deque: O(1) Operations on Both Ends

pythonrunnable cell

from collections import deque
import time

# Demonstrate the performance gap
n = 100_000

# list.insert(0) is O(n) -- shifts every element
lst = []
start = time.time()
for i in range(n):
    lst.insert(0, i)
list_time = time.time() - start

# deque.appendleft() is O(1) -- no shifting
dq = deque()
start = time.time()
for i in range(n):
    dq.appendleft(i)
deque_time = time.time() - start

print(f"list.insert(0): {list_time:.3f}s")
print(f"deque.appendleft: {deque_time:.4f}s")
# list is typically 100-1000x slower for large n

#Core deque Operations

pythonreference · read-only

dq = deque([1, 2, 3, 4, 5])

# Append / pop from both ends -- all O(1)
dq.append(6)           # [1, 2, 3, 4, 5, 6]  (right end)
dq.appendleft(0)       # [0, 1, 2, 3, 4, 5, 6]  (left end)
right = dq.pop()       # 6  (from right)
left  = dq.popleft()   # 0  (from left)
print(list(dq))        # [1, 2, 3, 4, 5]

# Rotate -- move n elements from one end to the other
dq.rotate(2)           # move 2 from right to left
print(list(dq))        # [4, 5, 1, 2, 3]
dq.rotate(-1)          # move 1 from left to right
print(list(dq))        # [5, 1, 2, 3, 4]

#Fixed-Size deque: The Sliding Window Pattern

pythonrunnable cell

from collections import deque

# maxlen: when full, adding to one end auto-discards from the other
history = deque(maxlen=5)
for i in range(10):
    history.append(i)
    print(f"Added {i}: {list(history)}")
# Added 0: [0]
# Added 1: [0, 1]
# ...
# Added 5: [1, 2, 3, 4, 5]  -- 0 was auto-discarded
# Added 9: [5, 6, 7, 8, 9]  -- always the last 5

# Sliding window average (useful for time-series smoothing)
def moving_average(data: list[float], window: int) -> list[float]:
    """Compute moving average using a deque window."""
    window_data: deque[float] = deque(maxlen=window)
    averages: list[float] = []

    for value in data:
        window_data.append(value)
        if len(window_data) == window:
            averages.append(sum(window_data) / window)

    return averages


prices = [10, 12, 11, 14, 15, 13, 16, 18, 17, 20]
ma = moving_average(prices, window=3)
print("Moving average (window=3):", [round(x, 2) for x in ma])
# [11.0, 12.33, 13.33, 14.0, 14.67, 15.67, 17.0, 18.33]

#BFS with deque

pythonrunnable cell

from collections import deque

def bfs_shortest_path(graph: dict, start: str, end: str) -> list[str] | None:
    """Find shortest path using BFS with deque."""
    if start == end:
        return [start]

    visited: set[str] = {start}
    # Each item in queue is a path so far
    queue: deque[list[str]] = deque([[start]])

    while queue:
        path = queue.popleft()
        current = path[-1]

        for neighbor in graph.get(current, []):
            if neighbor not in visited:
                new_path = path + [neighbor]
                if neighbor == end:
                    return new_path
                visited.add(neighbor)
                queue.append(new_path)

    return None   # no path found


graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

print(bfs_shortest_path(graph, "A", "F"))   # ['A', 'C', 'F']

Quick check

Change the single line `path = queue.popleft()` to `path = queue.pop()`. What does the function still do, and what does it stop doing?

#ChainMap: Layered Dict Lookups

ChainMap groups multiple dicts into a single logical view. Lookups search each map in order. Writes go to the first map.

pythonrunnable cell

from collections import ChainMap

# Classic use case: layered configuration
defaults = {
    "timeout": 30,
    "retries": 3,
    "debug": False,
    "log_level": "INFO",
}
env_vars = {
    "timeout": 60,
    "debug": True,
}
cli_args = {
    "log_level": "DEBUG",
}

# Priority: CLI > env vars > defaults
config = ChainMap(cli_args, env_vars, defaults)

print(config["timeout"])     # 60  (from env_vars)
print(config["retries"])     # 3   (from defaults)
print(config["log_level"])   # "DEBUG"  (from cli_args)
print(config["debug"])       # True  (from env_vars)

# Writes go to the first map only
config["new_key"] = "hello"
print(cli_args)   # {'log_level': 'DEBUG', 'new_key': 'hello'}
print(defaults)   # unchanged

# .maps gives access to the underlying list of dicts
print(config.maps)   # [cli_args, env_vars, defaults]

# Create a child context (adds a new layer at the front)
child = config.new_child({"timeout": 5})
print(child["timeout"])   # 5 (child override)
print(config["timeout"])  # 60 (parent unchanged)

What Do You Think?

config = ChainMap(cli_args, env_vars, defaults) and config['timeout'] reads 60 from env_vars. You then assign config['timeout'] = 99. Which dict changes?

#heapq: Priority Queues

Python's heapq module implements a min-heap on top of a regular Python list. The smallest element is always at index 0. Push and pop are O(log n).

pythonrunnable cell

import heapq

# heapq operates on a regular list
heap: list[int] = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

print(heap)               # [1, 3, 7, 10, 5] (heap-ordered, not sorted)
print(heapq.heappop(heap))  # 1 (smallest always pops first)
print(heapq.heappop(heap))  # 3
print(heapq.heappop(heap))  # 5

# heapify: convert an existing list to a heap in O(n)
data = [8, 2, 6, 4, 1, 9, 3]
heapq.heapify(data)
print(data)               # [1, 2, 3, 4, 8, 9, 6] (heap property satisfied)

# nlargest / nsmallest: efficiently find top-K elements
scores = [45, 92, 78, 55, 88, 91, 63, 71, 84, 97]
print(heapq.nlargest(3, scores))   # [97, 92, 91]
print(heapq.nsmallest(3, scores))  # [45, 55, 63]

#Max-Heap Trick

Python only has min-heap. To simulate a max-heap, negate your values.

pythonrunnable cell

import heapq

max_heap: list[int] = []
for value in [5, 1, 8, 3, 7]:
    heapq.heappush(max_heap, -value)   # store negated

print(-heapq.heappop(max_heap))  # 8 (largest)
print(-heapq.heappop(max_heap))  # 7
print(-heapq.heappop(max_heap))  # 5

#Priority Queue with Tasks

pythonrunnable cell

import heapq
from dataclasses import dataclass, field

@dataclass(order=True)
class Task:
    """A task with a priority and name."""
    priority: int
    name: str = field(compare=False)

task_queue: list[Task] = []
heapq.heappush(task_queue, Task(priority=3, name="Send report"))
heapq.heappush(task_queue, Task(priority=1, name="Fix critical bug"))
heapq.heappush(task_queue, Task(priority=2, name="Code review"))
heapq.heappush(task_queue, Task(priority=1, name="Deploy hotfix"))

# Process in priority order (lowest number = highest priority)
while task_queue:
    task = heapq.heappop(task_queue)
    print(f"  [{task.priority}] {task.name}")
# [1] Fix critical bug
# [1] Deploy hotfix
# [2] Code review
# [3] Send report

#K Closest Points to Origin

pythonrunnable cell

import heapq
import math

def k_closest(points: list[tuple[int, int]], k: int) -> list[tuple[int, int]]:
    """Return k points closest to the origin using a heap."""
    # Use a min-heap keyed by distance squared (avoid sqrt for speed)
    heap = [(p[0]**2 + p[1]**2, p) for p in points]
    heapq.heapify(heap)
    return [heapq.heappop(heap)[1] for _ in range(k)]


points = [(1, 3), (-2, 2), (5, 8), (0, 1), (3, -2)]
print(k_closest(points, k=2))   # [(0, 1), (-2, 2)]

Quick check

Pushing 10, 3, 7, 1, 5 gives the list `[1, 3, 7, 10, 5]`. Why is it not `[1, 3, 5, 7, 10]`?

#bisect: Binary Search on Sorted Lists

The bisect module provides binary search on already-sorted lists. Search is O(log n), but insertion maintains sort order at O(n) due to shifting.

pythonrunnable cell

import bisect

sorted_list = [1, 3, 5, 7, 9, 11, 15]

# bisect_left: index of leftmost position where x can be inserted
# (also the index where x would be if it already exists)
print(bisect.bisect_left(sorted_list, 7))    # 3 (7 is at index 3)
print(bisect.bisect_left(sorted_list, 6))    # 3 (6 would go at index 3)
print(bisect.bisect_left(sorted_list, 1))    # 0

# bisect_right (same as bisect.bisect): index AFTER any existing occurrences
sorted_with_dups = [1, 3, 3, 3, 5, 7]
print(bisect.bisect_left(sorted_with_dups, 3))    # 1 (before the 3s)
print(bisect.bisect_right(sorted_with_dups, 3))   # 4 (after the 3s)

# insort: insert while maintaining sorted order
data = [1, 3, 5, 7]
bisect.insort(data, 4)
print(data)   # [1, 3, 4, 5, 7]
bisect.insort(data, 6)
print(data)   # [1, 3, 4, 5, 6, 7]

#Grade Lookup with bisect

pythonrunnable cell

import bisect

def grade(score: int) -> str:
    """Assign a letter grade using binary search."""
    breakpoints = [60, 70, 80, 90]
    grades      = ["F", "D", "C", "B", "A"]
    return grades[bisect.bisect(breakpoints, score)]


test_scores = [45, 62, 75, 83, 91, 100]
for s in test_scores:
    print(f"  {s} -> {grade(s)}")
# 45 -> F
# 62 -> D
# 75 -> C
# 83 -> B
# 91 -> A
# 100 -> A

#Range Query with bisect

pythonrunnable cell

import bisect

def count_in_range(sorted_data: list[int], lo: int, hi: int) -> int:
    """Count elements in [lo, hi] using binary search. O(log n)."""
    left  = bisect.bisect_left(sorted_data, lo)
    right = bisect.bisect_right(sorted_data, hi)
    return right - left

data = sorted([12, 5, 19, 3, 8, 15, 7, 22, 11, 4])
print(data)   # [3, 4, 5, 7, 8, 11, 12, 15, 19, 22]
print(count_in_range(data, 5, 15))   # 6 (values: 5, 7, 8, 11, 12, 15)
print(count_in_range(data, 10, 20))  # 4 (values: 11, 12, 15, 19)

What Do You Think?

grade() uses bisect([60, 70, 80, 90], score). A student scores exactly 60. What grade comes back?

#Code Playground

pythonplayground.py · Pyodide

# Streaming word frequency analyzer
# Combine Counter + deque to analyze text in a sliding window
from collections import Counter, deque

# A streaming text processor that:
# 1. Maintains a sliding window of the last N words
# 2. Shows the most common words in the current window
# 3. Updates as each new word arrives

class StreamingAnalyzer:
  """Analyze word frequency in a sliding window of text."""

def __init__(self, window_size: int = 10) -> None:
      self.window_size = window_size
      self.window: deque[str] = deque(maxlen=window_size)
      self.counts: Counter = Counter()

self.window.append(word)
      self.counts[word] += 1

def snapshot(self) -> str:
      """Return a readable snapshot of the current window state."""
      return f"Window: {list(self.window)} | Top: {self.top_words(3)}"

# Test with a stream of words
text = "the cat sat on the mat the cat and the dog sat on the mat too"
words = text.split()

analyzer = StreamingAnalyzer(window_size=6)

Tests · Build a streaming word frequency analyzer with Counter and deque!

#Key Takeaways

Counter is a specialized dict for counting — Counter(iterable) counts frequencies automatically, supports arithmetic between counters, and .most_common(n) retrieves top-N in one call
defaultdict eliminates missing-key boilerplate — pass a factory (list, int, set, or a lambda) and missing keys are auto-initialized. Essential for grouping, graph adjacency lists, and inverted indexes
namedtuple creates readable, memory-efficient records — access by name (p.x) instead of index (p[0]), fully immutable and hashable, uses far less memory than a dict or class
deque gives O(1) both-end operations — appendleft/popleft are O(1) vs list's O(n). Use maxlen for sliding windows and fixed-size buffers. Always prefer deque over list for queues
heapq provides a priority queue on a regular list — min-heap by default; negate values for max-heap. nlargest/nsmallest find top-K efficiently without sorting the whole collection
bisect enables O(log n) search in sorted lists — bisect_left/bisect_right find insertion points, insort maintains order. Use for range queries, grade lookups, and anywhere you maintain a sorted structure

Quick Check1 / 5

What does Counter({'a': 3, 'b': 1}) - Counter({'a': 2, 'b': 5}) produce?

The collections Module: Python's Supercharged Data Structures

#Why the collections Module Exists

#Counter: Counting Made Effortless

#.most_common(n)

#Counter Arithmetic

#Use Case: Finding the Most Common Words

#defaultdict: Eliminate Missing-Key Boilerplate

#Common Default Factories

#Building a Graph with defaultdict

#OrderedDict: Order-Sensitive Operations

#LRU Cache with OrderedDict

#namedtuple: Readable, Memory-Efficient Records

#Memory Comparison: namedtuple vs dict vs class

#deque: O(1) Operations on Both Ends

#Core deque Operations

#Fixed-Size deque: The Sliding Window Pattern

#BFS with deque

#ChainMap: Layered Dict Lookups

#heapq: Priority Queues

#Max-Heap Trick

#Priority Queue with Tasks

#K Closest Points to Origin

#bisect: Binary Search on Sorted Lists

#Grade Lookup with bisect

#Range Query with bisect

#Code Playground

How deque Is Implemented: Doubly-Linked List of Fixed-Size Blocks

#Key Takeaways

Your Reflection

Continue Learning

Discussion

The collections Module: Python's Supercharged Data Structures

#Why the collections Module Exists

#Counter: Counting Made Effortless

#.most_common(n)

#Counter Arithmetic

#Use Case: Finding the Most Common Words

#defaultdict: Eliminate Missing-Key Boilerplate

#Common Default Factories

#Building a Graph with defaultdict

#OrderedDict: Order-Sensitive Operations

#LRU Cache with OrderedDict

#namedtuple: Readable, Memory-Efficient Records

#Memory Comparison: namedtuple vs dict vs class

#deque: O(1) Operations on Both Ends

#Core deque Operations

#Fixed-Size deque: The Sliding Window Pattern

#BFS with deque

#ChainMap: Layered Dict Lookups

#heapq: Priority Queues

#Max-Heap Trick

#Priority Queue with Tasks

#K Closest Points to Origin

#bisect: Binary Search on Sorted Lists

#Grade Lookup with bisect

#Range Query with bisect

#Code Playground

How deque Is Implemented: Doubly-Linked List of Fixed-Size Blocks

#Key Takeaways

Your Reflection

Continue Learning

Discussion