Week 1

Chapter 1: Fundamentals

Master the building blocks of data structures and algorithms: understand time complexity, implement essential data structures like stacks, queues, and hash maps, then conquer the most important sorting algorithms and learn how to customize them for any use case.

Chapter Overview

Every great programmer stands on a foundation of data structures and algorithms. Before you can solve complex problems, you need to understand how data is organized, how operations perform at scale, and which tools to reach for in different situations.

This chapter starts with Big O notation --- the universal language for reasoning about efficiency. You will learn to look at code and immediately estimate whether it will run in milliseconds or hours. Then you will build the fundamental data structures that appear in nearly every technical interview and production codebase: stacks, queues, and hash maps.

The second half focuses on sorting, one of the most studied problems in computer science. You will implement the simple quadratic sorts to understand the basics, then level up to merge sort and quick sort --- the divide-and-conquer algorithms that power real-world systems. Finally, you will learn to write custom comparators so you can sort anything by any criteria.

This chapter covers:

Big O Notation: Analyzing time and space complexity
Stacks & Queues: LIFO and FIFO data structures
Hash Maps: O(1) lookups with key-value pairs
Elementary Sorting: Bubble, selection, and insertion sort
Advanced Sorting: Merge sort and quick sort
Custom Comparators: Sorting with flexible criteria

Chapter Roadmap

Click any topic to jump in

Data Structures & Big O

The mental model: choosing how to organize data determines which operations are cheap. Big O lets you compare choices before you code.

What Are Data Structures?Big O NotationSpace Complexity

Complexity drives choice of structure

Stacks and queues are the two simplest linear structures built on arrays or linked lists.

Stacks (LIFO)

Last-in-first-out storage that mirrors the call stack and solves matching problems like valid parentheses.

LIFO Principle and Core OperationsThe Call StackValid Parentheses Problem

Queues (FIFO)

First-in-first-out storage that powers BFS, level-order traversal, and rate limiting via sliding windows.

FIFO Principle and Core OperationsBFS and Level-Order TraversalRecent Counter Problem

From linear scans to hashed lookups

Hash Maps

Average-case $O(1)$ lookups via hashing — the workhorse of counting, deduping, and complement lookups.

Key-Value Storage and Hash FunctionsCollision HandlingTwo Sum Using Hash Map

From storage to ordering

Once you can store and retrieve, the next question is how to order data efficiently.

Sorting Basics

Bubble, selection, insertion — the $O(n^2)$ baseline. Understanding stability matters more than raw speed here.

Bubble SortSelection SortInsertion SortStability in Sorting

Merge & Quick Sort

Divide and conquer sorts that reach $O(n \log n)$ — merge sort is stable, quick sort is faster in practice.

Divide and ConquerMerge SortQuick Sort

From $O(n^2)$ to $O(n \log n)$

Custom Comparators

Sorting by arbitrary criteria — key functions, multi-key, and the strict-weak-ordering contract.

Sorting with Key FunctionsMulti-Key SortingCustom Comparison Functions

Data structures are specialized formats for organizing and storing data so that operations like searching, inserting, and deleting can be performed efficiently. Choosing the right data structure can mean the difference between a program that runs in seconds and one that takes hours.

Big O notation provides a way to describe how an algorithm's runtime grows as the input size increases. It strips away constants and lower-order terms to focus on the dominant factor.

In this topic

1What Are Data Structures?

2Big O Notation

3Space Complexity

1 of 3

What Are Data Structures?

A data structure is a way of organizing data in memory so that particular operations can be performed efficiently. Different data structures excel at different operations: arrays provide O(1) random access, linked lists provide O(1) insertion at the head, hash maps provide O(1) average-case lookups. Choosing the right data structure is the first and most important algorithmic decision you make.

Mathematical Intuition

A data structure is a triple $(S, \text{Ops}, \text{Costs})$ where $S$ is the set of states, $\text{Ops}$ are the supported operations, and $\text{Costs}: \text{Ops} \to \mathbb{R}_{\ge 0}$ is the cost model. Choosing a structure means minimising $\sum_{i} f_i \cdot c(op_i)$ where $f_i$ is how often each operation is performed. For a workload with $N$ lookups and $M$ inserts, a hash set costs $O(N + M)$ while a sorted array costs $O(N \log N + M \cdot N)$ — the right choice can change the total by a polynomial factor.

Example:

Compare the time complexity of finding an element in an unsorted list vs. a sorted list vs. a hash set. Which would you choose if you need to check membership millions of times?

2 of 3

Big O Notation

Big O notation describes the upper bound of an algorithm's growth rate. The most common complexities, from fastest to slowest: O(1) constant --- hash map lookup, O(log n) logarithmic --- binary search, O(n) linear --- scanning an array, O(n log n) linearithmic --- merge sort, O(n^2) quadratic --- nested loops. When analyzing code, count the number of times the innermost operation executes as a function of n.

Mathematical Intuition

$f(n) = O(g(n))$ iff there exist constants $c > 0$ and $n_0 \ge 0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$ . This definition ignores constants and lower-order terms because for any polynomial $a n^k + b n^{k-1} + \dots$ , the dominant term eventually dwarfs the rest: $\lim_{n \to \infty} \frac{a n^k}{a n^k + b n^{k-1}} = 1$ . Big O is an upper bound on growth, giving a machine-independent way to compare algorithms.

Example:

What is the time complexity of the following code?

for i in range(n):
    for j in range(n):
        print(i, j)

3 of 3

Space Complexity

Space complexity measures how much additional memory an algorithm uses relative to input size. An in-place algorithm like insertion sort uses O(1) extra space, while merge sort requires O(n) extra space for the temporary arrays. When memory is constrained, space complexity matters as much as time complexity.

Mathematical Intuition

Space complexity counts the extra memory used as a function of input size $n$ , excluding the input itself. For a recursive algorithm with recursion depth $d$ and local variables of size $s$ , space is $O(d \cdot s)$ because the call stack holds $d$ frames simultaneously. Example: merge sort uses $O(n)$ auxiliary space for the merge buffer plus $O(\log n)$ for recursion, totalling $O(n)$ .

Example:

What is the space complexity of creating a new list that contains the squares of every element in the input list?

Blogs

Big-O Cheat Sheet Asymptotic Notation — Khan Academy

Binary Search

Chapter 1: Fundamentals

Chapter Overview

Chapter Roadmap

Data Structures & Big O

Stacks (LIFO)

Queues (FIFO)

Hash Maps

Sorting Basics

Merge & Quick Sort

Custom Comparators

Data Structures Introduction

In this topic

What Are Data Structures?

Big O Notation

Space Complexity

Stacks

Queues

Hash Maps

Sorting Basics

Merge Sort & Quick Sort

Custom Comparators