The Python toolbox for DSA

Python code for DSA is short. That is its trap: one short line can copy a whole list or walk it from end to end, and some lines give a wrong answer with no error at all.

This lesson lists what each tool costs, the six traps that break correct ideas, and which module to use for a queue and a heap.

Lists: cheap at the end, costly at the front

A list keeps its items in numbered slots. Changing the end touches one slot. Changing the front moves every other item.

┌──────────────────────────────────────────────┐
│                                              │
│   append(5): add at the end, nothing moves   │
│   ┌───┬───┬───┬───┬───┐                      │
│   │ 4 │ 9 │ 2 │ 7 │ 5 │   O(1)               │
│   └───┴───┴───┴───┴───┘                      │
│                     ▲                        │
│                    new                       │
│                                              │
│   pop(0): take 4, the rest move left         │
│   ┌───┬───┬───┬───┐                          │
│   │ 9 │ 2 │ 7 │ 5 │       O(n)               │
│   └───┴───┴───┴───┘                          │
│     ◀   ◀   ◀   ◀    each moved one slot     │
│                                              │
└──────────────────────────────────────────────┘

The difference is real. In a test on this laptop with Python 3.14:

• Emptying 100,000 items with pop(0) took about half a second.
• Twice the items took about four times as long: the mark of O(n²).
• A deque emptied the same items with popleft() in about 2 milliseconds.

What each operation costs

A line is not one step. if x in a inside a loop over a list is a hidden loop inside a loop: O(n²). Make a a set and it is O(1).

sort() and sorted()

python

words = ["pear", "fig", "apple"]
print(sorted(words, key=len))                     # ['fig', 'pear', 'apple']
print(sorted(words, key=lambda w: (-len(w), w)))  # ['apple', 'pear', 'fig']
nums = [9, 10, 1]
nums.sort(reverse=True)
print(nums)                                       # [10, 9, 1]

• sorted returns a new list. a.sort() sorts in place and returns None, so a = a.sort() leaves you with None.
• key says what to compare. A tuple key sorts by its first item, then breaks ties with the next: here, longest first, then A to Z.
• Numbers sort as numbers, and the sort is stable: equal items keep their order.

dict, set and Counter

Two tools solve a large share of array problems:

• set answers "have I seen this?" in one step.
• dict answers "how many?" or "where?" in one step.

The counting pattern you will write most often, by hand and with Counter:

python

from collections import Counter

count: dict[str, int] = {}
for ch in "banana":
    count[ch] = count.get(ch, 0) + 1
print(count)             # {'b': 1, 'a': 3, 'n': 2}

c = Counter("banana")
print(c.most_common(1))  # [('a', 3)]
print(c["z"])            # 0: a missing key counts as 0

• count.get(ch, 0) returns 0 the first time. count[ch] on a missing key raises a KeyError.
• Counter does the same count in one call. most_common(k) returns the k largest counts, largest first.

Three rules keep a dict or set correct:

• Keys must be hashable. A list cannot be a key: {[0, 1]} raises a TypeError. For a grid cell, use the tuple (row, col).
• A dict keeps insertion order. The printout above lists b first because it came first. A set keeps no order.
• defaultdict(list) builds lists for you. graph[u].append(v) works even the first time you see u.

Six traps

1. Slicing copies

python

a = [4, 9, 2, 7]
b = a[1:3]            # a new list with 2 items
b[0] = 99
print(a, b)           # [4, 9, 2, 7] [99, 2]
print("hello"[::-1])  # olleh

• A slice of k items costs O(k) time and memory.
• The costly case is recursion: solve(a[1:]) copies the list at every call, O(n²) in total. Pass an index instead, as in solve(a, i + 1).

2. Strings cannot change

s[0] = "j" raises a TypeError. Every string method returns a new string.

To build a string piece by piece, collect the pieces in a list and join once:

python

s = "hello"
parts: list[str] = []
for i in range(len(s) - 1, -1, -1):
    parts.append(s[i])
print("".join(parts))  # olleh

The Python docs warn that building a sequence with repeated + costs O(n²) in total. The list and join are O(n).

3. // and % round down

python

print(7 // 2, -7 // 2)  # 3 -4: rounds down, not toward zero
print(int(-7 / 2))      # -3: rounds toward zero
print(-7 % 3)           # 2: the sign follows the right side
print(6 / 2)            # 3.0: / always returns a float
print(2 ** 63)          # 9223372036854775808: no overflow

• Java and JavaScript give -3 for -7 / 2 and -1 for -7 % 3. Python gives -4 and 2. Check negative values when you port a solution.
• Use // for whole-number division. A float loses digits past about 9 × 10¹⁵, so int(a / b) can be wrong for large values.
• A Python int never overflows. Large numbers are slower, though, so "modulo 10⁹ + 7" still means % after every step.

You use % 10 and // 10 in the next lesson to take a number apart, digit by digit.

4. The recursion limit

Python stops a recursion at about 1,000 calls deep.

python

import sys

def depth(n: int) -> int:
    return 0 if n == 0 else 1 + depth(n - 1)

print(sys.getrecursionlimit())  # 1000
# depth(5000) raises RecursionError
sys.setrecursionlimit(10_000)
print(depth(5000))              # 5000

• A depth-first search on a path of 10⁵ nodes goes 10⁵ calls deep and fails.
• sys.setrecursionlimit raises the limit, but the docs warn that a limit set too high can crash Python. On this laptop, Python 3.9 at a depth of 10⁶ died with a segmentation fault and no Python error.
• For very deep inputs, turn the recursion into a loop with your own stack.

5. Mutable default arguments

Python builds a default value once, when it defines the function. A list default is then shared by every call.

python

def add_item(x: int, items: list[int] = []) -> list[int]:
    items.append(x)
    return items

print(add_item(1))  # [1]
print(add_item(2))  # [1, 2]: the same list as the first call

The fix: default to None, and make a new list inside the function.

python

def add_item(x: int, items: list[int] | None = None) -> list[int]:
    if items is None:
        items = []
    items.append(x)
    return items

print(add_item(1), add_item(2))  # [1] [2]

Watch for this in def dfs(node, path=[]) and def solve(n, memo={}). Results from one test case leak into the next.

6. The shared-row grid

* 3 on a list of lists repeats the same row object. Change one row, and all rows change.

┌────────────────────────────────────────────┐
│                                            │
│       [[0] * 3] * 3: one shared row        │
│       grid[0] ──┐                          │
│       grid[1] ──┼──▶ [ 1, 0, 0 ]           │
│       grid[2] ──┘                          │
│                                            │
│       a comprehension: three rows          │
│       grid[0] ─────▶ [ 1, 0, 0 ]           │
│       grid[1] ─────▶ [ 0, 0, 0 ]           │
│       grid[2] ─────▶ [ 0, 0, 0 ]           │
│                                            │
└────────────────────────────────────────────┘

python

bad = [[0] * 3] * 3
bad[0][0] = 1
print(bad)   # [[1, 0, 0], [1, 0, 0], [1, 0, 0]]

grid = [[0] * 3 for _ in range(3)]
grid[0][0] = 1
print(grid)  # [[1, 0, 0], [0, 0, 0], [0, 0, 0]]

The comprehension runs [0] * 3 once per row, so each row is a new list. The inner [0] * 3 is safe: a number cannot change, so sharing it does no harm.

Queues and heaps

Python has no queue or heap class you call by name. Use these:

python

from collections import deque
import heapq

queue = deque([4, 9])
queue.append(2)
print(queue.popleft())           # 4: first in, first out

heap = [5, 1, 8]
heapq.heapify(heap)              # reorders the list in place, O(n)
heapq.heappush(heap, 3)
print(heapq.heappop(heap))       # 1: smallest first

max_heap: list[int] = []
for x in [5, 1, 8]:
    heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap))  # 8: largest first

• heapq is a min-heap. For a max-heap, push -x and negate what you pop. Python ints never overflow, so this is safe.
• Push tuples to order by a key: heapq.heappush(heap, (dist, node)) pops the smallest dist first.
• Python 3.14 adds heappush_max and heappop_max. Older versions do not have them, so negation is the habit that works everywhere.
• bisect finds a place in a sorted list in O(log n), but inserting there is still O(n).

Read more

• TimeComplexity on the Python wiki, the cost of every list, deque, dict and set operation
• collections in the Python docs, for deque, Counter and defaultdict
• heapq in the Python docs, with examples of a priority queue
• Default argument values in the Python tutorial, on why a default is built once

Next: working with digits. Skip the other toolbox lessons unless you code in those languages too. You will take a number apart with % and //.