Measure efficiency with Big-O, then use searching, sorting, hash maps, stacks, linked lists, trees, graphs and dynamic programming in Python.

Data Structures & Algorithms

## Why it matters

Most real programs are built on two structures: an ordered sequence (an **array**, which Python calls a `list`) and a key-value lookup table (a **hash map**, which Python calls a `dict`; a `set` is a hash map with keys only). Choosing the right one is often the whole difference between a solution that takes a second and one that takes an hour. Counting, grouping, de-duplicating and "have I seen this before?" are all hash map problems.

## Arrays (Python lists)

A list stores items one after another, so the computer can jump straight to any position.

| operation | cost | why |
|---|---|---|
| `items[i]`, `items[i] = x` | O(1) | jump straight to position i |
| `items.append(x)` | O(1) on average | add at the end; occasionally the list grows its storage |
| `items.pop()` | O(1) | remove from the end |
| `items.insert(0, x)`, `items.pop(0)` | O(n) | every other item shifts one place |
| `x in items`, `items.index(x)` | O(n) | must scan |

Lists are great when order matters and you access by position or add at the end. They are slow when you search by value or change the front.

## Hash maps (Python dicts and sets)

A hash map runs each key through a **hash function** that turns it into a number, and uses that number to choose a slot in an internal array. To look the key up later, it hashes it again and goes straight to the slot. Two keys can land in the same slot (a **collision**); the table handles that and grows when it gets full, so the average cost stays constant.

| operation | average cost |
|---|---|
| `d[key]`, `d[key] = value`, `key in d`, `del d[key]` | O(1) |
| `x in some_set`, `some_set.add(x)` | O(1) |

Keys must be **hashable**: numbers, strings and tuples work; lists and dicts do not (they can change, which would change their hash). Since Python 3.7, dicts also remember insertion order.

## Worked example 1: counting

Count how often each word appears.

```python
def word_counts(text):
    counts = {}
    for word in text.lower().split():
        counts[word] = counts.get(word, 0) + 1
    return counts

word_counts("the cat and the hat")
# {'the': 2, 'cat': 1, 'and': 1, 'hat': 1}
```

`counts.get(word, 0)` returns the current count, or 0 the first time. One pass, O(1) per word, so O(n) overall. The standard library has a ready-made version, `collections.Counter`, and `Counter(words).most_common(3)` gives the top three. Writing the loop yourself first makes it clear what `Counter` does.

To find the most common word, loop over the dict once and keep the best so far. Decide what happens on ties (for example, pick the alphabetically first word) and on empty input (return `None`), and write the rule down. Interviewers and teammates will ask.

## Worked example 2: two sum

Given a list of numbers and a target, return the indexes of two different items that add up to the target.

The brute-force version checks every pair: O(n^2). The hash map version asks a better question at each step: "have I already seen the number that would complete this pair?"

```python
def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, n in enumerate(nums):
        need = target - n
        if need in seen:
            return (seen[need], i)
        seen[n] = i
    return None
```

Trace `nums = [2, 7, 11, 15]`, `target = 9`:

- i = 0, n = 2, need 7, not seen. Store `{2: 0}`.
- i = 1, n = 7, need 2, seen at index 0. Return `(0, 1)`.

Checking `seen` **before** storing the current number stops an item pairing with itself: with `[3]` and target 6, the 3 is not in `seen` yet when we look for its partner. With `[3, 3]`, the second 3 finds the first. One pass, O(n) time, O(n) space.

## Patterns to recognise

- "How many times..." or "most frequent..." means **count with a dict**.
- "Have I seen..." or "remove duplicates" means **a set**.
- "Find a pair / complement" means **store what you have seen, look up what you need**.
- "Group by..." means **dict of lists**: `groups.setdefault(key, []).append(item)`.

## Common mistakes

- **Searching a list inside a loop** (`if x in my_list`) when a set would make it O(1).
- **KeyError** from `counts[word] += 1` on a new key. Use `.get(word, 0)`, `setdefault`, or `collections.defaultdict(int)`.
- **Using a list as a key.** Convert it to a tuple first.
- **Pairing an item with itself** in two-sum by storing before checking.
- **Forgetting normalisation.** "The" and "the" are different keys unless you lowercase first.

## Quick recap

- Lists: O(1) by position and at the end; O(n) to search or change the front.
- Dicts and sets: O(1) average lookup, insert and delete by key.
- Count with `d.get(k, 0) + 1`; find pairs by storing what you have seen.

## Try it

The **Do** tab has three small functions: count words, find the most common one (with a tie rule), and two-sum in one pass.


Know what lists and dicts are fast and slow at, and use a dict to count things and solve two-sum in one pass.

Arrays and hash maps

Hash Tables - CS50 Shorts

Two Sum - Leetcode 1 - HashMap - Python

## Why it matters

Stacks and queues are lists with a rule about which end you use. That small rule makes them the right model for a lot of real systems: the browser back button and "undo" are stacks; print jobs, web request handling and message brokers are queues. Your Python interpreter keeps a **call stack** of functions, which is why a traceback lists the calls in order. Matching brackets with a stack is a classic first problem, and the same idea powers code editors, linters and parsers.

## Stack: last in, first out (LIFO)

Picture a stack of plates. You add (**push**) to the top and remove (**pop**) from the top. The last plate you put on is the first one you take off.

A Python list is a good stack, because adding and removing at the **end** are both O(1):

```python
stack = []
stack.append("a")    # push
stack.append("b")
stack.append("c")
top = stack[-1]      # peek: "c"
stack.pop()          # "c"
stack.pop()          # "b"
len(stack) == 0      # is it empty? not yet, "a" is left
```

Calling `pop()` on an empty list raises `IndexError`, so check `if stack:` first.

## Queue: first in, first out (FIFO)

Picture a line at a shop. You join at the back (**enqueue**) and leave from the front (**dequeue**).

Do not use `list.pop(0)` for this: removing the front of a list shifts every other item, which is O(n). Use `collections.deque` ("deck"), which is O(1) at both ends:

```python
from collections import deque

queue = deque()
queue.append("job1")     # enqueue at the back
queue.append("job2")
queue.append("job3")
queue.popleft()          # "job1": first in, first out
queue[0]                 # peek at the front: "job2"
```

You will use a deque as the queue in breadth-first search later in this course.

## Worked example: balanced brackets

A string is balanced if every opening bracket `(`, `[` or `{` is closed by the matching bracket in the right order. `"([]{})"` is balanced. `"(]"` and `"([)]"` are not, and neither is `"(("` (never closed) or `")("` (closed before opened).

The insight: the most recent unclosed bracket is the one that must close next. "Most recent" means a stack.

```python
def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return not stack
```

Trace `"{[()]}"`:

| char | action | stack after |
|---|---|---|
| `{` | push | `{` |
| `[` | push | `{ [` |
| `(` | push | `{ [ (` |
| `)` | matches `(`, pop | `{ [` |
| `]` | matches `[`, pop | `{` |
| `}` | matches `{`, pop | empty |

End of string and the stack is empty, so it is balanced. With `"([)]"`, the `)` arrives while `[` is on top, so it fails immediately.

Three checks catch every bad case:

1. A closer arrives and the stack is **empty** (`")("`).
2. A closer does not match the **top** (`"(]"`).
3. The stack is **not empty** at the end (`"(("`).

Characters that are not brackets are skipped, so `"print(x[0])"` works. The whole thing is one pass: O(n) time, O(n) space in the worst case.

## Choosing between them

- Need to undo, backtrack or match nested things? **Stack.**
- Need to process things in arrival order, or explore level by level? **Queue.**
- Need the highest priority first instead of the oldest? That is a **priority queue** (Python's `heapq`), a topic for later.

## Common mistakes

- **Using `list.pop(0)` as a queue.** It works but is O(n) per call; use `deque.popleft()`.
- **Popping an empty stack.** Check `if stack:` before `pop()` or `stack[-1]`.
- **Forgetting the final check.** `"(("` never triggers a mismatch; only `return not stack` catches it.
- **Counting instead of stacking.** Counting opens and closes passes `"([)]"`, which is wrong. Order matters, so you need the stack.

## Quick recap

- Stack = LIFO: `append` and `pop` on a list, both O(1).
- Queue = FIFO: `deque.append` and `deque.popleft`, both O(1).
- Bracket matching: push openers, match closers against the top, and end with an empty stack.

## Try it

In the **Do** tab, write `is_balanced` and a small queue function. The checks cover the empty string, single brackets, nesting, wrong order and text mixed in.


Use a stack (last in, first out) to check brackets, and a deque as a queue (first in, first out).

Stacks and queues

Stacks - CS50 Shorts

Valid Parentheses - Stack - Leetcode 20 - Python

## Why it matters

A linked list stores items in separate **nodes**, each pointing to the next. You will rarely build one by hand in Python application code, but the idea is everywhere: `collections.deque` is built from linked blocks, many operating system and database internals use them, and trees and graphs are "nodes with pointers" too. Linked lists are also the standard way to practise thinking about references, which is the skill that stops "why did changing this variable change that one?" bugs.

## The core idea

Each node holds a value and a reference to the next node. The list is just a reference to the first node, called the **head**. The last node points to `None`.

```python
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# 1 -> 2 -> 3 -> None
head = Node(1, Node(2, Node(3)))
```

An empty list is simply `head = None`.

## Lists versus linked lists

| operation | Python list | singly linked list |
|---|---|---|
| get item i | O(1) | O(n): walk from the head |
| add or remove at the front | O(n) | O(1): re-point the head |
| add at the end | O(1) average | O(n), or O(1) if you keep a tail reference |
| insert after a node you already hold | O(n) | O(1) |

Linked lists win when you add and remove near nodes you already have, and lose when you need random access.

## Walking a list

Almost every linked-list function uses the same loop: start at the head and follow `.next` until you reach `None`.

```python
def to_list(head):
    values = []
    current = head
    while current is not None:
        values.append(current.value)
        current = current.next
    return values

to_list(head)    # [1, 2, 3]
to_list(None)    # []
```

Building one from a Python list is easiest backwards, so each new node can point at the one already built:

```python
def from_list(values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head
```

## Worked example: reversing in place

Reverse `1 -> 2 -> 3 -> None` into `3 -> 2 -> 1 -> None` without creating new nodes. The trick is to walk the list once and turn each arrow around. You need three references:

- `prev`: the part already reversed (starts as `None`),
- `current`: the node you are fixing,
- `nxt`: the rest of the list, saved before you break the link.

```python
def reverse(head):
    prev = None
    current = head
    while current is not None:
        nxt = current.next      # 1. remember the rest
        current.next = prev     # 2. turn this arrow around
        prev = current          # 3. step prev forward
        current = nxt           # 4. step current forward
    return prev                 # prev is the new head
```

Trace:

| step | prev | current | list so far |
|---|---|---|---|
| start | None | 1 | `1 -> 2 -> 3` |
| 1 | 1 | 2 | reversed part `1 -> None` |
| 2 | 2 | 3 | reversed part `2 -> 1 -> None` |
| 3 | 3 | None | reversed part `3 -> 2 -> 1 -> None` |

When `current` becomes `None`, `prev` is the old last node, now the head. One pass, O(n) time, O(1) extra space. It works for the empty list (the loop never runs, return `None`) and a single node (one step, it points to `None`).

The order of the four lines matters. If you set `current.next = prev` before saving `nxt`, you lose the rest of the list.

## Draw it

The most reliable way to write pointer code is to draw boxes and arrows on paper for a three-node list, then update the drawing one line of code at a time. Then test the empty list and the one-node list separately: most linked-list bugs live there.

## Common mistakes

- **Losing the rest of the list** by overwriting `.next` before saving it.
- **Returning `head` after reversing.** The old head is now the tail; return `prev`.
- **`AttributeError: 'NoneType' object has no attribute 'next'`.** You followed `.next` past the end. Check `current is not None` first.
- **Infinite loops** from a cycle you created by accident (a node pointing back to an earlier node).
- **Using a linked list for random access.** If you need `items[i]` often, use a Python list.

## Quick recap

- A linked list is nodes with `value` and `next`; the head is the first node, `None` ends it.
- Front insert and removal are O(1); access by position is O(n).
- Walk with `while current is not None: ... current = current.next`.
- Reverse with `prev`, `current`, `nxt`: save, flip, step, step. Return `prev`.

## Try it

In the **Do** tab, write `from_list`, `to_list`, `length` and `reverse`. One check confirms you reversed the existing nodes rather than building new ones.


Build a singly linked list from nodes, walk it, and reverse it in place by re-pointing links.

Linked lists

Singly-Linked Lists - CS50 Shorts

Reverse Linked List - Iterative AND Recursive - Leetcode 206 - Python

Choose the right container: lists and hash maps for lookups and counting, stacks and queues for order, and linked lists for pointer-based data.