Setting Up: Python for DSA

Every algorithm you learn in this course eventually has to run somewhere, and how you set up Python shapes how fast you can write, test, and trust that code. This lesson is not a Python syntax primer — it assumes you already know functions, classes, and control flow — it’s about the specific habits, tools, and standard-library modules that make Python productive for practicing data structures and algorithms. Get this foundation right once, and every later lesson in this course, from arrays to graphs, will be faster to write and easier to debug.

Overview: Setting Up Python for DSA Work

Use Python 3.10 or newer. Recent versions let you write built-in generic type hints like list[int] and dict[str, int] directly, and the union syntax int | None instead of the older Optional[int] from the typing module. This course uses type hints on every function signature because they double as documentation and because writing them is expected in most technical interviews.

Resist the temptation to solve every problem by typing one-off expressions into a REPL. Instead, write each problem as a small, standalone script: define your function, then call it with concrete sample input inside a guarded main(), and print() the result. This habit matters for three reasons. First, it makes your reasoning reproducible — you (or a reviewer) can re-run the exact script and see the exact output. Second, it builds a personal library of solved problems you can revisit before interviews. Third, it mirrors how this lesson’s own examples are structured, since every one is a complete script you can paste and run as-is.

def solve(...):
    ...

if __name__ == "__main__":
    result = solve(sample_input)
    print(result)

Two standard-library modules matter immediately, before you write a single algorithm. The sys module exposes sys.getrecursionlimit() and sys.setrecursionlimit(). CPython defaults to a recursion limit of roughly 1000 stack frames, which matters because so many classic DSA solutions — tree traversals, backtracking, divide-and-conquer — are naturally recursive, and a large enough input will hit that ceiling and raise RecursionError. The time module lets you benchmark code, but only one of its clocks is appropriate: time.perf_counter() is a monotonic, high-resolution timer meant specifically for measuring short durations, while time.time() reads the system’s wall clock, which can jump backward or forward if the OS adjusts it. Always benchmark with time.perf_counter().

Beyond those, a handful of standard-library modules cover the vast majority of what DSA problems and coding interviews need, so you rarely have to build these structures from scratch (this course has dedicated lessons where you do build them, to see what’s underneath):

• collections.deque — a double-ended queue with O(1) append and pop from both ends; the right choice for queues, stacks, and sliding windows.
• collections.defaultdict — a dict that supplies a default value for missing keys instead of raising KeyError, ideal for grouping and counting.
• collections.Counter — a specialized dict for frequency counting, with a handy .most_common(n) method.
• heapq — a binary min-heap built directly on a plain list; Python’s built-in priority queue.
• bisect — binary search helpers for finding insertion points in a sorted sequence.
• itertools — combinatorics generators: permutations, combinations, product, and more, without writing the recursion yourself.
• functools.lru_cache — a one-line decorator that memoizes a recursive function’s results, turning many exponential-time recursive solutions into polynomial-time ones.

Time and Space Complexity

None of these tools are magic — each has a complexity cost rooted in how it’s implemented, and knowing that cost is the whole point of setting things up correctly before you start solving problems.

Operation	Time Complexity	Why
list.append(x)	O(1) amortized	Python over-allocates list capacity, so most appends just write into existing space; occasional resizes are rare enough to average out.
list.insert(0, x) / list.pop(0)	O(n)	A list is a contiguous array; inserting or removing at the front shifts every other element over by one.
x in list	O(n)	No index structure exists, so membership testing scans element by element in the worst case.
x in set / x in dict	O(1) average, O(n) worst case	Backed by a hash table: a hash of x usually jumps straight to its bucket; worst case only occurs with many hash collisions.
deque.append(x) / deque.appendleft(x)	O(1)	Implemented as a doubly linked list of fixed-size blocks, so both ends are reachable directly, with no shifting.
heapq.heappush / heapq.heappop	O(log n)	The heap invariant is restored by bubbling one element up or down the binary tree’s height, which is log n.
sorted(list)	O(n log n)	Python’s Timsort is a comparison sort; n log n is the proven lower bound for comparison-based sorting.

Space complexity deserves the same rigor, especially for recursion. Every recursive call pushes a new stack frame holding its local variables and return address, and that frame isn’t freed until the call returns. So a recursive function whose maximum call depth is n uses O(n) additional space on the call stack, even if it allocates no other memory. That’s exactly why Python enforces a recursion limit by default: without one, a runaway recursive function would keep consuming stack memory until the process crashed outright instead of failing with a catchable exception.

Examples

The following three scripts are complete and runnable — paste any of them into a file and run it to see the same output shown here.

Example 1: Benchmarking membership testing with time.perf_counter

import time


def time_membership_test(container, target: int) -> float:
    start = time.perf_counter()
    result = target in container
    end = time.perf_counter()
    return end - start


def main() -> None:
    size = 100_000
    numbers_list = list(range(size))
    numbers_set = set(range(size))
    target = size - 1  # last element: worst case for a list scan

    list_elapsed = time_membership_test(numbers_list, target)
    set_elapsed = time_membership_test(numbers_set, target)

    print(f"Target found in list: {target in numbers_list}")
    print(f"Target found in set: {target in numbers_set}")
    print(f"List timing is non-negative: {list_elapsed >= 0}")
    print(f"Set timing is non-negative: {set_elapsed >= 0}")
    print("List lookup is O(n), set lookup is O(1) average")


if __name__ == "__main__":
    main()

Output:

Target found in list: True
Target found in set: True
List timing is non-negative: True
Set timing is non-negative: True
List lookup is O(n), set lookup is O(1) average

Both containers hold the numbers 0 through 99,999, and the target is the very last one — the worst case for a list scan, since in must check every element before finding it at the end. The script deliberately doesn’t print the raw elapsed times, because wall-clock durations vary machine to machine and would make this lesson’s output non-reproducible. Instead it checks a fact that’s always true of perf_counter(): because it’s monotonic, end can never be earlier than start, so the elapsed time is always zero or positive.

Example 2: Recursion limits with a recursive factorial

import sys


def factorial(n: int) -> int:
    if n <= 1:  # base case prevents infinite recursion
        return 1
    return n * factorial(n - 1)


def main() -> None:
    print(f"Default recursion limit: {sys.getrecursionlimit()}")

    result = factorial(10)
    print(f"10! = {result}")

    try:
        factorial(5000)
    except RecursionError:
        print("RecursionError: exceeded Python's call stack depth")


if __name__ == "__main__":
    main()

Output:

Default recursion limit: 1000
10! = 3628800
RecursionError: exceeded Python's call stack depth

factorial(10) only recurses 10 levels deep, well under the default limit of 1000, so it returns normally with 3628800. factorial(5000) would need 5000 nested calls to complete, but the interpreter raises RecursionError once the call depth passes the limit — long before it would ever reach the base case — and the try/except catches it cleanly instead of letting the script crash.

Example 3: deque vs. list for queue-like access

from collections import deque


def process_with_list(n: int) -> list[int]:
    queue = list(range(n))
    processed = []
    while queue:
        processed.append(queue.pop(0))  # O(n) per call: shifts every remaining item
    return processed


def process_with_deque(n: int) -> list[int]:
    queue = deque(range(n))
    processed = []
    while queue:
        processed.append(queue.popleft())  # O(1) per call: no shifting needed
    return processed


def main() -> None:
    n = 5
    list_result = process_with_list(n)
    deque_result = process_with_deque(n)
    print(f"List-based result: {list_result}")
    print(f"Deque-based result: {deque_result}")
    print(f"Results match: {list_result == deque_result}")


if __name__ == "__main__":
    main()

Output:

List-based result: [0, 1, 2, 3, 4]
Deque-based result: [0, 1, 2, 3, 4]
Results match: True

Both functions produce identical output because they implement the same logic — drain a queue front to back. They differ only in cost: queue.pop(0) on a list is O(n) because every remaining element must shift left by one to fill the gap, making the whole loop O(n²) for n items; queue.popleft() on a deque is O(1) because a deque is a doubly linked list of blocks with direct access to both ends, making the whole loop O(n).

How It Works Step by Step

Trace Example 2’s call stack to see recursion depth concretely. Calling factorial(10) does not compute anything immediately — it first calls factorial(9), which calls factorial(8), and so on, each call pausing and waiting on the one below it. This builds a stack of frames: factorial(10) → factorial(9) → … → factorial(1), ten frames deep. Only when factorial(1) hits the base case (n <= 1) does it return 1 without recursing further, and the stack unwinds: factorial(2) computes 2 * 1 = 2 and returns, factorial(3) computes 3 * 2 = 6 and returns, and multiplication accumulates back up to factorial(10) returning 3628800.

factorial(5000) starts the same way, building one frame per call: factorial(5000) → factorial(4999) → factorial(4998) → …. Python tracks the current depth as it goes, and as soon as the next call would push the depth past sys.getrecursionlimit() (1000 by default), it raises RecursionError immediately — it never gets anywhere near n == 1. That exception propagates up through every already-open frame until it reaches the nearest matching except RecursionError, which in this script is the one in main().

Common Mistakes

Mistake 1: A mutable default argument

Default argument values in Python are evaluated once, when the function is defined — not once per call. If that default is a mutable object like a list, every call that doesn’t supply its own argument shares the exact same list.

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


def main() -> None:
    first_call = add_item(1)
    second_call = add_item(2)
    print(f"First call: {first_call}")
    print(f"Second call: {second_call}")


if __name__ == "__main__":
    main()

Output:

First call: [1, 2]
Second call: [1, 2]

This looks like it should print [1] then [2], but both calls append to the same underlying list object, so by the time anything is printed, first_call and second_call are two names pointing at that one shared list, now holding both items. This bug is especially dangerous in recursive, backtracking-style code that accumulates results into a list parameter. Fix it by defaulting to None and creating a fresh list inside the function body:

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


def main() -> None:
    first_call = add_item(1)
    second_call = add_item(2)
    print(f"First call: {first_call}")
    print(f"Second call: {second_call}")


if __name__ == "__main__":
    main()

Output:

First call: [1]
Second call: [2]

Mistake 2: A recursive function with no base case

Every recursive function needs a condition that stops the recursion. Skip it, and the function calls itself forever — or rather, until it exhausts the recursion limit and crashes.

def countdown(n: int) -> None:
    print(n)
    countdown(n - 1)  # no base case: this recurses forever until RecursionError


countdown(5)

This snippet is intentionally broken and is shown only as a diagram — running it prints 5, 4, 3, 2, 1, 0, -1, -2, ... all the way down past zero into negative numbers until Python raises RecursionError around depth 1000, since nothing ever stops it. The fix is a single guard clause that returns once the work is done:

def countdown(n: int) -> None:
    if n < 0:  # base case: stop once we pass zero
        return
    print(n)
    countdown(n - 1)


def main() -> None:
    countdown(3)


if __name__ == "__main__":
    main()

Output:

3
2
1
0

Best Practices

• Benchmark with time.perf_counter(), never time.time() — the latter reads the system clock and can jump if the OS adjusts it.
• Structure every practice script with a guarded if __name__ == "__main__": block so your functions stay importable and testable without side effects when reused later in this course.
• Reach for collections.deque instead of a plain list whenever you need O(1) work at both ends — queues, sliding windows, and breadth-first search all fit this pattern.
• Reach for heapq whenever you repeatedly need the smallest (or, by negating values, largest) item from a changing collection — it’s Python’s built-in priority queue.
• Use functools.lru_cache(maxsize=None) to memoize a pure recursive function once you’ve confirmed its base case is correct, rather than hand-rolling a dictionary cache.
• Treat sys.setrecursionlimit() as a last resort, not a fix. Raising it doesn’t grow the operating system’s real call stack, so a limit set too high can crash the interpreter outright (a segmentation fault) instead of raising a catchable RecursionError. Prefer rewriting deep recursion iteratively with an explicit stack.
• Start with small, deterministic sample inputs so you can trace and verify output by hand, then scale up input size afterward to observe the complexity you predicted.

Practice Exercises

1. Word frequency counter. Write a script with a function count_frequencies(words: list[str]) -> dict[str, int] that counts how often each word appears in a list of 10 sample words, using collections.Counter, and prints the two most common words. Hint: Counter objects have a .most_common(n) method that returns a list of (word, count) tuples.

2. Recursive vs. iterative sum. Write two functions that each sum a list of numbers: a recursive one with a base case for an empty list, and an iterative one using a loop. Call the recursive version on a list of 2000 numbers and confirm it raises RecursionError; then explain in a comment why the iterative version has no such limitation.

3. Front vs. back insertion. Using time.perf_counter(), write a script that appends 50,000 integers to a list with list.append and, separately, inserts 50,000 integers at the front with list.insert(0, item). Don’t print the raw timings (they vary by machine) — print only which one finished faster, and explain the result using this lesson’s complexity table.

Summary

• Python for DSA work is mostly about picking the right built-in tool, not new syntax: collections, heapq, bisect, itertools, and functools.lru_cache cover most of what interview-style problems need.
• list.append is O(1) amortized; list.insert(0, x) and list.pop(0) are O(n); membership and insertion on set/dict are O(1) average; deque gives O(1) at both ends.
• Every recursive call adds one O(1) stack frame, so a recursive algorithm’s space complexity includes its maximum call depth; Python’s default recursion limit (about 1000) raises a catchable RecursionError before it can exhaust real memory.
• Never use a mutable default argument like collected=[] — it’s created once and shared across every call that doesn’t supply its own; default to None and initialize inside the function instead.
• Always give recursive functions a base case, benchmark with time.perf_counter() instead of time.time(), and structure practice scripts with a main() function so solved problems become a reusable library as this course continues.