Data Structures and Algorithms Introduction

Every program you write comes down to two questions: how do you store your data, and how do you process it? A data structure is a way of organizing data in memory — an array, a linked list, a hash map, a tree — so it can be accessed and changed efficiently. An algorithm is a precise, step-by-step procedure for solving a problem, like searching for a value or sorting a list. This course teaches you both halves of that toolbox, plus the analytical skill of measuring how fast and how much memory a solution uses, so you can tell which tool actually fits the job.

Overview: Why Data Structures and Algorithms Matter

Picture a contacts app with ten thousand names. Store them in a plain list and look someone up by scanning from the start, and you might check all ten thousand entries before finding — or ruling out — the one you want. Store the same data in a dict keyed by name, and a lookup takes roughly the same handful of steps whether there are ten contacts or ten million. Same data, same problem, two different data structures, and a completely different growth curve as the app scales — that gap is the entire reason this subject exists. Every structure has a shape: arrays give fast indexed access but slow middle-insertion; linked lists give fast insertion at a known point but slow indexed access; hash maps give fast lookup by key but no ordering; trees give ordered, fast lookup at a higher cost per operation. Algorithms are what you run on top of a structure to answer a question, and the two choices depend on each other — binary search needs sorted, indexable data; a graph traversal needs an adjacency structure.

Correctness always comes first — a fast but wrong algorithm is useless — but once a solution is correct, efficiency decides whether it survives real input sizes. Code that’s fine on a 100-row test fixture can grind to a halt on a 10-million-row production table for no reason other than nobody reasoned about how the work grows with input size; that reasoning is complexity analysis, covered next. The rest of this course builds outward from here: arrays and lists, linked lists, stacks and queues, hash tables, trees, and graphs as structures, then sorting, searching, recursion, and dynamic programming as the algorithm families you run on top of them.

Time and Space Complexity

Big-O notation describes how an algorithm’s running time (or memory use) grows as the input size, conventionally called n, grows — not the actual number of seconds or bytes on any particular machine. It answers “if I double n, roughly what happens to the work done?” rather than “how many milliseconds did this take on my laptop.” Because Big-O only cares about growth as n gets large, you drop constant factors and lower-order terms: an algorithm that does 3n + 20 steps is still O(n), because as n grows the +20 becomes irrelevant and the 3 just scales the line without changing its shape.

You’ll often see three variants of the same bound: best case (the friendliest input), average case (a typical input), and worst case (the input that makes the algorithm work hardest). Interviews and course material usually quote worst case unless stated otherwise, because it’s a guarantee — average case depends on assumptions about the input distribution that may not hold in production.

Notation	Name	Typical example
O(1)	Constant	Indexing a list by position; a dict lookup (average case)
O(log n)	Logarithmic	Binary search on a sorted array
O(n)	Linear	Linear search; scanning a list once
O(n log n)	Linearithmic	Efficient comparison sorts (merge sort, Python’s Timsort)
O(n²)	Quadratic	Nested loops comparing every pair; naive sorts
O(2ⁿ)	Exponential	Naive recursive generation of all subsets

Two examples ground this. Linear search may inspect every one of the n elements before finding (or ruling out) the target, so its worst case is O(n). Binary search instead throws away half of the remaining search space on every comparison — after one step at most n/2 elements are left, after two steps at most n/4, and so on, so it takes about log₂(n) steps to shrink the space down to one element, giving O(log n). That halving trick only works because the array is sorted: sortedness is what lets the algorithm know, from a single comparison against the midpoint, which half the target could possibly be in. Run binary search on unsorted data and the result is simply wrong.

Hash-based structures (dict, set) get their O(1) average-case lookup from hashing: a key is fed through a hash function that maps it to a bucket index, so finding, inserting, or checking membership just means computing the hash and jumping straight to that bucket instead of scanning. That average case can degrade to O(n) worst case if many keys collide into the same bucket, but Python’s hash implementation makes this rare enough in practice that dict/set lookups are treated as O(1) by default.

A few Python-specific facts are worth memorizing: list indexing and appending at the end are O(1) amortized, but inserting or deleting at the front is O(n) because every later element has to shift. The in operator is O(n) on a list but O(1) average on a set or dict — this single fact explains a huge number of “why is my code slow” questions. dict and set preserve insertion order since Python 3.7, but insertion order is not sorted order — don’t assume iterating a dict gives you sorted keys. And building a string by repeated concatenation inside a loop is O(n²) overall, because each concatenation copies the whole string built so far; use a list and "".join(...) instead, which is O(n).

Space complexity measures extra memory used beyond the input itself. Iterative binary search uses O(1) extra space (a few index variables); the hash-map version of two-sum below trades O(n) extra space for an O(n) time bound instead of the O(n²) time a nested-loop version would need. Trading space for time — and knowing when that trade is worth it — is one of the most common decisions in this course.

Examples

The three examples below all solve a “find something” problem with different structures and different resulting complexity. Each counts its own steps so you can see the growth pattern directly in the output, without timing anything.

Example 1: Linear Search

def linear_search(arr: list[int], target: int) -> tuple[int, int]:
    steps = 0
    for i, value in enumerate(arr):
        steps += 1
        if value == target:
            return i, steps
    return -1, steps

numbers = [4, 2, 9, 7, 5, 1, 8, 3, 6, 0]
index, steps = linear_search(numbers, 6)
print(f"Found 6 at index {index} after {steps} steps")

Output:

Found 6 at index 8 after 9 steps

linear_search walks the list from the front, incrementing steps on every comparison. The value 6 sits at index 8 in numbers, so the function checks 9 elements (indices 0 through 8) before it finds a match — it has no way to skip ahead. If 6 weren’t in the list at all, it would take all 10 steps and return (-1, 10). Worst case is always proportional to n, the length of the list.

Example 2: Binary Search

def binary_search(arr: list[int], target: int) -> tuple[int, int]:
    left, right = 0, len(arr) - 1
    steps = 0
    while left <= right:
        steps += 1
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid, steps
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1, steps

sorted_numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
index, steps = binary_search(sorted_numbers, 6)
print(f"Found 6 at index {index} after {steps} steps")

Output:

Found 6 at index 6 after 4 steps

The list is sorted first, which lets binary_search compare against the midpoint and discard half the remaining range each iteration. Even though sorted_numbers also has 10 elements, the function needs only 4 steps instead of 9 — the next section traces exactly how those 4 steps narrow the range down to index 6. That’s the payoff of O(log n): the gap between it and O(n) widens dramatically as n grows into the thousands or millions.

Example 3: Two Sum with a Hash Map

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for index, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index
    return []

numbers = [2, 7, 11, 15]
result = two_sum(numbers, 9)
print(f"Indices: {result}")

Output:

Indices: [0, 1]

A naive solution to “find two numbers that add up to a target” checks every pair with nested loops, which is O(n²). two_sum does it in one pass by keeping a dict called seen that maps each value it has already visited to its index. For every new value it asks “have I already seen the number that, combined with this one, hits the target?” — the complement check — which is an O(1) average-case dict lookup instead of an O(n) inner scan. At index 0 it sees 2, computes complement = 7, hasn’t seen a 7 yet, and records 2 → 0. At index 1 it sees 7, computes complement = 2, and 2 is in seen (from index 0), so it immediately returns [0, 1]. One pass, O(n) time, at the cost of O(n) extra space.

How It Works Step by Step

Binary search is worth tracing carefully because “halve the range” is easy to state but easy to get wrong at the boundaries. Here’s exactly what happens for binary_search(sorted_numbers, 6) from Example 2, where sorted_numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:

Step	left	right	mid	arr[mid]	Comparison	Action
1	0	9	4	4	4 < 6	target is bigger, search right half: left = 5
2	5	9	7	7	7 > 6	target is smaller, search left half: right = 6
3	5	6	5	5	5 < 6	target is bigger, search right half: left = 6
4	6	6	6	6	6 == 6	match — return index 6

The invariant that makes this correct: if the target is anywhere in the array, it’s always somewhere in arr[left..right]. Every comparison either confirms a match or safely discards the half of the range that provably cannot contain the target, because the array is sorted. The range shrinks by roughly half each step (9 → 4 → 1 → 0 elements wide), which is why it takes O(log n) steps instead of O(n): you divide the problem size by two each time rather than subtracting one.

Common Mistakes

Mistake 1: Off-by-one in the loop condition

It’s tempting to write the binary search loop as while left < right instead of while left <= right. The bug is subtle because it still works most of the time — it only fails when the search range has narrowed to exactly one element:

def binary_search_buggy(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left < right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

single_element = [1]
print(binary_search_buggy(single_element, 1))

Output:

-1

With a one-element array, left and right both start at 0, so left < right is immediately False and the loop body never runs — the one element never gets compared, even though it’s the answer. Using <= fixes it, because a range with left == right still has one valid element left to check:

def binary_search_fixed(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

single_element = [1]
print(binary_search_fixed(single_element, 1))

Output:

0

The general lesson: whenever a loop bound decides whether the last element gets processed, trace the one-element case before trusting the condition.

Mistake 2: Mutable default arguments

Default argument values in Python are evaluated once, when the function is defined — not once per call. That’s harmless for immutable defaults like 0 or None, but dangerous for a mutable default like [], because every call that doesn’t supply its own argument shares the exact same list object:

def add_to_cart(item: str, cart: list[str] = []) -> list[str]:
    cart.append(item)
    return cart

print(add_to_cart("apple"))
print(add_to_cart("banana"))

Output:

['apple']
['apple', 'banana']

The second call didn’t start with a fresh cart — it kept appending to the same list object left over from the first call, so "apple" leaks into a cart that should have only contained "banana". The fix is the standard idiom: default to None, and create a new list inside the function body when no cart was passed in:

def add_to_cart(item: str, cart: list[str] | None = None) -> list[str]:
    if cart is None:
        cart = []
    cart.append(item)
    return cart

print(add_to_cart("apple"))
print(add_to_cart("banana"))

Output:

['apple']
['banana']

Now every call that doesn’t pass its own cart gets a brand-new empty list, because the list is created fresh inside the function body each time, not shared from the function’s definition.

Best Practices

• State the time and space complexity of any solution you write, even in casual code — it’s the fastest way to catch a design that won’t scale before it ships.
• Reach for Python’s built-in structures (list, dict, set, collections.deque, heapq) before writing your own; they’re implemented in C and heavily optimized.
• Match the structure to the operation you do most often: mostly looking things up by key → dict; mostly need order and indexed access → list; mostly checking membership → set.
• Don’t optimize blindly. Big-O describes growth as n gets large; for small, fixed-size inputs an algorithm with a “worse” bound but lower constant overhead can still be faster in practice.
• Remember average case and worst case can differ — a dict is O(1) average but O(n) worst case under heavy collisions — and know which one actually matters for your problem.
• Always test the edge cases: an empty input, a single-element input, and an input with duplicate values. Off-by-one and base-case bugs love to hide there.
• In interviews, state the brute-force solution and its complexity first, then explain the optimization and why it improves the bound — that shows you understand the tradeoff, not just the trick.

Practice Exercises

1. Write contains_duplicate(nums: list[int]) -> bool that returns True if any value appears more than once in nums, using O(n) time. Hint: a set lets you check “have I seen this before?” in O(1) average time. Test on [1, 2, 3, 1] (expect True) and [1, 2, 3] (expect False).
2. The two_sum function above returns only the first matching pair and stops. Rewrite it as two_sum_all(nums: list[int], target: int) -> list[list[int]] that returns every pair of indices that sums to target. What’s the time complexity of your version, and why?
3. Trace binary_search by hand on sorted_numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] searching for target = 10, a value that isn’t in the list. Write out left, right, and mid at every iteration, and explain what condition ends the loop and causes it to return -1.

Summary

• A data structure organizes data for efficient access and modification; an algorithm is a step-by-step procedure for solving a problem — this course builds both on top of the Python you already know.
• Big-O notation describes how time or space scales with input size n, ignoring constants and lower-order terms; always state whether you mean best, average, or worst case.
• Linear search is O(n) because it may scan every element; binary search is O(log n) because it halves the search space each step, but it requires the input to already be sorted.
• A hash-based solution (dict/set) can turn an O(n²) nested-loop problem into O(n) time at the cost of O(n) extra space — a core time/space tradeoff you’ll see throughout this course.
• Off-by-one loop bounds and mutable default arguments are two of the most common Python bugs in DSA code — watch for both, and always test empty, single-element, and duplicate-value inputs.
• Coming next: arrays and lists, linked lists, stacks and queues, hash tables, trees, and graphs as structures, followed by sorting, searching, recursion, and dynamic programming as algorithm families built on top of them.