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 array and string problems you meet at work or in interviews are not new. They are variations on a handful of **patterns**. Recognising the pattern is usually the hard part; the code is short once you see it. Two of the most useful are **two pointers** and **sliding window**. Both turn a brute-force "check every pair" or "check every subarray" solution, which is O(n^2) or worse, into a single O(n) pass.

## Pattern 1: two pointers

Keep two indexes into the same list and move them toward each other (or in the same direction) based on what you see. It works when the data has an order you can exploit, usually because it is **sorted**.

**Example: pair with a given sum in a sorted list.** Find two numbers in `[1, 3, 4, 6, 8, 11]` that add to 10.

Brute force tries every pair: O(n^2). With two pointers, start at both ends:

```python
def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return (left, right)
        if total < target:
            left += 1        # need a bigger sum: move the small end up
        else:
            right -= 1       # need a smaller sum: move the big end down
    return None
```

| left | right | sum | action |
|---|---|---|---|
| 0 (1) | 5 (11) | 12 | too big, right -= 1 |
| 0 (1) | 4 (8) | 9 | too small, left += 1 |
| 1 (3) | 4 (8) | 11 | too big, right -= 1 |
| 1 (3) | 3 (6) | 9 | too small, left += 1 |
| 2 (4) | 3 (6) | 10 | found (2, 3) |

Why is it safe to skip pairs? If `nums[left] + nums[right]` is too small, then pairing `nums[left]` with anything left of `right` is even smaller, so `nums[left]` can never be part of the answer. Each step rules out a whole row of pairs. At most `n` steps: **O(n)** time and **O(1)** space. (For an **unsorted** list, use the dict approach from the hash maps lesson instead.)

Other two-pointer problems: checking a palindrome (compare the ends and move inward), removing duplicates from a sorted list in place, and merging two sorted lists (which you already did in merge sort).

## Pattern 2: sliding window

A **window** is a stretch of consecutive items, `nums[start:end]`. Instead of recomputing each window from scratch, slide it one step and update the answer using only what entered and what left.

**Fixed size: maximum sum of k consecutive items.** For `[2, 1, 5, 1, 3, 2]` and `k = 3`, the windows are `[2,1,5]=8`, `[1,5,1]=7`, `[5,1,3]=9`, `[1,3,2]=6`, so the answer is 9.

Recomputing each sum is O(n x k). Sliding is O(n):

```python
def max_window_sum(nums, k):
    if k <= 0 or k > len(nums):
        return None
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]   # add the new item, drop the old one
        best = max(best, window)
    return best
```

**Variable size: longest substring without repeating characters.** Grow the window on the right; when a repeat appears, shrink it from the left until the window is valid again.

```python
def longest_unique(s):
    last_seen = {}
    start = 0
    best = 0
    for end, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1     # jump past the earlier copy
        last_seen[ch] = end
        best = max(best, end - start + 1)
    return best

longest_unique("abcabcbb")   # 3 ("abc")
longest_unique("pwwkew")     # 3 ("wke")
```

Each character enters and leaves the window at most once: O(n).

## How to spot them

| clue in the problem | try |
|---|---|
| sorted input; find a pair or triple with a target | two pointers from both ends |
| compare from both ends (palindromes) | two pointers moving inward |
| "consecutive", "subarray", "substring", "window of size k" | sliding window |
| "longest / shortest stretch such that..." | variable sliding window |
| unsorted input; find a pair | hash map |

Patterns are a starting point, not a rule. Always write the brute-force idea first in one sentence. It gives you a correct baseline and a set of answers to test the faster version against.

## Common mistakes

- **Using two pointers on unsorted data** for a sum problem. Moving a pointer only makes sense if you know which way the sum will change.
- **`while left <= right`** in pair problems, which lets an item pair with itself.
- **Not handling `k > len(nums)`** or an empty list in window problems.
- **Off-by-one window length.** A window from `start` to `end` inclusive has `end - start + 1` items.
- **Moving `start` backwards** in the variable window. That is why the code checks `last_seen[ch] >= start`.

## Quick recap

- Two pointers: two indexes that move based on a comparison; usually needs sorted input; O(n), O(1) space.
- Sliding window: update a running answer as items enter and leave; O(n).
- Start from the brute force, look for the clue, then apply the pattern and test edge cases.

## Try it

The **Do** tab has three functions: a two-pointer pair search, a fixed sliding window and the longest substring without repeats. The checks compare against brute force on random inputs.


Recognise two-pointer and sliding-window problems and turn O(n^2) pair and subarray searches into one pass.

Common patterns

Two Pointers in 7 minutes | LeetCode Pattern

Sliding Window in 7 minutes | LeetCode Pattern

## Why it matters

Some recursive solutions are correct but hopelessly slow because they solve the same smaller problem again and again. **Dynamic programming (DP)** fixes that by solving each sub-problem once and reusing the answer. It powers spell checkers and `diff` (edit distance), DNA sequence alignment, route planning, resource allocation, and pricing problems. DP has a reputation for being hard, but the beginner version is one idea: **remember what you already computed**.

## The problem: repeated work

From the recursion lesson, the number of ways to climb `n` stairs taking 1 or 2 steps:

```python
def climb(n):
    if n <= 1:
        return 1
    return climb(n - 1) + climb(n - 2)
```

Draw the calls for `climb(5)`: it calls `climb(4)` and `climb(3)`; `climb(4)` calls `climb(3)` again and `climb(2)`; and so on. `climb(3)` is computed twice, `climb(2)` three times, `climb(1)` five times. The number of calls roughly doubles each time `n` goes up by one, about **O(2^n)**. `climb(30)` makes more than a million calls; `climb(80)` would not finish in your lifetime.

There are only `n + 1` different questions here (`climb(0)` up to `climb(n)`). The slowness comes entirely from asking them repeatedly.

## Fix 1: memoisation (top-down)

Keep a dictionary of answers. Before computing, check it; after computing, store the result.

```python
def climb(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = climb(n - 1, memo) + climb(n - 2, memo)
    return memo[n]

climb(80)   # 37889062373143906, instantly
```

Each value from 0 to `n` is computed once, so the time is **O(n)** with **O(n)** memory. Python can do this for you with a decorator:

```python
from functools import lru_cache

@lru_cache(maxsize=None)
def climb(n):
    if n <= 1:
        return 1
    return climb(n - 1) + climb(n - 2)
```

Memoisation keeps the recursive shape, which is often the easiest way to think about the problem. It is still limited by Python's recursion depth (about 1,000).

## Fix 2: tabulation (bottom-up)

Instead of starting from `n` and recursing down, start from the base cases and fill a table upward:

```python
def climb(n):
    ways = [1, 1] + [0] * (n - 1)      # ways[0] = ways[1] = 1
    for i in range(2, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2]
    return ways[n]
```

No recursion, no depth limit, same O(n). Since each entry only needs the previous two, you could even keep two variables instead of a list.

## Worked example: fewest coins

Given coin values and an amount, what is the fewest coins that make the amount exactly? For coins `[1, 3, 4]` and amount 6, the greedy choice (take the biggest coin first: 4 + 1 + 1) uses 3 coins, but 3 + 3 uses only 2. Greedy fails; DP does not.

Define `best[a]` = fewest coins to make amount `a`. Then `best[0] = 0`, and for each larger `a`, try every coin `c` that fits: `best[a] = min(best[a - c] + 1)`.

```python
def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

min_coins([1, 3, 4], 6)    # 2
min_coins([2], 3)          # -1, impossible
min_coins([5], 0)          # 0
```

| a | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| best[a] | 0 | 1 | 2 | 1 | 1 | 2 | 2 |

Time is O(amount x number of coins).

## A recipe for DP problems

1. **Write a brute-force recursive solution** and say in words what the function returns.
2. **Spot repeated sub-problems.** Do different paths of calls ask the same question?
3. **Identify the state**: the arguments that define a sub-problem (here just `n` or `a`).
4. **Memoise** on that state. Check correctness against the slow version on small inputs.
5. Optionally **convert to a table**, filling it in an order where every entry's dependencies come first.

## Common mistakes

- **Shared mutable defaults** like `def f(n, memo={})`, which leak answers between unrelated calls. Use `memo=None` and create the dict inside.
- **Memoising on the wrong key**: if the answer depends on two arguments, the key must include both (a tuple).
- **Wrong base cases**, such as `best[0]` set to infinity instead of 0.
- **Trusting greedy** without checking a counterexample like coins `[1, 3, 4]`.
- **Forgetting the impossible case** (return -1 or None, and say which).

## Quick recap

- DP = solve each sub-problem once and reuse it.
- Memoisation (top-down): recursion plus a dict or `lru_cache`.
- Tabulation (bottom-up): fill a list from the base cases upward.
- Turns exponential recursion like `climb` into O(n).

## Try it

In the **Do** tab, memoise `climb` so `climb(90)` returns instantly, and write `min_coins` bottom-up. The checks include zero, impossible amounts and a case where greedy is wrong.


Speed up recursive solutions by remembering answers to sub-problems (memoisation), then build them bottom-up in a table.

Intro to dynamic programming

What Is Dynamic Programming and How To Use It

Programming Terms: Memoization

Start the recorder and a 45-minute timer. Say the problem back in your own words, then list at least three clarifying questions out loud (for example: can the list be empty, can k be 0, what if no item fits) and write down the answers you will assume.

Write one normal example and three edge cases by hand with their expected answers, for example [3, 1, 2, 1] with k = 4 gives 3 ([1, 2, 1]); an empty list gives 0; [5] with k = 3 gives 0; [0, 0] with k = 0 gives 2.

Say a brute-force approach out loud (check every start and end) and state its time and space complexity.

Name the pattern that fits (non-negative items, consecutive stretch, longest such that...) and explain out loud how the faster approach works and its Big-O before writing any code.

Write the code on paper or in a plain editor without running it, narrating what each part does (what the window holds, when it grows, when it shrinks).

Trace your code by hand on the normal example and each edge case, saying the variable values out loud. Fix any bug you find and say what it was.

Finish by stating the final time and space complexity and one thing you would improve with more time. Stop the recording.

Now type your code into the Python activity of the Common patterns lesson (or any Python editor) and run it on your examples. Note whether your hand trace was right.

Listen to the recording and write down: how long you were silent at the longest stretch, whether you stated Big-O for both approaches, and whether you tested every edge case.

## Why it matters

Technical interviews for software developer, data scientist and machine learning engineer roles usually include a live problem-solving session. The interviewer cares less about whether you remember a trick and more about **how you think**: do you clarify the problem, consider options, write clear code and test it? The same habits make you a better teammate in code reviews, pair programming and design discussions, and they help a teacher model problem solving for a class. Thinking out loud is a skill, and like any skill it improves with deliberate practice.

## A framework you can repeat

Use the same steps every time so you never freeze on a blank editor.

**1. Understand (about 10% of the time).** Restate the problem in your own words. Ask about inputs and outputs: types, sizes, sorted or not, duplicates, negative numbers, empty input. Ask what to return when there is no answer.

> "So I get a list of integers, possibly empty, and a target. I return the indexes of two different items that add up to the target, or None. Can the list have duplicates? Roughly how large can it be?"

**2. Examples.** Work one normal example and at least two edge cases by hand **before** coding: empty, one item, no answer, duplicates. Write them down; they become your tests.

**3. Brute force first.** Say the simplest correct idea and its Big-O, even if it is slow.

> "The simple approach checks every pair. That is O(n^2) time and O(1) space. It's correct, so it's my fallback."

**4. Optimise.** Look for the pattern. Is it sorted (binary search, two pointers)? A counting or "seen before" question (hash map)? Consecutive items (sliding window)? Repeated sub-problems (DP)? Nested or tree-shaped (recursion, BFS/DFS)? State the new complexity and the trade-off.

> "If I store each number's index in a dict as I go, I can check for the complement in O(1). That's O(n) time and O(n) extra space."

**5. Code.** Narrate at the level of intent, not every keystroke: "this loop keeps a running window sum", "this check stops an item pairing with itself". Use clear names. If you get stuck, say what you are trying to do; interviewers often give a hint.

**6. Test.** Run your examples through the code by hand, line by line, tracking variables. Then the edge cases. Fix bugs calmly and say what you found.

**7. Review.** Restate the final time and space complexity and mention what you would improve with more time (input validation, a library function, handling very large inputs).

## What "out loud" sounds like

Good narration is short and specific:

- "I'm going to assume the input fits in memory; let me know if not."
- "I'm not sure yet whether sorting helps. Let me try the example."
- "This is failing on the empty list because `nums[0]` doesn't exist. I'll add a guard."

Silence for a few seconds while you think is fine. Say "Let me think for a moment" so the interviewer knows you are working.

## Practising effectively

- **Practise on paper or a plain editor** sometimes, without autocomplete or running code, because many interviews do not let you run code.
- **Time-box** yourself: about 30 to 45 minutes per problem. If you are stuck after 20, read a hint, then solve it yourself the next day.
- **Record yourself** or practise with a friend. Listening back is uncomfortable and very effective.
- **Keep a log** of problems: the pattern, the mistake you made, and the complexity. Reviewing patterns beats grinding hundreds of random problems.
- Use free practice sites (LeetCode, HackerRank, Exercism, NeetCode's free roadmap) and focus on **easy and medium** problems that use this course's patterns.

## Be honest about the process

Interview formats vary by company, and many now include take-home projects, pair programming or system design instead of, or as well as, algorithm puzzles. Data science and ML roles often add statistics, SQL and modelling questions. Teaching roles may ask you to explain a concept to a beginner. Read the job posting and ask the recruiter what to expect; many companies publish their interview guides.

## Common mistakes

- **Coding immediately** before understanding the problem or agreeing on the output.
- **Going silent** for minutes, so the interviewer cannot help or give you credit.
- **Skipping the brute force** and getting stuck on a clever idea with nothing to show.
- **Never testing**, or only testing the happy path.
- **Arguing with hints.** A hint is help, not criticism.

## Quick recap

Understand, examples, brute force, optimise, code, test, review. Say what you are doing and why, state Big-O at each stage, and test edge cases out loud.

## Try it

The **Do** tab walks you through a full practice session on a problem from this course, recorded on your phone or computer, with a short self-review.


Use a repeatable framework to understand, plan, code, test and explain a problem while talking through your thinking.

Solving problems out loud

How to Solve ANY Coding Interview Question in 6 Steps

How to NOT Fail a Technical Interview

Apply the two-pointer and sliding-window patterns, speed up recursion with dynamic programming, and practise solving problems out loud.