# DSA Roadmap: full content

CoSc3111 (AAU) in C++. Don't just watch: implement it yourself, then solve 2–3 problems.


---

# 1.1 What Is a Data Structure?

> A data structure is a way of organising data in memory so the operations you need are fast. Learn how they are classified and what makes a good one.

Chapter: Introduction to Data Structures · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/what-is-a-data-structure

## Mental model

Think of a **kitchen**. You could throw every ingredient into one big box, but then finding the salt takes forever. So you use a spice rack (quick to grab by position), a fridge with shelves (grouped by type) and a stack of plates (you only ever take the top one). Same food, different **organisation**, and each one makes a different job fast.

A **data structure** is exactly that for a program: *a way of storing and organising data in memory so that the operations we need are efficient.*

### How we classify them

- **Primitive**: built into the language, holds one value: `int`, `float`, `char`, `bool`.
- **Non-primitive**: built from primitives, holds a collection.
  - **Linear**: items form a sequence; each has at most one "next": arrays, linked lists, stacks, queues.
  - **Non-linear**: one item can connect to many: trees, graphs.
- **Static vs dynamic** (a separate question): is the size fixed when the program is compiled (array), or can it change while running (linked list, `vector`)?

### Characteristics: what we do with a data structure

Every structure is judged by how well it supports a few standard operations: **traversing** (visit every item), **searching**, **inserting**, **deleting**, **sorting** and **merging**. When we analyse a structure, we ask "how much time and memory does each of these cost?"

### Data structure vs algorithm

A data structure is the *shelf*; an algorithm is the *recipe*. Binary search (an algorithm) only works because the data sits in a sorted array (a data structure). Good programs pick both together.

## C++ code: one of each kind

```cpp
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

struct Node {           // building block of a linked list (dynamic, linear)
    int data;
    Node* next;
};

int main() {
    int age = 20;                    // primitive
    char grade = 'A';                // primitive
    int marks[5] = {70, 85, 90, 65, 88};  // static, linear: size fixed at compile time

    vector<int> scores;              // dynamic, linear: grows at run time
    for (int m : marks) scores.push_back(m);
    scores.push_back(95);

    Node* second = new Node{2, nullptr};
    Node* head = new Node{1, second};  // 1 -> 2 -> nullptr

    stack<int> s;  s.push(1); s.push(2);   // linear ADT: last in, first out
    queue<int> q;  q.push(1); q.push(2);   // linear ADT: first in, first out

    cout << "age=" << age << " grade=" << grade << "\n";
    cout << "marks has fixed size " << sizeof(marks) / sizeof(marks[0]) << "\n";
    cout << "scores grew to " << scores.size() << "\n";
    cout << "list: " << head->data << " -> " << head->next->data << "\n";
    cout << "stack top=" << s.top() << ", queue front=" << q.front() << "\n";

    delete second;
    delete head;
}
```

Expected output:

```text
age=20 grade=A
marks has fixed size 5
scores grew to 6
list: 1 -> 2
stack top=2, queue front=1
```

## Complexity

| Case | Cost |
| --- | --- |
| Array: read item i | O(1) |
| Array: insert at the front | O(n): shift everything |
| Linked list: insert at the front | O(1) |
| Linked list: read item i | O(n): walk from the head |


There is no "best" data structure, only the best one **for the operations you do most**. This table is the whole reason the course exists.

## Videos

- [Introduction to data structures](https://youtu.be/92S4zgXN17o) (mycodeschool): Six minutes that set up the whole course, including the ADT idea you meet next.

## Exam lens

Likely questions:

- Define a data structure. Give two examples of linear and two of non-linear data structures.
- Differentiate between primitive and non-primitive data structures with examples.
- What is the difference between static and dynamic data structures? Classify array and linked list.
- List the characteristics (operations) of a data structure.

Common mistakes:

- Calling a stack "non-linear". Stacks and queues are linear; only trees and graphs are non-linear here.
- Saying an array is dynamic. A C++ array has a fixed size; `vector` and linked lists are dynamic.
- Confusing a data structure (how data is stored) with an algorithm (the steps that use it).

## Quick check

1. Which of these is a **non-linear** data structure?
   A. Queue
   B. Stack
   C. Tree
   D. Array
   Answer: C. In a tree, one node can lead to several children. Queue, stack and array are all sequences.

2. An `int marks[50];` in C++ is best described as:
   A. Primitive and dynamic
   B. Non-primitive, linear and static
   C. Non-primitive, non-linear and dynamic
   D. Primitive and static
   Answer: B. An array holds many values (non-primitive), in a sequence (linear), with a size fixed at compile time (static).

3. Which structure can grow and shrink at run time one item at a time without copying?
   A. A plain C++ array
   B. A linked list
   C. A 2-D array
   D. An `int`
   Answer: B. Each linked-list node is created with `new` and removed with `delete` when needed.

4. Choosing a data structure mainly depends on…
   A. how many lines of code it needs
   B. which operations must be fast
   C. the programming language
   D. whether it is linear
   Answer: B. Arrays give O(1) indexing, linked lists give O(1) front insertion, and so on. Pick for your most frequent operations.

## Practice

**Trace by hand.** Classify each as primitive/non-primitive, linear/non-linear, static/dynamic: `char`, `int a[10]`, `vector<string>`, a family tree, a road map between cities, a printer queue.

Solution:

- `char`: primitive
- `int a[10]`: non-primitive, linear, static
- `vector<string>`: non-primitive, linear, dynamic
- family tree: non-primitive, non-linear (tree), usually dynamic
- road map: non-primitive, non-linear (graph)
- printer queue: non-primitive, linear (queue)


**Implement it.** Write a program that stores 5 temperatures in an array and the same values in a `vector`. Then add a 6th value to both. What happens with the array?

Hint: You cannot add a 6th element to `double t[5]`; writing `t[5]` is out of bounds. The vector just calls `push_back`.

**Problems:**

- [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/) (easy). Hint: Compare a double loop over an array (O(n²)) with a `set` that remembers what you have seen (O(n)). Same problem, different data structure.
- [Two Sum](https://leetcode.com/problems/two-sum/) (easy). Hint: For each number x you need to know quickly whether `target - x` appeared before. Which structure answers "have I seen this?" in O(1)?

## Mastery checklist

- [ ] I can define a data structure in one sentence.
- [ ] I can draw the classification tree from memory.
- [ ] I can classify any structure as linear/non-linear and static/dynamic.
- [ ] I can explain why there is no single best data structure.


---

# 1.2 ADTs & Abstraction

> An Abstract Data Type says WHAT operations exist; a data structure says HOW they are built. Separating the two is the key idea of this course.

Chapter: Introduction to Data Structures · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/adt-and-abstraction

## Mental model

Think of a **TV remote**. You know *what* the buttons do: power, volume up, next channel. You have no idea *how* the infrared signal is encoded, and you don't need to. If the manufacturer redesigns the circuit board, you keep pressing the same buttons.

**Abstraction** means showing only what matters to the user and hiding the rest.

### Abstract Data Type (ADT)

An **ADT** is the "remote control" view of a data type. It describes:

1. **the data** it holds (logically, e.g. "an ordered collection"),
2. **the operations** allowed on it (e.g. `push`, `pop`, `top`, `isEmpty`),
3. **the rules and error conditions** (e.g. "pop on an empty stack is an error").

It says nothing about arrays, pointers or memory.

### Data structure

A **data structure** is the *circuit board*: a concrete way to store the data so the ADT's operations work. The Stack ADT can be implemented with an array **or** a linked list. Both are valid data structures for the same ADT.

| | ADT | Data structure |
|---|---|---|
| Answers | *What* can I do? | *How* is it stored? |
| Level | Logical | Physical / implementation |
| Example | Stack, Queue, List | Array-based stack, linked list |

### In C++

A `class` makes this concrete: the **public** member functions are the ADT's interface, and the **private** members are the implementation. Hiding them is called **encapsulation**. Code that uses the class cannot break its internal rules.

## C++ code: a Stack ADT with two implementations

```cpp
#include <iostream>
using namespace std;

// The ADT: WHAT a stack does. Users only see these operations.
class Stack {
public:
    virtual void push(int x) = 0;
    virtual int pop() = 0;
    virtual int top() const = 0;
    virtual bool isEmpty() const = 0;
    virtual ~Stack() {}
};

// Implementation 1: array (fixed capacity)
class ArrayStack : public Stack {
    int a[100];
    int t = -1;
public:
    void push(int x) override { a[++t] = x; }
    int pop() override { return a[t--]; }
    int top() const override { return a[t]; }
    bool isEmpty() const override { return t == -1; }
};

// Implementation 2: linked list (grows as needed)
class ListStack : public Stack {
    struct Node { int data; Node* next; };
    Node* head = nullptr;
public:
    void push(int x) override { head = new Node{x, head}; }
    int pop() override {
        Node* old = head;
        int x = old->data;
        head = head->next;
        delete old;
        return x;
    }
    int top() const override { return head->data; }
    bool isEmpty() const override { return head == nullptr; }
    ~ListStack() { while (!isEmpty()) pop(); }
};

// Client code only knows the ADT, so it works with either implementation.
void demo(Stack& s, const char* name) {
    for (int i = 1; i <= 3; i++) s.push(i * 10);
    cout << name << ": ";
    while (!s.isEmpty()) cout << s.pop() << " ";
    cout << "\n";
}

int main() {
    ArrayStack a;
    ListStack l;
    demo(a, "array stack");
    demo(l, "list stack ");
}
```

Expected output:

```text
array stack: 30 20 10 
list stack : 30 20 10
```

## Complexity

| Case | Cost |
| --- | --- |
| push / pop / top (array implementation) | O(1) |
| push / pop / top (linked implementation) | O(1) |
| Maximum size | array: fixed · linked list: limited only by memory |


The ADT promises the operations; each implementation decides their cost. That is why we analyse implementations, not ADTs.

## Videos

- [Introduction to data structures](https://youtu.be/92S4zgXN17o) (mycodeschool): The second half explains ADTs with the list example, exactly the "interface vs implementation" split.
- [Introduction to stack](https://youtu.be/F1F2imiOJfk) (mycodeschool): Shows the stack as an ADT before any code. A preview of Chapter 5.

## Exam lens

Likely questions:

- Define Abstract Data Type (ADT). Give one example and list its operations.
- What is abstraction? Why is it useful in programming?
- Differentiate between an ADT and a data structure.
- Explain how a C++ class supports abstraction and encapsulation.

Common mistakes:

- Saying an ADT "is" an array. An ADT has no storage details at all; an array can only *implement* one.
- Listing implementation details (like `top` index) as part of the ADT's definition.
- Forgetting error conditions. "pop on an empty stack is an error" IS part of the ADT.

## Quick check

1. An Abstract Data Type specifies…
   A. the data and the operations, but not how they are implemented
   B. the exact memory layout
   C. the C++ code of each operation
   D. only the data, not the operations
   Answer: A. An ADT is a logical description, a "contract". Implementation is the data structure's job.

2. Which is an implementation (a data structure), not an ADT?
   A. Stack
   B. Queue
   C. List
   D. Singly linked list with a head pointer
   Answer: D. "Singly linked list with a head pointer" describes how the data is stored, so it is a data structure that can implement the List ADT.

3. In C++, which feature hides implementation details from users of a class?
   A. `public` members
   B. `private` members
   C. `#include`
   D. `cout`
   Answer: B. Private members can only be used inside the class. Users must go through the public interface; that is encapsulation.

4. You replace an array-based stack with a linked-list stack. What must change in code that only uses push/pop?
   A. Everything
   B. Only the type name it is created with
   C. All pop calls
   D. All push calls
   Answer: B. Because the client depends only on the ADT's operations, swapping implementations does not affect it.

## Practice

**Trace by hand.** Write the ADT specification (data + operations + error conditions) for a **Queue**, without writing any code.

Solution:

**Data:** an ordered collection; items leave in the order they arrived (FIFO).

**Operations:** `enqueue(x)` adds at the rear, `dequeue()` removes and returns the front item, `front()` returns the front item without removing it, `isEmpty()`, `size()`.

**Errors:** `dequeue()` / `front()` on an empty queue; `enqueue` on a full queue (bounded implementations only).


**Implement it.** Write a `Counter` class whose value can only change through `increment()`, `decrement()` (never below 0) and `reset()`, and read through `get()`.

Hint: Keep `int value` private. The rule "never below 0" lives inside `decrement()`; that is abstraction protecting an invariant.

```cpp
class Counter {
    int value = 0;
public:
    void increment() { value++; }
    void decrement() { if (value > 0) value--; }
    void reset() { value = 0; }
    int get() const { return value; }
};
```


**Problems:**

- [Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/) (easy). Hint: The Stack ADT does not care what is underneath. Can you meet its contract using only queue operations?
- [Design Parking System](https://leetcode.com/problems/design-parking-system/) (easy). Hint: Decide the interface first (`addCar`), then the hidden data (three counters).

## Mastery checklist

- [ ] I can define ADT and abstraction in my own words.
- [ ] I can explain the difference between an ADT and a data structure.
- [ ] I can write an ADT specification (data, operations, errors) for stack and queue.
- [ ] I can use private members to hide implementation details in C++.


---

# 1.3 Arrays & 2-D Arrays (Review)

> Arrays store items side by side in memory, which is why reading any index is instant. 2-D arrays are stored row by row.

Chapter: Introduction to Data Structures · ~35 min · easy
URL: https://dsa.fetehadin.com/learn/arrays

## Mental model

Picture a **row of numbered lockers** in a corridor. Every locker is the same size and they sit right next to each other. If locker 0 is at the start of the corridor and each is 4 steps wide, you can walk straight to locker 7: it's 28 steps away. You never open lockers 0 to 6 on the way.

That is an **array**: same-type items stored **contiguously** (side by side) in memory.

### Why access is instant

The compiler knows three things: the **base address** (where `a[0]` lives), the **size of one item**, and the **index**. So

`address of a[i] = base + i × sizeof(type)`

One multiplication and one addition, for any `i`: **O(1) random access**.

### The price you pay

- **Fixed size**: `int a[100]` is static. Need 101? Make a new array and copy.
- **Insert / delete in the middle is O(n)**: every item after the gap must shift.
- **No bounds checking**: `a[100]` on a 100-item array compiles and runs, but reads or overwrites whatever is next in memory.

### 2-D arrays

A matrix `int m[R][C]` *looks* like a grid, but memory is one long line. C++ stores it **row by row (row-major)**:

`address of m[i][j] = base + (i × C + j) × sizeof(type)`

So looping `i` (rows) outside and `j` (columns) inside walks memory in order. That is the natural and fastest way.

## C++ code: 1-D and 2-D arrays

```cpp
#include <iostream>
using namespace std;

int main() {
    // 1-D array: contiguous memory, index i is at base + i * sizeof(int)
    int a[5] = {12, 7, 31, 4, 19};
    int n = sizeof(a) / sizeof(a[0]);
    cout << "a[3] = " << a[3] << "\n";
    cout << "elements are " << sizeof(int) << " bytes apart: "
         << (&a[1] - &a[0]) * sizeof(int) << "\n";

    int sum = 0;
    for (int i = 0; i < n; i++) sum += a[i];
    cout << "sum = " << sum << "\n";

    // 2-D array: stored row by row (row-major)
    const int R = 3, C = 4;
    int m[R][C];
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            m[i][j] = i * C + j + 1;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) cout << m[i][j] << "\t";
        cout << "\n";
    }
    // m[1][2] is element number 1*C + 2 = 6 in memory
    cout << "m[1][2] = " << m[1][2] << ", offset = " << (&m[1][2] - &m[0][0]) << "\n";
}
```

Expected output:

```text
a[3] = 4
elements are 4 bytes apart: 4
sum = 73
1	2	3	4	
5	6	7	8	
9	10	11	12	
m[1][2] = 7, offset = 6
```

## Complexity

| Case | Cost |
| --- | --- |
| Access a[i] | O(1) |
| Search (unsorted) | O(n) |
| Insert / delete at position i | O(n): shift items |
| Insert / delete at the end | O(1) if there is space |
| Traverse an R × C matrix | O(R·C) |

Space: O(n) for n items

Address formula (row-major): `&m[i][j] = base + (i × COLS + j) × sizeof(type)`.

## Videos

- [Introduction to data structures](https://youtu.be/92S4zgXN17o) (mycodeschool): Uses the array as its first example and explains contiguous memory.
- [Data Structures: Full Course Using C and C++](https://youtu.be/B31LgI4Y4DQ) (freeCodeCamp.org): Full course backup. Skim the array and memory parts if you need more practice with C/C++ arrays.

## Exam lens

Likely questions:

- An int array starts at address 1000 and `sizeof(int)` = 4. What is the address of `a[7]`?
- A `float m[5][8]` starts at 2000 (`sizeof(float)` = 4). Find the address of `m[3][6]` in row-major order.
- Why is accessing `a[i]` O(1) but inserting at the front O(n)?
- Write a function to find the sum of each row of a 2-D array.

Common mistakes:

- Using 1-based indexes. C++ arrays start at 0, so the last valid index is n − 1.
- Writing `a[n]` (out of bounds). C++ does not check, so it silently corrupts memory.
- Using `sizeof(a)/sizeof(a[0])` inside a function. There, `a` is a pointer, so the trick gives the wrong size. Pass `n` instead.
- Mixing up rows and columns in the address formula (multiply the row index by the number of COLUMNS).

## Quick check

1. `int a[10]` starts at address 500 and `sizeof(int)` = 4. Where is `a[6]`?
   A. 506
   B. 520
   C. 524
   D. 530
   Answer: C. 500 + 6 × 4 = 524.

2. In `int m[3][4]`, how many elements come before `m[2][1]` in memory (row-major)?
   A. 3
   B. 7
   C. 9
   D. 6
   Answer: C. 2 × 4 + 1 = 9 elements come before it.

3. Why is reading `a[i]` constant time?
   A. The array is sorted
   B. The address is computed with one multiply and one add
   C. C++ caches arrays
   D. Arrays are dynamic
   Answer: B. Items are contiguous, so the address is base + i × size. No searching is needed.

4. What does this print?

```cpp
int a[4] = {5, 2, 8};
cout << a[3];
```
   A. 8
   B. Garbage
   C. 0
   D. Compile error
   Answer: C. With an initializer list, any missing elements are set to 0.

## Practice

**Trace by hand.** `int m[4][5]` starts at address 3000 with 4-byte ints. Compute the address of `m[2][3]` and of `m[3][4]`.

Solution:

- `m[2][3]`: offset = 2 × 5 + 3 = 13, address = 3000 + 13 × 4 = **3052**
- `m[3][4]`: offset = 3 × 5 + 4 = 19, address = 3000 + 19 × 4 = **3076** (the last element)


**Implement it.** Write `void transpose(int a[3][3])` that swaps rows and columns in place, and a `main()` that prints the matrix before and after.

Hint: Only swap the upper triangle, `a[i][j]` with `a[j][i]` for `j > i`. Otherwise you swap everything twice and end up back where you started.

```cpp
void transpose(int a[3][3]) {
    for (int i = 0; i < 3; i++)
        for (int j = i + 1; j < 3; j++)
            swap(a[i][j], a[j][i]);
}
```


**Problems:**

- [Running Sum of 1d Array](https://leetcode.com/problems/running-sum-of-1d-array/) (easy). Hint: Each output is the previous output plus the current item. One loop, O(n).
- [Richest Customer Wealth](https://leetcode.com/problems/richest-customer-wealth/) (easy). Hint: Sum each row of the 2-D array, keep the maximum.
- [Matrix Diagonal Sum](https://leetcode.com/problems/matrix-diagonal-sum/) (easy). Hint: Primary diagonal is `m[i][i]`, the other is `m[i][n-1-i]`. Don't count the centre twice when n is odd.

## Mastery checklist

- [ ] I can compute the address of a[i] and m[i][j] by hand.
- [ ] I can explain why array access is O(1) and insertion is O(n).
- [ ] I can loop over a 2-D array row by row.
- [ ] I know why out-of-bounds access is dangerous in C++.


---

# 2.1 Algorithms & Their Properties

> An algorithm is a finite, unambiguous sequence of steps that solves a problem. Learn the 11 properties every correct algorithm must have.

Chapter: Algorithm & Algorithm Analysis · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/algorithm-properties

## Mental model

An **algorithm** is a recipe precise enough for a machine: *a finite sequence of well-defined steps that takes some input and produces the correct output.*

A cooking recipe that says "bake until it looks good" is fine for humans, but it isn't an algorithm. A computer can't judge "looks good". Every step must be exact.

### The 11 properties

| Property | Meaning |
|---|---|
| **Finiteness** | It must stop after a finite number of steps. |
| **Definiteness** | Every step is clear and has exactly one meaning. |
| **Sequence** | Steps run in a defined order; each step has a unique next step. |
| **Feasibility** | Every step can actually be carried out with the available resources. |
| **Correctness** | It produces the right output for every valid input. |
| **Language independence** | The steps can be written in any language (C++, Python, pseudocode). |
| **Completeness** | It solves the whole problem, including edge cases. |
| **Effectiveness** | Each step is basic enough to do exactly, in finite time, even by hand. |
| **Efficiency** | It uses as little time and memory as possible. |
| **Generality** | It works for a whole class of problems, not one fixed input. |
| **Input / Output** | Zero or more inputs; at least one output. |

> Memory trick: **"Fine Dogs Sit, Feel Calm, Learn Commands; Every Excited Good I/O."** Silly, but it sticks.

### Algorithm vs program

A **program** is an algorithm written in a specific language and run on a machine. A program may run forever (a web server); an algorithm must finish.

## C++ code: find-max.cpp

```cpp
#include <iostream>
using namespace std;

// Input: an array and its size. Output: the largest value.
// Finite (n-1 comparisons), definite, effective, general, correct.
int findMax(const int a[], int n) {
    int max = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] > max)
            max = a[i];
    return max;
}

int main() {
    int a[] = {14, 3, 27, 9, 31, 8};
    int b[] = {-5, -2, -9};
    cout << "max of a = " << findMax(a, 6) << "\n";
    cout << "max of b = " << findMax(b, 3) << "\n";
}
```

Expected output:

```text
max of a = 31
max of b = -2
```

## Complexity

| Case | Cost |
| --- | --- |
| findMax: comparisons | exactly n − 1 |
| findMax: time | O(n), and best = worst |

Space: O(1)

Efficiency is one of the 11 properties. Chapter 2 is about measuring it precisely.

## Videos

- [Introduction to Algorithms](https://youtu.be/0IAPZzGSbME) (Abdul Bari): Abdul Bari covers what an algorithm is, its characteristics and how it differs from a program.

## Exam lens

Likely questions:

- Define algorithm. List and explain any five properties of an algorithm.
- What is the difference between finiteness and effectiveness?
- Why must an algorithm be language independent?
- Give an example of a set of steps that is NOT an algorithm and say which property it breaks.

Common mistakes:

- Confusing **definiteness** (each step has one clear meaning) with **finiteness** (the algorithm stops).
- Saying an algorithm needs at least one input. It needs **zero or more** inputs but **at least one** output.
- Treating "a program" and "an algorithm" as the same. A program may run forever (an OS); an algorithm must terminate.

## Quick check

1. "Add a pinch of salt" breaks which property?
   A. Finiteness
   B. Definiteness
   C. Generality
   D. Sequence
   Answer: B. "A pinch" can mean different amounts to different people. Each step must have exactly one meaning.

2. An algorithm must produce…
   A. zero or more outputs
   B. at least one output
   C. exactly one input
   D. at least one input
   Answer: B. Zero or more inputs, but at least one output. Otherwise it achieved nothing.

3. `while (true) { }` violates which property?
   A. Finiteness
   B. Feasibility
   C. Language independence
   D. Input
   Answer: A. It never terminates.

4. "Works for any array size, not just 5 items" describes…
   A. Correctness
   B. Generality
   C. Effectiveness
   D. Completeness
   Answer: B. A general algorithm solves every instance of the problem, not one special case.

## Practice

**Trace by hand.** Here is a "recipe": (1) pick a random number, (2) if it is the answer, stop; otherwise go to (1). Which properties does it break?

Solution:

- **Finiteness**: it may never stop.
- **Definiteness**: "pick a random number" is not one exact action.
- **Efficiency**: there is no bound on the number of steps.


**Implement it.** Write `findMin` and a `main()` that tests it on an array of negative numbers. Then write which property your test checks.

Hint: Start with `min = a[0]`, not `min = 0`. With `0` the algorithm is incorrect for all-positive arrays. That's the *correctness* property.

**Problems:**

- [Find Greatest Common Divisor of Array](https://leetcode.com/problems/find-greatest-common-divisor-of-array/) (easy). Hint: Find min and max in one pass, then apply Euclid's algorithm (a classic finite, definite algorithm).
- [Find the Highest Altitude](https://leetcode.com/problems/find-the-highest-altitude/) (easy). Hint: A running sum and a running max. Write the steps in plain English first, then code.

## Mastery checklist

- [ ] I can define an algorithm.
- [ ] I can list and explain the 11 properties.
- [ ] I can say which property a broken "algorithm" violates.
- [ ] I can explain the difference between an algorithm and a program.


---

# 2.2 Measuring Efficiency

> Empirical vs theoretical analysis, qualitative vs quantitative, the three classic avoidable inefficiencies, and the time–space trade-off.

Chapter: Algorithm & Algorithm Analysis · ~35 min · easy
URL: https://dsa.fetehadin.com/learn/analysis-approaches

## Mental model

How do you decide which of two algorithms is "better"? There are two ways to find out.

### Empirical vs theoretical

- **Empirical analysis** = *run it and measure*. Implement both, time them on test data. It is easy to understand, but the result depends on the **computer, compiler, language, other running programs and the inputs you chose**. A fast laptop can make a bad algorithm look good.
- **Theoretical analysis** = *count the steps on paper* as a function of the input size **n**. It is independent of the machine and covers **all** inputs. This is what the rest of the chapter teaches.

### Qualitative vs quantitative

- **Qualitative**: Is it simple? Readable? Easy to maintain and modify? Does it handle errors?
- **Quantitative**: How much **time** (number of operations) and **space** (memory) does it use?

### Avoidable inefficiencies

These are "free" speed-ups that don't change the algorithm's idea:

1. **Redundant computation**: computing the same value again and again inside a loop. Move it out of the loop.
2. **Late loop termination**: continuing to loop after the answer is already known. `break` or `return` early.
3. **Repeated array referencing**: reading `a[i]` several times in one iteration. Read it once into a local variable.

### The time–space trade-off

You can often buy speed with memory: a lookup table, a set of seen values, a prefix-sum array. Or save memory by recomputing. Good design picks the balance the problem needs. On a phone with little memory you may choose differently than on a server.

## C++ code: fixing the three inefficiencies

```cpp
#include <iostream>
using namespace std;

int checks = 0;

// Late termination: keeps looping after the answer is known.
bool containsSlow(const int a[], int n, int key) {
    bool found = false;
    for (int i = 0; i < n; i++) {
        checks++;
        if (a[i] == key) found = true;
    }
    return found;
}

// Fixed: stop as soon as we know.
bool containsFast(const int a[], int n, int key) {
    for (int i = 0; i < n; i++) {
        checks++;
        if (a[i] == key) return true;
    }
    return false;
}

int main() {
    int a[] = {5, 12, 8, 3, 19, 7, 25, 11};
    int n = 8;

    checks = 0; containsSlow(a, n, 8);
    cout << "slow: " << checks << " checks\n";
    checks = 0; containsFast(a, n, 8);
    cout << "fast: " << checks << " checks\n";

    // Redundant computation: x*x is recomputed on every pass
    double x = 3, total = 0;
    for (int i = 0; i < 4; i++) total += a[i] * (x * x);
    // Better: compute it once, outside the loop
    double x2 = x * x, total2 = 0;
    for (int i = 0; i < 4; i++) total2 += a[i] * x2;
    cout << "same result: " << total << " == " << total2 << "\n";

    // Repeated array referencing: read a[i] once into a local variable
    int best = a[0];
    for (int i = 1; i < n; i++) {
        int v = a[i];            // one reference instead of two
        if (v > best) best = v;
    }
    cout << "max = " << best << "\n";
}
```

Expected output:

```text
slow: 8 checks
fast: 3 checks
same result: 252 == 252
max = 25
```

## Complexity

| Case | Cost |
| --- | --- |
| Search with late termination | always n checks |
| Search that breaks early | 1 … n checks |
| Duplicate check with nested loops | O(n²) time, O(1) space |
| Duplicate check with a set | O(n) time, O(n) space ← trade-off |


Trading memory for speed (or the reverse) is the **time–space trade-off**. Neither side is free.

## Videos

- [Time Complexity #1](https://youtu.be/9TlHvipP5yA) (Abdul Bari): Explains why we count steps instead of timing with a stopwatch.
- [Big O Notation](https://youtu.be/v4cd1O4zkGw) (HackerRank): A short, clear intuition for why growth rate matters more than exact seconds.

## Exam lens

Likely questions:

- Compare empirical and theoretical analysis. Give two drawbacks of empirical analysis.
- What is the difference between qualitative and quantitative analysis of an algorithm?
- Explain three avoidable inefficiencies with a code example of each.
- Explain the time–space trade-off with an example.

Common mistakes:

- Saying empirical analysis is useless. It is useful, but its results depend on the machine, compiler, language and inputs.
- Mixing up "redundant computation" (recomputing the same value in a loop) with "repeated array referencing" (reading `a[i]` many times).
- Thinking the faster algorithm is always better. It may need far more memory.

## Quick check

1. Running two programs and timing them with a stopwatch is…
   A. theoretical analysis
   B. empirical analysis
   C. asymptotic analysis
   D. qualitative analysis
   Answer: B. Empirical = by experiment. Results depend on hardware, compiler and test inputs.

2. Readability, simplicity and maintainability are part of…
   A. quantitative analysis
   B. qualitative analysis
   C. empirical analysis
   D. Big-O analysis
   Answer: B. Qualitative analysis judges the quality of the design. Quantitative analysis measures time and space numerically.

3. Which inefficiency is in this loop?

```cpp
for (int i = 0; i < n; i++)
    total += a[i] * sqrt(x);
```
   A. Late termination
   B. Redundant computation
   C. Repeated array referencing
   D. None
   Answer: B. `sqrt(x)` never changes, but it is recomputed n times. Compute it once before the loop.

4. Using a hash set to find duplicates in O(n) instead of O(n²) is an example of…
   A. the time–space trade-off
   B. late termination
   C. empirical analysis
   D. definiteness
   Answer: A. We spend O(n) extra memory to save time.

## Practice

**Trace by hand.** Spot every avoidable inefficiency: `for (i = 0; i < n; i++) { if (a[i] > a[i] * k * k / 2) found = true; }` (we only need to know whether at least one such item exists).

Solution:

1. **Redundant computation**: `k * k / 2` is recomputed every iteration; compute `half = k*k/2` once.
2. **Repeated array referencing**: `a[i]` is read twice; store it in `int v = a[i];`.
3. **Late termination**: once `found` is true we should `break`.


**Implement it.** Write a program that checks whether an array has two equal items in two ways (nested loops, and a `std::set`). Count the comparisons each method makes on 1000 random numbers.

Hint: Use a global counter, incremented before each comparison. Nested loops make about n²/2 comparisons.

**Problems:**

- [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/) (easy). Hint: Brute force is O(n²) time and O(1) space. A set is O(n) time and O(n) space. Sorting first is O(n log n) time with little extra space. Three points on the trade-off curve.
- [Two Sum](https://leetcode.com/problems/two-sum/) (easy). Hint: The textbook time–space trade-off. Write the O(n²) version first, then the hash-map version.

## Mastery checklist

- [ ] I can compare empirical and theoretical analysis.
- [ ] I can explain qualitative vs quantitative analysis.
- [ ] I can spot and fix redundant computation, late termination and repeated array referencing.
- [ ] I can explain the time–space trade-off with an example.


---

# 2.3 Counting Time Units

> Turn code into a formula T(n) using the instructor's counting rules. Loops become sums, and nested loops multiply.

Chapter: Algorithm & Algorithm Analysis · ~50 min · medium
URL: https://dsa.fetehadin.com/learn/counting-time-units

## Mental model

Instead of timing code with a stopwatch, we **count operations**. Each simple operation costs **1 time unit**. Then T(n), the total as a function of input size n, tells us how the work grows.

### The rules (use exactly these on the exam)

1. **1 unit** each for: an assignment, a single input/output, a Boolean operation (`<`, `==`, `&&`, …), an arithmetic operation (`+`, `-`, `*`, `/`, `%`, `++`), and a `return`.
2. **if / switch**: time of the condition **+ the time of the largest branch**.
3. **Loops**: the loop header costs **1** (initialization) **+ (n + 1)** (tests: n true plus one false) **+ n** (increments). The body costs *(body time) × (number of iterations)*.
4. **Nested loops**: multiply. The inner body runs (outer iterations) × (inner iterations) times.
5. **Function call**: **1** (call setup) **+ the parameters + the time of the body**.

### Worked example

```cpp
for (i = 0; i < n; i++)
    k = k + 1;
cout << k;
```

| Part | Units |
|---|---|
| `i = 0` | 1 |
| `i < n` | n + 1 |
| `i++` | n |
| `k = k + 1` (add + assign) | 2n |
| `cout << k` | 1 |

$$T(n) = 1 + (n+1) + n + 2n + 1 = 4n + 3$$

### Loops → summations

When the inner loop depends on the outer variable, write the count as a sum:

```cpp
for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
        x++;
```

The body runs $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ times, so it grows like n².

Three sums to memorise:

- $\sum_{i=1}^{n} 1 = n$
- $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$
- $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

## C++ code: counting by instrumenting the code

```cpp
#include <iostream>
using namespace std;

// We count time units with the instructor's rules by adding to `t`
// next to each operation, then compare with the formula T(n) = 4n + 3.
long long countLoop(int n) {
    long long t = 0;
    int k = 0;
    int i;
    t++; i = 0;                  // 1 assignment (init)
    while (true) {
        t++;                     // 1 test: i < n
        if (!(i < n)) break;
        t += 2; k = k + 1;       // add + assign
        t++; i++;                // 1 increment
    }
    t++; (void)k;                // cout << k: 1 output
    return t;
}

long long countNested(int n) {
    long long t = 0;
    int k = 0;
    t++;                                     // k = 0
    t++;                                     // i = 0
    for (int i = 0; ; i++) {
        t++;                                 // i < n
        if (!(i < n)) break;
        t++;                                 // j = 0
        for (int j = 0; ; j++) {
            t++;                             // j < n
            if (!(j < n)) break;
            t++; k++;                        // k++
            t++;                             // j++
        }
        t++;                                 // i++
    }
    return t;
}

int main() {
    for (int n : {1, 3, 10}) {
        cout << "n=" << n << "  loop: counted " << countLoop(n)
             << ", 4n+3 = " << 4 * n + 3
             << "  |  nested: counted " << countNested(n)
             << ", 3n^2+4n+3 = " << 3 * n * n + 4 * n + 3 << "\n";
    }
}
```

Expected output:

```text
n=1  loop: counted 7, 4n+3 = 7  |  nested: counted 10, 3n^2+4n+3 = 10
n=3  loop: counted 15, 4n+3 = 15  |  nested: counted 42, 3n^2+4n+3 = 42
n=10  loop: counted 43, 4n+3 = 43  |  nested: counted 343, 3n^2+4n+3 = 343
```

## Complexity

| Case | Cost |
| --- | --- |
| Single loop `for(i=0;i<n;i++) k=k+1; cout<<k;` | T(n) = 4n + 3 → O(n) |
| Nested n × n loop with `k++` | T(n) = 3n² + 4n + 3 → O(n²) |
| Loop where i doubles (`i *= 2`) | ≈ log₂ n iterations → O(log n) |


The exact T(n) depends on the counting rules; the **growth rate** (Big-O) does not. Use your instructor's rules on the exam.

## Videos

- [Time Complexity #1](https://youtu.be/9TlHvipP5yA) (Abdul Bari): Abdul Bari counts statements in loops step by step, the same skill as here.

## Exam lens

Likely questions:

- Calculate T(n) for: `int k=0; for(int i=0;i<n;i++) k=k+1; cout<<k;`
- Calculate T(n) for a nested loop where both loops run n times and the body is `sum++`.
- Express the loop `for(i=1;i<=n;i++) for(j=1;j<=i;j++) x++;` as a summation and simplify it.
- State the counting rules for if-statements, loops and function calls.

Common mistakes:

- Counting the loop test n times instead of **n + 1** (the last, failing test counts too).
- Counting `k = k + 1` as 1 unit. It is **2**: one addition and one assignment.
- For `if/else`, adding both branches. Count the condition **plus the larger branch only**.
- Forgetting the initialization of the loop (1 unit, done once).

## Quick check

1. Using the course rules, T(n) for `for(i=0;i<n;i++) k=k+1; cout<<k;` is:
   A. 3n + 2
   B. 4n + 3
   C. 4n + 2
   D. 2n + 3
   Answer: B. 1 (init) + (n+1) tests + n increments + 2n (add + assign) + 1 (cout) = 4n + 3.

2. How many times is the condition `i < n` evaluated in `for (i = 0; i < n; i++)`?
   A. n − 1
   B. n
   C. n + 1
   D. 2n
   Answer: C. True n times plus the final false test.

3. An `if (x > 0) a = b + c; else a = 0;` costs:
   A. 1 + 2 + 1 = 4
   B. 1 + 2 = 3
   C. 2 + 1 = 3
   D. 1
   Answer: B. Condition (1) + the larger branch (`a = b + c` = 2).

4. The summation $\sum_{i=1}^{n} i$ equals:
   A. n
   B. n²
   C. n(n+1)/2
   D. 2ⁿ
   Answer: C. Gauss's formula. It is why a loop whose inner part runs i times is O(n²).

5. What is the order of growth of `for (i = 1; i < n; i *= 2) count++;`?
   A. O(1)
   B. O(log n)
   C. O(n)
   D. O(n log n)
   Answer: B. i takes values 1, 2, 4, 8, … so it reaches n after about log₂ n iterations.

## Practice

**Trace by hand.** Compute T(n) with the course rules:
```cpp
int sum = 0;
for (int i = 0; i < n; i++)
    sum = sum + i;
return sum;
```


Solution:

- `sum = 0`: 1
- loop: 1 (init) + (n + 1) (tests) + n (increments)
- body `sum = sum + i`: 2 per iteration → 2n
- `return sum`: 1

**T(n) = 1 + 1 + (n+1) + n + 2n + 1 = 4n + 4 → O(n)**


**Implement it.** Add a global `long long t` counter to `selectionSort` that counts every comparison and assignment. Print t for n = 10, 100, 1000 and check that it grows like n².

Hint: When n is ×10, a quadratic count should be ≈ ×100.

**Problems:**

- [Count Odd Numbers in an Interval Range](https://leetcode.com/problems/count-odd-numbers-in-an-interval-range/) (easy). Hint: A loop from low to high is O(n). Can you find a formula that is O(1)? Count units for both versions.
- [Sqrt(x)](https://leetcode.com/problems/sqrtx/) (easy). Hint: Trying i = 1, 2, 3… is O(√x). Binary search over [0, x] is O(log x). Count iterations of each for x = 10⁶.

## Mastery checklist

- [ ] I can apply the counting rules for assignments, I/O, operators, if, loops and calls.
- [ ] I can get T(n) = 4n + 3 for the standard single loop without notes.
- [ ] I can count a nested loop and write it as a summation.
- [ ] I can simplify Σ1, Σi and Σi² sums.


---

# 2.4 Best, Average & Worst Case

> The same algorithm can be fast or slow depending on the input. We analyse the best, average and worst case, and usually report the worst.

Chapter: Algorithm & Algorithm Analysis · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/best-average-worst

## Mental model

Looking for your keys in a row of 10 pockets: if they're in the **first** pocket you're done in one check; if they're in the **last** pocket (or not there at all) you check all 10. Same algorithm, same n, very different effort.

### The three cases

- **Best case**: the input arrangement that needs the **fewest** steps. Linear search: key at index 0 → **1 comparison**.
- **Worst case**: the arrangement that needs the **most** steps. Linear search: key last or missing → **n comparisons**.
- **Average case**: the expected steps over all inputs (assuming each is equally likely). Linear search, key present: on average $\frac{1 + 2 + \dots + n}{n} = \frac{n+1}{2}$ comparisons.

### Which one do we report?

Usually the **worst case**, because:

- it is a **guarantee**: the algorithm will never be slower;
- it often happens in practice (searching for something that isn't there);
- the average case needs assumptions about the input that may not hold.

> The case is about the **input arrangement** for a fixed n. "n = 1" is not the best case. A sorted array of size 1,000,000 can be the best case for insertion sort.

## C++ code: counting comparisons per case

```cpp
#include <iostream>
using namespace std;

int comparisons;

int linearSearch(const int a[], int n, int key) {
    for (int i = 0; i < n; i++) {
        comparisons++;
        if (a[i] == key) return i;
    }
    return -1;
}

int main() {
    int a[] = {8, 3, 14, 6, 21, 9, 17, 2};
    int n = 8;
    struct { const char* label; int key; } cases[] = {
        {"best  (first item)", 8}, {"middle", 6}, {"worst (missing)", 99}};
    for (auto c : cases) {
        comparisons = 0;
        int pos = linearSearch(a, n, c.key);
        cout << c.label << ": key " << c.key << " -> index " << pos
             << " after " << comparisons << " comparisons\n";
    }
    // Average over every key that is present: (1 + 2 + ... + n) / n = (n + 1) / 2
    int total = 0;
    for (int i = 0; i < n; i++) { comparisons = 0; linearSearch(a, n, a[i]); total += comparisons; }
    cout << "average when found: " << total << "/" << n << " = " << (double)total / n << "\n";
}
```

Expected output:

```text
best  (first item): key 8 -> index 0 after 1 comparisons
middle: key 6 -> index 3 after 4 comparisons
worst (missing): key 99 -> index -1 after 8 comparisons
average when found: 36/8 = 4.5
```

## Complexity

| Case | Cost |
| --- | --- |
| Linear search: best (key is first) | O(1): 1 comparison |
| Linear search: average (key present) | (n + 1) / 2 comparisons → O(n) |
| Linear search: worst (last or missing) | n comparisons → O(n) |
| Bubble sort with flag: best / worst | O(n) / O(n²) |

Space: O(1)

The **worst case** is an upper bound you can promise to a user, which is why it is the one usually reported.

## Videos

- [Time Complexity #1](https://youtu.be/9TlHvipP5yA) (Abdul Bari): Works through how the same code takes different numbers of steps for different inputs.
- [Asymptotic Notations: Big Oh, Omega, Theta](https://youtu.be/A03oI0znAoc) (Abdul Bari): Links the three cases to the notations you meet next (O, Ω, Θ).

## Exam lens

Likely questions:

- Define best, worst and average case complexity with linear search as the example.
- Why is worst-case analysis used more often than average-case analysis?
- Give an input that produces the best case and the worst case for insertion sort.
- Show that the average number of comparisons for a successful linear search is (n + 1)/2.

Common mistakes:

- "Best case is when n is small." No: best case is about the **arrangement** of the input for a given n, never about a small n.
- Thinking the average case is (best + worst) / 2. It is an expected value over all inputs.
- Mixing up the case with the notation. "Worst case" is not the same thing as "Big-O".

## Quick check

1. For linear search, the worst case happens when the key is…
   A. in the middle
   B. the first item
   C. the last item or not present
   D. repeated
   Answer: C. Then every item must be compared.

2. Best-case input for insertion sort is…
   A. a reversed array
   B. an already sorted array
   C. all equal except one
   D. random
   Answer: B. Each new key is already ≥ the item before it, so the inner while loop never runs. That gives O(n).

3. Why do we usually report the worst case?
   A. It is the easiest to compute
   B. It guarantees an upper limit for every input
   C. It is always the average
   D. It is the most common input
   Answer: B. Whatever the input, the algorithm will never be slower than this.

4. The best case of an algorithm depends on…
   A. n being 1
   B. the input arrangement for a given n
   C. the computer speed
   D. the language
   Answer: B. For a fixed size n, which arrangement of the data makes it fastest?

## Practice

**Trace by hand.** Count comparisons for linear search in `[4, 9, 2, 7, 5]` with keys 4, 2, 5 and 8. Which is the best case and which is the worst?

Solution:

- key 4: 1 comparison (**best**)
- key 2: 3 comparisons
- key 5: 5 comparisons
- key 8: 5 comparisons, not found (**worst**, tied with 5)


**Implement it.** Add a comparison counter to insertion sort and print it for a sorted, a reversed and a random array of 10 items.

Hint: Sorted → 9 comparisons (n − 1). Reversed → 45 (n(n−1)/2). Random falls somewhere in between.

**Problems:**

- [Search Insert Position](https://leetcode.com/problems/search-insert-position/) (easy). Hint: Write the linear version first and name its best and worst case. Then do it in O(log n) with binary search.
- [Find Numbers with Even Number of Digits](https://leetcode.com/problems/find-numbers-with-even-number-of-digits/) (easy). Hint: Counting digits by dividing by 10 depends on the value. What is the worst case per number?

## Mastery checklist

- [ ] I can define best, average and worst case.
- [ ] I can give the input that triggers each case for linear search and insertion sort.
- [ ] I can derive (n + 1)/2 for the average successful linear search.
- [ ] I can explain why we usually analyse the worst case.


---

# 2.5 Asymptotic Notation & Big-O Proofs

> O, Ω, Θ, o and ω describe how fast T(n) grows for large n. Learn the definitions, the order of growth, and how to prove f(n) = O(g(n)) by finding c and k.

Chapter: Algorithm & Algorithm Analysis · ~60 min · medium
URL: https://dsa.fetehadin.com/learn/asymptotic-notation

## Mental model

T(n) = 4n + 3 and T(n) = 7n + 100 look different, but for a million items both grow **in a straight line**. Asymptotic notation throws away constants and small terms and keeps only the **shape of growth** for large n. Think of describing a car as "fast" rather than "214.3 km/h".

### The five notations

Let f(n) be the running time and g(n) a simple function like n or n².

| Notation | Read as | Meaning | Like |
|---|---|---|---|
| f = **O**(g) | big-oh | f(n) ≤ c·g(n) for all n ≥ k | ≤ (upper bound) |
| f = **Ω**(g) | big-omega | f(n) ≥ c·g(n) for all n ≥ k | ≥ (lower bound) |
| f = **Θ**(g) | big-theta | both O(g) and Ω(g) | = (tight bound) |
| f = **o**(g) | little-oh | f grows strictly slower: f/g → 0 | &lt; |
| f = **ω**(g) | little-omega | f grows strictly faster: f/g → ∞ | &gt; |

### How to prove f(n) = O(g(n))

The definition says: find constants **c > 0** and **k ≥ 1** with

$$f(n) \le c \cdot g(n) \quad \text{for all } n \ge k$$

The recipe for polynomials:

1. For n ≥ 1, replace every smaller power of n by g(n) (it can only get bigger).
2. Add the coefficients. That sum is **c**.
3. The bound holds from n = 1, so **k = 1**.

**Example 1.** f(n) = 10n + 5. For n ≥ 1, 5 ≤ 5n, so 10n + 5 ≤ 15n. **c = 15, k = 1** ⇒ O(n).

**Example 2.** f(n) = 3n² + 4n + 1. For n ≥ 1, 4n ≤ 4n² and 1 ≤ n², so f(n) ≤ 8n². **c = 8, k = 1** ⇒ O(n²).

### Simplifying rules

- Drop constant factors: O(5n) = O(n).
- Keep the dominant term: O(n² + n + 1) = O(n²).
- Sequential code adds: O(n) + O(n²) = O(n²).
- Nested code multiplies: a loop of n around a loop of n = O(n²).

## C++ code: growth table + numeric check of a proof

```cpp
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
    cout << left << setw(6) << "n" << setw(9) << "log n" << setw(8) << "n"
         << setw(11) << "n log n" << setw(9) << "n^2" << "2^n\n";
    for (int n : {1, 2, 4, 8, 16, 32}) {
        double lg = log2(n);
        cout << left << setw(6) << n << setw(9) << lg << setw(8) << n
             << setw(11) << n * lg << setw(9) << n * n << (long long)pow(2, n) << "\n";
    }
    // Big-O check for f(n) = 3n^2 + 4n + 1 with c = 8, k = 1
    bool ok = true;
    for (long long n = 1; n <= 1000; n++)
        if (3 * n * n + 4 * n + 1 > 8 * n * n) ok = false;
    cout << "3n^2+4n+1 <= 8n^2 for n = 1..1000: " << (ok ? "true" : "false") << "\n";
}
```

Expected output:

```text
n     log n    n       n log n    n^2      2^n
1     0        1       0          1        2
2     1        2       2          4        4
4     2        4       8          16       16
8     3        8       24         64       256
16    4        16      64         256      65536
32    5        32      160        1024     4294967296
3n^2+4n+1 <= 8n^2 for n = 1..1000: true
```

## Complexity

| Case | Cost |
| --- | --- |
| O(1) | constant: array access, push/pop |
| O(log n) | logarithmic: binary search |
| O(n) | linear: linear search, traversal |
| O(n log n) | linearithmic: merge sort, heap sort |
| O(n²) | quadratic: bubble, selection, insertion sort |
| O(n³) | cubic: three nested loops |
| O(2ⁿ) | exponential: all subsets, naive Fibonacci |


Order to memorise: **1 < log n < n < n log n < n² < n³ < 2ⁿ < n!**

## Videos

- [Asymptotic Notations: Big Oh, Omega, Theta](https://youtu.be/A03oI0znAoc) (Abdul Bari): The clearest explanation of O, Ω and Θ with the c and n₀ definition, exactly what proofs need.
- [Big O Notation](https://youtu.be/v4cd1O4zkGw) (HackerRank): Eight-minute intuition with code examples; good before tackling proofs.

## Exam lens

Likely questions:

- Define Big-O, Big-Omega and Big-Theta formally.
- Show that f(n) = 10n + 5 is O(n). State your c and k.
- Show that f(n) = 3n² + 4n + 1 is O(n²).
- Arrange in increasing order of growth — n², log n, 2ⁿ, n, n log n, 1.
- What is the difference between O(g(n)) and o(g(n))?

Common mistakes:

- Forgetting to state c and k explicitly. A proof without numbers gets partial marks.
- Claiming 3n² = O(n). False: no constant c makes 3n² ≤ c·n for all large n.
- Thinking Big-O means "worst case". Big-O is an **upper bound** on a function; you can give an upper bound for the best case too.
- Keeping constants or lower terms. O(2n² + n) should be written O(n²).

## Quick check

1. To prove f(n) = O(g(n)) you must find…
   A. c > 0 and k such that f(n) ≤ c·g(n) for all n ≥ k
   B. c such that f(n) = c·g(n)
   C. k such that f(k) = g(k)
   D. the limit of f(n)
   Answer: A. That is the definition. Any valid pair works.

2. Which pair (c, k) proves 10n + 5 = O(n)?
   A. c = 10, k = 1
   B. c = 15, k = 1
   C. c = 5, k = 1
   D. c = 1, k = 10
   Answer: B. For n ≥ 1, 5 ≤ 5n, so 10n + 5 ≤ 15n. (c = 10 fails because 10n + 5 > 10n for every n.)

3. Θ(g(n)) means f(n) is…
   A. only bounded above by g
   B. only bounded below by g
   C. bounded above AND below by constant multiples of g
   D. strictly smaller than g
   Answer: C. Θ is a tight bound, both O and Ω.

4. Which grows fastest?
   A. n³
   B. n log n
   C. 2ⁿ
   D. n²
   Answer: C. Exponential beats any polynomial for large n. Drag the chart's slider to n = 30.

5. n is o(n²) because…
   A. n ≤ n² only for n = 1
   B. n grows strictly slower: n/n² → 0
   C. they are equal
   D. n² is o(n)
   Answer: B. Little-o is a strict upper bound. The ratio f/g goes to 0.

## Practice

**Trace by hand.** Prove that f(n) = 5n² + 3n + 2 is O(n²). Show c and k and check one value.

Solution:

For n ≥ 1: 3n ≤ 3n² and 2 ≤ 2n². So
5n² + 3n + 2 ≤ 5n² + 3n² + 2n² = **10n²**.

Choose **c = 10, k = 1**. Check n = 2: 20 + 6 + 2 = 28 ≤ 40 ✓. Therefore f(n) = O(n²). ∎


**Implement it.** Extend `growth.cpp` to check numerically, for n from 1 to 10 000, that 5n² + 3n + 2 ≤ 10n². Then try c = 5 and see where it fails.

Hint: With c = 5 it fails for every n ≥ 1, because 3n + 2 > 0. A numeric check doesn't replace a proof, but it does catch wrong constants.

**Problems:**

- [Fibonacci Number](https://leetcode.com/problems/fibonacci-number/) (easy). Hint: Naive recursion is O(2ⁿ). A simple loop with two variables is O(n). Time both for n = 40.
- [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/) (easy). Hint: Same recurrence as Fibonacci. Which growth rate does your solution have?
- [Power of Two](https://leetcode.com/problems/power-of-two/) (easy). Hint: Dividing by 2 until you reach 1 is O(log n). There is also an O(1) bit trick `n > 0 && (n & (n-1)) == 0`.

## Mastery checklist

- [ ] I can state the definitions of O, Ω, Θ, o and ω.
- [ ] I can prove 10n + 5 = O(n) and 3n² + 4n + 1 = O(n²) with explicit c and k.
- [ ] I can order the common growth rates from slowest to fastest.
- [ ] I can simplify any T(n) to its Big-O class.


---

# 3.1 Selection Sort

> Find the smallest remaining item and swap it to the front. Repeat. Simple, at most n − 1 swaps, but always O(n²) comparisons.

Chapter: Simple Sorting & Searching · ~35 min · easy
URL: https://dsa.fetehadin.com/learn/selection-sort

## Mental model

You're picking a football team, best player first. You look at **everyone** still available, pick the best, and they step forward. Then you look at everyone remaining again… That is selection sort, except we pick the *smallest* each time.

### The idea

The array has two parts: a **sorted** part on the left (initially empty) and an **unsorted** part on the right.

1. Scan the unsorted part to find the **minimum**.
2. **Swap** it with the first unsorted item. The sorted part grows by one.
3. Repeat n − 1 times.

### Why it's always O(n²)

To be sure an item is the minimum, you must look at every remaining item. Pass 1 makes n − 1 comparisons, pass 2 makes n − 2, and so on:

$$(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$$

That happens **no matter what the input is**, even if it's already sorted.

### Its one strength

It does **at most n − 1 swaps**. If moving data is very expensive (huge records, flash memory), that matters. For huge records, see *pointer sort* next.

## C++ code: selection-sort.cpp

```cpp
#include <iostream>
#include <utility>
using namespace std;

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIdx])
                minIdx = j;
        swap(a[i], a[minIdx]);   // at most one swap per pass
    }
}

int main() {
    int a[] = {29, 10, 14, 37, 13, 5};
    int n = sizeof(a) / sizeof(a[0]);
    selectionSort(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << "\n";
}
```

Expected output:

```text
5 10 13 14 29 37
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case | O(n²): it still scans for the minimum every pass |
| Average case | O(n²) |
| Worst case | O(n²): n(n−1)/2 comparisons |
| Swaps | at most n − 1 (the fewest of the simple sorts) |

Space: O(1)
Stable: no
In-place: yes

Good when **writing** to memory is expensive (few swaps). Bad when the data is already nearly sorted, because it cannot stop early.

## Videos

- [Selection sort algorithm](https://youtu.be/GUDLRan2DWM) (mycodeschool): Derives the algorithm from the "find the minimum" idea and analyses it carefully.
- [Selection sort in 3 minutes](https://youtu.be/g-PGLbMth_g) (Michael Sambol): A 3-minute animation. Ideal as a pre-exam refresher.

## Exam lens

Likely questions:

- Trace selection sort on `64, 25, 12, 22, 11`, showing the array after each pass.
- How many comparisons and swaps does selection sort make for n items?
- Why is selection sort not stable? Give an example.
- Compare selection sort and bubble sort in terms of swaps.

Common mistakes:

- Swapping inside the inner loop every time a smaller item is found. Swap **once**, after the inner loop.
- Starting the inner loop at `j = i` instead of `j = i + 1` (compares an item with itself).
- Claiming selection sort has an O(n) best case. It has none; it always scans.

## Quick check

1. After 2 passes of selection sort on `5, 3, 8, 1, 2` the array is:
   A. `1, 2, 8, 5, 3`
   B. `1, 3, 8, 5, 2`
   C. `1, 2, 3, 5, 8`
   D. `3, 5, 1, 2, 8`
   Answer: A. Pass 1 swaps 5↔1 → `1, 3, 8, 5, 2`. Pass 2 swaps 3↔2 → `1, 2, 8, 5, 3`.

2. Maximum number of swaps for n items?
   A. n − 1
   B. n²
   C. n(n−1)/2
   D. log n
   Answer: A. One swap per pass, n − 1 passes.

3. Selection sort on an already sorted array runs in…
   A. O(1)
   B. O(n)
   C. O(n log n)
   D. O(n²)
   Answer: D. It still compares every remaining pair to be sure it found the minimum.

4. Is selection sort stable on `2a, 2b, 1`?
   A. Yes
   B. No: after sorting, 2b comes before 2a
   Answer: B. Pass 1 swaps 2a with 1 → `1, 2b, 2a`. The equal items swapped order.

## Practice

**Trace by hand.** Trace selection sort on `64, 25, 12, 22, 11`. Show the array after each pass and count comparisons.

Solution:

- Pass 1: min 11 → `11 25 12 22 64`
- Pass 2: min 12 → `11 12 25 22 64`
- Pass 3: min 22 → `11 12 22 25 64`
- Pass 4: min 25 → `11 12 22 25 64`

Comparisons: 4 + 3 + 2 + 1 = **10** = 5·4/2.


**Implement it.** Write `selectionSortMax` that sorts ascending by repeatedly finding the **maximum** and placing it at the **end**.

Hint: Outer loop: `for (int end = n - 1; end > 0; end--)`. Inner loop finds the index of the max in `[0..end]`.

```cpp
void selectionSortMax(int a[], int n) {
    for (int end = n - 1; end > 0; end--) {
        int maxIdx = 0;
        for (int j = 1; j <= end; j++)
            if (a[j] > a[maxIdx]) maxIdx = j;
        swap(a[maxIdx], a[end]);
    }
}
```


**Problems:**

- [Sort Colors](https://leetcode.com/problems/sort-colors/) (medium). Hint: Selection sort works (n ≤ 300). Then try the one-pass "Dutch national flag" approach with three pointers.
- [Height Checker](https://leetcode.com/problems/height-checker/) (easy). Hint: Copy the array, sort the copy with your own selection sort, then count positions that differ.
- [Third Maximum Number](https://leetcode.com/problems/third-maximum-number/) (easy). Hint: This is three passes of "find the max", the core step of selection sort. Watch out for duplicates.

## Mastery checklist

- [ ] I can trace selection sort pass by pass.
- [ ] I can write it from memory with exactly one swap per pass.
- [ ] I can state its comparisons (n(n−1)/2) and swaps (≤ n − 1).
- [ ] I can show with an example why it is unstable.


---

# 3.2 Bubble Sort

> Compare neighbours and swap them if they are out of order. After each pass the biggest remaining item has "bubbled" to the end.

Chapter: Simple Sorting & Searching · ~35 min · easy
URL: https://dsa.fetehadin.com/learn/bubble-sort

## Mental model

Imagine bubbles in a glass of water: the **big ones rise to the top**. Bubble sort walks along the array comparing each pair of neighbours. If the left one is bigger, they swap. By the end of one pass, the largest item has floated to the last position, and it never moves again.

So each pass fixes one more item at the end:

- **Pass 1** puts the largest item in the last slot.
- **Pass 2** puts the second largest in the second-to-last slot.
- …and after **n − 1 passes**, everything is in place.

### The early-exit trick

If a whole pass makes **no swaps**, every neighbour pair is already in order, so the whole array is sorted. The `swapped` flag lets us stop right there. That is the "avoid late loop termination" idea from Chapter 2, put into practice.

### Why the inner loop shrinks

After pass `i`, the last `i` items are final. So the inner loop only needs to go up to `n - 1 - i`. Comparing against the finished part is wasted work.

> Bubble sort is rarely used in real programs, but it is the easiest sort to reason about and a favourite for exam traces.

## C++ code: bubble-sort.cpp

```cpp
#include <iostream>
#include <utility>
using namespace std;

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // no swaps: already sorted
    }
}

void print(const int a[], int n) {
    for (int i = 0; i < n; i++) cout << a[i] << (i + 1 < n ? " " : "\n");
}

int main() {
    int a[] = {29, 10, 14, 37, 13, 5};
    int n = sizeof(a) / sizeof(a[0]);
    cout << "Before: ";
    print(a, n);
    bubbleSort(a, n);
    cout << "After:  ";
    print(a, n);
}
```

Expected output:

```text
Before: 29 10 14 37 13 5
After:  5 10 13 14 29 37
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case (already sorted) | O(n): one pass, no swaps, stop |
| Average case | O(n²) |
| Worst case (reversed) | O(n²): n(n−1)/2 comparisons and swaps |

Space: O(1)
Stable: yes
In-place: yes

The O(n) best case only exists **because of the `swapped` flag**. Without it, bubble sort always does n(n−1)/2 comparisons.

## Videos

- [Bubble sort algorithm](https://youtu.be/Jdtq5uKz-w4) (mycodeschool): Slow and careful. Traces every comparison and builds the C code with you.
- [Bubble sort in 2 minutes](https://youtu.be/xli_FI7CuzA) (Michael Sambol): A 2-minute visual recap. Watch it right before an exam.

## Exam lens

Likely questions:

- Show every pass of bubble sort on `5, 1, 4, 2, 8`. How many swaps happen?
- What is the purpose of the `swapped` flag? What is the best-case complexity with and without it?
- Is bubble sort stable? Explain why using the `>` comparison.
- How many comparisons does bubble sort make on n items in the worst case?

Common mistakes:

- Looping `j` up to `n - 1` in every pass instead of `n - 1 - i`. It still works, but does useless comparisons.
- Writing `a[j] >= a[j+1]`. Swapping equal items breaks stability.
- Reading past the array with `j < n` and then accessing `a[j + 1]`.
- Forgetting to reset `swapped = false` at the start of each pass.

## Quick check

1. After the **first** pass of bubble sort on `4, 3, 2, 1`, the array is:
   A. `3, 2, 1, 4`
   B. `1, 2, 3, 4`
   C. `3, 4, 2, 1`
   D. `1, 4, 3, 2`
   Answer: A. The 4 bubbles all the way to the end. The rest moves left by one place each.

2. What is the best-case time complexity of bubble sort **with** the early-exit flag?
   A. O(1)
   B. O(n)
   C. O(n log n)
   D. O(n²)
   Answer: B. On sorted input the first pass makes n−1 comparisons, no swaps, and stops.

3. Which change makes bubble sort **unstable**?
   A. Using `>=` instead of `>`
   B. Removing the `swapped` flag
   C. Looping `i` from `n-1` down to 1
   D. Using `std::swap`
   Answer: A. With `>=`, two equal items get swapped, so their original order is lost.

4. How many comparisons does bubble sort make on 6 items in the worst case?
   A. 6
   B. 15
   C. 30
   D. 36
   Answer: B. n(n−1)/2 = 6·5/2 = 15.

## Practice

**Trace by hand.** Trace bubble sort on `5, 1, 4, 2, 8`. Write the array after every pass and count the swaps.

Solution:

- Pass 1: `1 4 2 5 8` (3 swaps)
- Pass 2: `1 2 4 5 8` (1 swap)
- Pass 3: `1 2 4 5 8` (0 swaps, so stop early)

Total: 4 swaps, 4 + 3 + 2 = 9 comparisons.


**Implement it.** Write `bubbleSortDesc(int a[], int n)` that sorts in **descending** order, and make it print the number of passes it actually used.

Hint: Flip one comparison. Count passes in the outer loop and print after the loop (or after `break`).

```cpp
void bubbleSortDesc(int a[], int n) {
    int passes = 0;
    for (int i = 0; i < n - 1; i++) {
        passes++;
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] < a[j + 1]) { swap(a[j], a[j + 1]); swapped = true; }
        if (!swapped) break;
    }
    cout << "passes: " << passes << "\n";
}
```


**Problems:**

- [Sort an Array (try bubble sort first, see it time out)](https://leetcode.com/problems/sort-an-array/) (medium). Hint: Bubble sort is correct but O(n²) and will hit the time limit. That is the lesson. Come back after Chapter 8 with merge sort.
- [Move Zeroes](https://leetcode.com/problems/move-zeroes/) (easy). Hint: Think of zeros as "heavy" items that must sink to the end, like bubble sort, but you can do it in one pass.
- [Bubble Sort (HackerRank)](https://www.hackerrank.com/challenges/ctci-bubble-sort/problem) (easy). Hint: Count every swap while sorting, then print the count, first and last element.

## Mastery checklist

- [ ] I can trace bubble sort pass by pass on a small array.
- [ ] I can write bubble sort from memory, including the swapped flag.
- [ ] I can explain why the best case is O(n) and the worst case is O(n²).
- [ ] I can explain why bubble sort is stable.


---

# 3.3 Insertion Sort

> Grow a sorted part on the left by inserting each new item into its correct place, like sorting cards in your hand. Fast on nearly sorted data.

Chapter: Simple Sorting & Searching · ~40 min · easy
URL: https://dsa.fetehadin.com/learn/insertion-sort

## Mental model

You're dealt cards one at a time. Your hand is always sorted: each new card slides left past the bigger ones until it finds its spot. You never re-sort the whole hand. That's insertion sort.

### The idea

- The part `a[0..i-1]` is always **sorted**.
- Take `key = a[i]`.
- Walk left from `i - 1`, **shifting** every item bigger than `key` one place right.
- When you hit an item ≤ key (or the start), drop `key` into the gap.

### Why it's adaptive

If the array is already sorted, every key is ≥ its left neighbour, so the while loop stops at once: **n − 1 comparisons, O(n)**. If it's reversed, every key travels all the way to the front: **n(n−1)/2**, O(n²). The less "out of order" the data, the faster it runs.

### Shift, don't swap

Each step of the while loop is **one assignment** (`a[j+1] = a[j]`), not a three-assignment swap. That's why insertion sort usually beats bubble sort in practice, even though both are O(n²).

## C++ code: insertion-sort.cpp

```cpp
#include <iostream>
using namespace std;

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {   // shift bigger items right
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;                  // drop key into the gap
    }
}

int main() {
    int a[] = {29, 10, 14, 37, 13, 5};
    int n = sizeof(a) / sizeof(a[0]);
    insertionSort(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << "\n";
}
```

Expected output:

```text
5 10 13 14 29 37
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case (already sorted) | O(n): n − 1 comparisons, 0 shifts |
| Average case | O(n²) |
| Worst case (reversed) | O(n²): n(n−1)/2 comparisons and shifts |

Space: O(1)
Stable: yes
In-place: yes

Insertion sort is **adaptive** (faster on nearly sorted input) and **online** (it can sort items as they arrive). Real libraries use it for small sub-arrays.

## Videos

- [Insertion sort algorithm](https://youtu.be/i-SKeOcBwko) (mycodeschool): Builds the "shift right, then drop the key" loop carefully and analyses the cases.
- [Insertion sort in 2 minutes](https://youtu.be/JU767SDMDvA) (Michael Sambol): Two-minute animation to lock in the picture.

## Exam lens

Likely questions:

- Trace insertion sort on `12, 11, 13, 5, 6`, showing the array after each insertion.
- What are the best and worst case inputs and complexities of insertion sort?
- Why does insertion sort perform well on nearly sorted data?
- Compare insertion sort with selection sort.

Common mistakes:

- Writing `a[j] >= key` in the while loop. That breaks stability.
- Forgetting `j >= 0` in the loop condition, which reads `a[-1]`.
- Putting `a[j + 1] = key` inside the while loop. It goes **after** the loop.
- Starting the outer loop at `i = 0`. Item 0 alone is already "sorted", so start at 1.

## Quick check

1. Insertion sort on `2, 3, 4, 5, 1`: how many shifts happen in total?
   A. 1
   B. 4
   C. 5
   D. 10
   Answer: B. Only the last key (1) moves, shifting 2, 3, 4 and 5 one place right.

2. Best case of insertion sort?
   A. O(1)
   B. O(n)
   C. O(n log n)
   D. O(n²)
   Answer: B. Each key is compared once with its left neighbour and stays put.

3. What does the inner while loop do?
   A. Finds the minimum
   B. Swaps neighbours until sorted
   C. Shifts larger items right to open a gap for key
   D. Splits the array
   Answer: C. Shifting (one assignment each) is cheaper than swapping (three assignments).

4. Which sort is best for an array that is already sorted except for 2 items?
   A. Selection sort
   B. Insertion sort
   C. All are the same
   D. None
   Answer: B. It is adaptive, so the work is close to O(n). Selection sort would still do n²/2 comparisons.

## Practice

**Trace by hand.** Trace insertion sort on `12, 11, 13, 5, 6`. Write the array after each value of i.

Solution:

- i = 1 (key 11): `11 12 13 5 6`
- i = 2 (key 13): `11 12 13 5 6` (no shift)
- i = 3 (key 5): `5 11 12 13 6` (3 shifts)
- i = 4 (key 6): `5 6 11 12 13` (3 shifts)


**Implement it.** Write `insertionSortDesc` (descending order), then a version that sorts an array of `string` names alphabetically.

Hint: Only the comparison changes. `string` supports `<` and `>` out of the box.

**Problems:**

- [Insertion Sort List](https://leetcode.com/problems/insertion-sort-list/) (medium). Hint: Same idea on a linked list. Use a dummy head for the sorted list and insert each node after the right predecessor (revisit after Chapter 4).
- [Sort an Array](https://leetcode.com/problems/sort-an-array/) (medium). Hint: Insertion sort will time out on the large tests, which shows why O(n²) matters.
- [Insertion Sort - Part 1 (HackerRank)](https://www.hackerrank.com/challenges/insertionsort1/problem) (easy). Hint: Print the array after every shift. A great tracing exercise.

## Mastery checklist

- [ ] I can trace insertion sort and show every shift.
- [ ] I can write it from memory with the correct while condition.
- [ ] I can name the best/worst inputs and their complexities.
- [ ] I can explain why it is stable and adaptive.


---

# 3.4 Pointer Sort

> When records are big, don't move them. Sort an array of pointers (or indices) to the records instead, and only small addresses get swapped.

Chapter: Simple Sorting & Searching · ~30 min · medium
URL: https://dsa.fetehadin.com/learn/pointer-sort

## Mental model

A library has 10,000 heavy books on shelves. To list them by title you don't **carry the books around**. You sort the **index cards** that say where each book is. The books never move; the cards do.

That is **pointer sort** (also called *indirect* or *index* sort).

### The problem it solves

Each swap in a normal sort copies whole items. If each item is a big `struct` (name, ID, address, photo…), every swap copies hundreds of bytes three times. That's slow.

### The trick

1. Make an array of pointers: `p[i] = &records[i]`.
2. Run any sort on **p**, but compare through the pointers: `p[j]->score < p[min]->score`.
3. Swap **pointers**: `swap(p[i], p[min])`. Each swap moves 8 bytes.
4. Read records in order through p: `p[0]->name`, `p[1]->name`, …

The original array keeps its order. You can even keep **several pointer arrays** (by name, by score, by ID) over the same data at once.

## C++ code: pointer-sort.cpp

```cpp
#include <iostream>
#include <string>
#include <utility>
using namespace std;

struct Student {
    string name;
    int score;
    char bigData[1000];   // pretend each record is large and slow to copy
};

// Sort an array of POINTERS by score. The records never move.
void pointerSort(Student* p[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (p[j]->score < p[min]->score)
                min = j;
        swap(p[i], p[min]);   // swaps two addresses (8 bytes), not two records
    }
}

int main() {
    Student s[5] = {{"Abel", 72, {}}, {"Bethel", 95, {}}, {"Dawit", 58, {}},
                    {"Hana", 81, {}}, {"Kidus", 66, {}}};
    const int n = 5;
    Student* p[n];
    for (int i = 0; i < n; i++) p[i] = &s[i];

    pointerSort(p, n);

    cout << "Sorted view:   ";
    for (int i = 0; i < n; i++) cout << p[i]->name << "(" << p[i]->score << ") ";
    cout << "\nOriginal array: ";
    for (int i = 0; i < n; i++) cout << s[i].name << " ";
    cout << "\n";
}
```

Expected output:

```text
Sorted view:   Dawit(58) Kidus(66) Abel(72) Hana(81) Bethel(95) 
Original array: Abel Bethel Dawit Hana Kidus
```

## Complexity

| Case | Cost |
| --- | --- |
| Comparisons | same as the underlying sort (here selection: n(n−1)/2) |
| Data moved per swap | one pointer (8 bytes) instead of one whole record |
| Time | O(n²) with selection sort; O(n log n) with a fast sort |

Space: O(n) for the pointer array
Stable: no
In-place: no

Pointer sort is a **technique**, not a new algorithm. Any sort (selection, insertion, quick…) can be made indirect.

## Videos

- [Introduction to pointers in C/C++](https://youtu.be/h-HBipu_1P0) (mycodeschool): You need pointers for this; mycodeschool's intro is the best 10-minute refresher.
- [Selection sort algorithm](https://youtu.be/GUDLRan2DWM) (mycodeschool): The underlying sort in our example is selection sort.

## Exam lens

Likely questions:

- What is pointer sort and why is it used?
- Write a function that sorts an array of pointers to `Student` records by score.
- After pointer-sorting, how do you print records in sorted order? Has the original array changed?
- Compare the cost of a swap in normal sorting vs pointer sorting for 1 KB records.

Common mistakes:

- Swapping the records (`swap(*p[i], *p[min])`) instead of the pointers (`swap(p[i], p[min])`). That defeats the purpose.
- Comparing the pointers themselves (`p[j] < p[min]`) instead of what they point to (`p[j]->score`).
- Forgetting to initialise `p[i] = &s[i]` before sorting.

## Quick check

1. In pointer sort, what gets swapped?
   A. The records
   B. The pointers (or indices) to the records
   C. The keys only
   D. Nothing
   Answer: B. Records stay put; only small addresses move.

2. Which line correctly compares scores through pointers?
   A. `if (p[j] < p[min])`
   B. `if (p[j]->score < p[min]->score)`
   C. `if (*p[j] < *p[min])`
   D. `if (&p[j] < &p[min])`
   Answer: B. `->` follows the pointer to the struct and reads its `score`.

3. After pointer sort, the original `Student s[]` array is…
   A. sorted
   B. unchanged
   C. reversed
   D. deleted
   Answer: B. Only the pointer array p[] is in sorted order.

4. Main benefit of pointer sort?
   A. Fewer comparisons
   B. Less data copied per swap
   C. O(n log n) time
   D. No extra memory
   Answer: B. Comparisons are the same; the saving is in how much data each swap moves.

## Practice

**Trace by hand.** Records: `[0] Abel 72, [1] Bethel 95, [2] Dawit 58`. Show `p[]` (as indices) after each pass of pointer selection sort by score.

Solution:

- Start: `p = [0, 1, 2]`
- Pass 1: min score 58 at p[2] → swap p[0], p[2] → `p = [2, 1, 0]`
- Pass 2: compare Bethel 95 vs Abel 72 → swap → `p = [2, 0, 1]`

Sorted order: Dawit, Abel, Bethel. The records array is untouched.


**Implement it.** Rewrite pointer sort using an `int idx[]` array of indices instead of pointers, and sort by **name** alphabetically.

Hint: Compare `s[idx[j]].name < s[idx[min]].name`, swap `idx[i]` and `idx[min]`.

```cpp
void indexSort(Student s[], int idx[], int n) {
    for (int i = 0; i < n; i++) idx[i] = i;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (s[idx[j]].name < s[idx[min]].name) min = j;
        swap(idx[i], idx[min]);
    }
}
```


**Problems:**

- [Sort the People](https://leetcode.com/problems/sort-the-people/) (easy). Hint: Exactly pointer/index sort. Sort an index array by `heights[i]` (descending), then output `names[idx[k]]`.
- [Rank Transform of an Array](https://leetcode.com/problems/rank-transform-of-an-array/) (easy). Hint: Sort indices by value, then walk them to assign ranks without disturbing the original order.

## Mastery checklist

- [ ] I can explain why we sort pointers instead of records.
- [ ] I can write pointer sort with `->` comparisons and pointer swaps.
- [ ] I can print records in sorted order through the pointer array.
- [ ] I can do the same with an index array.


---

# 3.5 Linear Search

> Check every item from left to right until you find the key or run out. Works on any array, sorted or not, but costs O(n).

Chapter: Simple Sorting & Searching · ~25 min · easy
URL: https://dsa.fetehadin.com/learn/linear-search

## Mental model

Looking for your friend in a queue of strangers, you walk from the front and check **each face** until you see them, or reach the end. That's linear (sequential) search.

### The algorithm

```text
for each index i from 0 to n-1:
    if a[i] == key: return i
return -1        (only after checking everything)
```

### Strengths and weaknesses

- ✅ Works on **unsorted** data and on **linked lists**.
- ✅ Dead simple, no preparation needed.
- ❌ Slow for big data: up to **n** comparisons.

If you'll search the same large array many times, it's worth sorting it **once** and using binary search after that.

## C++ code: linear-search.cpp

```cpp
#include <iostream>
using namespace std;

int linearSearch(const int a[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key)
            return i;      // found: stop right away
    return -1;             // checked everything: not there
}

int main() {
    int a[] = {23, 7, 41, 15, 9, 32, 18};
    int n = 7;
    cout << "search 9  -> " << linearSearch(a, n, 9) << "\n";
    cout << "search 23 -> " << linearSearch(a, n, 23) << "\n";
    cout << "search 50 -> " << linearSearch(a, n, 50) << "\n";
}
```

Expected output:

```text
search 9  -> 4
search 23 -> 0
search 50 -> -1
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case | O(1): key at index 0 |
| Average case (found) | (n + 1)/2 comparisons → O(n) |
| Worst case | O(n): last item or not present |
| Needs sorted data? | No |

Space: O(1)

On a linked list, linear search is the **only** option, because you can't jump to the middle.

## Videos

- [What is binary search](https://youtu.be/j5uXyPJ0Pew) (mycodeschool): Starts with linear search, then shows why binary search is a huge improvement.

## Exam lens

Likely questions:

- Write a linear search function that returns the index of the key or −1.
- What are the best, average and worst case complexities of linear search?
- When is linear search preferred over binary search?
- Modify linear search to return the index of the LAST occurrence.

Common mistakes:

- Returning `-1` inside the loop (in an `else`), which stops after checking only the first item.
- Looping with `i <= n`, one past the end.
- Forgetting that an unsorted array cannot use binary search.

## Quick check

1. What is wrong here?

```cpp
for (int i = 0; i < n; i++)
    if (a[i] == key) return i;
    else return -1;
```
   A. Nothing
   B. It only ever checks a[0]
   C. It loops forever
   D. It reads past the end
   Answer: B. Either branch returns on the first iteration. `return -1` belongs after the loop.

2. Linear search on 1000 items, key not present. Comparisons?
   A. 1
   B. 500
   C. 1000
   D. 10
   Answer: C. Every item must be checked.

3. Linear search is the better choice when…
   A. the data is huge and sorted
   B. the data is small or unsorted
   C. you search millions of times
   D. never
   Answer: B. Sorting first costs O(n log n). For a single search on unsorted data, just scan.

## Practice

**Trace by hand.** How many comparisons does linear search make on `[7, 2, 9, 4, 9, 1]` for keys 9, 1 and 5?

Solution:

- key 9: **3** (first occurrence at index 2)
- key 1: **6**
- key 5: **6** (not found)


**Implement it.** Write `countOccurrences(a, n, key)` and `lastIndexOf(a, n, key)`.

Hint: For lastIndexOf, loop backwards from `n - 1` and return the first match, or loop forwards and remember the latest match.

**Problems:**

- [Check If N and Its Double Exist](https://leetcode.com/problems/check-if-n-and-its-double-exist/) (easy). Hint: For each item, linearly search for its double (O(n²)). Then think about how a set makes it O(n).
- [Find Numbers with Even Number of Digits](https://leetcode.com/problems/find-numbers-with-even-number-of-digits/) (easy). Hint: A linear scan with a digit counter.

## Mastery checklist

- [ ] I can write linear search returning the index or −1.
- [ ] I can state its best, average and worst case.
- [ ] I can explain when linear search beats binary search.


---

# 3.6 Binary Search

> On a sorted array, check the middle, then throw away the half that cannot contain the key. Each step halves the problem, so it takes O(log n).

Chapter: Simple Sorting & Searching · ~40 min · medium
URL: https://dsa.fetehadin.com/learn/binary-search

## Mental model

Guess-my-number from 1 to 100: you say 50; "higher"; 75; "lower"; 62… Every guess **cuts the possibilities in half**. You'll always win within 7 guesses. That's binary search.

### The algorithm (array must be sorted)

1. `low = 0`, `high = n - 1`.
2. While `low <= high`:
   - `mid = (low + high) / 2`
   - if `a[mid] == key` → found.
   - if `a[mid] < key` → the key can only be on the right: `low = mid + 1`.
   - else → it can only be on the left: `high = mid - 1`.
3. If the loop ends, the key isn't there: return −1.

### Why O(log n)

After each comparison the range halves: n → n/2 → n/4 → … → 1. The number of halvings is **log₂ n**. For a million items that's about **20 comparisons** instead of a million.

### Two requirements

- **Sorted** data, otherwise discarding a half is wrong.
- **Random access** (an array), so jumping to `mid` is O(1). On a linked list, reaching the middle costs O(n), which ruins the speed.

## C++ code: binary-search.cpp (iterative)

```cpp
#include <iostream>
using namespace std;

int binarySearch(const int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // same as (low+high)/2, but cannot overflow
        if (a[mid] == key) return mid;
        else if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    int a[] = {3, 8, 12, 17, 23, 31, 38, 45, 52, 60};   // must be sorted
    int n = 10;
    cout << "search 38 -> " << binarySearch(a, n, 38) << "\n";
    cout << "search 3  -> " << binarySearch(a, n, 3) << "\n";
    cout << "search 40 -> " << binarySearch(a, n, 40) << "\n";
}
```

Expected output:

```text
search 38 -> 6
search 3  -> 0
search 40 -> -1
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case | O(1): key is at the first mid |
| Average / worst case | O(log n): about ⌊log₂ n⌋ + 1 comparisons |
| 1,000,000 items | at most 20 comparisons |
| Needs sorted data? | Yes, and random access (an array, not a linked list) |

Space: O(1) iterative · O(log n) recursive (call stack)

## Videos

- [What is binary search](https://youtu.be/j5uXyPJ0Pew) (mycodeschool): Builds the idea from scratch and writes careful code including the edge cases.
- [Binary search in 4 minutes](https://youtu.be/fDKIpRe8GW4) (Michael Sambol): Four-minute visual summary.

## Exam lens

Likely questions:

- Trace binary search for key 23 in `2, 5, 8, 12, 16, 23, 38, 56, 72, 91`, giving low, mid and high at each step.
- Write an iterative binary search function in C++.
- What is the worst-case number of comparisons for n = 1024?
- Why can't binary search be applied to a linked list efficiently?

Common mistakes:

- Using `while (low < high)` instead of `low <= high`. That misses a key when one item is left.
- Setting `low = mid` or `high = mid` instead of `mid ± 1`, which can loop forever.
- Running it on unsorted data. The result is meaningless.
- `(low + high) / 2` can overflow for huge arrays; `low + (high - low) / 2` is safe.

## Quick check

1. Maximum comparisons for binary search on 1000 items?
   A. 10
   B. 100
   C. 500
   D. 1000
   Answer: A. 2¹⁰ = 1024 ≥ 1000, so about 10 halvings.

2. In `3, 8, 12, 17, 23, 31, 38`, searching 31: what is the first mid?
   A. index 2 (12)
   B. index 3 (17)
   C. index 4 (23)
   D. index 5 (31)
   Answer: B. (0 + 6) / 2 = 3.

3. If `a[mid] < key`, the next step is…
   A. high = mid − 1
   B. low = mid + 1
   C. low = mid
   D. return mid
   Answer: B. The key must be to the right of mid.

4. Binary search requires…
   A. a linked list
   B. a sorted array
   C. unique values
   D. an even n
   Answer: B. Sorted order lets us discard a half; an array gives O(1) access to mid.

## Practice

**Trace by hand.** Trace binary search for 23 and for 50 in `2, 5, 8, 12, 16, 23, 38, 56, 72, 91` (indices 0–9).

Solution:

**Key 23:** (0,9) mid 4 = 16 → low 5 · (5,9) mid 7 = 56 → high 6 · (5,6) mid 5 = 23 ✓ **3 comparisons**

**Key 50:** (0,9) mid 4 = 16 → low 5 · (5,9) mid 7 = 56 → high 6 · (5,6) mid 5 = 23 → low 6 · (6,6) mid 6 = 38 → low 7 · low > high → **−1 after 4 comparisons**


**Implement it.** Write `firstOccurrence(a, n, key)` that returns the **first** index of key in a sorted array with duplicates.

Hint: When `a[mid] == key`, don't return. Record `ans = mid` and keep searching left with `high = mid - 1`.

```cpp
int firstOccurrence(const int a[], int n, int key) {
    int low = 0, high = n - 1, ans = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key) { ans = mid; high = mid - 1; }
        else if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return ans;
}
```


**Problems:**

- [Binary Search](https://leetcode.com/problems/binary-search/) (easy). Hint: The textbook version. Get it right without looking.
- [Search Insert Position](https://leetcode.com/problems/search-insert-position/) (easy). Hint: When the loop ends without finding the key, `low` is exactly where it would be inserted.
- [First Bad Version](https://leetcode.com/problems/first-bad-version/) (easy). Hint: Binary search on the *answer*. Same pattern as firstOccurrence.

## Mastery checklist

- [ ] I can trace low, mid and high by hand.
- [ ] I can write iterative binary search with the correct `<=` and `± 1`.
- [ ] I can explain why it is O(log n) and needs sorted data.
- [ ] I can modify it to find the first occurrence.


---

# 3.7 Recursion Primer

> A function that calls itself on a smaller problem until it reaches a base case. You need this for trees (Ch 6) and merge/quick sort (Ch 8).

Chapter: Simple Sorting & Searching · ~45 min · medium
URL: https://dsa.fetehadin.com/learn/recursion

## Mental model

Russian **matryoshka dolls**: to find the smallest doll you open a doll, and inside is… a smaller doll, which you open the same way. You stop when a doll doesn't open. That last doll is the **base case**.

### Two required parts

1. **Base case**: a small input you can answer directly, with no further calls (`n <= 1` → return 1).
2. **Recursive case**: solve the problem using the answer to a **smaller** version of itself (`n * factorial(n - 1)`). Each call must move **toward** the base case.

### The call stack

Every call gets its own **stack frame** (its own copy of `n`, its own return address). When `factorial(4)` calls `factorial(3)`, the first call **pauses** and waits. Frames pile up until the base case returns, then they **unwind** one by one, each finishing its multiplication.

That's why recursion uses **O(depth)** memory, and why a missing base case ends in a **stack overflow**.

### When to use it

Recursion shines when a problem naturally contains smaller copies of itself: **trees** (a subtree is a tree), **divide and conquer** sorts (merge and quick sort), and searching by halves.

## C++ code: recursion.cpp

```cpp
#include <iostream>
using namespace std;

int factorial(int n) {
    if (n <= 1) return 1;            // base case: stops the recursion
    return n * factorial(n - 1);     // recursive case: smaller problem
}

int bs(const int a[], int low, int high, int key) {
    if (low > high) return -1;               // base case 1: empty range
    int mid = (low + high) / 2;
    if (a[mid] == key) return mid;           // base case 2: found
    if (a[mid] < key) return bs(a, mid + 1, high, key);
    return bs(a, low, mid - 1, key);
}

void countDown(int n) {
    if (n == 0) { cout << "liftoff!\n"; return; }
    cout << n << " ";
    countDown(n - 1);
}

int main() {
    cout << "5! = " << factorial(5) << "\n";
    int a[] = {2, 5, 9, 14, 20, 27, 33, 41};
    cout << "bs(27) -> " << bs(a, 0, 7, 27) << "\n";
    cout << "bs(4)  -> " << bs(a, 0, 7, 4) << "\n";
    countDown(3);
}
```

Expected output:

```text
5! = 120
bs(27) -> 5
bs(4)  -> -1
3 2 1 liftoff!
```

## Complexity

| Case | Cost |
| --- | --- |
| factorial(n): time | O(n): n calls, O(1) work each |
| factorial(n): space | O(n) stack frames |
| recursive binary search: time | O(log n) |
| recursive binary search: space | O(log n) stack frames (iterative version: O(1)) |


Every recursive call uses a **stack frame**. Too deep (or no base case) means a stack overflow and a crash.

## Videos

- [Recursion (CS50 Shorts)](https://youtu.be/mz6tAJMVmfM) (CS50): CS50's short is the friendliest explanation of base case, recursive case and the call stack.
- [5 Simple Steps for Solving Any Recursive Problem](https://youtu.be/ngCos392W4w) (Reducible): A 5-step method for writing recursive functions. It pays off in Ch 6 and Ch 8.

## Exam lens

Likely questions:

- What is recursion? What are the two required parts of a recursive function?
- Trace `factorial(4)` showing the call stack.
- Write a recursive binary search function.
- What happens if a recursive function has no base case?

Common mistakes:

- No base case, or a base case that is never reached (e.g. `factorial(n + 1)`).
- Forgetting to `return` the recursive call's result (`bs(...)` instead of `return bs(...)`).
- Thinking recursion is always slower or always better. It trades stack memory for simpler code.

## Quick check

1. What does `f(3)` return?

```cpp
int f(int n) {
    if (n == 0) return 0;
    return n + f(n - 1);
}
```
   A. 3
   B. 5
   C. 6
   D. 0
   Answer: C. 3 + 2 + 1 + 0 = 6.

2. The base case of a recursive function…
   A. calls the function again
   B. stops the recursion with a direct answer
   C. is optional
   D. must be the last line
   Answer: B. Without it the calls never stop.

3. Calling `factorial(5)` creates at most how many frames on the stack at once?
   A. 1
   B. 5
   C. 6
   D. 120
   Answer: B. factorial(5) → (4) → (3) → (2) → (1). Five frames before unwinding.

4. Missing base case usually causes…
   A. a compile error
   B. a stack overflow at run time
   C. the wrong answer silently
   D. nothing
   Answer: B. Each call adds a frame until the stack memory runs out.

## Practice

**Trace by hand.** Trace `power(2, 4)` where `power(b, e)` returns 1 if e == 0, else `b * power(b, e - 1)`. Show the calls going down and the values coming back up.

Solution:

Down: power(2,4) → power(2,3) → power(2,2) → power(2,1) → power(2,0)

Up: power(2,0) = 1 → power(2,1) = 2 → power(2,2) = 4 → power(2,3) = 8 → power(2,4) = **16**


**Implement it.** Write recursive `sumArray(a, n)`, `reverseString(s, l, r)` and `fib(n)`. Which one is slow for n = 40 and why?

Hint: `fib(n) = fib(n-1) + fib(n-2)` recomputes the same values exponentially many times → O(2ⁿ).

```cpp
int sumArray(const int a[], int n) { return n == 0 ? 0 : a[n - 1] + sumArray(a, n - 1); }
void reverseString(string& s, int l, int r) { if (l >= r) return; swap(s[l], s[r]); reverseString(s, l + 1, r - 1); }
long long fib(int n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }   // exponential!
```


**Problems:**

- [Fibonacci Number](https://leetcode.com/problems/fibonacci-number/) (easy). Hint: Write it recursively first, then notice the repeated work.
- [Power of Two](https://leetcode.com/problems/power-of-two/) (easy). Hint: Base cases: n == 1 → true; n odd or n ≤ 0 → false. Recursive case: isPowerOfTwo(n / 2).
- [Reverse String](https://leetcode.com/problems/reverse-string/) (easy). Hint: Swap the ends, recurse on the inside. Base case — `l >= r`.

## Mastery checklist

- [ ] I can name the base case and recursive case of any recursive function.
- [ ] I can draw the call stack for factorial(4).
- [ ] I can write recursive binary search.
- [ ] I can explain stack overflow and the O(n) space of deep recursion.


---

# 4.1 Pointers, new/delete & the Heap

> A pointer holds an address. new asks the heap for memory that lives until you delete it. Master this and linked lists become easy.

Chapter: Linked Lists · ~45 min · medium
URL: https://dsa.fetehadin.com/learn/pointers-and-memory

## Mental model

A variable is a **house**; its value is the **person living there**; its address is the **street address**. A **pointer** is a slip of paper with an address written on it. It doesn't hold the person, it tells you where to find them.

```cpp
int x = 5;      // a house with 5 in it
int* p = &x;    // & = "address of": p holds x's address
*p = 10;        // * = "go to that address": changes x to 10
```

### Stack vs heap

- **Stack**: local variables. Created when a function starts, destroyed automatically when it returns. Fast, but small, and its size is fixed at compile time.
- **Heap**: memory you request at run time with **`new`**. It stays alive until **you** call **`delete`**. This is how we make data structures that grow while the program runs.

```cpp
Node* n = new Node{7, nullptr};   // lives on the heap
delete n;                          // give it back
n = nullptr;                       // don't keep a stale address
```

### Three classic bugs

1. **Null dereference**: `*p` when `p == nullptr`. Crash.
2. **Dangling pointer**: using `p` after `delete p`. Random behaviour.
3. **Memory leak**: losing the last pointer to heap memory, so it can never be freed.

> Rule of thumb: every `new` has exactly one matching `delete`. After deleting, set the pointer to `nullptr`.

## C++ code: pointers.cpp

```cpp
#include <iostream>
using namespace std;

int main() {
    int x = 5;
    int* p = &x;                 // p holds the address of x
    *p = 10;                     // write through the pointer
    cout << "x = " << x << ", *p = " << *p << "\n";
    cout << "p points to x? " << (p == &x ? "yes" : "no") << "\n";

    int* q = new int(42);        // one int on the heap
    cout << "*q = " << *q << "\n";
    delete q;                    // give it back
    q = nullptr;                 // never leave a dangling pointer
    if (q == nullptr) cout << "q is safely null\n";

    int n = 4;
    int* arr = new int[n];       // array on the heap: size chosen at run time
    for (int i = 0; i < n; i++) arr[i] = (i + 1) * 10;
    cout << "arr: ";
    for (int i = 0; i < n; i++) cout << *(arr + i) << " ";   // pointer arithmetic
    cout << "\n";
    delete[] arr;                // new[] needs delete[]
    arr = nullptr;
}
```

Expected output:

```text
x = 10, *p = 10
p points to x? yes
*q = 42
q is safely null
arr: 10 20 30 40
```

## Complexity

| Case | Cost |
| --- | --- |
| `&x`, `*p`, `p->field` | O(1) |
| `new` / `delete` one object | O(1) (amortised; done by the allocator) |
| Stack memory | automatic: freed when the function returns |
| Heap memory | manual: lives until `delete` |


Linked lists, trees and graphs are built from heap nodes connected by pointers. Every bug in Chapters 4–7 is a pointer bug in disguise.

## Videos

- [Introduction to pointers in C/C++](https://youtu.be/h-HBipu_1P0) (mycodeschool): The clearest 10-minute introduction to `&`, `*` and what a pointer really stores.
- [Pointers and dynamic memory: stack vs heap](https://youtu.be/_8-ht2AKyH4) (mycodeschool): Explains stack vs heap with diagrams. This is exactly what the visualizer above animates.

## Exam lens

Likely questions:

- What is a pointer? Explain `&` and `*` with an example.
- Differentiate between stack and heap memory.
- What is a memory leak? Write code that causes one and fix it.
- What is a dangling pointer and how do you avoid it?

Common mistakes:

- Dereferencing `nullptr` or an uninitialised pointer, which crashes (segmentation fault).
- Using memory after `delete` (dangling pointer). Set the pointer to `nullptr` right after.
- `new[]` paired with `delete` instead of `delete[]`.
- Overwriting the only pointer to heap memory before deleting it, which leaks it forever.

## Quick check

1. What does this print?

```cpp
int x = 3;
int* p = &x;
*p = *p + 4;
cout << x;
```
   A. 3
   B. 4
   C. 7
   D. an address
   Answer: C. `*p` IS x, so x becomes 3 + 4.

2. Memory from `new` is freed…
   A. when the function returns
   B. when you call delete
   C. never
   D. when the pointer goes out of scope
   Answer: B. Heap memory is manual. If the pointer disappears first, you have a leak.

3. Which line causes a leak?

```cpp
int* p = new int(5);   // A
p = new int(6);       // B
delete p;             // C
```
   A. A
   B. B
   C. C
   D. none
   Answer: B. The address of the 5 is lost at line B, so it can never be deleted.

4. For a pointer `Node* n`, `n->data` is the same as…
   A. `*n.data`
   B. `(*n).data`
   C. `&n.data`
   D. `n.data`
   Answer: B. Arrow = dereference, then access the member.

## Practice

**Trace by hand.** Draw the stack and heap after each line and say what is printed:
```cpp
int a = 2;
int* p = &a;
int* q = new int(a * 5);
*p = *q + 1;
cout << a << " " << *q;
delete q;
```


Solution:

- stack: a = 2, p → a; heap: (none)
- `q = new int(10)`: heap gets 10, q → it
- `*p = *q + 1` sets a = 11
- prints **11 10**
- `delete q` frees the heap int (q is now dangling, so set it to `nullptr`)


**Implement it.** Write `int* makeArray(int n)` that returns a heap array filled with 1..n, use it in `main`, print the sum, and free it correctly.

Hint: `int* a = new int[n];` … `delete[] a;`. Check with `g++ -fsanitize=address` that there is no leak.

**Problems:**

- [Design Linked List](https://leetcode.com/problems/design-linked-list/) (medium). Hint: The best pointer workout. Start with addAtHead and get; draw boxes and arrows on paper for every line.
- [Pointers in C (HackerRank)](https://www.hackerrank.com/challenges/c-tutorial-pointer/problem) (easy). Hint: Modify two values through pointers. Warm-up for `*` and `&`.

## Mastery checklist

- [ ] I can explain `&`, `*` and `->` with a drawing.
- [ ] I can explain the difference between stack and heap memory.
- [ ] I can pair every `new` with exactly one `delete` (and `new[]` with `delete[]`).
- [ ] I can spot leaks and dangling pointers in code.


---

# 4.2 Singly Linked List

> Nodes on the heap, each pointing to the next. Insert at front, end or a position, delete by value, search and traverse, plus the dummy-node trick and the classic pitfalls.

Chapter: Linked Lists · ~75 min · medium
URL: https://dsa.fetehadin.com/learn/singly-linked-list

## Mental model

A **treasure hunt**: each clue tells you where the next clue is hidden. You can't jump to clue #7. You must follow clues 1 → 2 → … → 7. But adding a new clue in the middle is easy: change one clue to point to the new one, and the new one to point onward.

That is a **singly linked list**: nodes scattered around the heap, each holding **data** and a **pointer to the next node**. The program only keeps **`head`**, the address of the first node. The last node's `next` is `nullptr`.

```cpp
struct Node {
    int data;
    Node* next;
};
```

### The golden rule of rewiring

When inserting, **connect the new node first, then redirect the old pointer**. If you move `head` (or `temp->next`) first, you lose the rest of the list.

### Deleting needs the node before

To remove node X you change the arrow that points **to** X, and that arrow belongs to the **previous** node. So deletion walks with a `prev` pointer. Deleting the head is a special case: there is no previous node.

### The dummy (sentinel) node

Put a fake node **before** the head: `Node dummy{0, head};`. Now every real node, including the first, has a previous node, so one loop handles all cases. At the end, `head = dummy.next`.

### Pitfalls checklist

- Check `nullptr` before every `->`.
- Handle the **empty list**, **one node**, **head** and **tail** cases.
- `delete` every node you unlink.
- Never move `head` to traverse. Use a `temp` copy.

## C++ code: singly-linked-list.cpp

```cpp
#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void insertFront(Node*& head, int x) {
    Node* n = new Node{x, nullptr};
    n->next = head;          // 1. new node points at the old head
    head = n;                // 2. head points at the new node
}

void insertEnd(Node*& head, int x) {
    Node* n = new Node{x, nullptr};
    if (head == nullptr) { head = n; return; }
    Node* temp = head;
    while (temp->next != nullptr)
        temp = temp->next;
    temp->next = n;
}

void insertAt(Node*& head, int pos, int x) {      // pos is 0-based
    if (pos == 0) { insertFront(head, x); return; }
    Node* temp = head;
    for (int i = 0; i < pos - 1 && temp != nullptr; i++)
        temp = temp->next;
    if (temp == nullptr) return;                  // position too big
    Node* n = new Node{x, temp->next};
    temp->next = n;
}

void deleteValue(Node*& head, int x) {
    if (head == nullptr) return;
    if (head->data == x) {                        // deleting the head
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node* prev = head;
    while (prev->next != nullptr && prev->next->data != x)
        prev = prev->next;
    if (prev->next == nullptr) return;            // not found
    Node* temp = prev->next;
    prev->next = temp->next;
    delete temp;
}

void deleteDummy(Node*& head, int x) {            // same job, no special case
    Node dummy{0, head};
    Node* prev = &dummy;
    while (prev->next != nullptr && prev->next->data != x)
        prev = prev->next;
    if (prev->next != nullptr) {
        Node* temp = prev->next;
        prev->next = temp->next;
        delete temp;
    }
    head = dummy.next;
}

bool search(Node* head, int x) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == x) return true;
        temp = temp->next;
    }
    return false;
}

void print(Node* head) {
    for (Node* t = head; t != nullptr; t = t->next) cout << t->data << " -> ";
    cout << "null\n";
}

void freeList(Node*& head) {
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    Node* head = nullptr;
    insertEnd(head, 12);
    insertEnd(head, 7);
    insertEnd(head, 31);
    insertFront(head, 9);
    print(head);
    insertAt(head, 2, 15);
    print(head);
    deleteValue(head, 9);      // head
    deleteValue(head, 31);     // tail
    print(head);
    deleteDummy(head, 12);     // new head, handled by the dummy
    print(head);
    cout << "search 15: " << search(head, 15) << ", search 99: " << search(head, 99) << "\n";
    freeList(head);
    print(head);
}
```

Expected output:

```text
9 -> 12 -> 7 -> 31 -> null
9 -> 12 -> 15 -> 7 -> 31 -> null
12 -> 15 -> 7 -> null
15 -> 7 -> null
search 15: 1, search 99: 0
null
```

## Complexity

| Case | Cost |
| --- | --- |
| Insert at front | O(1) |
| Insert at end | O(n), or O(1) with a tail pointer |
| Insert at position k | O(k) |
| Delete by value / search | O(n) |
| Access the i-th item | O(n): no random access |

Space: O(n) plus one pointer per node

Compared with an array, a linked list wins at **inserting and deleting** (no shifting) and loses at **indexing** (must walk) and cache-friendliness.

## Videos

- [Introduction to linked list](https://youtu.be/NobHlGUjV3g) (mycodeschool): Why linked lists exist and how they compare with arrays.
- [Linked List: Implementation in C/C++](https://youtu.be/vcQIFT79_50) (mycodeschool): Writes the C/C++ node struct and insertion functions line by line.
- [Data Structures: Full Course Using C and C++](https://youtu.be/B31LgI4Y4DQ) (freeCodeCamp.org): The full freeCodeCamp version of mycodeschool's course; includes insert at nth position and delete.

## Exam lens

Likely questions:

- Write a function to insert a node at the beginning, at the end and at a given position of a singly linked list.
- Write a function that deletes the first node with a given value.
- Compare arrays and linked lists (memory, access, insertion, deletion).
- What is a dummy (sentinel) node and why does it simplify deletion?
- What happens if you write `head = n; n->next = head;` (wrong order)?

Common mistakes:

- Losing the list by updating `head` before linking the new node (`head = n;` first).
- Dereferencing `temp->next` without checking `temp != nullptr`.
- Forgetting the empty-list and delete-the-head special cases.
- Not calling `delete` on removed nodes (memory leak).
- Passing `Node* head` by value to a function that changes head. Use `Node*& head`.

## Quick check

1. Correct order to insert node n at the front?
   A. `head = n; n->next = head;`
   B. `n->next = head; head = n;`
   C. `n->next = nullptr; head = n;`
   D. `head->next = n;`
   Answer: B. Link to the old head first, then move head. The other order makes n point to itself and loses the list.

2. To delete a node in a singly linked list you need a pointer to…
   A. the node itself only
   B. the node BEFORE it
   C. the tail
   D. the head only
   Answer: B. The previous node's `next` is the arrow you must change.

3. What does this print? List: 3 → 8 → 5

```cpp
int c = 0;
for (Node* t = head; t; t = t->next) c += t->data;
cout << c;
```
   A. 3
   B. 16
   C. 5
   D. crash
   Answer: B. A traversal summing 3 + 8 + 5.

4. Why use a dummy node?
   A. It saves memory
   B. Every real node then has a previous node, so deleting the head needs no special case
   C. It makes search O(1)
   D. It sorts the list
   Answer: B. The dummy sits before head, and at the end `head = dummy.next`.

5. Why must `insertFront` take `Node*& head`?
   A. For speed
   B. So the change to head is visible to the caller
   C. References are required for pointers
   D. It doesn't need to
   Answer: B. A plain `Node*` parameter is a copy; assigning to it would not update the caller's head.

## Practice

**Trace by hand.** Start empty. Do insertEnd 4, insertFront 7, insertAt(1, 2), insertEnd 9, delete 7, delete 9. Write the list after each step.

Solution:

- insertEnd 4 → `4`
- insertFront 7 → `7 → 4`
- insertAt(1, 2) → `7 → 2 → 4`
- insertEnd 9 → `7 → 2 → 4 → 9`
- delete 7 (head case) → `2 → 4 → 9`
- delete 9 → `2 → 4`


**Implement it.** Write `reverse(Node*& head)` (iterative, O(1) extra space), `length(Node* head)` and `deleteAt(Node*& head, int pos)`.

Hint: Reverse: keep `prev = nullptr`, `cur = head`. Each step: save `next = cur->next`, set `cur->next = prev`, move `prev = cur`, `cur = next`. Finally `head = prev`.

```cpp
void reverse(Node*& head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur) {
        Node* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    head = prev;
}
```


**Problems:**

- [Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/) (easy). Hint: Three pointers, prev / cur / next. Draw it.
- [Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/) (easy). Hint: While `cur->next` has the same value as `cur`, unlink it.
- [Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/) (easy). Hint: A dummy node plus a tail pointer. Always attach the smaller head.
- [Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii/) (medium). Hint: Walk to the node before position `left`, then reverse the sublist with the same three-pointer trick. A dummy node saves you when left = 1.

## Mastery checklist

- [ ] I can insert at the front, the end and a position without losing the list.
- [ ] I can delete by value, including the head and not-found cases.
- [ ] I can use a dummy node to remove special cases.
- [ ] I can reverse a linked list iteratively.
- [ ] I free every removed node with delete.


---

# 4.3 Doubly Linked List

> Each node points both forward and backward. You can walk in both directions and delete a node knowing only its address, at the cost of one extra pointer per node.

Chapter: Linked Lists · ~50 min · medium
URL: https://dsa.fetehadin.com/learn/doubly-linked-list

## Mental model

A **train**: every carriage is coupled to the one in front **and** the one behind. You can walk through the train in either direction, and to unhook a carriage you only need that carriage, because it knows both neighbours.

```cpp
struct DNode {
    int data;
    DNode* prev;
    DNode* next;
};
```

We usually keep both **`head`** and **`tail`**, which makes inserting and deleting at **either end O(1)**.

### Updating both directions

Every insert or delete updates up to four pointers. A safe order for inserting `n` between `A` and `B`:

1. `n->prev = A; n->next = B;` (the new node first; nothing is lost yet)
2. `A->next = n; B->prev = n;`

For deleting `cur`: `cur->prev->next = cur->next;` and `cur->next->prev = cur->prev;`, and check for `nullptr` at the head and the tail.

### When to use it

Browser back/forward history, music playlists (previous/next), undo/redo, and any "delete this node now" situation. Pay the extra pointer when you need to move backwards.

## C++ code: doubly-linked-list.cpp

```cpp
#include <iostream>
using namespace std;

struct DNode {
    int data;
    DNode* prev;
    DNode* next;
};

void insertFront(DNode*& head, DNode*& tail, int x) {
    DNode* n = new DNode{x, nullptr, head};
    if (head != nullptr) head->prev = n;
    else tail = n;
    head = n;
}

void insertEnd(DNode*& head, DNode*& tail, int x) {
    DNode* n = new DNode{x, tail, nullptr};
    if (tail != nullptr) tail->next = n;
    else head = n;
    tail = n;
}

void deleteValue(DNode*& head, DNode*& tail, int x) {
    DNode* cur = head;
    while (cur != nullptr && cur->data != x) cur = cur->next;
    if (cur == nullptr) return;
    if (cur->prev) cur->prev->next = cur->next;
    else head = cur->next;
    if (cur->next) cur->next->prev = cur->prev;
    else tail = cur->prev;
    delete cur;
}

void printForward(DNode* head) {
    for (DNode* c = head; c != nullptr; c = c->next) cout << c->data << " ";
    cout << "\n";
}

void printBackward(DNode* tail) {
    for (DNode* c = tail; c != nullptr; c = c->prev) cout << c->data << " ";
    cout << "\n";
}

int main() {
    DNode* head = nullptr;
    DNode* tail = nullptr;
    insertEnd(head, tail, 10);
    insertEnd(head, tail, 20);
    insertEnd(head, tail, 30);
    insertFront(head, tail, 5);
    cout << "forward:  "; printForward(head);
    cout << "backward: "; printBackward(tail);
    deleteValue(head, tail, 20);   // middle
    deleteValue(head, tail, 30);   // tail
    cout << "after deletes: "; printForward(head);
    cout << "tail is now " << tail->data << "\n";
    while (head) deleteValue(head, tail, head->data);
    cout << "empty: " << (head == nullptr && tail == nullptr ? "yes" : "no") << "\n";
}
```

Expected output:

```text
forward:  5 10 20 30 
backward: 30 20 10 5 
after deletes: 5 10 
tail is now 10
empty: yes
```

## Complexity

| Case | Cost |
| --- | --- |
| Insert / delete at front or end (with tail) | O(1) |
| Delete a node you already have a pointer to | O(1): no need to find prev |
| Search / delete by value | O(n) |
| Traverse backward | O(n): impossible in a singly list without extra memory |

Space: O(n), with 2 pointers per node

The trade-off: more memory and more pointers to update (4 instead of 2 on insert), in exchange for two-way movement.

## Videos

- [Introduction to Doubly Linked List](https://youtu.be/JdQeNxWCguQ) (mycodeschool): A short intro to the node structure and insert/print in both directions.
- [Linked List: Implementation in C/C++](https://youtu.be/vcQIFT79_50) (mycodeschool): Revisit the singly version first if the pointer updates feel shaky.

## Exam lens

Likely questions:

- Write the node structure of a doubly linked list.
- Write a function to insert a node at the front of a doubly linked list.
- Write a function to delete a given node from a doubly linked list.
- Compare singly and doubly linked lists.

Common mistakes:

- Updating `next` but forgetting `prev` (or the reverse). Each insert or delete touches **both** directions.
- Forgetting `cur->next->prev` when `cur->next` is `nullptr` (deleting the tail) → crash.
- Not updating `tail` when deleting the last node.

## Quick check

1. Deleting node `cur` from the middle requires:
   A. `cur->prev->next = cur->next;` only
   B. `cur->next->prev = cur->prev;` only
   C. both of the above, then `delete cur`
   D. `delete cur` only
   Answer: C. Both neighbours must skip over cur.

2. Main advantage over a singly linked list?
   A. Less memory
   B. Traversal in both directions and O(1) delete given the node
   C. Faster search
   D. Random access
   Answer: B. It knows its own predecessor.

3. In a list 5 ⇄ 10 ⇄ 20 with tail at 20, after inserting 30 at the end, `tail->prev->data` is…
   A. 10
   B. 20
   C. 30
   D. 5
   Answer: B. 30 is now tail; its prev is 20.

## Practice

**Trace by hand.** Start empty. insertFront 10, insertEnd 20, insertFront 5, delete 10. Write all prev and next pointers at the end.

Solution:

Final list: `5 ⇄ 20`.

- 5: prev = null, next = 20
- 20: prev = 5, next = null
- head = 5, tail = 20


**Implement it.** Write `insertAfter(DNode* node, int x)` that inserts a new node right after `node` (update the tail if needed).

Hint: Four pointers to set (n->prev, n->next, node->next, and the old next's prev). Do the new node's pointers first.

```cpp
void insertAfter(DNode*& tail, DNode* node, int x) {
    DNode* n = new DNode{x, node, node->next};
    if (node->next) node->next->prev = n;
    else tail = n;
    node->next = n;
}
```


**Problems:**

- [Design Linked List](https://leetcode.com/problems/design-linked-list/) (medium). Hint: Implement it again, doubly linked, with dummy head AND dummy tail. All the edge cases vanish.
- [Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/) (easy). Hint: With prev pointers you could walk from both ends. With a singly list, use fast & slow pointers and reverse the second half (see Level Up).

## Mastery checklist

- [ ] I can write the DNode struct.
- [ ] I can insert at the front and end, updating prev, next, head and tail.
- [ ] I can delete any node, including the head and tail.
- [ ] I can compare singly and doubly linked lists.


---

# 5.1 Stacks with an Array

> Last in, first out. The stack ADT (push, pop, peek, isEmpty, isFull) built on a fixed array with a top index, plus overflow and underflow.

Chapter: Stacks & Queues · ~45 min · easy
URL: https://dsa.fetehadin.com/learn/stack-array

## Mental model

Think of a **stack of plates** in the cafeteria. You put a clean plate on **top**, and you take a plate from the **top**. The plate at the bottom was put there first and comes out last. That rule is **LIFO**: Last In, First Out.

A stack is an **ADT**: it is defined by its operations, not by how it is stored.

| Operation | Meaning |
| --- | --- |
| `push(x)` | put x on top |
| `pop()` | remove and return the top item |
| `peek()` / `top()` | look at the top item without removing it |
| `isEmpty()` | is there nothing on the stack? |
| `isFull()` | no room left (array version only) |

### Building it on an array

Keep an array `st[MAX]` and one integer **`top`**, the index of the top item. An empty stack has `top = -1`.

- **push**: `st[++top] = x;` moves top up, then writes.
- **pop**: `return st[top--];` reads, then moves top down.

The old value stays in the array after a pop, but it no longer counts. Only `0..top` is the stack.

### Overflow and underflow

- **Overflow**: push when `top == MAX - 1`. The array has no room.
- **Underflow**: pop when `top == -1`. There is nothing to take.

Always check before you act. These two checks are the most common exam marks on this topic.

### Where stacks show up

Undo/redo, the browser back button, **checking balanced brackets**, evaluating postfix expressions, and the **call stack** that makes recursion work (Chapter 3).

## C++ code: stack-array.cpp

```cpp
#include <iostream>
using namespace std;

const int MAX = 5;

class Stack {
    int st[MAX];
    int top = -1;
public:
    bool isEmpty() const { return top == -1; }
    bool isFull() const { return top == MAX - 1; }
    void push(int x) {
        if (isFull()) { cout << "Overflow! cannot push " << x << "\n"; return; }
        st[++top] = x;
    }
    int pop() {
        if (isEmpty()) { cout << "Underflow!\n"; return -1; }
        return st[top--];
    }
    int peek() const {
        if (isEmpty()) { cout << "Empty!\n"; return -1; }
        return st[top];
    }
};

int main() {
    Stack s;
    for (int i = 1; i <= 6; i++) s.push(i * 10);   // the 6th push overflows
    cout << "peek: " << s.peek() << "\n";
    cout << "pop:  ";
    while (!s.isEmpty()) cout << s.pop() << " ";
    cout << "\n";
    s.pop();                                        // underflow
}
```

Expected output:

```text
Overflow! cannot push 60
peek: 50
pop:  50 40 30 20 10 
Underflow!
```

## Complexity

| Case | Cost |
| --- | --- |
| push | O(1) |
| pop | O(1) |
| peek / isEmpty / isFull | O(1) |
| search for a value | O(n): not a stack operation |

Space: O(MAX), fixed when the array is declared

Every stack operation touches only `st[top]`, so all of them are **O(1)**. The price of an array is a **fixed capacity**.

## Videos

- [Introduction to stack](https://youtu.be/F1F2imiOJfk) (mycodeschool): The stack ADT and LIFO idea with everyday examples, before any code.
- [Array implementation of stacks](https://youtu.be/sFVxsglODoo) (mycodeschool): Builds the array stack in C/C++ with a `top` index, exactly like this page.

## Exam lens

Likely questions:

- Define a stack. Why is it called a LIFO structure?
- Write push and pop for an array stack, including overflow and underflow checks.
- Show the stack after: push 3, push 7, pop, push 2, push 9, pop. What does peek return?
- What does `top = -1` mean? What is the condition for a full stack?
- Give three real applications of a stack.

Common mistakes:

- Writing `st[top++] = x` with `top = -1` (writes to index −1). Use `st[++top] = x`.
- Popping without checking `isEmpty()` (underflow).
- Pushing without checking `isFull()` (writes past the array).
- Thinking `pop` must erase the value. Moving `top` down is enough.

## Quick check

1. Start empty. push 4, push 8, pop, push 1, push 6, pop. What is on top?
   A. 4
   B. 8
   C. 1
   D. 6
   Answer: C. Stack after each step - [4], [4,8], [4], [4,1], [4,1,6], [4,1]. The top is 1.

2. With `int st[MAX]; int top = -1;` the stack is full when…
   A. `top == MAX`
   B. `top == MAX - 1`
   C. `top == 0`
   D. `top == -1`
   Answer: B. The last valid index is MAX − 1.

3. Popping from an empty stack is called…
   A. overflow
   B. underflow
   C. a memory leak
   D. a segmentation fault, always
   Answer: B. Underflow. Overflow is pushing onto a full stack.

4. Which of these naturally uses a stack?
   A. A printer queue
   B. The undo button
   C. A ticket line
   D. Round-robin scheduling
   Answer: B. Undo reverses the most recent action first. The other three are first-come, first-served (queues).

## Practice

**Trace by hand.** MAX = 3. Do push 5, push 2, push 8, push 1, pop, pop, peek, pop, pop. Write the array, `top`, and anything printed after each step.

Solution:

- push 5 → `[5]`, top 0
- push 2 → `[5,2]`, top 1
- push 8 → `[5,2,8]`, top 2 (now full)
- push 1 → **Overflow**, nothing changes
- pop → returns 8, top 1
- pop → returns 2, top 0
- peek → 5
- pop → returns 5, top −1
- pop → **Underflow**


**Implement it.** Use your array stack to reverse a string, and to print a number in binary (push `n % 2`, then pop everything).

Hint: Push every character, then pop them all. The last one in is the first one out, so the order flips.

```cpp
string reverseStr(const string& s) {
    char st[100]; int top = -1;
    for (char c : s) st[++top] = c;
    string r;
    while (top != -1) r += st[top--];
    return r;
}
```


**Problems:**

- [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) (easy). Hint: Push opening brackets. On a closing bracket the top must be its partner. At the end the stack must be empty.
- [Backspace String Compare](https://leetcode.com/problems/backspace-string-compare/) (easy). Hint: Build each string with a stack. `#` means pop (if not empty). Compare the results.
- [Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/) (medium). Hint: Numbers are pushed. An operator pops b, then a, and pushes a op b. Order matters for − and /.

## Mastery checklist

- [ ] I can explain LIFO with a real example.
- [ ] I can write push, pop, peek, isEmpty and isFull for an array stack.
- [ ] I can trace a sequence of stack operations by hand.
- [ ] I always check for overflow before push and underflow before pop.


---

# 5.2 Stacks with a Linked List

> The same stack ADT, but the top is the head of a linked list. No fixed capacity, push and pop stay O(1), and the bracket-matching application.

Chapter: Stacks & Queues · ~35 min · easy
URL: https://dsa.fetehadin.com/learn/stack-list

## Mental model

An array stack is a box with a fixed number of slots. A linked-list stack is a **pile that can grow forever**: each new plate is a new node, linked to the plate under it.

The trick is choosing **which end is the top**. In a singly linked list, the **head** is the only end where both insert and delete are O(1). So:

- **push(x)** = insert at the front: `top = new Node{x, top};`
- **pop()** = delete the front: save `top`, move `top = top->next`, `delete` the old node.

There is **no `isFull()`**. The list only fills up if the whole heap runs out.

### Array or linked list?

| | Array stack | Linked-list stack |
| --- | --- | --- |
| Capacity | fixed (MAX) | grows as needed |
| Memory per item | just the value | value + pointer |
| Speed | O(1), cache-friendly | O(1), one `new`/`delete` each |
| Can overflow? | yes | no (until the heap is exhausted) |

### Application: balanced brackets

Scan the string left to right. Push every **opening** bracket. At a **closing** bracket the stack's top must be its partner; pop it. Fail if the stack is empty or the partner is wrong. At the end the stack **must be empty**.

## C++ code: stack-list.cpp

```cpp
#include <iostream>
#include <string>
using namespace std;

class Stack {
    struct Node { char data; Node* next; };
    Node* top = nullptr;
public:
    bool isEmpty() const { return top == nullptr; }
    void push(char x) { top = new Node{x, top}; }
    char pop() {
        if (isEmpty()) return '\0';
        Node* temp = top;
        char x = temp->data;
        top = top->next;
        delete temp;
        return x;
    }
    char peek() const { return isEmpty() ? '\0' : top->data; }
    ~Stack() { while (!isEmpty()) pop(); }
};

// Classic stack application: are the brackets balanced?
bool balanced(const string& s) {
    Stack st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (c == ')' || c == ']' || c == '}') {
            if (st.isEmpty()) return false;
            char o = st.pop();
            if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{')) return false;
        }
    }
    return st.isEmpty();
}

int main() {
    for (string s : {"{[()()]}", "([)]", "((", "a*(b+c)"})
        cout << s << " -> " << (balanced(s) ? "balanced" : "not balanced") << "\n";
}
```

Expected output:

```text
{[()()]} -> balanced
([)] -> not balanced
(( -> not balanced
a*(b+c) -> balanced
```

## Complexity

| Case | Cost |
| --- | --- |
| push (insert at head) | O(1) |
| pop (delete head) | O(1) |
| peek / isEmpty | O(1) |

Space: O(n), one node (data + pointer) per item

Use the **head** as the top. Pushing and popping at the tail of a singly linked list would be O(n), because you would need the node before the tail.

## Videos

- [Linked List implementation of stacks](https://youtu.be/MuwxQ2IB8lQ) (mycodeschool): Shows why the head (not the tail) must be the top, and writes push/pop in C/C++.
- [Introduction to stack](https://youtu.be/F1F2imiOJfk) (mycodeschool): A recap of the stack ADT if you skipped the array version.

## Exam lens

Likely questions:

- Implement a stack using a singly linked list. Which end is the top and why?
- Compare array and linked-list stacks (capacity, memory, speed).
- Use a stack to check whether `{[()]}` and `([)]` are balanced. Show the stack at each step.
- Why does the linked-list stack have no `isFull()`?

Common mistakes:

- Using the tail as the top, making pop O(n).
- Forgetting `delete` in pop (memory leak).
- Reading `top->data` after deleting the node. Save the value first.
- In bracket matching, forgetting that the stack must be **empty** at the end (`((` is not balanced).

## Quick check

1. In a linked-list stack, push is the same as…
   A. insert at the end
   B. insert at the front (head)
   C. insert at a position
   D. sorting the list
   Answer: B. The head is the top, so push is an O(1) insert at the front.

2. Bracket check on `([)]`: what happens at `)`?
   A. top is `(`, match
   B. top is `[`, mismatch, so not balanced
   C. stack is empty
   D. it is skipped
   Answer: B. After `(` and `[` the top is `[`, which does not match `)`.

3. What is wrong with this pop?

```cpp
Node* temp = top;
delete temp;
int x = top->data;
top = top->next;
```
   A. Nothing
   B. It reads freed memory after delete
   C. It never moves top
   D. It leaks memory
   Answer: B. Read the data and move top first, then delete.

4. Main advantage of the linked-list stack over the array stack?
   A. Faster push
   B. No fixed capacity
   C. Less memory per item
   D. Random access
   Answer: B. It grows as needed. The cost is an extra pointer per item.

## Practice

**Trace by hand.** Run the bracket checker on `{[()()]}` and `a*(b+c))`. Write the stack after each bracket.

Solution:

`{[()()]}`: `{` → `{[` → `{[(` → `{[` → `{[(` → `{[` → `{` → empty. **Balanced.**

`a*(b+c))`: `(` → empty (matched) → second `)` finds an **empty stack**. **Not balanced.**


**Implement it.** Write `string toPostfix(string infix)` for single-letter operands with `+ - * /` and brackets, using your stack.

Hint: Letters go straight to output. `(` is pushed. `)` pops until `(`. An operator pops every operator of higher or equal precedence first, then is pushed. Pop the rest at the end.

**Problems:**

- [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) (easy). Hint: This page's `balanced()` function, almost unchanged.
- [Simplify Path](https://leetcode.com/problems/simplify-path/) (medium). Hint: Split by `/`. Push folder names, pop on `..`, ignore `.` and empty parts. Join what is left.
- [Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/) (medium). Hint: Push a 0 for each `(`. On `)`, pop v; add `max(2*v, 1)` to the new top.

## Mastery checklist

- [ ] I can implement push and pop on a linked list in O(1).
- [ ] I can explain why the head is the top.
- [ ] I can check balanced brackets with a stack and trace it.
- [ ] I can compare array and linked-list stacks.


---

# 5.3 Queues with an Array

> First in, first out. Why a naive array queue makes dequeue O(n), how a front index makes it O(1), and the wasted-slot problem that leads to the circular queue.

Chapter: Stacks & Queues · ~40 min · easy
URL: https://dsa.fetehadin.com/learn/queue-array

## Mental model

A **queue** is a line at the bank. New people join at the **rear**. The person at the **front** is served and leaves. Whoever arrived first is served first: **FIFO**, First In, First Out.

| Operation | Meaning |
| --- | --- |
| `enqueue(x)` | add x at the rear |
| `dequeue()` | remove and return the front item |
| `front()` / `peek()` | look at the front item |
| `isEmpty()` / `isFull()` | the usual checks |

### Attempt 1: keep the front at index 0

Enqueue is easy: `q[++rear] = x`. But on dequeue, the front leaves and **everyone shuffles forward**: `q[0] = q[1]; q[1] = q[2]; …`. That is **n − 1 moves per dequeue, so O(n)**. It is like a line where every customer takes a step each time someone is served.

### Attempt 2: move the front instead

Keep a **`front`** index. Dequeue just returns `q[front++]`. No one moves, so it is **O(1)**. It is like the cashier walking down the line instead of the line walking up.

The catch: `front` and `rear` only ever move right. After a few dequeues, the slots before `front` are empty, but `rear` hits `MAX - 1` and the queue says **"full"**. Those slots are wasted forever.

The fix is to let the indices **wrap around** to 0. That is the **circular queue**, next.

## C++ code: queue-array.cpp

```cpp
#include <iostream>
using namespace std;

const int MAX = 6;

// Naive queue: dequeue shifts everything left -> O(n)
struct NaiveQueue {
    int q[MAX]; int rear = -1; int moves = 0;
    void enqueue(int x) { if (rear == MAX - 1) { cout << "Full\n"; return; } q[++rear] = x; }
    int dequeue() {
        if (rear == -1) { cout << "Empty\n"; return -1; }
        int x = q[0];
        for (int i = 0; i < rear; i++) { q[i] = q[i + 1]; moves++; }
        rear--;
        return x;
    }
};

// Front-index queue: dequeue just moves front -> O(1), but wastes slots
struct FrontQueue {
    int q[MAX]; int front = 0, rear = -1;
    void enqueue(int x) { if (rear == MAX - 1) { cout << "Full (front=" << front << ")\n"; return; } q[++rear] = x; }
    int dequeue() {
        if (front > rear) { cout << "Empty\n"; return -1; }
        return q[front++];
    }
};

int main() {
    NaiveQueue a;
    for (int i = 1; i <= 5; i++) a.enqueue(i);
    cout << "naive: ";
    for (int i = 0; i < 5; i++) cout << a.dequeue() << " ";
    cout << "| element moves: " << a.moves << "\n";

    FrontQueue b;
    for (int i = 1; i <= 6; i++) b.enqueue(i);
    cout << "front-index: " << b.dequeue() << " " << b.dequeue() << "\n";
    b.enqueue(7);   // "Full" although 2 slots at the front are free
}
```

Expected output:

```text
naive: 1 2 3 4 5 | element moves: 10
front-index: 1 2
Full (front=2)
```

## Complexity

| Case | Cost |
| --- | --- |
| enqueue (at rear) | O(1) |
| dequeue, naive (shift left) | O(n) |
| dequeue, with front index | O(1) |
| front / isEmpty | O(1) |

Space: O(MAX)

The front-index version is fast but **cannot reuse** the slots it leaves behind. The **circular queue** fixes that.

## Videos

- [Introduction to Queues](https://youtu.be/XuCbpw6Bj1U) (mycodeschool): The queue ADT, FIFO and real examples, before code.
- [Array implementation of Queue](https://youtu.be/okr-XE8yTO8) (mycodeschool): Builds the array queue, shows the wasted space, and then the circular fix.

## Exam lens

Likely questions:

- Define a queue and its operations. What does FIFO mean?
- Why is dequeue O(n) in a naive array queue? How does a front index make it O(1)?
- Show front, rear and the array after: enqueue 5, enqueue 3, dequeue, enqueue 8.
- Explain why a linear array queue can report "full" when it has free slots.

Common mistakes:

- Confusing front and rear (items enter at the rear, leave at the front).
- Dequeuing without checking for empty.
- With a front index, testing `rear == -1` for empty. The correct test is `front > rear`.
- Forgetting that the naive shift costs n − 1 moves on every dequeue.

## Quick check

1. enqueue 1, enqueue 2, enqueue 3, dequeue, enqueue 4. Which item is at the front?
   A. 1
   B. 2
   C. 3
   D. 4
   Answer: B. 1 left first, so 2 is the oldest item still waiting.

2. Why is naive dequeue O(n)?
   A. It searches for the item
   B. Every remaining item shifts one place left
   C. It sorts the queue
   D. It allocates memory
   Answer: B. Removing q[0] and keeping the front at index 0 means moving everything else.

3. MAX = 4 front-index queue: enqueue ×4, dequeue ×2, enqueue 9. Result?
   A. 9 is stored at index 0
   B. "Full", because rear is already MAX − 1
   C. 9 replaces the front
   D. it crashes
   Answer: B. The rear cannot move past MAX − 1, so slots 0 and 1 are wasted.

4. Which is a queue, not a stack?
   A. Undo
   B. Browser back button
   C. Printer jobs
   D. Function calls
   Answer: C. Print jobs are served in the order they arrive.

## Practice

**Trace by hand.** Naive queue, MAX = 5. enqueue 10, 20, 30, 40; dequeue; dequeue; enqueue 50. Write the array, rear, and the number of element moves after each dequeue.

Solution:

- after 4 enqueues: `[10,20,30,40]`, rear 3
- dequeue → 10, array `[20,30,40]`, rear 2, **3 moves**
- dequeue → 20, array `[30,40]`, rear 1, **2 moves**
- enqueue 50 → `[30,40,50]`, rear 2


**Implement it.** Add `int size()` and `void print()` to the front-index queue, and make `enqueue` reset `front = 0, rear = -1` whenever the queue becomes empty.

Hint: Size is `rear - front + 1`. The reset is a cheap trick that recovers space only when the queue empties completely.

**Problems:**

- [Number of Recent Calls](https://leetcode.com/problems/number-of-recent-calls/) (easy). Hint: Enqueue every ping time; dequeue from the front while it is older than `t - 3000`. Return the size.
- [Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/) (easy). Hint: An `in` stack for push and an `out` stack for pop. Only move items from in to out when out is empty.

## Mastery checklist

- [ ] I can explain FIFO and name the front and rear.
- [ ] I can explain why naive dequeue is O(n) and a front index makes it O(1).
- [ ] I can trace front and rear through a sequence of operations.
- [ ] I can explain the wasted-slot problem.


---

# 5.4 Queues with a Linked List

> Keep two pointers, front and rear. Enqueue at the rear and dequeue at the front, both O(1), with no capacity limit.

Chapter: Stacks & Queues · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/queue-list

## Mental model

Picture a **conga line**. Each dancer holds the shoulders of the dancer in front. New dancers join at the back; the leader leaves from the front.

A linked-list queue keeps **two pointers**:

- **`front`** → the head node. Dequeue removes it: O(1).
- **`rear`** → the last node. Enqueue links a new node after it: `rear->next = n; rear = n;`, O(1).

Why not the other way round? Removing the **tail** of a singly linked list needs the node **before** it, and finding that node means walking the whole list.

### The two edge cases

1. **Enqueue into an empty queue**: there is no `rear->next` to set. Point **both** `front` and `rear` at the new node.
2. **Dequeue the last node**: `front` becomes `nullptr`. Set **`rear = nullptr`** too, or it will dangle.

There is no `isFull()`, and no wasted slots.

## C++ code: queue-list.cpp

```cpp
#include <iostream>
using namespace std;

class Queue {
    struct Node { int data; Node* next; };
    Node* front = nullptr;
    Node* rear = nullptr;
public:
    bool isEmpty() const { return front == nullptr; }
    void enqueue(int x) {
        Node* n = new Node{x, nullptr};
        if (rear == nullptr) { front = rear = n; return; }
        rear->next = n;
        rear = n;
    }
    int dequeue() {
        if (isEmpty()) { cout << "Empty\n"; return -1; }
        Node* temp = front;
        int x = temp->data;
        front = front->next;
        if (front == nullptr) rear = nullptr;   // queue became empty
        delete temp;
        return x;
    }
    int peek() const { return isEmpty() ? -1 : front->data; }
    ~Queue() { while (!isEmpty()) dequeue(); }
};

int main() {
    Queue q;
    q.enqueue(4); q.enqueue(9); q.enqueue(6);
    cout << "front: " << q.peek() << "\n";
    cout << "served: ";
    while (!q.isEmpty()) cout << q.dequeue() << " ";
    cout << "\n";
    q.enqueue(1);                       // works again after becoming empty
    cout << "front after reuse: " << q.peek() << "\n";
}
```

Expected output:

```text
front: 4
served: 4 9 6 
front after reuse: 1
```

## Complexity

| Case | Cost |
| --- | --- |
| enqueue (insert after rear) | O(1) |
| dequeue (delete front) | O(1) |
| peek / isEmpty | O(1) |

Space: O(n)

Both ends are O(1) only because we keep a **rear** pointer. Without it, enqueue would have to walk the whole list.

## Videos

- [Linked List implementation of Queue](https://youtu.be/A5_XdiK4J8A) (mycodeschool): Explains why you need both front and rear, and writes enqueue/dequeue in C/C++.

## Exam lens

Likely questions:

- Implement a queue with a singly linked list. Which end is front, which is rear, and why?
- What must happen to `rear` when the last node is dequeued?
- Compare array and linked-list queues.

Common mistakes:

- Dequeuing from the tail (needs the previous node, so O(n)).
- Forgetting `rear = nullptr` when the queue becomes empty. The next enqueue then writes through a dangling pointer.
- Enqueue into an empty queue without setting **both** front and rear.
- Forgetting `delete` in dequeue.

## Quick check

1. Where does a linked-list queue insert and delete?
   A. insert at front, delete at rear
   B. insert at rear, delete at front
   C. both at front
   D. both at rear
   Answer: B. Deleting the head is O(1); inserting after a known tail is O(1). Deleting the tail would be O(n).

2. The queue has one node. After dequeue, what must be true?
   A. front == rear, both pointing at freed memory
   B. front == nullptr and rear == nullptr
   C. only front == nullptr
   D. rear->next == nullptr
   Answer: B. If rear still points to the deleted node, the next enqueue writes to freed memory.

3. Without a rear pointer, enqueue costs…
   A. O(1)
   B. O(log n)
   C. O(n)
   D. O(n²)
   Answer: C. You would have to walk from front to the last node every time.

## Practice

**Trace by hand.** Draw front, rear and the nodes after: enqueue 4, enqueue 9, dequeue, dequeue, enqueue 1.

Solution:

- enqueue 4 → `4`, front = rear = node(4)
- enqueue 9 → `4 → 9`, rear = node(9)
- dequeue → returns 4, list `9`, front = rear = node(9)
- dequeue → returns 9, list empty, **front = rear = nullptr**
- enqueue 1 → `1`, front = rear = node(1)


**Implement it.** Add `int size()` in O(1) and a `print()` to the queue class.

Hint: Keep a `count` member. Increment it in enqueue, decrement it in dequeue.

**Problems:**

- [Number of Recent Calls](https://leetcode.com/problems/number-of-recent-calls/) (easy). Hint: A queue of timestamps. Drop the old ones from the front.
- [Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/) (easy). Hint: Two stacks. Amortised O(1) per operation.

## Mastery checklist

- [ ] I can implement enqueue and dequeue with front and rear pointers.
- [ ] I can handle the empty-queue and one-node cases.
- [ ] I can explain why front is the head and rear is the tail.


---

# 5.5 Circular Queue

> Let front and rear wrap around with the modulo operator, so freed slots are reused. All operations O(1) on a fixed array.

Chapter: Stacks & Queues · ~40 min · medium
URL: https://dsa.fetehadin.com/learn/circular-queue

## Mental model

Picture a **revolving sushi belt** with N plates. The chef places food on the next empty plate; diners take food from the oldest plate. When the chef reaches the end of the belt, they just carry on at the start. Nothing is wasted.

A circular queue is the same fixed array as before, but we treat it as a **ring**. When an index reaches the last slot, the next step takes it back to **0**:

```cpp
rear  = (rear + 1) % N;   // enqueue
front = (front + 1) % N;  // dequeue
```

So the slots freed by dequeue are reused by later enqueues. Every operation is still **O(1)**.

### Full or empty?

With only `front` and `rear`, a full ring and an empty ring can look the same. Two common fixes:

1. **Keep a `count`** (this page): empty when `count == 0`, full when `count == N`.
2. **Leave one slot unused**: empty when `front == rear`, full when `(rear + 1) % N == front`.

Your instructor may use either. Know both.

### Printing in order

Start at `front` and step `count` times: `k = (k + 1) % N`. Do not just print `q[0..rear]`.

## C++ code: circular-queue.cpp

```cpp
#include <iostream>
using namespace std;

const int N = 5;

class CircularQueue {
    int q[N];
    int front = 0, rear = -1, count = 0;
public:
    bool isFull() const { return count == N; }
    bool isEmpty() const { return count == 0; }
    bool enqueue(int x) {
        if (isFull()) return false;
        rear = (rear + 1) % N;          // wrap around
        q[rear] = x;
        count++;
        return true;
    }
    int dequeue() {
        if (isEmpty()) return -1;
        int x = q[front];
        front = (front + 1) % N;        // wrap around
        count--;
        return x;
    }
    void print() const {
        cout << "[front=" << front << " rear=" << rear << " count=" << count << "] ";
        for (int i = 0, k = front; i < count; i++, k = (k + 1) % N) cout << q[k] << " ";
        cout << "\n";
    }
};

int main() {
    CircularQueue cq;
    for (int i = 1; i <= 5; i++) cq.enqueue(i * 10);
    cq.print();
    cout << "enqueue 60 when full: " << (cq.enqueue(60) ? "ok" : "rejected") << "\n";
    cout << "dequeued " << cq.dequeue() << " and " << cq.dequeue() << "\n";
    cq.enqueue(60);
    cq.enqueue(70);                     // these reuse slots 0 and 1
    cq.print();
}
```

Expected output:

```text
[front=0 rear=4 count=5] 10 20 30 40 50 
enqueue 60 when full: rejected
dequeued 10 and 20
[front=2 rear=1 count=5] 30 40 50 60 70
```

## Complexity

| Case | Cost |
| --- | --- |
| enqueue | O(1) |
| dequeue | O(1) |
| front / isEmpty / isFull | O(1) |

Space: O(N), and every slot is usable

The magic line is `rear = (rear + 1) % N`. When `rear` is N − 1, the next slot is 0.

## Videos

- [Array implementation of Queue](https://youtu.be/okr-XE8yTO8) (mycodeschool): Walks from the linear array queue to the circular version and derives the modulo formula.
- [Introduction to Queues](https://youtu.be/XuCbpw6Bj1U) (mycodeschool): Queue basics refresher.

## Exam lens

Likely questions:

- What problem of the linear array queue does a circular queue solve?
- Write enqueue and dequeue for a circular queue of size N.
- N = 5, front = 3, rear = 1. How many items are in the queue? Which indices?
- Give two ways to tell a full circular queue from an empty one.

Common mistakes:

- Writing `rear++` instead of `rear = (rear + 1) % N`.
- Testing `front == rear` for both empty and full. Without a `count` (or one spare slot) they look the same.
- Printing from `0` to `rear` instead of starting at `front` and wrapping.

## Quick check

1. N = 6, rear = 5. After one enqueue, rear is…
   A. 6
   B. 0
   C. 5
   D. -1
   Answer: B. (5 + 1) % 6 = 0. The rear wraps to the start.

2. N = 5, front = 3, count = 4. Which indices hold items, in queue order?
   A. 3, 4, 5, 6
   B. 3, 4, 0, 1
   C. 0, 1, 2, 3
   D. 1, 2, 3, 4
   Answer: B. Start at 3 and wrap. 3, 4, then 0, 1.

3. Why keep a `count` variable?
   A. To make enqueue faster
   B. To tell full from empty, since front and rear alone can look identical
   C. It is required by C++
   D. To sort the queue
   Answer: B. Another option is to leave one slot always empty, so full means `(rear + 1) % N == front`.

4. Which real system is a circular buffer?
   A. A keyboard input buffer
   B. An undo history
   C. A binary search tree
   D. A hash map
   Answer: A. Keystrokes are written into a fixed ring and read in the same order.

## Practice

**Trace by hand.** N = 4. Start front 0, rear −1, count 0. Do: enq A, enq B, enq C, deq, deq, enq D, enq E, enq F, enq G. Write front, rear, count after each.

Solution:

- enq A → f0 r0 c1 · enq B → f0 r1 c2 · enq C → f0 r2 c3
- deq (A) → f1 r2 c2 · deq (B) → f2 r2 c1
- enq D → f2 r3 c2 · enq E → f2 **r0** c3 · enq F → f2 r1 c4 (full)
- enq G → **rejected**, queue is full


**Implement it.** Rewrite the circular queue **without** a count variable, keeping one slot empty.

Hint: Start with front = rear = 0. Empty: `front == rear`. Full: `(rear + 1) % N == front`. Enqueue writes `q[rear]` then advances rear.

**Problems:**

- [Design Circular Queue](https://leetcode.com/problems/design-circular-queue/) (medium). Hint: This page's class, plus Front() and Rear(). Rear item is at index `rear`.
- [Design Circular Deque](https://leetcode.com/problems/design-circular-deque/) (medium). Hint: Moving front backwards: `front = (front - 1 + k) % k`. Add k before taking % so it never goes negative.

## Mastery checklist

- [ ] I can explain why the circular queue exists.
- [ ] I can write enqueue and dequeue with modulo wrap-around.
- [ ] I can tell full from empty.
- [ ] I can trace front and rear as they wrap.


---

# 5.6 std::stack, std::queue & std::deque

> The standard library versions you will use in real code and on LeetCode, their method names, and the classic traps (pop returns void, empty checks).

Chapter: Stacks & Queues · ~25 min · easy
URL: https://dsa.fetehadin.com/learn/stl-stack-queue

## Mental model

You have built stacks and queues yourself, which is what the exam asks for. In real C++ code (and on LeetCode) you use the **Standard Template Library** versions. Same ideas, ready-made.

| | `std::stack<T>` | `std::queue<T>` | `std::deque<T>` |
| --- | --- | --- | --- |
| add | `push(x)` | `push(x)` (at back) | `push_front(x)`, `push_back(x)` |
| remove | `pop()` | `pop()` (from front) | `pop_front()`, `pop_back()` |
| look | `top()` | `front()`, `back()` | `front()`, `back()`, `d[i]` |
| size | `size()`, `empty()` | `size()`, `empty()` | `size()`, `empty()` |

### Trap 1: pop() returns nothing

`s.pop()` removes the top, but **returns `void`**. Read first, then pop:

```cpp
int x = s.top();
s.pop();
```

### Trap 2: empty containers

Calling `top()`, `front()` or `pop()` on an empty container is **undefined behaviour**. It may crash or print garbage. Check `empty()` first.

### What is a deque?

A **d**ouble-**e**nded **que**ue (say "deck"): add or remove at **both** ends in O(1). A stack uses one end; a queue uses both ends, but each for one job. A deque can do both jobs, so it can act as either.

## C++ code: stl-containers.cpp

```cpp
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

int main() {
    stack<int> s;
    s.push(1); s.push(2); s.push(3);
    cout << "stack top: " << s.top() << ", size: " << s.size() << "\n";
    s.pop();                                  // pop() returns void!
    cout << "after pop, top: " << s.top() << "\n";

    queue<string> q;
    q.push("Abel"); q.push("Hana"); q.push("Liya");
    cout << "queue front: " << q.front() << ", back: " << q.back() << "\n";
    q.pop();
    cout << "after pop, front: " << q.front() << "\n";

    deque<int> d = {3, 6, 9};
    d.push_front(1);
    d.push_back(12);
    cout << "deque: ";
    for (int x : d) cout << x << " ";
    cout << "| d[2] = " << d[2] << "\n";
    d.pop_front(); d.pop_back();
    cout << "after pops: front " << d.front() << ", back " << d.back() << "\n";

    stack<int> e;
    if (!e.empty()) e.pop();                  // always check empty() first
    cout << "empty stack handled safely\n";
}
```

Expected output:

```text
stack top: 3, size: 3
after pop, top: 2
queue front: Abel, back: Liya
after pop, front: Hana
deque: 1 3 6 9 12 | d[2] = 6
after pops: front 3, back 9
empty stack handled safely
```

## Complexity

| Case | Cost |
| --- | --- |
| stack push / pop / top | O(1) |
| queue push / pop / front / back | O(1) |
| deque push/pop at either end | O(1) |
| deque d[i] | O(1) |

Space: O(n)

`std::stack` and `std::queue` are **adapters**: they wrap a `std::deque` by default and only expose the allowed operations.

## Videos

- [Introduction to stack](https://youtu.be/F1F2imiOJfk) (mycodeschool): Recap of the stack idea behind std::stack.
- [Introduction to Queues](https://youtu.be/XuCbpw6Bj1U) (mycodeschool): Recap of the queue idea behind std::queue.

## Exam lens

Likely questions:

- Write C++ that pushes 1, 2, 3 onto a std::stack and prints them in pop order.
- What does `s.pop()` return in std::stack?
- What is a deque? How is it different from a queue?

Common mistakes:

- Writing `int x = s.pop();`. It does not compile; `pop()` returns `void`. Read `top()` first.
- Calling `top()` / `front()` / `pop()` on an empty container (undefined behaviour). Check `empty()`.
- Using `q.top()` on a queue (it is `front()`), or `s.front()` on a stack (it is `top()`).

## Quick check

1. How do you remove and keep the top of a `std::stack<int> s`?
   A. `int x = s.pop();`
   B. `int x = s.top(); s.pop();`
   C. `int x = s.front(); s.pop();`
   D. `int x = s.back();`
   Answer: B. `pop()` returns void, so read `top()` first.

2. What does this print?

```cpp
queue<int> q;
q.push(1); q.push(2); q.push(3);
q.pop();
cout << q.front() << q.back();
```
   A. 13
   B. 23
   C. 12
   D. 31
   Answer: B. 1 leaves; the front is 2 and the back is 3.

3. Which container lets you add and remove at both ends in O(1)?
   A. std::stack
   B. std::queue
   C. std::deque
   D. std::vector
   Answer: C. A vector is O(1) only at the back; inserting at its front is O(n).

## Practice

**Trace by hand.** Predict the output: `deque<int> d = {5}; d.push_front(3); d.push_back(8); d.push_front(1); d.pop_back(); for (int x : d) cout << x << " ";`

Solution:

`{5}` → `{3,5}` → `{3,5,8}` → `{1,3,5,8}` → `{1,3,5}`. Prints `1 3 5`.

**Implement it.** Solve the bracket checker and the "recent calls" counter again, this time using std::stack and std::queue.

Hint: Same logic as your own classes. Only the method names change (`top`, `front`, `empty`).

**Problems:**

- [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) (easy). Hint: `stack<char>`; check `empty()` before `top()`.
- [Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/) (easy). Hint: After pushing x, rotate the queue size − 1 times so x comes to the front.
- [Design Circular Deque](https://leetcode.com/problems/design-circular-deque/) (medium). Hint: Build it on an array with modulo, then compare with std::deque.

## Mastery checklist

- [ ] I know the method names of std::stack, std::queue and std::deque.
- [ ] I always read top()/front() before pop(), and check empty() first.
- [ ] I can explain what a deque is.


---

# 6.1 Binary Trees & Tree Terms

> Root, parent, child, leaf, sibling, depth, height, level, subtree; full, complete and perfect binary trees; and the Node struct with recursive count and height.

Chapter: Trees · ~45 min · easy
URL: https://dsa.fetehadin.com/learn/binary-trees

## Mental model

A **family tree** turned upside down. At the top is one ancestor, the **root**. Each person can have children, those children have children, and so on. Unlike a linked list, a tree **branches**: it is **non-linear** and **hierarchical**.

In a **binary tree**, each node has **at most two** children: a **left** and a **right**.

```cpp
struct Node {
    int data;
    Node* left;
    Node* right;
};
```

### The vocabulary

| Term | Meaning |
| --- | --- |
| **Root** | the top node; it has no parent |
| **Parent / child** | a node and the nodes directly below it |
| **Siblings** | children of the same parent |
| **Leaf** | a node with no children |
| **Internal node** | a node with at least one child |
| **Ancestor / descendant** | anything on the path up / down |
| **Subtree** | a node plus all its descendants |
| **Degree** | number of children of a node |
| **Depth** of a node | edges from the root down to it (root depth = 0) |
| **Level** | all nodes at the same depth |
| **Height** of a node | edges on the longest path down to a leaf |
| **Height of the tree** | height of the root |

### Special shapes

- **Full**: every node has **0 or 2** children.
- **Complete**: every level is full **except possibly the last**, which is filled **from the left**. (Heaps in Chapter 8 are complete trees.)
- **Perfect**: every level is completely full. A perfect tree of height h has **2^(h+1) − 1** nodes.

### Thinking recursively

Every tree is "a root plus a left subtree plus a right subtree". So most tree functions look like this:

```cpp
int f(Node* r) {
    if (r == nullptr) return /* base value */;
    return /* combine */ (r, f(r->left), f(r->right));
}
```

## C++ code: binary-tree.cpp

```cpp
#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* make(int x, Node* l = nullptr, Node* r = nullptr) { return new Node{x, l, r}; }

int countNodes(Node* r) { return r ? 1 + countNodes(r->left) + countNodes(r->right) : 0; }
int countLeaves(Node* r) {
    if (!r) return 0;
    if (!r->left && !r->right) return 1;
    return countLeaves(r->left) + countLeaves(r->right);
}
int height(Node* r) {                         // edges on the longest root-to-leaf path
    if (!r) return -1;                        // empty tree: -1, single node: 0
    return 1 + max(height(r->left), height(r->right));
}
int depthOf(Node* r, int x, int d = 0) {      // -1 if not found
    if (!r) return -1;
    if (r->data == x) return d;
    int L = depthOf(r->left, x, d + 1);
    return L != -1 ? L : depthOf(r->right, x, d + 1);
}
void destroy(Node* r) { if (!r) return; destroy(r->left); destroy(r->right); delete r; }

int main() {
    //          1
    //        /   \
    //       2     3
    //      / \     \
    //     4   5     6
    //        / \
    //       7   8
    Node* root = make(1, make(2, make(4), make(5, make(7), make(8))), make(3, nullptr, make(6)));
    cout << "nodes:  " << countNodes(root) << "\n";
    cout << "leaves: " << countLeaves(root) << "\n";
    cout << "height: " << height(root) << "\n";
    cout << "depth of 7: " << depthOf(root, 7) << "\n";
    destroy(root);
}
```

Expected output:

```text
nodes:  8
leaves: 4
height: 3
depth of 7: 3
```

## Complexity

| Case | Cost |
| --- | --- |
| count nodes / leaves | O(n): visits every node once |
| height | O(n) |
| find a value (no ordering) | O(n) |

Space: O(h) recursion stack, where h is the height

A binary tree with n nodes has height between ⌊log₂ n⌋ (perfectly balanced) and n − 1 (a straight line). A perfect tree of height h has 2^(h+1) − 1 nodes.

## Videos

- [Binary Tree](https://youtu.be/H5JubkIy_p8) (mycodeschool): Every tree term, plus full/complete/perfect binary trees, with clear drawings.

## Exam lens

Likely questions:

- Define: root, leaf, internal node, sibling, ancestor, descendant, depth, height, level, degree.
- Draw a full, a complete and a perfect binary tree. How do they differ?
- What is the maximum number of nodes at level k? In a binary tree of height h?
- Write recursive functions to count the nodes and compute the height of a binary tree.

Common mistakes:

- Mixing up depth (from the root down to a node) and height (from a node down to its deepest leaf).
- Not stating your height convention. Here, a single node has height 0 and an empty tree −1. Some books count nodes instead of edges.
- Thinking "complete" and "full" mean the same thing.
- Forgetting the `nullptr` base case in recursive tree functions.

## Quick check

1. In the tree on this page (1 at the root, 7 and 8 under 5), what is the depth of node 7?
   A. 1
   B. 2
   C. 3
   D. 4
   Answer: C. Path 1 → 2 → 5 → 7 has 3 edges.

2. A node with no children is a…
   A. root
   B. leaf
   C. sibling
   D. internal node
   Answer: B. Leaves sit at the bottom. Nodes with at least one child are internal.

3. Maximum number of nodes in a binary tree of height 3?
   A. 7
   B. 8
   C. 15
   D. 16
   Answer: C. 2^(3+1) − 1 = 15, which is a perfect tree with levels of 1, 2, 4 and 8 nodes.

4. A complete binary tree is one where…
   A. every node has 0 or 2 children
   B. every level is full except possibly the last, filled from the left
   C. all leaves are at the same depth
   D. it is sorted
   Answer: B. "0 or 2 children" is full. "All levels completely full" is perfect.

## Practice

**Trace by hand.** Draw the tree: A has children B, C. B has D, E. C has right child F. E has left child G. List leaves, internal nodes, the height of the tree, the depth of G, and the siblings of D.

Solution:

- Leaves: D, G, F
- Internal: A, B, C, E
- Height: 3 (A → B → E → G)
- Depth of G: 3
- Sibling of D: E


**Implement it.** Write `int countInternal(Node* r)` and `int sumAll(Node* r)`, and `bool isFull(Node* r)` (every node has 0 or 2 children).

Hint: Each one is "handle nullptr, handle this node, recurse on left and right". For isFull: a node with exactly one child returns false.

```cpp
bool isFull(Node* r) {
    if (!r) return true;
    if (!r->left != !r->right) return false;   // exactly one child
    return isFull(r->left) && isFull(r->right);
}
```


**Problems:**

- [Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/) (easy). Hint: Like `height()`, but LeetCode counts nodes, so return 0 for nullptr.
- [Same Tree](https://leetcode.com/problems/same-tree/) (easy). Hint: Both null → true; one null → false; else compare values and recurse on both sides.
- [Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/) (easy). Hint: Swap left and right, then recurse on both.

## Mastery checklist

- [ ] I can define every tree term and point to it on a drawing.
- [ ] I can tell full, complete and perfect binary trees apart.
- [ ] I can write recursive count, leaves and height functions.
- [ ] I can compute the maximum number of nodes for a given height.


---

# 6.2 Binary Search Tree

> Left is smaller, right is bigger. Insert, search, find min and max by walking one path, and why the tree's shape decides whether that is O(log n) or O(n).

Chapter: Trees · ~55 min · medium
URL: https://dsa.fetehadin.com/learn/bst

## Mental model

Think of a **guessing game**: "I'm thinking of a number. Is it 50?" "Lower." "30?" "Higher." Each answer throws away half the possibilities. That is **binary search** (Chapter 3), but stored as a tree so that **inserting** is also fast.

### The BST property

For **every** node:

- everything in its **left** subtree is **smaller**,
- everything in its **right** subtree is **bigger**.

(Duplicates: this site ignores them. Some courses send them right. Say which rule you use.)

### Search, insert, min, max

All four start at the root and walk **down one path**:

- **search(x)**: equal → found; smaller → go left; bigger → go right; hit `nullptr` → not found.
- **insert(x)**: search for x; where you fall off the tree (`nullptr`), put the new node.
- **min**: keep going **left**. **max**: keep going **right**.

```cpp
Node* insert(Node* root, int x) {
    if (!root) return new Node{x, nullptr, nullptr};
    if (x < root->data) root->left = insert(root->left, x);
    else if (x > root->data) root->right = insert(root->right, x);
    return root;
}
```

### The shape matters

Each step goes down one level, so the cost is the **height h**. A bushy, balanced tree has h ≈ log₂ n (a million items in about 20 steps). But inserting **already-sorted** data makes every node go right. The "tree" becomes a linked list, and search is **O(n)**. (Self-balancing trees fix this, but they are beyond this course.)

### A free sort

**Inorder** traversal (left, node, right) visits a BST in **sorted order**. See the Traversals topic.

## C++ code: bst.cpp

```cpp
#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* insert(Node* root, int x) {
    if (root == nullptr) return new Node{x, nullptr, nullptr};
    if (x < root->data) root->left = insert(root->left, x);
    else if (x > root->data) root->right = insert(root->right, x);
    return root;                       // duplicates are ignored
}

bool search(Node* root, int x) {
    if (root == nullptr) return false;
    if (x == root->data) return true;
    if (x < root->data) return search(root->left, x);
    return search(root->right, x);
}

Node* findMin(Node* root) {
    while (root->left != nullptr) root = root->left;
    return root;
}

Node* findMax(Node* root) {
    while (root->right != nullptr) root = root->right;
    return root;
}

void inorder(Node* r) {
    if (!r) return;
    inorder(r->left);
    cout << r->data << " ";
    inorder(r->right);
}

void destroy(Node* r) { if (!r) return; destroy(r->left); destroy(r->right); delete r; }

int main() {
    Node* root = nullptr;
    for (int x : {50, 30, 70, 20, 40, 60, 80, 45})
        root = insert(root, x);
    cout << "inorder (sorted): ";
    inorder(root);
    cout << "\nsearch 45: " << (search(root, 45) ? "found" : "not found") << "\n";
    cout << "search 65: " << (search(root, 65) ? "found" : "not found") << "\n";
    cout << "min: " << findMin(root)->data << ", max: " << findMax(root)->data << "\n";
    destroy(root);
}
```

Expected output:

```text
inorder (sorted): 20 30 40 45 50 60 70 80 
search 45: found
search 65: not found
min: 20, max: 80
```

## Complexity

| Case | Cost |
| --- | --- |
| search / insert, balanced | O(log n) |
| search / insert, skewed | O(n) |
| min / max | O(h) |
| inorder (sorted output) | O(n) |

Space: O(n) for the nodes, O(h) recursion

Every operation walks **one root-to-leaf path**, so the cost is the height **h**. Balanced trees have h ≈ log₂ n; inserting sorted data gives h = n − 1.

## Videos

- [Binary Search Tree](https://youtu.be/pYT9F8_LFTM) (mycodeschool): The BST property and why it gives fast search, compared with arrays and lists.
- [Binary search tree: Implementation in C/C++](https://youtu.be/COZK7NATh4k) (mycodeschool): Writes recursive insert and search in C/C++ step by step.

## Exam lens

Likely questions:

- Insert 50, 30, 70, 20, 40, 60, 80 into an empty BST. Draw it.
- Write recursive `insert` and `search` for a BST.
- How do you find the minimum and maximum of a BST?
- What is the worst-case time of BST search? Give an input that causes it.
- Why does inorder traversal of a BST give sorted output?

Common mistakes:

- Writing `insert(root->left, x);` without assigning the result back to `root->left`.
- Checking only a node's children, not the whole subtree, when asked "is this a BST?".
- Forgetting the `nullptr` check before reading `root->data`.
- Saying BST search is always O(log n). That only holds for a balanced tree.

## Quick check

1. In the BST built from 50, 30, 70, 20, 40, 60, 80, where does 45 go?
   A. left child of 20
   B. right child of 40
   C. left child of 60
   D. right child of 80
   Answer: B. 45 < 50 go left; 45 > 30 go right; 45 > 40 go right of 40.

2. The minimum value in a BST is…
   A. the root
   B. the leftmost node
   C. any leaf
   D. the rightmost node
   Answer: B. Keep going left until there is no left child.

3. Inserting 10, 20, 30, 40, 50 into an empty BST produces…
   A. a balanced tree of height 2
   B. a right-skewed chain of height 4
   C. a complete tree
   D. an error
   Answer: B. Each value is bigger than all before it, so it always goes right. Search becomes O(n).

4. Why must you write `root->left = insert(root->left, x);`?
   A. Style only
   B. When root->left is null, insert returns the new node, and the parent must link to it
   C. For speed
   D. To balance the tree
   Answer: B. Without the assignment, the new node is created but never attached.

## Practice

**Trace by hand.** Insert 40, 20, 60, 10, 30, 50, 70, 25 into an empty BST. Then trace search(25) and search(55), listing every node visited.

Solution:

```text
        40
      /    \
    20      60
   /  \    /  \
  10  30  50  70
     /
    25
```
- search(25): 40 → 20 → 30 → 25 **found** (4 nodes)
- search(55): 40 → 60 → 50 → right of 50 is null, **not found**


**Implement it.** Write iterative `bool search(Node* root, int x)` (no recursion), and `int countInRange(Node* r, int lo, int hi)`.

Hint: Iterative: `while (root) { if (x == root->data) return true; root = x < root->data ? root->left : root->right; }`. Range: skip the left subtree when `r->data < lo`.

**Problems:**

- [Search in a Binary Search Tree](https://leetcode.com/problems/search-in-a-binary-search-tree/) (easy). Hint: This page's search, returning the node instead of a bool.
- [Insert into a Binary Search Tree](https://leetcode.com/problems/insert-into-a-binary-search-tree/) (medium). Hint: Exactly `insert()` from this page. It is rated medium but it is a 5-line function.
- [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/) (medium). Hint: Pass down allowed bounds: `valid(node, lo, hi)`. Left gets `(lo, node->val)`, right gets `(node->val, hi)`. Use long long for the bounds.

## Mastery checklist

- [ ] I can build a BST from a list of numbers by hand.
- [ ] I can write recursive insert and search.
- [ ] I can find the min and max.
- [ ] I can explain why BST operations are O(h) and when h becomes n.


---

# 6.3 BST Delete (3 Cases)

> Deleting a leaf, a node with one child, and a node with two children by copying the inorder successor. The most-asked BST exam question.

Chapter: Trees · ~45 min · hard
URL: https://dsa.fetehadin.com/learn/bst-delete

## Mental model

Removing someone from an **org chart**. If they manage nobody, just remove them. If they manage one person, that person reports to their old boss. If they manage two teams, you need a replacement who fits between both teams. That is the whole idea.

First **search** for the node like normal. Then:

### Case 1: a leaf (no children)

Just remove it. The parent's pointer becomes `nullptr`.

### Case 2: one child

**Bypass** it: the parent points directly to the node's only child. The whole subtree moves up one level and the BST property still holds.

### Case 3: two children

You cannot bypass a node with two children. Instead, find a value that can **sit in its place**: bigger than everything on the left, smaller than everything on the right. That is the **inorder successor**, the **smallest value in the right subtree** (go right once, then left until you can't).

1. Copy the successor's value into the node.
2. Delete the successor from the right subtree. It has no left child, so this is case 1 or 2.

(Using the **inorder predecessor**, the largest on the left, also works. Use whichever your instructor uses.)

### Why the code is short

The recursive version returns the **new root of each subtree**. Cases 1 and 2 merge into one: "if there is no left child, return the right child (which may be `nullptr`)".

## C++ code: bst-delete.cpp

```cpp
#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* insert(Node* root, int x) {
    if (!root) return new Node{x, nullptr, nullptr};
    if (x < root->data) root->left = insert(root->left, x);
    else if (x > root->data) root->right = insert(root->right, x);
    return root;
}

Node* findMin(Node* root) {
    while (root->left != nullptr) root = root->left;
    return root;
}

Node* remove(Node* root, int x) {
    if (root == nullptr) return nullptr;
    if (x < root->data) root->left = remove(root->left, x);
    else if (x > root->data) root->right = remove(root->right, x);
    else {
        if (root->left == nullptr) {           // case 1 (leaf) and case 2 (only right child)
            Node* r = root->right; delete root; return r;
        }
        if (root->right == nullptr) {          // case 2 (only left child)
            Node* l = root->left; delete root; return l;
        }
        Node* s = findMin(root->right);        // case 3: two children
        root->data = s->data;                  // copy the inorder successor
        root->right = remove(root->right, s->data);
    }
    return root;
}

void inorder(Node* r) { if (!r) return; inorder(r->left); cout << r->data << " "; inorder(r->right); }
void destroy(Node* r) { if (!r) return; destroy(r->left); destroy(r->right); delete r; }

int main() {
    Node* root = nullptr;
    for (int x : {50, 30, 70, 20, 40, 60, 80, 65, 35}) root = insert(root, x);
    cout << "start:        "; inorder(root); cout << "\n";
    root = remove(root, 20);  cout << "delete 20 (leaf):       "; inorder(root); cout << "\n";
    root = remove(root, 60);  cout << "delete 60 (one child):  "; inorder(root); cout << "\n";
    root = remove(root, 50);  cout << "delete 50 (two children): "; inorder(root); cout << "\n";
    cout << "new root: " << root->data << "\n";
    destroy(root);
}
```

Expected output:

```text
start:        20 30 35 40 50 60 65 70 80 
delete 20 (leaf):       30 35 40 50 60 65 70 80 
delete 60 (one child):  30 35 40 50 65 70 80 
delete 50 (two children): 30 35 40 65 70 80 
new root: 65
```

## Complexity

| Case | Cost |
| --- | --- |
| delete, balanced | O(log n) |
| delete, skewed | O(n) |

Space: O(h) recursion

Case 3 walks down twice (to find the node, then to its successor), but both walks are on one path, so it is still **O(h)**.

## Videos

- [Delete a node from Binary Search Tree](https://youtu.be/gcULXE7ViZw) (mycodeschool): Draws all three cases, then writes the recursive delete in C/C++. Exactly this page.

## Exam lens

Likely questions:

- Explain the three cases of deleting a node from a BST, with a diagram for each.
- Delete 50 (the root) from the BST of 50, 30, 70, 20, 40, 60, 80. Draw the result.
- What is the inorder successor? Why does replacing with it keep the BST property?
- Write a recursive function to delete a node from a BST.

Common mistakes:

- Case 3: copying the successor value but forgetting to delete the successor node itself (you get a duplicate).
- Case 3: searching for the successor in the left subtree. Successor = **min of the right** subtree.
- Not returning the new subtree root, so the parent still points at the deleted node.
- Forgetting `delete`, or using the node after deleting it.

## Quick check

1. Deleting a node with **one** child means…
   A. delete its whole subtree
   B. connect its parent directly to its child
   C. replace it with the root
   D. it cannot be deleted
   Answer: B. The child (with its subtree) moves up one level.

2. The inorder successor of a node with two children is…
   A. its left child
   B. the max of its left subtree
   C. the min of its right subtree
   D. its parent
   Answer: C. Go right once, then left as far as possible.

3. BST 50, 30, 70, 60, 80, 65. After deleting 50, the root is…
   A. 30
   B. 60
   C. 65
   D. 70
   Answer: B. The min of the right subtree (70 → 60) is 60. Its value is copied to the root, then the old 60 node is removed (65 moves up into its place).

4. Can the inorder successor (in case 3) have a left child?
   A. Yes, always
   B. No; it is the leftmost node of that subtree, so its own removal is case 1 or 2
   C. Only in skewed trees
   D. Only if it is a leaf
   Answer: B. That is why the recursive call to remove it is easy.

## Practice

**Trace by hand.** Build the BST from 50, 30, 70, 20, 40, 60, 80, 35, 45, 65. Delete 20, then 30, then 50. Draw the tree after each.

Solution:

- Delete 20 (leaf): 30's left becomes null.
- Delete 30: now 30 has only a right child (40), so case 2: 50's left becomes 40 (with 35 and 45 below it).
- Delete 50 (two children): successor = min of right = 60. Copy 60 to the root, then delete old 60 (case 2: 70's left becomes 65).

```text
        60
      /    \
    40      70
   /  \    /  \
  35  45  65  80
```


**Implement it.** Rewrite delete using the inorder **predecessor** (max of the left subtree) instead of the successor.

Hint: Swap `findMin(root->right)` for `findMax(root->left)`, and recurse into `root->left` to remove it.

**Problems:**

- [Delete Node in a BST](https://leetcode.com/problems/delete-node-in-a-bst/) (medium). Hint: This page's `remove()` function, using TreeNode.
- [Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) (medium). Hint: Inorder traversal with a counter. Stop when the counter reaches k.

## Mastery checklist

- [ ] I can delete a leaf from a BST.
- [ ] I can delete a node with one child.
- [ ] I can delete a node with two children using the inorder successor.
- [ ] I can write the recursive delete function from memory.


---

# 6.4 Tree Traversals

> Preorder, inorder and postorder (depth-first, recursive) and level order (breadth-first, with a queue). Know them by hand and in code.

Chapter: Trees · ~45 min · medium
URL: https://dsa.fetehadin.com/learn/tree-traversals

## Mental model

You are visiting every room in a building. **Depth-first** means you go down one corridor to the end before trying the next. **Breadth-first** means you visit every room on floor 1 before going to floor 2.

### The three depth-first orders

All three go **left before right**. They differ only in **when you visit the node itself**:

| Order | Rule | Memory trick |
| --- | --- | --- |
| **Preorder** | **N**ode, Left, Right | node comes **pre** (before) |
| **Inorder** | Left, **N**ode, Right | node is **in** the middle |
| **Postorder** | Left, Right, **N**ode | node comes **post** (after) |

```cpp
void inorder(Node* r) {
    if (!r) return;
    inorder(r->left);
    cout << r->data << " ";
    inorder(r->right);
}
```

Move the `cout` line up for preorder, down for postorder.

### What each is good for

- **Preorder**: copying a tree, printing folder structures.
- **Inorder**: a BST in **sorted order**.
- **Postorder**: deleting a tree (children before parent), evaluating expression trees.

### Level order (breadth-first)

Use a **queue**: push the root; repeatedly pop a node, print it, push its left and right children. The queue makes sure nodes come out level by level, left to right. This is BFS, which you will meet again on graphs in Chapter 7.

## C++ code: traversals.cpp

```cpp
#include <iostream>
#include <queue>
using namespace std;

struct Node { int data; Node* left; Node* right; };

Node* insert(Node* r, int x) {
    if (!r) return new Node{x, nullptr, nullptr};
    if (x < r->data) r->left = insert(r->left, x);
    else r->right = insert(r->right, x);
    return r;
}

void preorder(Node* r)  { if (!r) return; cout << r->data << " "; preorder(r->left); preorder(r->right); }
void inorder(Node* r)   { if (!r) return; inorder(r->left); cout << r->data << " "; inorder(r->right); }
void postorder(Node* r) { if (!r) return; postorder(r->left); postorder(r->right); cout << r->data << " "; }

void levelOrder(Node* root) {
    if (root == nullptr) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* cur = q.front(); q.pop();
        cout << cur->data << " ";
        if (cur->left)  q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

void destroy(Node* r) { if (!r) return; destroy(r->left); destroy(r->right); delete r; }   // postorder!

int main() {
    Node* root = nullptr;
    for (int x : {50, 30, 70, 20, 40, 60, 80}) root = insert(root, x);
    cout << "preorder:    "; preorder(root);   cout << "\n";
    cout << "inorder:     "; inorder(root);    cout << "\n";
    cout << "postorder:   "; postorder(root);  cout << "\n";
    cout << "level order: "; levelOrder(root); cout << "\n";
    destroy(root);
}
```

Expected output:

```text
preorder:    50 30 20 40 70 60 80 
inorder:     20 30 40 50 60 70 80 
postorder:   20 40 30 60 80 70 50 
level order: 50 30 70 20 40 60 80
```

## Complexity

| Case | Cost |
| --- | --- |
| pre / in / post order | O(n): every node once |
| level order | O(n) |

Space: O(h) recursion for DFS; O(w) queue for level order (w = widest level)

All four visit every node exactly once. They only differ in **when** a node is printed.

## Videos

- [Binary tree traversal: Preorder, Inorder, Postorder](https://youtu.be/gm8DUJJhmY4) (mycodeschool): Preorder, inorder, postorder with recursion, traced on a real tree.
- [Binary tree: Level Order Traversal](https://youtu.be/86g8jAQug04) (mycodeschool): Level order with a queue. This is the same idea as BFS in Chapter 7.

## Exam lens

Likely questions:

- Give the preorder, inorder, postorder and level-order traversals of a drawn tree.
- Write recursive functions for preorder, inorder and postorder.
- Which traversal of a BST gives sorted output?
- Which data structure does level-order traversal use, and why?
- Given preorder and inorder sequences, rebuild the tree.

Common mistakes:

- Mixing the orders. Remember where the **N**ode goes - **pre** = N L R, **in** = L N R, **post** = L R N.
- Forgetting that "left before right" is the same in all three.
- Using a stack for level order (that gives a DFS order instead).

## Quick check

1. Tree: root 1, left 2 (children 4, 5), right 3. Preorder?
   A. 1 2 4 5 3
   B. 4 2 5 1 3
   C. 4 5 2 3 1
   D. 1 2 3 4 5
   Answer: A. Node, then the whole left subtree (2 4 5), then right (3).

2. Same tree. Postorder?
   A. 1 2 4 5 3
   B. 4 2 5 1 3
   C. 4 5 2 3 1
   D. 1 3 2 5 4
   Answer: C. Left subtree (4 5 2), right subtree (3), then root (1).

3. Same tree. Level order?
   A. 1 2 4 5 3
   B. 1 2 3 4 5
   C. 4 5 2 3 1
   D. 4 2 5 1 3
   Answer: B. Level 0 → 1; level 1 → 2 3; level 2 → 4 5.

4. Which traversal would you use to delete every node of a tree safely?
   A. preorder
   B. inorder
   C. postorder
   D. any of them
   Answer: C. Postorder frees both children before the parent, so you never use a freed pointer.

## Practice

**Trace by hand.** Using the BST from 50, 30, 70, 20, 40, 60, 80, 35: write all four traversals.

Solution:

- Preorder: `50 30 20 40 35 70 60 80`
- Inorder: `20 30 35 40 50 60 70 80` (sorted)
- Postorder: `20 35 40 30 60 80 70 50`
- Level order: `50 30 70 20 40 60 80 35`


**Implement it.** Rebuild a tree from preorder `A B D E C F` and inorder `D B E A F C`, then write its postorder.

Hint: The first preorder item is the root. Find it in the inorder list; everything to its left is the left subtree. Repeat.

Root A. Inorder left `D B E`, right `F C`. Left root B (children D, E). Right root C (left child F).

Postorder: `D E B F C A`


**Problems:**

- [Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) (easy). Hint: Recursive first. Then try it with an explicit stack.
- [Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/) (easy). Hint: Same template, print before recursing.
- [Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/) (medium). Hint: Inside the queue loop, process `q.size()` nodes at a time. That batch is one level.

## Mastery checklist

- [ ] I can write all four traversals of a tree by hand.
- [ ] I can write recursive pre/in/postorder from memory.
- [ ] I can write level order with a queue.
- [ ] I know inorder of a BST is sorted.


---

# 6.5 General Trees (Left-Child, Right-Sibling)

> Trees where a node can have any number of children, stored with only two pointers per node using the left-child/right-sibling representation.

Chapter: Trees · ~30 min · medium
URL: https://dsa.fetehadin.com/learn/general-trees

## Mental model

A **folder on your computer** can hold any number of files and sub-folders. A **company** boss can manage 2 people or 20. These are **general trees** (also called n-ary trees): a node can have **any number** of children.

### The storage problem

A binary tree node has exactly two child pointers. For a general tree, how many should we reserve? Ten? Most would be `nullptr` and wasted, and an eleventh child would not fit.

### The fix: left-child, right-sibling

Give each node just **two** pointers:

```cpp
struct GNode {
    char data;
    GNode* firstChild;    // the leftmost child
    GNode* nextSibling;   // the next brother to the right
};
```

Each parent points only to its **first** child. The children of one parent are chained together like a **linked list** through `nextSibling`.

So "A has children B, C, D" becomes: `A.firstChild = B`, `B.nextSibling = C`, `C.nextSibling = D`.

### It's secretly a binary tree

Rename `firstChild` to `left` and `nextSibling` to `right` and you have a binary tree. That is why this is also called the **binary tree representation of a general tree**. Exams often ask you to draw it: children go **down-left**, siblings go **across to the right**.

## C++ code: general-tree.cpp

```cpp
#include <iostream>
#include <string>
using namespace std;

struct GNode {
    char data;
    GNode* firstChild;    // leftmost child
    GNode* nextSibling;   // next brother to the right
};

GNode* make(char c) { return new GNode{c, nullptr, nullptr}; }

void addChild(GNode* parent, GNode* child) {
    if (!parent->firstChild) { parent->firstChild = child; return; }
    GNode* s = parent->firstChild;
    while (s->nextSibling) s = s->nextSibling;
    s->nextSibling = child;
}

void print(GNode* n, int depth) {          // preorder with indentation
    if (n == nullptr) return;
    cout << string(depth * 2, ' ') << n->data << "\n";
    print(n->firstChild, depth + 1);
    print(n->nextSibling, depth);
}

int countChildren(GNode* n) {
    int c = 0;
    for (GNode* k = n->firstChild; k; k = k->nextSibling) c++;
    return c;
}

void destroy(GNode* n) { if (!n) return; destroy(n->firstChild); destroy(n->nextSibling); delete n; }

int main() {
    GNode *A = make('A'), *B = make('B'), *C = make('C'), *D = make('D');
    addChild(A, B); addChild(A, C); addChild(A, D);
    addChild(B, make('E')); addChild(B, make('F'));
    addChild(D, make('G')); addChild(D, make('H')); addChild(D, make('I'));
    print(A, 0);
    cout << "children of A: " << countChildren(A) << ", of D: " << countChildren(D) << "\n";
    destroy(A);
}
```

Expected output:

```text
A
  B
    E
    F
  C
  D
    G
    H
    I
children of A: 3, of D: 3
```

## Complexity

| Case | Cost |
| --- | --- |
| visit all nodes | O(n) |
| find the k-th child | O(k) |
| count the children of a node | O(degree) |

Space: O(n), exactly two pointers per node

A node with d children needs d pointers in the "array of children" design, but only 2 in left-child/right-sibling, whatever d is.

## Videos

- [Left Child Right Sibling Representation of N-ary Tree](https://youtu.be/O8rDi6a5R3g) (CSE Guru): Builds the left-child/right-sibling form of an n-ary tree step by step.
- [Convert general tree to binary tree](https://youtu.be/TE2-Zs2QTTw) (EZCSE): A 5-minute drill on converting a general tree to a binary tree, the usual exam question.

## Exam lens

Likely questions:

- What is a general tree? Why is a fixed number of child pointers a problem?
- Convert a drawn general tree into its left-child/right-sibling binary tree.
- Write the Node struct for the left-child/right-sibling representation.

Common mistakes:

- Linking a node's second child to the **parent** instead of to the first child's `nextSibling`.
- Drawing siblings as "right child of the parent".
- Forgetting that the root has no siblings.

## Quick check

1. In left-child/right-sibling, the `nextSibling` of node B points to…
   A. B's first child
   B. B's next brother (same parent)
   C. B's parent
   D. the root
   Answer: B. Children of one parent form a linked list through `nextSibling`.

2. A has children B, C, D. In the binary form, C is…
   A. A's left child
   B. B's right pointer (nextSibling)
   C. D's left child
   D. A's right child
   Answer: B. A → first child B; B → next sibling C; C → next sibling D.

3. How many pointers per node does this representation need?
   A. 1
   B. 2
   C. as many as the children
   D. log n
   Answer: B. firstChild and nextSibling.

## Practice

**Trace by hand.** General tree: R has children A, B, C. A has D, E. C has F. Write firstChild and nextSibling for every node.

Solution:

| node | firstChild | nextSibling |
| --- | --- | --- |
| R | A | – |
| A | D | B |
| B | – | C |
| C | F | – |
| D | – | E |
| E | – | – |
| F | – | – |


**Implement it.** Write `int height(GNode* n)` and `int countLeaves(GNode* n)` for the left-child/right-sibling tree.

Hint: Height: 1 + max over children (loop over `firstChild` → `nextSibling`). A leaf is a node with `firstChild == nullptr`.

**Problems:**

- [N-ary Tree Preorder Traversal](https://leetcode.com/problems/n-ary-tree-preorder-traversal/) (easy). Hint: Visit the node, then each child in order.
- [Maximum Depth of N-ary Tree](https://leetcode.com/problems/maximum-depth-of-n-ary-tree/) (easy). Hint: 1 + the max depth over all children.

## Mastery checklist

- [ ] I can explain what a general tree is.
- [ ] I can convert a general tree to left-child/right-sibling form.
- [ ] I can write the GNode struct and traverse it.


---

# 7.1 Graph Terminology

> Vertices and edges, adjacency, degree, paths, cycles, connected graphs, weighted graphs, and how a tree is a special graph.

Chapter: Graphs · ~35 min · easy
URL: https://dsa.fetehadin.com/learn/graph-terms

## Mental model

A **map of cities and roads**. The cities are **vertices** (nodes); the roads are **edges**. Unlike a tree, there is no root and no parent: any city can connect to any other, and you can drive in circles.

A graph is written **G = (V, E)**: a set of vertices and a set of edges.

| Term | Meaning |
| --- | --- |
| **Adjacent** | two vertices joined by an edge |
| **Degree** | number of edges at a vertex |
| **Path** | a sequence of vertices joined by edges; its **length** is the number of edges |
| **Cycle** | a path that returns to its start without reusing an edge |
| **Connected** | there is a path between every pair of vertices |
| **Weighted** | each edge carries a number (distance, cost, time) |
| **Directed** | edges are one-way arrows (next topics) |

### Trees are graphs too

A **tree** is a connected graph with **no cycles**. It always has exactly **V − 1** edges. Add one more edge and a cycle appears.

### The handshake rule

Every edge has two ends, so it adds 1 to the degree of **two** vertices. The sum of all degrees is therefore **2E**. This is a favourite short-answer question.

## C++ code: graph-rep.cpp

```cpp
#include <iostream>
#include <vector>
using namespace std;

const int V = 6;

int main() {
    int edges[][2] = {{0, 1}, {0, 3}, {1, 2}, {1, 4}, {3, 4}, {2, 5}, {4, 5}};

    int matrix[V][V] = {};                    // O(V²) space
    vector<vector<int>> list(V);              // O(V + E) space
    for (auto& e : edges) {
        int u = e[0], v = e[1];
        matrix[u][v] = matrix[v][u] = 1;      // undirected: both directions
        list[u].push_back(v);
        list[v].push_back(u);
    }

    cout << "Adjacency matrix:\n   ";
    for (int j = 0; j < V; j++) cout << j << " ";
    cout << "\n";
    for (int i = 0; i < V; i++) {
        cout << i << ": ";
        for (int j = 0; j < V; j++) cout << matrix[i][j] << " ";
        cout << "\n";
    }

    cout << "Adjacency list:\n";
    for (int i = 0; i < V; i++) {
        cout << i << " ->";
        for (int v : list[i]) cout << " " << v;
        cout << "   (degree " << list[i].size() << ")\n";
    }

    cout << "edge 1-4? " << (matrix[1][4] ? "yes" : "no") << ", edge 0-5? " << (matrix[0][5] ? "yes" : "no") << "\n";
}
```

Expected output:

```text
Adjacency matrix:
   0 1 2 3 4 5 
0: 0 1 0 1 0 0 
1: 1 0 1 0 1 0 
2: 0 1 0 0 0 1 
3: 1 0 0 0 1 0 
4: 0 1 0 1 0 1 
5: 0 0 1 0 1 0 
Adjacency list:
0 -> 1 3   (degree 2)
1 -> 0 2 4   (degree 3)
2 -> 1 5   (degree 2)
3 -> 0 4   (degree 2)
4 -> 1 3 5   (degree 3)
5 -> 2 4   (degree 2)
edge 1-4? yes, edge 0-5? no
```

## Complexity

| Case | Cost |
| --- | --- |
| max edges, undirected | V(V − 1)/2 |
| max edges, directed | V(V − 1) |
| sum of all degrees | 2E (each edge counted at both ends) |

Space: Depends on the representation (next topic)

A graph with E close to V² is **dense**; with E close to V it is **sparse**. Road maps and social networks are sparse.

## Videos

- [Introduction to graphs](https://youtu.be/gXgEDyodOJU) (mycodeschool): Graph vocabulary with real examples (social networks, maps), and how graphs differ from trees.

## Exam lens

Likely questions:

- Define: vertex, edge, adjacent, degree, path, cycle, connected graph, weighted graph.
- What is the maximum number of edges in an undirected graph with V vertices?
- Prove that the sum of the degrees of all vertices is 2E.
- How is a tree different from a general graph?

Common mistakes:

- Counting path length in vertices instead of edges.
- Saying every graph is connected.
- Forgetting that a cycle must not reuse an edge.

## Quick check

1. A graph has degrees 2, 3, 2, 2, 3, 2. How many edges?
   A. 6
   B. 7
   C. 14
   D. 12
   Answer: B. Sum of degrees = 14 = 2E, so E = 7.

2. A connected graph with V vertices and no cycles has how many edges?
   A. V
   B. V − 1
   C. V + 1
   D. V²
   Answer: B. That is a tree.

3. Maximum edges in a simple undirected graph with 5 vertices?
   A. 5
   B. 10
   C. 20
   D. 25
   Answer: B. 5 · 4 / 2 = 10.

## Practice

**Trace by hand.** Graph: V = {A, B, C, D, E}, E = {AB, AC, BC, CD}. Give the degree of each vertex, one cycle, a path from A to D, and say whether it is connected.

Solution:

- Degrees: A 2, B 2, C 3, D 1, E 0 (sum 8 = 2 × 4 edges)
- Cycle: A → B → C → A
- Path A → D: A → C → D (length 2)
- **Not connected**: E has no edges.


**Implement it.** Read V, E and E pairs of vertices. Print the degree of every vertex and say whether the sum equals 2E.

Hint: An `int deg[V]` array; each edge (u, v) does `deg[u]++; deg[v]++;`.

**Problems:**

- [Find Center of Star Graph](https://leetcode.com/problems/find-center-of-star-graph/) (easy). Hint: The center is in every edge. Compare the first two edges.
- [Find the Town Judge](https://leetcode.com/problems/find-the-town-judge/) (easy). Hint: Count in-degree and out-degree. The judge has in = n − 1 and out = 0.

## Mastery checklist

- [ ] I can define every graph term and point to it on a drawing.
- [ ] I know the sum of degrees equals 2E.
- [ ] I can explain how a tree is a special graph.


---

# 7.2 Adjacency Matrix & Adjacency List

> Two ways to store a graph in memory, what each costs, and when to choose which.

Chapter: Graphs · ~45 min · medium
URL: https://dsa.fetehadin.com/learn/graph-representation

## Mental model

Two ways to write down who knows whom in a class.

**A big table** (adjacency matrix): rows and columns are students, and you put a 1 where two students know each other. Checking any pair is instant, but a class of 1,000 needs a million cells, mostly zeros.

**A contact list per student** (adjacency list): each student keeps a list of only the people they know. It is compact, and listing a student's friends is fast. But checking "does A know B?" means scanning A's list.

### Adjacency matrix

```cpp
int m[V][V] = {};
m[u][v] = m[v][u] = 1;   // undirected edge u–v
```

- Space **O(V²)**, whatever the number of edges.
- Edge check **O(1)**.
- Symmetric for undirected graphs. For weighted graphs, store the weight instead of 1.

### Adjacency list

```cpp
vector<vector<int>> adj(V);
adj[u].push_back(v);
adj[v].push_back(u);     // undirected: both ends
```

- Space **O(V + E)**.
- Looping over neighbours costs only **deg(u)**.

### Which one?

- **Sparse** graphs (most real ones): **list**.
- **Dense** graphs, or when you need many fast "is there an edge?" checks: **matrix**.

## C++ code: graph-rep.cpp

```cpp
#include <iostream>
#include <vector>
using namespace std;

const int V = 6;

int main() {
    int edges[][2] = {{0, 1}, {0, 3}, {1, 2}, {1, 4}, {3, 4}, {2, 5}, {4, 5}};

    int matrix[V][V] = {};                    // O(V²) space
    vector<vector<int>> list(V);              // O(V + E) space
    for (auto& e : edges) {
        int u = e[0], v = e[1];
        matrix[u][v] = matrix[v][u] = 1;      // undirected: both directions
        list[u].push_back(v);
        list[v].push_back(u);
    }

    cout << "Adjacency matrix:\n   ";
    for (int j = 0; j < V; j++) cout << j << " ";
    cout << "\n";
    for (int i = 0; i < V; i++) {
        cout << i << ": ";
        for (int j = 0; j < V; j++) cout << matrix[i][j] << " ";
        cout << "\n";
    }

    cout << "Adjacency list:\n";
    for (int i = 0; i < V; i++) {
        cout << i << " ->";
        for (int v : list[i]) cout << " " << v;
        cout << "   (degree " << list[i].size() << ")\n";
    }

    cout << "edge 1-4? " << (matrix[1][4] ? "yes" : "no") << ", edge 0-5? " << (matrix[0][5] ? "yes" : "no") << "\n";
}
```

Expected output:

```text
Adjacency matrix:
   0 1 2 3 4 5 
0: 0 1 0 1 0 0 
1: 1 0 1 0 1 0 
2: 0 1 0 0 0 1 
3: 1 0 0 0 1 0 
4: 0 1 0 1 0 1 
5: 0 0 1 0 1 0 
Adjacency list:
0 -> 1 3   (degree 2)
1 -> 0 2 4   (degree 3)
2 -> 1 5   (degree 2)
3 -> 0 4   (degree 2)
4 -> 1 3 5   (degree 3)
5 -> 2 4   (degree 2)
edge 1-4? yes, edge 0-5? no
```

## Complexity

| Case | Cost |
| --- | --- |
| space | matrix O(V²) · list O(V + E) |
| is there an edge u–v? | matrix O(1) · list O(deg u) |
| visit all neighbours of u | matrix O(V) · list O(deg u) |
| add an edge | matrix O(1) · list O(1) |


For BFS/DFS the list gives **O(V + E)** and the matrix gives **O(V²)**.

## Videos

- [Graph Representation: Adjacency Matrix](https://youtu.be/9C2cpQZVRBA) (mycodeschool): The adjacency matrix, its cost, and when it wastes space.
- [Graph Representation: Adjacency List](https://youtu.be/k1wraWzqtvQ) (mycodeschool): The adjacency list and a clear side-by-side cost comparison.

## Exam lens

Likely questions:

- Draw the adjacency matrix and adjacency list of a given graph.
- Compare the space and time costs of the two representations.
- Which representation suits a sparse graph? A dense one? Why?
- How do you store a weighted graph in each representation?

Common mistakes:

- Setting only `m[u][v]` for an undirected edge. Set `m[v][u]` too.
- Saying the list is always better. Edge lookup is O(1) only in the matrix.
- Forgetting that an undirected edge appears **twice** in the list.

## Quick check

1. An undirected graph has V = 1000, E = 3000. Which representation uses less memory?
   A. matrix
   B. list
   C. same
   D. depends on the weights
   Answer: B. Matrix = 1,000,000 cells. List ≈ V + 2E = 7,000 entries.

2. The adjacency matrix of an undirected graph is always…
   A. diagonal
   B. symmetric
   C. all ones
   D. upper triangular
   Answer: B. m[u][v] = m[v][u] for every edge.

3. Checking "is there an edge between u and v?" is O(1) in…
   A. the matrix
   B. the list
   C. both
   D. neither
   Answer: A. The list must scan u's neighbours.

4. How many entries does the adjacency list of an undirected graph hold in total?
   A. E
   B. 2E
   C. V
   D. V²
   Answer: B. Each edge is stored once at each end.

## Practice

**Trace by hand.** Vertices 0–3, undirected edges 0–1, 0–2, 1–2, 2–3. Write the adjacency matrix and adjacency list.

Solution:

```text
   0 1 2 3
0: 0 1 1 0
1: 1 0 1 0
2: 1 1 0 1
3: 0 0 1 0
```
List: `0 → 1 2` · `1 → 0 2` · `2 → 0 1 3` · `3 → 2`


**Implement it.** Store a **weighted** undirected graph both ways. Use `vector<vector<pair<int,int>>>` for the list (neighbour, weight) and 0 for "no edge" in the matrix.

Hint: `adj[u].push_back({v, w}); adj[v].push_back({u, w}); m[u][v] = m[v][u] = w;`

**Problems:**

- [Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/) (easy). Hint: Build an adjacency list from the edge array, then BFS or DFS from source.
- [Find Center of Star Graph](https://leetcode.com/problems/find-center-of-star-graph/) (easy). Hint: Count degrees with a list. The center has degree n − 1.

## Mastery checklist

- [ ] I can draw both representations of a graph.
- [ ] I can state the space and time costs of each.
- [ ] I can choose the right one for a sparse or dense graph.
- [ ] I can build an adjacency list in C++ with vector<vector<int>>.


---

# 7.3 Directed Graphs

> One-way edges, in-degree and out-degree, directed paths and cycles, and how the matrix and list change.

Chapter: Graphs · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/directed-graphs

## Mental model

On Facebook, friendship goes **both ways**. On Instagram, you can **follow** someone who does not follow you back. The first is an undirected graph; the second is a **directed graph** (digraph). Every edge is an **arrow** from u to v.

### What changes

- **Degree splits in two.** **Out-degree** = arrows leaving a vertex; **in-degree** = arrows arriving.
- **Paths follow the arrows.** 0 → 1 does not let you go from 1 to 0.
- **Storage**: a directed edge u → v is stored **once**:

```cpp
m[u][v] = 1;           // not m[v][u]
adj[u].push_back(v);   // not adj[v]
```

So the matrix is usually **not symmetric**. Its row sum is the out-degree, and its column sum is the in-degree.

### DAGs

A **D**irected **A**cyclic **G**raph has no directed cycles. Course prerequisites, task schedules and build systems are DAGs: you can always find an order that respects every arrow.

## C++ code: directed-graph.cpp

```cpp
#include <iostream>
#include <vector>
using namespace std;

const int V = 6;

int main() {
    // one-way arrows u -> v
    int edges[][2] = {{0, 1}, {1, 2}, {2, 5}, {3, 0}, {4, 3}, {1, 4}, {5, 4}};

    int matrix[V][V] = {};
    vector<vector<int>> out(V);
    for (auto& e : edges) {
        matrix[e[0]][e[1]] = 1;                // only one direction
        out[e[0]].push_back(e[1]);
    }

    for (int u = 0; u < V; u++) {
        int in = 0;
        for (int w = 0; w < V; w++) in += matrix[w][u];   // column sum
        cout << u << ": out ->";
        for (int v : out[u]) cout << " " << v;
        cout << " | in-degree " << in << ", out-degree " << out[u].size() << "\n";
    }

    bool symmetric = true;
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            if (matrix[i][j] != matrix[j][i]) symmetric = false;
    cout << "matrix symmetric? " << (symmetric ? "yes" : "no") << "\n";
    cout << "0->1? " << matrix[0][1] << "  1->0? " << matrix[1][0] << "\n";
}
```

Expected output:

```text
0: out -> 1 | in-degree 1, out-degree 1
1: out -> 2 4 | in-degree 1, out-degree 2
2: out -> 5 | in-degree 1, out-degree 1
3: out -> 0 | in-degree 1, out-degree 1
4: out -> 3 | in-degree 2, out-degree 1
5: out -> 4 | in-degree 1, out-degree 1
matrix symmetric? no
0->1? 1  1->0? 0
```

## Complexity

| Case | Cost |
| --- | --- |
| out-degree of u | list O(1) (size of adj[u]) · matrix O(V) (row sum) |
| in-degree of u | list O(V + E) · matrix O(V) (column sum) |
| space | matrix O(V²) · list O(V + E) |


The sum of all in-degrees equals the sum of all out-degrees, and both equal **E**.

## Videos

- [Graph Types: Directed and Undirected](https://youtu.be/amaH38_mXK4) (TutorialsPoint): A 4-minute side-by-side of directed and undirected graphs.
- [Intro to Directed Graphs](https://youtu.be/mXoiHgH4mEE) (Wrath of Math): Digraph vocabulary (in/out-degree, directed paths and cycles) with clear drawings.

## Exam lens

Likely questions:

- What is a directed graph? Give two real examples.
- Find the in-degree and out-degree of every vertex in a drawn digraph.
- Draw the adjacency matrix of a digraph. Why is it not symmetric?
- What is a DAG?

Common mistakes:

- Adding both `m[u][v]` and `m[v][u]` for a directed edge.
- Following an arrow backwards when tracing a path.
- Mixing up in-degree (arrows coming in) and out-degree (arrows going out).

## Quick check

1. In a digraph, the sum of all out-degrees equals…
   A. V
   B. E
   C. 2E
   D. V²
   Answer: B. Each arrow leaves exactly one vertex.

2. Edges 0→1, 1→2, 2→0, 2→3. In-degree of 0?
   A. 0
   B. 1
   C. 2
   D. 3
   Answer: B. Only 2 → 0 points into 0.

3. Which is naturally a directed graph?
   A. Facebook friendships
   B. Twitter/X follows
   C. Two-way roads
   D. A handshake network
   Answer: B. You can follow someone who does not follow you back.

## Practice

**Trace by hand.** Digraph with edges A→B, A→C, B→C, C→A, C→D. Give in- and out-degree for each vertex, the adjacency list, and one directed cycle.

Solution:

| vertex | in | out | list |
| --- | --- | --- | --- |
| A | 1 | 2 | B, C |
| B | 1 | 1 | C |
| C | 2 | 2 | A, D |
| D | 1 | 0 | – |

Cycle: A → B → C → A (or A → C → A). Totals: in 5 = out 5 = E.


**Implement it.** Given an adjacency list of a digraph, build its **reverse** (every arrow flipped) and compute all in-degrees in O(V + E).

Hint: For every u and every v in adj[u]: `rev[v].push_back(u); in[v]++;`

**Problems:**

- [Find the Town Judge](https://leetcode.com/problems/find-the-town-judge/) (easy). Hint: Trust is a directed edge. The judge has in-degree n − 1 and out-degree 0.
- [Course Schedule](https://leetcode.com/problems/course-schedule/) (medium). Hint: Courses and prerequisites form a digraph. You can finish all courses iff there is no directed cycle.

## Mastery checklist

- [ ] I can explain directed vs undirected edges with examples.
- [ ] I can compute in-degree and out-degree.
- [ ] I can draw the matrix and list of a digraph.


---

# 7.4 BFS & DFS

> Breadth-first search with a queue, depth-first search with recursion or a stack, the visited array, and O(V + E).

Chapter: Graphs · ~60 min · medium
URL: https://dsa.fetehadin.com/learn/bfs-dfs

## Mental model

You drop a stone in a pond. The ripples spread out **ring by ring**: everything 1 step away, then 2 steps, then 3. That is **Breadth-First Search**.

Now you explore a maze. You follow one corridor **as far as it goes**, and only when you hit a dead end do you **back up** to try the last turn you skipped. That is **Depth-First Search**.

### BFS: use a queue

1. Mark the start visited and enqueue it.
2. While the queue is not empty: dequeue u, process it, and enqueue every **unvisited** neighbour (marking it visited **now**).

The queue makes vertices come out in order of distance. So BFS gives the **shortest path in edges**.

### DFS: use a stack (or recursion)

```cpp
void dfs(int u) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u])
        if (!visited[v]) dfs(v);
}
```

The recursion **is** a stack: the call stack remembers where to back up to. An iterative version uses `std::stack`.

### Why "visited"?

Trees have no cycles, so tree traversals never revisit a node. Graphs can have cycles: 0 → 1 → 4 → 3 → 0 → … would loop forever. The **visited** array makes sure every vertex is processed **once**.

### Cost

Each vertex is enqueued (or called) once, and each edge is checked once from each end: **O(V + E)** with an adjacency list. With a matrix, finding a vertex's neighbours scans a whole row, so **O(V²)**.

> Tree level-order traversal (Chapter 6) is just BFS on a tree.

## C++ code: bfs-dfs.cpp

```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

void bfs(int s, const vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);
    queue<int> q;
    visited[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        for (int v : adj[u])
            if (!visited[v]) {
                visited[v] = true;            // mark when enqueued, not when printed
                q.push(v);
            }
    }
}

void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u])
        if (!visited[v]) dfs(v, adj, visited);
}

void dfsIterative(int s, const vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);
    stack<int> st;
    st.push(s);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        cout << u << " ";
        for (int i = adj[u].size() - 1; i >= 0; i--)   // push in reverse so the smallest pops first
            if (!visited[adj[u][i]]) st.push(adj[u][i]);
    }
}

int main() {
    vector<vector<int>> adj = {
        {1, 3},        // 0
        {0, 2, 4},     // 1
        {1, 5},        // 2
        {0, 4},        // 3
        {1, 3, 5},     // 4
        {2, 4},        // 5
    };
    cout << "BFS from 0: "; bfs(0, adj); cout << "\n";
    vector<bool> vis(adj.size(), false);
    cout << "DFS from 0: "; dfs(0, adj, vis); cout << "\n";
    cout << "DFS (stack): "; dfsIterative(0, adj); cout << "\n";
}
```

Expected output:

```text
BFS from 0: 0 1 3 2 4 5 
DFS from 0: 0 1 2 5 4 3 
DFS (stack): 0 1 2 5 4 3
```

## Complexity

| Case | Cost |
| --- | --- |
| BFS / DFS with adjacency list | O(V + E) |
| BFS / DFS with adjacency matrix | O(V²) |

Space: O(V) for visited plus the queue or stack

BFS finds the path with the **fewest edges** in an unweighted graph. DFS does not.

## Videos

- [Graph Traversals: BFS & DFS](https://youtu.be/pcKY4hjDrxk) (Abdul Bari): Abdul Bari traces BFS and DFS by hand. The exam format exactly.
- [Binary tree: Level Order Traversal](https://youtu.be/86g8jAQug04) (mycodeschool): Level-order tree traversal, which is BFS on a tree. A good warm-up.

## Exam lens

Likely questions:

- Give the BFS and DFS order of a drawn graph starting from a given vertex.
- Which data structure does BFS use? DFS?
- Write BFS in C++ using an adjacency list.
- Why do we need a visited array in a graph but not in a tree?
- What is the time complexity of BFS/DFS with a list? With a matrix?

Common mistakes:

- No visited array, so the search loops forever around a cycle.
- In BFS, marking a vertex visited when it is **dequeued** instead of **enqueued** (it can be enqueued twice).
- Visiting neighbours in a different order from the one the question uses (usually ascending).
- Forgetting disconnected graphs. Loop over all vertices and start a new search from each unvisited one.

## Quick check

1. Graph on this page, from 0 (neighbours in ascending order). BFS order?
   A. 0 1 2 5 4 3
   B. 0 1 3 2 4 5
   C. 0 3 4 1 2 5
   D. 0 1 2 3 4 5
   Answer: B. Wave 1: 1, 3. Wave 2: 2, 4. Wave 3: 5.

2. Same graph. DFS order?
   A. 0 1 2 5 4 3
   B. 0 1 3 2 4 5
   C. 0 3 4 5 2 1
   D. 0 1 4 3 5 2
   Answer: A. 0 → 1 → 2 → 5 → 4 → 3, going as deep as possible each time.

3. BFS uses a…
   A. stack
   B. queue
   C. heap
   D. hash table
   Answer: B. First discovered, first explored, so FIFO.

4. Shortest path (fewest edges) in an unweighted graph?
   A. DFS
   B. BFS
   C. both always
   D. neither
   Answer: B. BFS reaches all vertices at distance 1 before any at distance 2.

## Practice

**Trace by hand.** Edges A–B, A–C, B–D, C–D, D–E, C–F. Neighbours in alphabetical order. Write the BFS from A (with the queue after each dequeue) and the DFS from A.

Solution:

BFS: dequeue A → queue B C · B → C D · C → D F · D → F E · F → E · E → empty.
**BFS: A B C D F E**

DFS: A → B → D → C → F (back) → E. **DFS: A B D C F E**


**Implement it.** Use BFS to compute the distance (number of edges) from a source to every vertex, and count connected components with DFS.

Hint: Distance: `dist[v] = dist[u] + 1` when v is first enqueued. Components: loop over all vertices, and each time you find an unvisited one, run DFS and add 1.

**Problems:**

- [Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/) (easy). Hint: BFS or DFS from source; check whether destination is visited.
- [Flood Fill](https://leetcode.com/problems/flood-fill/) (easy). Hint: The grid is a graph where each cell has up to 4 neighbours. DFS from the start cell.
- [Number of Islands](https://leetcode.com/problems/number-of-islands/) (medium). Hint: Count how many times you must start a new DFS. That is connected components on a grid.

## Mastery checklist

- [ ] I can trace BFS and DFS by hand on a graph.
- [ ] I can write BFS with a queue and DFS with recursion.
- [ ] I can explain why graphs need a visited array.
- [ ] I know both are O(V + E) with an adjacency list.


---

# 8.1 Shell Sort

> Insertion sort on items a gap apart, with the gap shrinking to 1. Far-away items move in big jumps, so the final insertion sort has little work left.

Chapter: Advanced Sorting & Searching · ~35 min · medium
URL: https://dsa.fetehadin.com/learn/shell-sort

## Mental model

Insertion sort is slow when a small item sits **far to the right**: it creeps left **one step at a time**. Shell sort fixes this by letting items **jump**.

Picture lining up a class by height. First, compare students **4 places apart** and swap if needed. Then 2 apart. Finally, neighbours. After the big jumps, everyone is **nearly** in place, and the last neighbour pass (plain insertion sort) has almost nothing to do.

### The algorithm

```text
for gap = n/2, n/4, ..., 1:
    insertion sort, but compare a[j] with a[j - gap]
```

With gap = 4, the array is really four separate small lists (indices 0, 4 · 1, 5 · 2, 6 · 3, 7), and each one is insertion-sorted.

### Why it works

Insertion sort is **O(n)** on nearly sorted data. The large gaps make the data nearly sorted cheaply, so the final gap-1 pass is fast.

Shell sort is **not stable**: a jump can carry an item past an equal one.

## C++ code: shell-sort.cpp

```cpp
#include <iostream>
using namespace std;

void shellSort(int a[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {        // insertion sort on items gap apart
            int temp = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > temp) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = temp;
        }
        cout << "after gap " << gap << ": ";
        for (int k = 0; k < n; k++) cout << a[k] << " ";
        cout << "\n";
    }
}

int main() {
    int a[] = {35, 33, 42, 10, 14, 19, 27, 44};
    int n = sizeof(a) / sizeof(a[0]);
    shellSort(a, n);
}
```

Expected output:

```text
after gap 4: 14 19 27 10 35 33 42 44 
after gap 2: 14 10 27 19 35 33 42 44 
after gap 1: 10 14 19 27 33 35 42 44
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case (sorted) | O(n log n) |
| Average case | depends on the gaps; about O(n^1.5) for n/2, n/4, … |
| Worst case (gaps n/2, n/4, …) | O(n²) |

Space: O(1)
Stable: no
In-place: yes

Better gap sequences (Knuth's 1, 4, 13, 40, …) bring the worst case down to about O(n^1.5). The exam usually uses n/2, n/4, …, 1.

## Videos

- [Sorts 5: Shell Sort](https://youtu.be/ddeLSDsYVp8) (Rob Edwards): Short, clear explanation of why gaps help, with a hand trace.
- [Shell Sort: full explanation with code](https://youtu.be/9crZRd8GPWM) (Jenny's Lectures CS IT): A long, slow walkthrough with code, in the style of a class lecture.

## Exam lens

Likely questions:

- Trace shell sort with gaps 4, 2, 1 on `35, 33, 42, 10, 14, 19, 27, 44`.
- How is shell sort related to insertion sort? Why is it faster?
- Is shell sort stable? Give a reason.

Common mistakes:

- Comparing neighbours (gap 1) in every pass, which is just insertion sort.
- Forgetting that the last pass must use gap = 1, or the array may not be sorted.
- Claiming it is stable. Jumps over a gap can reorder equal keys.

## Quick check

1. With n = 8 and gaps n/2, n/4, …, which gaps are used?
   A. 8, 4, 2, 1
   B. 4, 2, 1
   C. 3, 2, 1
   D. 7, 3, 1
   Answer: B. 8/2 = 4, then 2, then 1.

2. The final pass of shell sort is…
   A. a selection sort
   B. a plain insertion sort (gap 1)
   C. a merge
   D. skipped if sorted
   Answer: B. Gap 1 is ordinary insertion sort, but on an almost-sorted array, so it is fast.

3. Is shell sort stable?
   A. Yes
   B. No
   Answer: B. Equal items in different gap groups can swap order.

## Practice

**Trace by hand.** Trace shell sort (gaps 4, 2, 1) on `35, 33, 42, 10, 14, 19, 27, 44`. Write the array after each gap.

Solution:

- gap 4: `14 19 27 10 35 33 42 44`
- gap 2: `14 10 27 19 35 33 42 44`
- gap 1: `10 14 19 27 33 35 42 44`


**Implement it.** Change the code to use Knuth's gaps (1, 4, 13, 40, …) and count comparisons for both versions on a reversed array of 100 items.

Hint: Start with `gap = 1; while (gap < n / 3) gap = 3 * gap + 1;` and shrink with `gap /= 3`.

**Problems:**

- [Sort an Array](https://leetcode.com/problems/sort-an-array/) (medium). Hint: Shell sort usually passes where bubble and insertion sort time out.
- [Sort Colors](https://leetcode.com/problems/sort-colors/) (medium). Hint: Any sort works. Then try a one-pass solution with three pointers.

## Mastery checklist

- [ ] I can explain shell sort as gapped insertion sort.
- [ ] I can trace the gap passes by hand.
- [ ] I know it is in-place and not stable.


---

# 8.2 Quick Sort

> Pick a pivot, partition so smaller items go left and bigger items go right, then sort each side recursively. Average O(n log n), worst O(n²).

Chapter: Advanced Sorting & Searching · ~55 min · hard
URL: https://dsa.fetehadin.com/learn/quick-sort

## Mental model

A teacher wants to sort exam papers. She picks one paper, say **score 70**, as the **pivot**. Everyone below 70 goes on the left pile, everyone above on the right pile, and 70 sits in the middle, **already in its final place**. Then she does the same with each pile. Piles of one paper are done.

That is **divide and conquer**: split the problem, solve the parts, and (here) there is nothing to combine.

### Partition (Lomuto)

Use the last item as the pivot. Keep `i` as the end of the "smaller than pivot" zone.

```cpp
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
    if (a[j] < pivot) swap(a[++i], a[j]);
swap(a[i + 1], a[hi]);   // pivot into place
return i + 1;
```

Then sort `lo .. p − 1` and `p + 1 .. hi`.

### Best vs worst

- **Good pivot** (near the median): each level halves the array, so log n levels of O(n) work gives **O(n log n)**.
- **Bad pivot** (the smallest or largest every time, e.g. sorted input with a last-item pivot): each level removes one item, so n levels gives **O(n²)**.

A random pivot makes the bad case very unlikely.

## C++ code: quick-sort.cpp

```cpp
#include <iostream>
using namespace std;

int partition(int a[], int lo, int hi) {      // Lomuto: last item is the pivot
    int pivot = a[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[hi]);
    return i + 1;
}

void print(int a[], int n) { for (int k = 0; k < n; k++) cout << a[k] << " "; cout << "\n"; }

void quickSort(int a[], int lo, int hi, int n) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        cout << "pivot " << a[p] << " -> index " << p << ": ";
        print(a, n);
        quickSort(a, lo, p - 1, n);
        quickSort(a, p + 1, hi, n);
    }
}

int main() {
    int a[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(a) / sizeof(a[0]);
    quickSort(a, 0, n - 1, n);
    cout << "sorted: "; print(a, n);
}
```

Expected output:

```text
pivot 70 -> index 4: 10 30 40 50 70 90 80 
pivot 50 -> index 3: 10 30 40 50 70 90 80 
pivot 40 -> index 2: 10 30 40 50 70 90 80 
pivot 30 -> index 1: 10 30 40 50 70 90 80 
pivot 80 -> index 5: 10 30 40 50 70 80 90 
sorted: 10 30 40 50 70 80 90
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case (pivot splits in half) | O(n log n) |
| Average case | O(n log n) |
| Worst case (sorted input, last-item pivot) | O(n²) |

Space: O(log n) recursion on average, O(n) worst
Stable: no
In-place: yes

Picking a **random** or **median-of-three** pivot makes the worst case very unlikely. In practice quick sort is often the fastest comparison sort.

## Videos

- [QuickSort Algorithm](https://youtu.be/7h1s2SojIRw) (Abdul Bari): Abdul Bari's classic. Partition traced by hand with i and j.
- [Quick sort in 4 minutes](https://youtu.be/Hoixgm4-P4M) (Michael Sambol): A 4-minute visual recap.

## Exam lens

Likely questions:

- Explain divide and conquer using quick sort.
- Partition `10, 80, 30, 90, 40, 50, 70` around the last item. Show i, j and every swap.
- What is the worst case of quick sort? Which input causes it with a last-item pivot?
- Write partition() and quickSort() in C++.

Common mistakes:

- Recursing on `(lo, p)` instead of `(lo, p − 1)`. The pivot is already in place.
- Forgetting the final `swap(a[i + 1], a[hi])` that puts the pivot in place.
- Saying quick sort is always O(n log n).
- Calling it stable.

## Quick check

1. After one partition, the pivot is…
   A. at index 0
   B. in its final sorted position
   C. at the end
   D. removed
   Answer: B. Everything left is smaller and everything right is bigger, so it never moves again.

2. Last-item pivot on an already sorted array gives…
   A. O(n)
   B. O(n log n)
   C. O(n²)
   D. O(log n)
   Answer: C. Every partition peels off just one item, so n levels of O(n) work.

3. Partition `3, 8, 2, 5, 4` around pivot 4 (Lomuto). Result?
   A. `3 2 4 5 8`
   B. `2 3 4 8 5`
   C. `3 2 4 8 5`
   D. `4 3 8 2 5`
   Answer: A. 3 stays (i=0), 8 skipped, 2 swaps with 8 → `3 2 8 5 4`, 5 skipped. Then the pivot swaps with a[2] → `3 2 4 5 8`.

4. Quick sort is…
   A. stable, not in-place
   B. in-place, not stable
   C. stable and in-place
   D. neither
   Answer: B. It only uses the recursion stack, but long-distance swaps break stability.

## Practice

**Trace by hand.** Run quick sort (Lomuto, last-item pivot) on `10, 80, 30, 90, 40, 50, 70`. Write the array after each partition and the pivot's final index.

Solution:

- pivot 70 → index 4: `10 30 40 50 70 90 80`
- pivot 50 → index 3: `10 30 40 50 70 90 80`
- pivot 40 → index 2 (left side `10 30 40`)
- pivot 30 → index 1
- pivot 80 → index 5: `10 30 40 50 70 80 90`


**Implement it.** Make quick sort pick a random pivot (swap a random item in [lo, hi] with a[hi] before partitioning). Compare comparison counts on a sorted array of 1,000.

Hint: `int r = lo + rand() % (hi - lo + 1); swap(a[r], a[hi]);` at the start of partition.

**Problems:**

- [Sort an Array](https://leetcode.com/problems/sort-an-array/) (medium). Hint: A plain last-item pivot can time out on sorted tests. Use a random pivot.
- [Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) (medium). Hint: Quickselect. Partition once and recurse into only the side that holds index n − k.

## Mastery checklist

- [ ] I can partition an array around a pivot by hand.
- [ ] I can write partition and quickSort from memory.
- [ ] I can explain best, average and worst case.
- [ ] I know quick sort is in-place and not stable.


---

# 8.3 Merge Sort

> Split the array in half, sort each half recursively, then merge the two sorted halves. Always O(n log n), stable, but needs O(n) extra space.

Chapter: Advanced Sorting & Searching · ~50 min · medium
URL: https://dsa.fetehadin.com/learn/merge-sort

## Mental model

Two people each hold a **sorted pile** of cards. To combine them, look at the top card of each pile, take the smaller one, and repeat. That **merge** is easy and takes one look per card.

Merge sort uses that trick recursively:

1. **Divide**: split the array into two halves.
2. **Conquer**: sort each half (recursively, until a piece has 1 item, which is already sorted).
3. **Combine**: merge the two sorted halves.

### The merge

```cpp
while (i <= mid && j <= hi)
    tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
// then copy whatever is left of either half
```

Using `<=` takes the **left** item when two are equal, so equal items keep their order: merge sort is **stable**.

### Why always n log n

Halving n repeatedly reaches 1 after **log₂ n** levels. Each level merges n items in total. So the cost is **n log n**, for sorted, reversed or random data alike. The price is the **O(n) temporary array**.

### Merge vs quick

| | Merge sort | Quick sort |
| --- | --- | --- |
| Worst case | O(n log n) | O(n²) |
| Extra space | O(n) | O(log n) |
| Stable | yes | no |

## C++ code: merge-sort.cpp

```cpp
#include <iostream>
#include <vector>
using namespace std;

void merge(int a[], int lo, int mid, int hi) {
    vector<int> tmp;                          // O(n) extra space
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);   // <= keeps it stable
        else tmp.push_back(a[j++]);
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= hi) tmp.push_back(a[j++]);
    for (int k = 0; k < (int)tmp.size(); k++) a[lo + k] = tmp[k];
}

void mergeSort(int a[], int lo, int hi) {
    if (lo >= hi) return;                     // 0 or 1 item: already sorted
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
    cout << "merged [" << lo << ".." << hi << "]: ";
    for (int k = lo; k <= hi; k++) cout << a[k] << " ";
    cout << "\n";
}

int main() {
    int a[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(a) / sizeof(a[0]);
    mergeSort(a, 0, n - 1);
    cout << "sorted: ";
    for (int x : a) cout << x << " ";
    cout << "\n";
}
```

Expected output:

```text
merged [0..1]: 27 38 
merged [2..3]: 3 43 
merged [0..3]: 3 27 38 43 
merged [4..5]: 9 82 
merged [4..6]: 9 10 82 
merged [0..6]: 3 9 10 27 38 43 82 
sorted: 3 9 10 27 38 43 82
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case | O(n log n) |
| Average case | O(n log n) |
| Worst case | O(n log n) |

Space: O(n) for the temporary array
Stable: yes
In-place: no

log₂ n levels of splitting, and each level does O(n) merging work, so **n log n** whatever the input.

## Videos

- [Merge Sort Algorithm](https://youtu.be/mB5HXBb_HY8) (Abdul Bari): Abdul Bari draws the full recursion tree and derives n log n.
- [Merge sort in 3 minutes](https://youtu.be/4VqmGXwpLqc) (Michael Sambol): The 3-minute visual version.

## Exam lens

Likely questions:

- Show the split and merge tree of merge sort on `38, 27, 43, 3, 9, 82, 10`.
- Write the merge function. Why is merge sort O(n log n) in every case?
- Compare merge sort and quick sort (time, space, stability).

Common mistakes:

- Forgetting to copy the leftover items after one half runs out.
- Using `<` instead of `<=` in merge, which breaks stability.
- Base case `lo > hi` only. A single item (`lo == hi`) must also stop the recursion.
- Calling merge sort in-place.

## Quick check

1. Merge `2 5 9` and `1 5 7`. Result and number of comparisons?
   A. `1 2 5 5 7 9`, 5 comparisons
   B. `1 2 5 5 7 9`, 6 comparisons
   C. `2 5 9 1 5 7`, 0
   D. `1 2 5 7 9`, 5
   Answer: A. Comparisons: 2/1, 2/5, 5/5, 9/5, 9/7. Then 9 is copied without comparing.

2. Worst-case time of merge sort?
   A. O(n)
   B. O(n log n)
   C. O(n²)
   D. O(log n)
   Answer: B. The splits are always even, whatever the data.

3. Main disadvantage of merge sort compared with quick sort?
   A. Worse worst case
   B. Needs O(n) extra memory
   C. Not stable
   D. Only works on linked lists
   Answer: B. The merge step writes into a temporary array.

## Practice

**Trace by hand.** Trace merge sort on `38, 27, 43, 3, 9, 82, 10`. Write every merge in the order it happens.

Solution:

- merge [0..1]: `27 38`
- merge [2..3]: `3 43`
- merge [0..3]: `3 27 38 43`
- merge [4..5]: `9 82`
- merge [4..6]: `9 10 82`
- merge [0..6]: `3 9 10 27 38 43 82`


**Implement it.** Count inversions (pairs i < j with a[i] > a[j]) by modifying merge sort.

Hint: When you take from the right half, every item left in the left half is bigger, so add `mid − i + 1`.

**Problems:**

- [Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/) (easy). Hint: Merge from the back so you don't overwrite nums1.
- [Sort List](https://leetcode.com/problems/sort-list/) (medium). Hint: Merge sort on a linked list. Find the middle with fast/slow pointers, split, sort, merge.

## Mastery checklist

- [ ] I can draw the split/merge tree by hand.
- [ ] I can write merge() and mergeSort() from memory.
- [ ] I can explain why it is always O(n log n).
- [ ] I know it is stable but needs O(n) extra space.


---

# 8.4 Heap Sort

> Build a max-heap in the array, then repeatedly swap the root (the largest item) to the end and sift down. O(n log n) in every case, in-place.

Chapter: Advanced Sorting & Searching · ~55 min · hard
URL: https://dsa.fetehadin.com/learn/heap-sort

## Mental model

A **sports knockout tournament**. The champion ends up at the top. Remove the champion and the runners-up compete again; the next winner rises to the top. Heap sort keeps finding "the champion" (the maximum) and moving it to the end.

### What is a max-heap?

A **complete binary tree** where every parent is **≥ its children**. So the largest item is always at the **root**.

Because the tree is complete, it fits in an array with no gaps (0-based):

| | index |
| --- | --- |
| left child of i | 2i + 1 |
| right child of i | 2i + 2 |
| parent of i | (i − 1) / 2 |

### heapify (sift down)

If a node is smaller than a child, swap it with the **larger** child and keep going down. O(log n).

### Heap sort in two phases

1. **Build** a max-heap: call heapify on every non-leaf, from `n/2 − 1` down to 0.
2. **Extract** repeatedly: swap `a[0]` (the max) with the last item of the heap, shrink the heap by 1, and heapify the root.

The sorted part grows from the right, just like selection sort, but each "find the max" costs **O(log n)** instead of O(n).

> The same heap is a **priority queue** (`std::priority_queue`), used in Dijkstra's algorithm and schedulers.

## C++ code: heap-sort.cpp

```cpp
#include <iostream>
using namespace std;

void heapify(int a[], int n, int i) {         // sift a[i] down in a max-heap of size n
    int largest = i;
    int l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest != i) {
        swap(a[i], a[largest]);
        heapify(a, n, largest);
    }
}

void print(int a[], int n) { for (int k = 0; k < n; k++) cout << a[k] << " "; cout << "\n"; }

void heapSort(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)      // build the max-heap
        heapify(a, n, i);
    cout << "max-heap: "; print(a, n);
    for (int end = n - 1; end > 0; end--) {
        swap(a[0], a[end]);                   // biggest goes to the end
        heapify(a, end, 0);
    }
}

int main() {
    int a[] = {4, 10, 3, 5, 1, 8};
    int n = sizeof(a) / sizeof(a[0]);
    heapSort(a, n);
    cout << "sorted:   "; print(a, n);
}
```

Expected output:

```text
max-heap: 10 5 8 4 1 3 
sorted:   1 3 4 5 8 10
```

## Complexity

| Case | Cost |
| --- | --- |
| Build heap | O(n) |
| Each extract-max (swap + heapify) | O(log n) |
| Best / average / worst | O(n log n) |

Space: O(1) iterative, O(log n) with recursive heapify
Stable: no
In-place: yes

Heap sort combines merge sort's guaranteed O(n log n) with quick sort's in-place storage, but it is usually slower in practice.

## Videos

- [Heap, Heap Sort, Heapify, Priority Queues](https://youtu.be/HqPJF2L5h9U) (Abdul Bari): Abdul Bari covers heaps, insert, delete, heapify and heap sort in one sitting.
- [Heap sort in 4 minutes](https://youtu.be/2DmK_H7IdTo) (Michael Sambol): A 4-minute visual of the swap-and-heapify loop.

## Exam lens

Likely questions:

- What is a max-heap? Why is it stored in an array?
- For index i, give the indices of its parent, left child and right child (0-based).
- Build a max-heap from `4, 10, 3, 5, 1, 8`. Show the array.
- Trace two steps of heap sort after the heap is built.

Common mistakes:

- Using 1-based formulas (2i, 2i+1) with a 0-based array. With 0-based it is 2i+1 and 2i+2.
- Starting the build loop at i = 0 instead of n/2 − 1, going down to 0.
- Calling heapify on the whole array instead of the shrinking heap size `end`.
- Confusing a heap with a BST. In a heap, left and right children have no order between them.

## Quick check

1. In a 0-based array heap, the children of index 2 are…
   A. 3 and 4
   B. 4 and 5
   C. 5 and 6
   D. 2 and 3
   Answer: C. 2·2 + 1 = 5 and 2·2 + 2 = 6.

2. In a max-heap, the largest item is…
   A. the last item
   B. the root, a[0]
   C. a leaf
   D. anywhere
   Answer: B. Every parent is ≥ its children, so the max sits at the top.

3. Build a max-heap from `4, 10, 3, 5, 1, 8`. Result?
   A. `10 5 8 4 1 3`
   B. `10 8 5 4 3 1`
   C. `1 3 4 5 8 10`
   D. `10 4 8 5 1 3`
   Answer: A. heapify(2): 8 up. heapify(1): 10 stays. heapify(0): 4 swaps with 10, then with 5.

4. Why can a heap be stored in an array with no pointers?
   A. It is sorted
   B. It is a complete binary tree, so there are no gaps
   C. It is a BST
   D. It has no children
   Answer: B. Complete trees fill levels left to right, so index arithmetic finds parents and children.

## Practice

**Trace by hand.** Heap sort `4, 10, 3, 5, 1, 8`. Write the max-heap, then the array after each of the first three swap-and-heapify steps.

Solution:

- max-heap: `10 5 8 4 1 3`
- swap 10↔3, heapify size 5 → `8 5 3 4 1 | 10`
- swap 8↔1, heapify size 4 → `5 4 3 1 | 8 10`
- swap 5↔1, heapify size 3 → `4 1 3 | 5 8 10`


**Implement it.** Write a min-heap priority queue with `push`, `pop` and `top` using a `vector<int>` (sift up on push, sift down on pop).

Hint: Sift up: while `i > 0 && a[(i-1)/2] > a[i]`, swap with the parent and move up.

**Problems:**

- [Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) (medium). Hint: Keep a min-heap of size k (`priority_queue<int, vector<int>, greater<int>>`). Its top is the answer.
- [Last Stone Weight](https://leetcode.com/problems/last-stone-weight/) (easy). Hint: A max-heap (`priority_queue<int>`). Pop two, push the difference.

## Mastery checklist

- [ ] I can explain a max-heap and its array storage.
- [ ] I can build a heap by hand with heapify.
- [ ] I can trace heap sort's swap-and-heapify loop.
- [ ] I know heap sort is O(n log n), in-place and not stable.


---

# 8.5 Hashing Basics

> A hash function turns a key into an array index, so search is O(1) on average. Collisions, separate chaining, linear probing and the load factor.

Chapter: Advanced Sorting & Searching · ~45 min · medium
URL: https://dsa.fetehadin.com/learn/hashing

## Mental model

A **library** puts every book on a shelf chosen by the first letter of the author's surname. To find "Tamassia" you walk straight to shelf **T**. You don't search the whole library. That shelf rule is a **hash function**.

### The idea

A **hash function** `h(key)` turns a key into an index of an array (the **hash table**) of size M. A common simple one:

```cpp
int h(int key) { return key % M; }   // M is often a prime
```

Store the key at `table[h(key)]`; to search, look in the same place. **No scanning**, so it is O(1) on average.

A good hash function is **fast** and **spreads keys evenly**.

### Collisions

Two keys can map to the same index (14 and 21 both give 0 when M = 7). Two classic fixes:

- **Separate chaining**: each slot holds a **linked list**. Colliding keys join the list.
- **Open addressing (linear probing)**: if the slot is taken, try the **next** one, `(h + 1) % M`, then `(h + 2) % M`, … until an empty slot. Searching stops at an **empty** slot.

### Load factor

**α = n / M**: how full the table is. As α grows, chains get longer and probe runs get longer. With probing, α must stay below 1 (keep it under about 0.7). With chaining, the table can still work above 1, but it gets slower.

> In C++, `std::unordered_map` and `std::unordered_set` are hash tables.

## C++ code: hashing.cpp

```cpp
#include <iostream>
#include <list>
#include <vector>
using namespace std;

const int M = 7;
int h(int key) { return key % M; }

struct ChainTable {                           // separate chaining
    vector<list<int>> table = vector<list<int>>(M);
    void insert(int key) { table[h(key)].push_back(key); }
    bool search(int key) const {
        for (int k : table[h(key)]) if (k == key) return true;
        return false;
    }
};

struct ProbeTable {                           // open addressing, linear probing
    int table[M];
    ProbeTable() { for (int& x : table) x = -1; }
    bool insert(int key) {
        for (int i = 0; i < M; i++) {
            int idx = (h(key) + i) % M;
            if (table[idx] == -1) { table[idx] = key; return true; }
        }
        return false;
    }
    int search(int key) const {               // index, or -1
        for (int i = 0; i < M; i++) {
            int idx = (h(key) + i) % M;
            if (table[idx] == -1) return -1;   // an empty slot ends the search
            if (table[idx] == key) return idx;
        }
        return -1;
    }
};

int main() {
    int keys[] = {14, 23, 12, 21, 30};
    ChainTable c;
    ProbeTable p;
    for (int k : keys) { c.insert(k); p.insert(k); }

    cout << "chaining:\n";
    for (int i = 0; i < M; i++) {
        cout << "  " << i << ":";
        for (int k : c.table[i]) cout << " " << k;
        cout << "\n";
    }
    cout << "linear probing: ";
    for (int x : p.table) cout << (x == -1 ? string("_") : to_string(x)) << " ";
    cout << "\n";
    cout << "search 21: chain " << (c.search(21) ? "found" : "missing") << ", probe index " << p.search(21) << "\n";
    cout << "search 5:  chain " << (c.search(5) ? "found" : "missing") << ", probe index " << p.search(5) << "\n";
}
```

Expected output:

```text
chaining:
  0: 14 21
  1:
  2: 23 30
  3:
  4:
  5: 12
  6:
linear probing: 14 21 23 30 _ 12 _ 
search 21: chain found, probe index 1
search 5:  chain missing, probe index -1
```

## Complexity

| Case | Cost |
| --- | --- |
| search / insert / delete, average | O(1) |
| search / insert / delete, worst (all keys collide) | O(n) |

Space: O(M + n)

Keep the **load factor** α = n / M low (under ~0.7 for probing) so chains and probe runs stay short.

## Videos

- [Hash Tables and Hash Functions](https://youtu.be/KyUTuwz_b7Q) (Computer Science Lessons): Hash functions, collisions, chaining and open addressing, with clear diagrams.

## Exam lens

Likely questions:

- What is hashing? What makes a good hash function?
- Insert 14, 23, 12, 21, 30 into a table of size 7 with h(k) = k mod 7 using (a) chaining, (b) linear probing.
- What is a collision? Describe two ways to resolve it.
- What is the load factor and why does it matter?

Common mistakes:

- With linear probing, stopping a search at a slot holding a **different** key. Only an **empty** slot means "not found".
- Forgetting to wrap around with `% M` when probing.
- Claiming hashing is always O(1). The worst case is O(n).

## Quick check

1. M = 7, h(k) = k % 7. Which two keys collide: 15, 22, 9, 31?
   A. 15 and 22
   B. 9 and 31
   C. 15 and 31
   D. none
   Answer: A. 15 % 7 = 1 and 22 % 7 = 1. 9 → 2 and 31 → 3.

2. Linear probing on a collision at index i tries…
   A. i − 1
   B. (i + 1) % M, then (i + 2) % M, …
   C. a random slot
   D. a new table
   Answer: B. Step forward one slot at a time, wrapping around.

3. Average search cost in a well-sized hash table?
   A. O(1)
   B. O(log n)
   C. O(n)
   D. O(n log n)
   Answer: A. The hash function jumps straight to (almost) the right place.

4. The load factor is…
   A. M / n
   B. n / M
   C. collisions / n
   D. the hash of the key
   Answer: B. Items stored divided by table size.

## Practice

**Trace by hand.** M = 7, h(k) = k % 7. Insert 14, 23, 12, 21, 30 with (a) chaining and (b) linear probing.

Solution:

(a) Chaining: bucket 0 → `14, 21` · bucket 2 → `23, 30` · bucket 5 → `12`

(b) Probing: 14 → 0 · 23 → 2 · 12 → 5 · 21 → 0 taken → **1** · 30 → 2 taken, 3 free → **3**

Table: `14 21 23 30 _ 12 _`


**Implement it.** Write a string hash `h(s) = (sum of s[i] × 31^i) % M` and use it in a chained table of words. Then count word frequencies with `std::unordered_map<string, int>`.

Hint: Compute it like Horner: `h = (h * 31 + c) % M` for each character.

**Problems:**

- [Two Sum](https://leetcode.com/problems/two-sum/) (easy). Hint: For each x, look up `target − x` in an unordered_map of value → index.
- [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/) (easy). Hint: Insert into an unordered_set; if the key is already there, you found a duplicate.
- [Valid Anagram](https://leetcode.com/problems/valid-anagram/) (easy). Hint: Count letters of s, subtract letters of t, check every count is 0.

## Mastery checklist

- [ ] I can explain hashing with a hash function and a table.
- [ ] I can insert keys by hand with chaining and with linear probing.
- [ ] I can explain collisions and the load factor.
- [ ] I know average O(1) and worst O(n).


---

# LU.1 Two Pointers

> Two indices that move toward each other (or in the same direction) to replace an O(n²) pair search with one O(n) pass.

Chapter: Level Up: Problem Patterns · ~40 min · medium · optional, not on the exam
URL: https://dsa.fetehadin.com/learn/two-pointers

## Mental model

Two people search a **sorted bookshelf** for two books whose prices add up to 15 birr. One starts at the cheap end, the other at the expensive end. Too expensive? The person at the expensive end steps in. Too cheap? The person at the cheap end steps in. They never need to go back.

### Why it works

The array is sorted. If `a[l] + a[r]` is **too small**, then `a[l]` paired with anything left of `r` is even smaller, so `a[l]` is useless: move `l` right. If it is **too big**, `a[r]` is useless: move `r` left. Every step discards one item, so the search is **O(n)** instead of checking all **n²** pairs.

### Two flavours

- **Opposite ends** (`l = 0`, `r = n − 1`, move inward): pair sums, reversing, palindromes, container with most water.
- **Same direction** (a slow write pointer and a fast read pointer): removing duplicates in place, moving zeros. Fast & slow pointers on linked lists are the same idea.

> Built on Chapter 3 (sorting and binary search thinking). Not on the exam.

## C++ code: two-pointers.cpp

```cpp
#include <iostream>
#include <vector>
using namespace std;

bool pairSum(const vector<int>& a, int target) {     // a must be sorted
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int sum = a[l] + a[r];
        if (sum == target) { cout << a[l] << " + " << a[r] << " = " << target << "\n"; return true; }
        if (sum < target) l++;                         // need a bigger sum
        else r--;                                      // need a smaller sum
    }
    cout << "no pair sums to " << target << "\n";
    return false;
}

void reverseInPlace(vector<int>& a) {
    for (int l = 0, r = a.size() - 1; l < r; l++, r--) swap(a[l], a[r]);
}

int main() {
    vector<int> a = {1, 3, 4, 6, 8, 11, 14};
    pairSum(a, 15);
    pairSum(a, 2);
    reverseInPlace(a);
    for (int x : a) cout << x << " ";
    cout << "\n";
}
```

Expected output:

```text
1 + 14 = 15
no pair sums to 2
14 11 8 6 4 3 1
```

## Complexity

| Case | Cost |
| --- | --- |
| brute force (all pairs) | O(n²) |
| two pointers on sorted data | O(n) |
| sort first, then two pointers | O(n log n) |

Space: O(1)

The opposite-ends version needs **sorted** data so you know which pointer to move.

## Videos

- [Two Pointers in 7 minutes](https://youtu.be/QzZ7nmouLTI) (AlgoMasterIO): The pattern and its variants in 7 minutes.
- [Two Sum II (Leetcode 167)](https://youtu.be/cQ1Oz4ckceM) (NeetCode): NeetCode solves Two Sum II, the textbook two-pointer problem.

## Exam lens

Likely questions:

- Why does the pair-sum algorithm only work on sorted input?
- Why is moving `l` right the only sensible move when the sum is too small?
- Name three problems solved with two pointers.

Common mistakes:

- Using `l <= r` and pairing an item with itself.
- Running opposite-end two pointers on unsorted data.
- Moving both pointers at once and skipping valid pairs.

## Quick check

1. Array `1 3 4 6 8 11 14`, target 15. First pair checked?
   A. 1 + 3
   B. 1 + 14
   C. 6 + 8
   D. 3 + 11
   Answer: B. Start at both ends.

2. sum < target. Which pointer moves?
   A. r moves left
   B. l moves right
   C. both
   D. neither
   Answer: B. Only a bigger left value can increase the sum.

3. Time complexity of the two-pointer pair search?
   A. O(1)
   B. O(n)
   C. O(n log n)
   D. O(n²)
   Answer: B. Each step moves one pointer, so at most n steps.

## Practice

**Trace by hand.** Find a pair summing to 10 in `1 2 4 5 7 9` with two pointers. List each (l, r, sum).

Solution:

- l=0, r=5: 1 + 9 = 10 → **found** on the first step.

Try target 11: (0,5) 10 < 11 → l=1 · (1,5) 2 + 9 = 11 → found.


**Implement it.** Check whether a string is a palindrome, skipping non-letters, using two pointers.

Hint: `l` from the start, `r` from the end. Skip characters that are not `isalnum`, compare `tolower`, move both inward.

**Problems:**

- [Two Sum II - Input Array Is Sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/) (medium). Hint: This page's code, returning 1-based indices.
- [Valid Palindrome](https://leetcode.com/problems/valid-palindrome/) (easy). Hint: Opposite-end pointers, skipping non-alphanumeric characters.
- [Container With Most Water](https://leetcode.com/problems/container-with-most-water/) (medium). Hint: Start wide. Always move the shorter wall; moving the taller one can never help.

## Mastery checklist

- [ ] I can explain why two pointers turns O(n²) into O(n).
- [ ] I can solve pair-sum on a sorted array.
- [ ] I can recognise when a problem fits the pattern.


---

# LU.2 Sliding Window

> Keep a running answer for a contiguous range, adding the item that enters and removing the one that leaves, instead of recomputing every window.

Chapter: Level Up: Problem Patterns · ~45 min · medium · optional, not on the exam
URL: https://dsa.fetehadin.com/learn/sliding-window

## Mental model

A **train window**: as the train moves, one new tree appears on the right and one old tree disappears on the left. You don't need to look at the whole view again.

### Fixed window (size k)

Compute the first window's sum once. Then for each step: `sum += a[r] − a[r − k]`. That is **O(n)** instead of O(n·k).

### Variable window

Two pointers `l` and `r` mark the window. Move `r` to **grow** it. Whenever the window breaks a rule (a repeated letter, a sum too big), move `l` to **shrink** it until it is valid again. Each index enters once and leaves once, so the total is **O(n)**, even with the inner `while`.

> Built on arrays (Ch1) and two pointers. Not on the exam.

## C++ code: sliding-window.cpp

```cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int maxSum(const vector<int>& a, int k) {             // fixed-size window
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];
    int best = sum;
    for (int r = k; r < (int)a.size(); r++) {
        sum += a[r] - a[r - k];                        // add new, drop old
        best = max(best, sum);
    }
    return best;
}

int longestUnique(const string& s) {                  // variable-size window
    int seen[256] = {};
    int best = 0;
    for (int l = 0, r = 0; r < (int)s.size(); r++) {
        seen[(unsigned char)s[r]]++;
        while (seen[(unsigned char)s[r]] > 1) seen[(unsigned char)s[l++]]--;   // shrink until valid
        best = max(best, r - l + 1);
    }
    return best;
}

int main() {
    cout << "max sum of 3: " << maxSum({2, 1, 5, 1, 3, 2, 7, 1}, 3) << "\n";
    cout << "longest without repeats in \"abcabcbb\": " << longestUnique("abcabcbb") << "\n";
}
```

Expected output:

```text
max sum of 3: 12
longest without repeats in "abcabcbb": 3
```

## Complexity

| Case | Cost |
| --- | --- |
| recompute every window | O(n·k) |
| fixed sliding window | O(n) |
| variable window (grow/shrink) | O(n): each item enters and leaves once |

Space: O(1), or O(alphabet) for a frequency table

Sliding windows work on **contiguous** ranges (subarrays, substrings), not subsequences.

## Videos

- [Sliding Window in 7 minutes](https://youtu.be/y2d0VHdvfdc) (AlgoMasterIO): Fixed vs variable windows in 7 minutes.
- [Sliding Window: Best Time to Buy and Sell Stock](https://youtu.be/1pkOgXD63yU) (NeetCode): NeetCode applies the window idea to Best Time to Buy and Sell Stock.

## Exam lens

Likely questions:

- What is the difference between a fixed and a variable sliding window?
- Why is the variable window still O(n) even though it has a nested while loop?

Common mistakes:

- Off-by-one when dropping the old item. It is `a[r − k]`, not `a[r − k + 1]`.
- Using a window on a problem that asks for a subsequence (not contiguous).
- Forgetting to update the answer after shrinking.

## Quick check

1. `2 1 5 1 3 2`, k = 3. The window sums are…
   A. 8, 7, 9, 6
   B. 8, 7, 9, 6, 5
   C. 3, 6, 6, 4
   D. 8, 9
   Answer: A. 2+1+5, 1+5+1, 5+1+3, 1+3+2.

2. Moving the window right by one costs…
   A. O(k)
   B. O(1)
   C. O(n)
   D. O(log n)
   Answer: B. Add the new item, subtract the old one.

3. Longest substring without repeats in `pwwkew`?
   A. 2
   B. 3
   C. 4
   D. 6
   Answer: B. `wke`.

## Practice

**Trace by hand.** Max sum of k = 3 in `2 1 5 1 3 2 7 1`. List each window sum.

Solution:

8, 7, 9, 6, 12, 10 → best **12** (`3 2 7`).

**Implement it.** Find the length of the shortest subarray with sum ≥ S (all numbers positive).

Hint: Grow `r`, adding to sum. While `sum >= S`, record `r − l + 1` and shrink from the left.

**Problems:**

- [Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) (easy). Hint: Track the lowest price so far; the window is "buy day … today".
- [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/) (medium). Hint: This page's `longestUnique()`.
- [Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/) (medium). Hint: Variable window. Shrink while the sum is big enough.

## Mastery checklist

- [ ] I can write a fixed-size window in O(n).
- [ ] I can write a variable window that grows and shrinks.
- [ ] I can explain why both are O(n).


---

# LU.3 Prefix Sum

> Precompute running totals once in O(n), then answer any range-sum query with one subtraction in O(1).

Chapter: Level Up: Problem Patterns · ~35 min · easy · optional, not on the exam
URL: https://dsa.fetehadin.com/learn/prefix-sum

## Mental model

A **car odometer**. To know how far you drove between Adama and Hawassa, you don't add up every kilometre again. You subtract the odometer reading at Adama from the reading at Hawassa.

A **prefix sum** array is that odometer: `p[i]` = sum of the first i items.

```cpp
p[0] = 0;
p[i + 1] = p[i] + a[i];
sum(a[l..r]) = p[r + 1] - p[l];
```

Building it is **O(n)**, once. After that, any range sum is **O(1)**. That is the time/space trade-off from Chapter 2: spend O(n) memory to save repeated work.

> Built on arrays and time/space trade-offs (Ch1–2). Not on the exam.

## C++ code: prefix-sum.cpp

```cpp
#include <iostream>
#include <vector>
using namespace std;

vector<int> buildPrefix(const vector<int>& a) {
    vector<int> p(a.size() + 1, 0);                   // p[i] = sum of first i items
    for (int i = 0; i < (int)a.size(); i++) p[i + 1] = p[i] + a[i];
    return p;
}

int rangeSum(const vector<int>& p, int l, int r) {    // sum of a[l..r]
    return p[r + 1] - p[l];
}

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9, 2};
    vector<int> p = buildPrefix(a);
    cout << "prefix: ";
    for (int x : p) cout << x << " ";
    cout << "\n";
    cout << "sum a[1..4] = " << rangeSum(p, 1, 4) << "\n";
    cout << "sum a[0..6] = " << rangeSum(p, 0, 6) << "\n";
    cout << "sum a[5..5] = " << rangeSum(p, 5, 5) << "\n";
}
```

Expected output:

```text
prefix: 0 3 4 8 9 14 23 25 
sum a[1..4] = 11
sum a[0..6] = 25
sum a[5..5] = 9
```

## Complexity

| Case | Cost |
| --- | --- |
| build | O(n) |
| each range query | O(1) |
| q queries without prefix sums | O(n·q) |

Space: O(n)

Using size n + 1 with `p[0] = 0` removes the special case for ranges that start at index 0.

## Videos

- [Prefix Sum in 4 minutes](https://youtu.be/yuws7YK0Yng) (AlgoMasterIO): The whole pattern in 4 minutes.
- [Subarray Sum Equals K: Prefix Sums](https://youtu.be/fFVZt-6sgyo) (NeetCode): NeetCode combines prefix sums with a hash map (Chapter 8) for Subarray Sum Equals K.

## Exam lens

Likely questions:

- Build the prefix array of a given array and compute a range sum.
- Why is `p` one longer than `a`?

Common mistakes:

- Writing `p[r] − p[l]`. With the n + 1 layout it is `p[r + 1] − p[l]`.
- Rebuilding the prefix array for every query.

## Quick check

1. a = `3 1 4 1 5`. p = ?
   A. `3 4 8 9 14`
   B. `0 3 4 8 9 14`
   C. `0 3 1 4 1 5`
   D. `14 11 10 6 5`
   Answer: B. p[0] = 0, then running totals.

2. With that p, sum(a[1..3]) = ?
   A. p[3] − p[1] = 5
   B. p[4] − p[1] = 6
   C. p[4] − p[0] = 9
   D. p[3] − p[0] = 8
   Answer: B. 9 − 3 = 6 = 1 + 4 + 1.

3. Range query cost after building?
   A. O(1)
   B. O(log n)
   C. O(n)
   D. O(n²)
   Answer: A. One subtraction.

## Practice

**Trace by hand.** a = `3 1 4 1 5 9 2`. Build p and compute sum(a[1..4]), sum(a[0..6]) and sum(a[5..5]).

Solution:

p = `0 3 4 8 9 14 23 25`
- a[1..4] = p[5] − p[1] = 14 − 3 = **11**
- a[0..6] = p[7] − p[0] = **25**
- a[5..5] = p[6] − p[5] = **9**


**Implement it.** Find the pivot index where the sum of the left side equals the sum of the right side.

Hint: Total = p[n]. At index i: left = p[i], right = total − p[i + 1].

**Problems:**

- [Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/) (easy). Hint: Build p in the constructor; sumRange is one subtraction.
- [Find Pivot Index](https://leetcode.com/problems/find-pivot-index/) (easy). Hint: Left sum vs total − left − a[i].
- [Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/) (medium). Hint: Count how many earlier prefix sums equal `current − k`, using an unordered_map.

## Mastery checklist

- [ ] I can build a prefix-sum array.
- [ ] I can answer a range sum in O(1).
- [ ] I can combine prefix sums with a hash map.


---

# LU.4 Fast & Slow Pointers

> Two pointers moving through a linked list at different speeds find the middle, the n-th node from the end, and cycles (Floyd's algorithm) in one pass with O(1) space.

Chapter: Level Up: Problem Patterns · ~40 min · medium · optional, not on the exam
URL: https://dsa.fetehadin.com/learn/fast-slow-pointers

## Mental model

Two runners on a track: the **hare** runs twice as fast as the **tortoise**.

- On a **straight road**, when the hare reaches the finish, the tortoise is exactly **halfway**. That finds the **middle** of a linked list.
- On a **circular track**, the hare eventually **laps** the tortoise and they meet. That detects a **cycle**.
- Give one runner an **n-step head start** at the same speed: when the leader finishes, the other is **n from the end**.

All three need only two pointers: **O(1) extra space**, one pass.

> Built on Chapter 4 (linked lists). Not on the exam.

## C++ code: fast-slow.cpp

```cpp
#include <iostream>
using namespace std;

struct Node { int data; Node* next; };

Node* middle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;                            // 1 step
        fast = fast->next->next;                      // 2 steps
    }
    return slow;
}

Node* nthFromEnd(Node* head, int n) {
    Node* lead = head;
    for (int i = 0; i < n; i++) { if (!lead) return nullptr; lead = lead->next; }
    Node* trail = head;
    while (lead) { lead = lead->next; trail = trail->next; }   // gap of n stays fixed
    return trail;
}

bool hasCycle(Node* head) {                           // Floyd's tortoise and hare
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

int main() {
    Node* nodes[7];
    for (int i = 6; i >= 0; i--) nodes[i] = new Node{i + 1, i < 6 ? nodes[i + 1] : nullptr};
    Node* head = nodes[0];                            // 1 2 3 4 5 6 7

    cout << "middle: " << middle(head)->data << "\n";
    cout << "2nd from end: " << nthFromEnd(head, 2)->data << "\n";
    cout << "cycle? " << (hasCycle(head) ? "yes" : "no") << "\n";
    nodes[6]->next = nodes[2];                        // 7 -> 3 makes a loop
    cout << "after linking 7 -> 3, cycle? " << (hasCycle(head) ? "yes" : "no") << "\n";
    nodes[6]->next = nullptr;

    for (Node* n : nodes) delete n;
}
```

Expected output:

```text
middle: 4
2nd from end: 6
cycle? no
after linking 7 -> 3, cycle? yes
```

## Complexity

| Case | Cost |
| --- | --- |
| middle node | O(n) |
| n-th from end | O(n), one pass |
| cycle detection | O(n) |

Space: O(1)

The obvious alternatives (count first, or store visited nodes in a set) need two passes or O(n) memory.

## Videos

- [Fast and Slow Pointers in 6 Minutes](https://youtu.be/b139yf7Ik-E) (AlgoMasterIO): All the fast/slow variants in 6 minutes.
- [Linked List Cycle: Floyd's Tortoise and Hare](https://youtu.be/gBTe7lFR3vc) (NeetCode): NeetCode explains why Floyd's tortoise and hare must meet inside a cycle.
- [Middle of the Linked List](https://youtu.be/A2_ldqM4QcY) (NeetCodeIO): Middle of the Linked List, solved and explained in 5 minutes.

## Exam lens

Likely questions:

- Why does `fast` meeting `slow` prove there is a cycle?
- For an even-length list, which middle does the loop return?

Common mistakes:

- Checking only `fast->next` and not `fast` first (null dereference).
- In n-th from end, moving the lead pointer n − 1 steps instead of n.

## Quick check

1. List `1 2 3 4 5 6 7`. Where is slow when fast stops?
   A. 3
   B. 4
   C. 5
   D. 7
   Answer: B. Fast visits 1, 3, 5, 7; slow visits 1, 2, 3, 4.

2. List `1 2 3 4 5 6`. middle() returns…
   A. 3
   B. 4
   C. 6
   D. nullptr
   Answer: B. This loop returns the second middle on even lengths.

3. Why must fast and slow meet if there is a cycle?
   A. Luck
   B. Inside the loop, fast gains exactly one node per step, so the gap shrinks to 0
   C. They start together
   D. The list is sorted
   Answer: B. The gap can't jump over 0 because it shrinks by 1 each step.

## Practice

**Trace by hand.** List `1 2 3 4 5 6 7`. Find the 2nd node from the end with a lead pointer. Show both pointers each step.

Solution:

Move lead 2 steps → lead at 3, trail at 1.
Then step both: (4,2) (5,3) (6,4) (7,5) (null,6). Answer: **6**.


**Implement it.** Return the node where a cycle begins (Linked List Cycle II).

Hint: After slow and fast meet, move one pointer back to head. Step both one at a time; they meet at the cycle's start.

**Problems:**

- [Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/) (easy). Hint: This page's `middle()`.
- [Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/) (easy). Hint: Floyd. Check `fast && fast->next` in the loop condition.
- [Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/) (medium). Hint: Use a dummy node and stop the trail one node early so you can unlink.
- [Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/) (medium). Hint: Meet, reset one pointer to head, then walk both at speed 1.

## Mastery checklist

- [ ] I can find the middle of a linked list in one pass.
- [ ] I can find the n-th node from the end in one pass.
- [ ] I can detect a cycle with Floyd's algorithm and explain why it works.


---

# LU.5 Monotonic Stack

> A stack kept in sorted (decreasing) order answers "next greater element" and "how far away is it" for every index in one O(n) pass.

Chapter: Level Up: Problem Patterns · ~50 min · hard · optional, not on the exam
URL: https://dsa.fetehadin.com/learn/monotonic-stack

## Mental model

People stand in a line, all looking right. For each person, who is the **first taller person** they can see?

Walk the line left to right with a **stack of people still waiting** for a taller person. Keep it **decreasing**: tallest at the bottom. When a new person arrives, every shorter person at the top of the stack has just found their answer: **pop** them and record it. Then push the newcomer.

```cpp
while (!st.empty() && a[st.top()] < a[i]) {
    ans[st.top()] = a[i];          // next greater
    span[st.top()] = i - st.top(); // how far away
    st.pop();
}
st.push(i);
```

Each index is pushed once and popped at most once, so the whole thing is **O(n)**.

- **Equal values**: with `<`, an equal height does not count as taller. Use `<=` if it should.
- **Circular arrays**: loop `i` from 0 to 2n − 1 and use `i % n`, pushing only during the first lap.
- **Store indices**, not values, so you can compute distances.

Also see the **LeetCode monotonic problems**: Car Fleet, Remove K Digits, Sum of Subarray Minimums, 132 Pattern, Shortest Subarray with Sum ≥ K (monotonic **queue**).

> Built on Chapter 5 (stacks). Not on the exam.

## C++ code: monotonic-stack.cpp

```cpp
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> nextGreater(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;                                    // indices; values decreasing
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {   // a[i] answers everyone smaller
            ans[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

vector<int> waitDays(const vector<int>& a) {          // span: how far away is the next greater?
    vector<int> d(a.size(), 0);
    stack<int> st;
    for (int i = 0; i < (int)a.size(); i++) {
        while (!st.empty() && a[st.top()] < a[i]) { d[st.top()] = i - st.top(); st.pop(); }
        st.push(i);
    }
    return d;
}

vector<int> nextGreaterCircular(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;
    for (int i = 0; i < 2 * n; i++) {                 // loop twice to wrap around
        while (!st.empty() && a[st.top()] < a[i % n]) { ans[st.top()] = a[i % n]; st.pop(); }
        if (i < n) st.push(i);
    }
    return ans;
}

void print(const char* label, const vector<int>& v) {
    cout << label;
    for (int x : v) cout << x << " ";
    cout << "\n";
}

int main() {
    vector<int> a = {2, 1, 3, 5, 6, 1};
    print("a:                ", a);
    print("next greater:     ", nextGreater(a));
    print("span (j - i):     ", waitDays(a));
    print("circular greater: ", nextGreaterCircular(a));
}
```

Expected output:

```text
a:                2 1 3 5 6 1 
next greater:     3 3 5 6 -1 -1 
span (j - i):     2 1 1 1 0 0 
circular greater: 3 3 5 6 -1 2
```

## Complexity

| Case | Cost |
| --- | --- |
| brute force (scan right from each i) | O(n²) |
| monotonic stack | O(n): each index pushed and popped once |

Space: O(n)

Pop on `<` and equal values do **not** answer each other; pop on `<=` and they do. For circular arrays, loop **twice** (i from 0 to 2n − 1, index i % n), pushing only in the first lap.

## Videos

- [Monotonic Stack Data Structure Explained](https://youtu.be/Dq_ObZwTY_Q) (AlgoMonster): The data structure itself, explained in under 6 minutes.
- [Daily Temperatures: Monotonic Stack](https://youtu.be/cTBiBSnjO3c) (NeetCode): NeetCode's Daily Temperatures, the span version of this page.

## Exam lens

Likely questions:

- Why is the monotonic stack O(n) despite the nested while loop?
- How does the answer change if you pop on `<=` instead of `<`?
- How do you handle a circular array?

Common mistakes:

- Storing values instead of indices, which loses the span (distance).
- Pushing during the second lap of a circular array.
- Forgetting that items left on the stack at the end have no answer (−1).

## Quick check

1. `2 1 3 5 6 1`: next greater element of index 1 (value 1)?
   A. 2
   B. 3
   C. 5
   D. -1
   Answer: B. The first bigger value to its right is 3.

2. Span (distance) for index 0 (value 2)?
   A. 1
   B. 2
   C. 3
   D. 0
   Answer: B. 3 is at index 2, which is 2 − 0 = 2 steps away.

3. Circular version: next greater for the last 1?
   A. -1
   B. 2
   C. 3
   D. 6
   Answer: B. Wrapping around, the first bigger value is the 2 at index 0.

## Practice

**Trace by hand.** Run next-greater on `2 1 3 5 6 1`. Write the stack (as values) after each i.

Solution:

- i0: `[2]` · i1: `[2 1]`
- i2: 3 pops 1 (ans 3) and 2 (ans 3) → `[3]`
- i3: pops 3 (ans 5) → `[5]` · i4: pops 5 (ans 6) → `[6]`
- i5: `[6 1]`, leftovers get −1

Answer: `3 3 5 6 -1 -1`, spans `2 1 1 1 0 0`.


**Implement it.** Compute the **previous smaller** element for every index.

Hint: Scan left to right with an increasing stack. Pop while the top is ≥ a[i]; the top that remains (if any) is the answer.

**Problems:**

- [Daily Temperatures](https://leetcode.com/problems/daily-temperatures/) (medium). Hint: This page's span version.
- [Car Fleet](https://leetcode.com/problems/car-fleet/) (medium). Hint: Sort by position descending; keep a stack of arrival times; a slower car ahead absorbs the faster ones behind.
- [Remove K Digits](https://leetcode.com/problems/remove-k-digits/) (medium). Hint: Increasing stack of digits. Pop a bigger digit while k > 0.
- [Sum of Subarray Minimums](https://leetcode.com/problems/sum-of-subarray-minimums/) (medium). Hint: For each i, find how far it is the minimum to the left and right (previous/next smaller). Use `<` on one side and `<=` on the other to avoid double counting.

## Mastery checklist

- [ ] I can run a monotonic stack by hand.
- [ ] I can compute next greater and its distance.
- [ ] I can handle equal values and circular arrays.