# Data Structures and Algorithms

> Data structures and algorithms, practiced in TypeScript, at https://datastructuresandalgorithms.com

Data structures and algorithms are how a program stores values and the steps it uses to work on those values. This site is a free four-week TypeScript course: the lesson sits beside a code editor, tests run on submit, and progress stays on the account. There is no payment and no trial.

## Canonical

https://datastructuresandalgorithms.com

## What the course covers

- Week 1: complexity, arrays, hash maps, two pointers, sliding windows
- Week 2: linked lists, stacks, queues, recursion, binary search, merge sort
- Week 3: trees, binary search trees, heaps, graphs
- Week 4: greedy choices, backtracking, dynamic programming, tries

Short lessons, with more than one exercise on each, and a follow-up step after every idea. Written for people who already write TypeScript.

## Answers

Data structures and algorithms are the arrangements of values (arrays, hash maps, trees, graphs) and the procedures that use them (search, sort, traversal, dynamic programming).

The course is 100% free and takes four weeks. A first passing submission earns three stars.

## Articles

- [All articles](https://datastructuresandalgorithms.com/articles): Index of every explainer, grouped by category.

## Categories

- [Cost](https://datastructuresandalgorithms.com/articles/categories/cost): These articles name how the number of steps changes as the input grows, and how much extra memory an algorithm needs. They cover Big O, constant, logarithmic, linear, linearithmic, and quadratic time, loop invariants, amortized cost, and trading space for time. A lesson that writes O(n) or O(n²) is pointing at one of these.
- [Arrays](https://datastructuresandalgorithms.com/articles/categories/arrays): An array keeps values in index order, so a known index is a direct read. These articles start from that layout, then explain the scans the lessons build on it: two pointers moving inward, a window that grows and shrinks, a prefix sum, and rotating values without losing their order.
- [Hash maps](https://datastructuresandalgorithms.com/articles/categories/hash-maps): A hash map stores a value under a key and finds it without scanning the whole collection. These articles explain the hash that chooses a bucket, what happens when two keys land in the same bucket, and the frequency count the lessons use to answer how many times a value appears.
- [Linear structures](https://datastructuresandalgorithms.com/articles/categories/linear-structures): These articles are about values kept in a line, where the useful end matters more than a random index. A linked list is walked by following pointers. A stack, and the call stack, give back the latest value first. A queue gives back the earliest. A deque uses both ends.
- [Search and sort](https://datastructuresandalgorithms.com/articles/categories/search-and-sort): Search finds one value. Sort puts every value in order so a later search can discard half the range. These articles cover recursion, binary search and its boundaries, bubble sort, merge sort, and quicksort, including how to choose among them and the off-by-one errors a half-open range invites.
- [Trees and graphs](https://datastructuresandalgorithms.com/articles/categories/trees-and-graphs): A tree is a graph with one path between any two nodes. These articles cover that shape, binary search trees, balance, heaps, and the walks that visit every node. They also cover general graphs: adjacency lists, breadth-first and depth-first search, Dijkstra, directed acyclic graphs, and disjoint-set union.
- [Patterns](https://datastructuresandalgorithms.com/articles/categories/patterns): A pattern is a way of deciding the next step when the structure alone does not settle it. These articles cover taking the best local choice, searching by trying a branch and undoing it, storing an answer you will need again, filling a table from smaller subproblems, and a trie that shares prefixes.

## Article pages

### Cost

- [What Is Big O? How Algorithm Cost Grows as Input Grows](https://datastructuresandalgorithms.com/articles/big-o): Big O describes how the number of steps grows as the input grows, ignoring constant factors and one machine's speed. An O(n) scan doubles when the input doubles; an O(n²) pair of loops grows much faster.
- [What Does O(1) Mean? Constant-Time Work That Stays Flat](https://datastructuresandalgorithms.com/articles/constant-time): O(1) means work stays flat as input grows. Reading a known array slot is constant time; dynamic-array append is O(1) amortized across a sequence of pushes.
- [What Is Linear Time O(n)? One Pass and Linear Search](https://datastructuresandalgorithms.com/articles/linear-time): O(n) means one pass over the input: twice the data, about twice the work. Linear search is that scan, and it looks at every element when the target is missing.
- [What Is O(n²) Quadratic Time? Nested Loops and Pairs](https://datastructuresandalgorithms.com/articles/quadratic-time): O(n²) is the cost of looking at the other elements for each element, usually a loop inside a loop. Ten items are a small triangle of comparisons; a thousand items are on the order of a million.
- [What Is a Loop Invariant? Proving Each Iteration Is Correct](https://datastructuresandalgorithms.com/articles/loop-invariants): A loop invariant is a statement that is true before or after every iteration. Establish it before the loop, preserve it through each update, and use it at termination to explain why the result is correct.
- [What Is Amortized Analysis? Cost Across a Sequence of Operations](https://datastructuresandalgorithms.com/articles/amortized-analysis): Amortized analysis bounds the total cost of a sequence and divides that cost across its operations. It explains why an occasional O(n) dynamic-array resize can coexist with O(1) amortized append.
- [What Is O(log n)? Logarithmic Time and Binary Search](https://datastructuresandalgorithms.com/articles/logarithmic-time): O(log n) means each step throws away a fraction of what remains. Binary search on a million sorted values is about twenty comparisons, and a balanced tree has about that many levels.
- [What Is O(n log n)? Linearithmic Time and Sorting](https://datastructuresandalgorithms.com/articles/linearithmic-time): O(n log n) is linear work repeated about log n times, which is the usual cost of a good sort. You can sometimes beat it when the input is already ordered, as with sorted squares.
- [What Is the Space-for-Time Tradeoff in Algorithms?](https://datastructuresandalgorithms.com/articles/space-for-time): Spending extra memory can turn a scan into a lookup. The extra space is part of the cost: say O(n) time and O(n) extra space, not the time on its own.
- [What Is Auxiliary Space? Measuring an Algorithm's Extra Memory](https://datastructuresandalgorithms.com/articles/auxiliary-space): Auxiliary space is the memory an algorithm uses beyond its input. A few counters are O(1), a table that grows with the input is O(n), and recursive call-stack frames count too.
- [How Do You Enumerate Every Index Pair Exactly Once?](https://datastructuresandalgorithms.com/articles/pair-enumeration): Pair enumeration uses i < j to exclude self-pairs and reversed duplicates. Its triangular iteration count explains the quadratic cost.

### Arrays

- [How Arrays Support Fast Indexing](https://datastructuresandalgorithms.com/articles/contiguous-arrays): An array gives each element an integer index, so reading a known position is O(1). Dense arrays scan efficiently, while insertions near the front are O(n) because later elements must move.
- [How Do You Rotate an Array Left?](https://datastructuresandalgorithms.com/articles/rotating-an-array): A left rotation moves a prefix to the back without changing relative order. Reducing the step count modulo the length avoids repeated shifts and gives an O(n) solution.
- [What Is the Two-Pointer Technique on a Sorted Array?](https://datastructuresandalgorithms.com/articles/two-pointers): Two pointers maintain two meaningful indexes and move them according to an invariant. For sorted squares, the largest remaining square must be at one of the two ends.
- [What Is a Sliding Window?](https://datastructuresandalgorithms.com/articles/sliding-windows): A sliding window represents one contiguous range with two boundaries. Reusing the previous range turns fixed-width sums into O(n), while variable windows require a condition that moves boundaries monotonically.
- [How Prefix Sums Answer Range Queries](https://datastructuresandalgorithms.com/articles/prefix-sums): A prefix-sum array precomputes totals from the start. After O(n) preprocessing, any half-open range sum can be answered in O(1) by subtracting two prefixes.
- [How Do Inward Pointers Move? Ends, Palindromes, and Pair Sums](https://datastructuresandalgorithms.com/articles/inward-pointers): Inward pointers start at the two ends of an array and move toward the middle. A rule decides which end moves, and each step drops one index.
- [What Is a Variable Window? Growing and Shrinking a Subarray](https://datastructuresandalgorithms.com/articles/variable-windows): A variable window grows on the right and shrinks on the left. With zeros and positive numbers, the left edge only moves forward, so the scan stays linear.
- [Why Does an Array Middle Edit Shift Elements?](https://datastructuresandalgorithms.com/articles/shifting-array-elements): A contiguous array keeps indexes adjacent, so insertion or deletion in the middle must copy the tail while direct indexed access remains constant-time.

### Hash maps

- [How a Hash Map Remembers What You Have Already Seen](https://datastructuresandalgorithms.com/articles/hash-maps): A hash map associates unique keys with values. Expected O(1) lookup can replace a repeated scan, as the one-pass Two Sum algorithm demonstrates.
- [What Is a Hash Collision? Why O(1) Is Only Expected](https://datastructuresandalgorithms.com/articles/collisions): A collision occurs when distinct keys select the same bucket. Correct collision resolution preserves results but can increase lookup time.
- [What Is a Frequency Count? Tallying Values in One Pass](https://datastructuresandalgorithms.com/articles/frequency-counts): A frequency count stores how many times each value has appeared. One pass updates the tally, and a tie keeps the value that showed up first.

### Linear structures

- [What Is a Linked List? Pointers Instead of Indexes](https://datastructuresandalgorithms.com/articles/linked-lists): A linked list stores each value in a node with a pointer to the next node. You cannot jump to an index, but rewiring a pointer you already hold is O(1).
- [What Is a Stack? Last-In First-Out and Bracket Matching](https://datastructuresandalgorithms.com/articles/stacks): A stack is last in, first out: push and pop touch only the most recent item, both O(1) at the end of an array. Bracket matching uses that order, because a counter cannot remember which opener is still waiting.
- [What Is the Call Stack? Frames, Returns, and Recursion](https://datastructuresandalgorithms.com/articles/call-stack): The call stack is the stack the runtime uses for calls. Each call pushes a frame and each return pops it, which is why recursion without a base case overflows instead of spinning in one loop.
- [What Is a Queue? FIFO Order, Enqueue, and Dequeue](https://datastructuresandalgorithms.com/articles/queues): A queue is first in, first out: enqueue joins the back and dequeue leaves from the front. Breadth-first search is that rule with vertices as the payload, and Array.shift on the front is O(n).
- [What Is a Deque? Constant-Time Access at Both Ends](https://datastructuresandalgorithms.com/articles/deques): A deque is a double-ended queue: values can enter or leave at either end. A doubly linked implementation makes all four end operations O(1), supporting sliding windows and both queue and stack behaviour.
- [What Are the Three Pointers in a Linked-List Reversal?](https://datastructuresandalgorithms.com/articles/three-pointers): Reversing a linked list keeps previous, current, and the next node you are about to lose. You save next before you overwrite current.next.
- [How Do Slow and Fast Pointers Measure a Linked List?](https://datastructuresandalgorithms.com/articles/linked-list-runner-pointers): Runner pointers turn relative movement into distance: one-and-two-step speeds find a middle, while a fixed head start finds a node from the end.
- [How Does a Monotonic Stack Find the Next Greater Value?](https://datastructuresandalgorithms.com/articles/next-greater-values): A monotonic stack keeps unresolved indexes in decreasing-value order. Each later value resolves every smaller value on top.

### Search and sort

- [What Is Recursion? Smaller Copies and a Base Case](https://datastructuresandalgorithms.com/articles/recursion): Recursion solves a smaller copy of the same problem and combines what comes back. One call, the base case, has to stop without calling again, or the call stack grows until it overflows.
- [What Is Binary Search? Throw Away Half of a Sorted Array](https://datastructuresandalgorithms.com/articles/binary-search): Binary search compares the target with the middle of a sorted array and throws away half. Keep an invariant for where the target can still sit, and return -1 when that range is empty.
- [Why Is Bubble Sort O(n²)? Neighbour Swaps Until It Settles](https://datastructuresandalgorithms.com/articles/bubble-sort): Bubble sort swaps neighbours until a pass makes no swaps. It is easy to get right and quadratic, so it is a contrast, not the sort to reach for.
- [How Does Merge Sort Stay O(n log n) in Every Case?](https://datastructuresandalgorithms.com/articles/merge-sort): Merge sort splits the array, sorts the halves, and merges two sorted runs with two pointers. That is O(n log n) time and O(n) extra memory in every case you implement here.
- [How Does Quicksort Partition Around a Pivot? (Optional Enrichment)](https://datastructuresandalgorithms.com/articles/quicksort): Optional enrichment: quicksort partitions values around a pivot, then recursively sorts the two sides. Balanced partitions give O(n log n) time, while repeated extreme pivots give O(n²).
- [What Is an Off-by-One Error? Ranges, Remainders, and Indexes](https://datastructuresandalgorithms.com/articles/off-by-one): An off-by-one error is a boundary that is one step away from the index you meant. Empty ranges, a zero remainder, and a match you fail to exclude are the usual places it shows up.
- [What Is a Sorted Run? The Merge Step Between Two Halves](https://datastructuresandalgorithms.com/articles/sorted-runs): A sorted run is a slice that is already in order. Merge sort's merge step takes two runs and writes one, using a pointer on each.
- [What Changes When Recursion Makes Two Calls?](https://datastructuresandalgorithms.com/articles/recursive-branching): Two recursive calls create a branching call tree. Correct indexing establishes the base values; overlapping branches explain exponential recomputation.
- [How Does Binary Search Find the First or Last Equal Index?](https://datastructuresandalgorithms.com/articles/binary-search-boundaries): Boundary binary search records a match and continues on one side. Inclusive bounds must move past mid so the candidate range strictly shrinks.
- [How Do You Choose Between Checking, Bubble Sort, and Merge Sort?](https://datastructuresandalgorithms.com/articles/choosing-a-sort): Checking order is linear, bubble sort is quadratic, and merge sort is linearithmic. The task contract determines which operation is needed.

### Trees and graphs

- [What Is a Tree? Roots, Leaves, and Depth in Nodes](https://datastructuresandalgorithms.com/articles/trees): A tree is a connected, acyclic hierarchy with one root and one parent per non-root node. This course's maxDepth counts nodes on the longest root-to-leaf path: an empty tree is 0 and a single node is 1.
- [What Is a Binary Search Tree? Left Smaller, Right Larger](https://datastructuresandalgorithms.com/articles/binary-search-trees): A binary search tree keeps every value in the left subtree smaller than the node and every value in the right subtree larger. This course leaves duplicates out, and search costs the height, not automatically log n.
- [What Is a Balanced Tree? AVL, Red-Black, and Height](https://datastructuresandalgorithms.com/articles/balanced-trees): AVL and red-black trees enforce different invariants with rotations and, for red-black trees, recoloring so height remains O(log n). A skewed BST is a list drawn vertically.
- [What Is a Binary Heap? Min, Max, and the kth Largest](https://datastructuresandalgorithms.com/articles/heaps): A heap is a complete binary tree stored in an array, with the minimum or the maximum at the root. Updating that extreme is O(log n), which is enough to find the kth largest without fully sorting.
- [How Do Preorder, Inorder, and Postorder Traverse a Tree?](https://datastructuresandalgorithms.com/articles/tree-traversals): Depth-first tree traversals differ only in when they visit the current node: preorder before both children, inorder between them, and postorder after them. Inorder lists a binary search tree in sorted order.
- [What Is a Graph? Vertices, Undirected Edges, and Cycles](https://datastructuresandalgorithms.com/articles/graphs): A graph is vertices plus edges. A tree is a graph with no cycles; a general graph can loop, so a search has to remember where it has been. This course uses undirected edges.
- [What Is an Adjacency List? Neighbours of Each Vertex](https://datastructuresandalgorithms.com/articles/adjacency-lists): An adjacency list stores, for each vertex, the vertices one edge away. One pass over the edge list builds it, and a search asks it for neighbours.
- [How Does Breadth-First Search Find the Fewest Edges?](https://datastructuresandalgorithms.com/articles/breadth-first-search): Breadth-first search uses a queue to walk neighbours, then neighbours of neighbours. When every edge costs the same, the first time you reach a vertex is the fewest edges.
- [How Does Depth-First Search Explore One Branch First?](https://datastructuresandalgorithms.com/articles/depth-first-search): Depth-first search uses a stack or recursion to finish one branch before the others. It answers reachability, not fewest edges.
- [What Is Dijkstra's Algorithm for Weighted Shortest Paths?](https://datastructuresandalgorithms.com/articles/dijkstra): Enrichment: Dijkstra finds shortest paths when edges have different non-negative costs. A heap always extends the cheapest path so far. The current exercises do not require an implementation.
- [How Do Directed Cycles and Topological Order Work?](https://datastructuresandalgorithms.com/articles/directed-acyclic-graphs): Enrichment: a directed acyclic graph has a topological order in which every edge points forward. Kahn's algorithm removes zero-indegree vertices; leftovers prove a directed cycle.
- [What Is Disjoint-Set Union? Tracking Connected Components](https://datastructuresandalgorithms.com/articles/disjoint-set-union): Enrichment: disjoint-set union maintains groups under repeated merges. Path compression and union by size make connectivity checks effectively constant-time across a long sequence.
- [How Do Heap Indexes Work? Parent and Child Arithmetic](https://datastructuresandalgorithms.com/articles/heap-indexes): A binary heap stores a complete tree in an array. The parent and the children of index i are arithmetic, not pointers.
- [What Is a Visited Set? Stopping a Graph Search from Looping](https://datastructuresandalgorithms.com/articles/visited-sets): A visited set remembers vertices a search has already queued. Without it, a cycle in an undirected graph makes the walk repeat forever.
- [How Does Insertion Order Determine BST Shape?](https://datastructuresandalgorithms.com/articles/bst-insertion-shape): A binary search tree preserves key order but not balance. Insertion order can produce a short tree or a linear spine.

### Patterns

- [When Is a Greedy Choice Safe? Interval Scheduling](https://datastructuresandalgorithms.com/articles/greedy-choices): A greedy algorithm commits to a local choice only when a proof shows that choice cannot make the final answer worse. Interval scheduling demonstrates the exchange argument.
- [What Is Backtracking? Choose, Explore, Then Undo](https://datastructuresandalgorithms.com/articles/backtracking): Backtracking performs depth-first search over decisions. It chooses, explores, and restores state before trying the next choice.
- [What Is Dynamic Programming? Overlapping Subproblems](https://datastructuresandalgorithms.com/articles/dynamic-programming): Dynamic programming defines states, a recurrence, and base cases, then evaluates each overlapping subproblem once.
- [What Is Memoisation? Caching an Overlapping Answer](https://datastructuresandalgorithms.com/articles/memoisation): Memoisation is top-down dynamic programming: cache a function's result by its complete state so repeated recursive calls become lookups.
- [What Is a Trie? A Prefix Tree for Shared Word Paths](https://datastructuresandalgorithms.com/articles/tries): A trie stores one character per edge. Shared prefixes share paths, making exact-word and prefix lookup proportional to query length.
- [What Is a Half-Open Interval? Why Touching Meetings Do Not Overlap](https://datastructuresandalgorithms.com/articles/half-open-intervals): A half-open interval includes the start and excludes the end. Two meetings that touch at that endpoint do not overlap, which is the rule interval scheduling relies on.
- [What Is a Permutation? Orderings from Choose, Explore, Undo](https://datastructuresandalgorithms.com/articles/permutations): A permutation is an ordering of values. Backtracking builds it by choosing an unused value, exploring, then undoing, and a copy of the path is what you save.
- [What Is Tabulation? Filling a Dynamic-Programming Table Upward](https://datastructuresandalgorithms.com/articles/tabulation): Tabulation writes answers from the base case toward the size you were asked for. Each cell is one sentence: the answer for this size, built from smaller cells.
- [How Do Trie Node Counts Measure Shared Prefixes?](https://datastructuresandalgorithms.com/articles/shared-prefix-counts): A count on each trie node records how many inserted words pass through it. Prefix queries and longest common prefixes then become path walks.