Data Structures

Every problem in Top Interview 150 is a question about data: where it lives, how fast you can reach it and what it costs to change it. Pick the right structure and most problems turn into a few lines. Pick the wrong one and you fight the problem the whole way. This chapter is the toolbox for the rest of the book.

• How to read this book
• Why C
• Big-O in five minutes
• Contiguous or linked
• Array and dynamic array
• String
• Linked list
• Stack
• Queue and deque
• Hash map and hash set
• Binary tree and BST
• Heap
• Graph
• Trie
• Cheat sheet
• Which one to reach for
• See them move: dsa-visual-c

How to read this book

The book follows the LeetCode Top Interview 150 study plan topic by topic. Chapter 1 is this introduction. Chapters 2 to 24 are the 23 topics of the plan, in the same order, from Array / String to Multidimensional DP.

Every problem in a chapter gets the same shape:

1. The idea: the one observation that cracks it, in a sentence or two.
2. The code: a clean solution in C, no tricks for the sake of tricks.
3. The cost: time and space, and why.
4. The trap: the edge case or mistake that usually costs a submission.

Why C

Every example in this book is in C. Not because C is the shortest way to pass a test, but because in C nothing happens behind your back. A higher-level language hands you a magic box: you call append or write map[key] = value and it just works, and the cost of that one line is hidden somewhere in a runtime you never read. In C there is no box. If memory grows, you wrote the realloc. If a key collides, you wrote the chain. If something is freed, you wrote the free.

That is exactly what Big-O is about. When the cost is on the screen, you stop guessing why a solution is slow. And once you have built a hash map by hand, you understand every hash map in every language.

A few things to know about C on LeetCode:

• Linked lists and trees come as struct ListNode and struct TreeNode, the same shapes used below.
• A function that returns an array allocates it with malloc and reports its length through int *returnSize. The judge frees it.
• There is no built-in hash map. For small keys (letters, digits, bounded numbers) a plain array is the hash map; for anything else you write one, or use uthash.h, which the LeetCode C environment includes.
• Locally, compile with sanitizers so memory bugs crash loudly instead of quietly: gcc -std=c11 -Wall -Wextra -g -fsanitize=address,undefined sol.c.

Big-O in five minutes

Big-O describes how the work grows when the input grows. It ignores constants and keeps the biggest term: 3n² + 10n + 7 is O(n²). You use it for two things: to compare two ideas before writing either, and to guess from the constraints which idea the problem wants.

A judge does roughly 10⁸ simple operations per second. Read the limit on n and you can usually tell the target complexity before you read the rest of the problem:

Space counts too. An extra hash map of n keys is O(n) space; a few variables are O(1). Many problems in the plan say "in place" or "O(1) extra space", which rules out the easy copy and pushes you towards pointers.

Contiguous or linked

Under every structure in this chapter there are only two ways to lay data out in memory.

contiguous (array)                  linked (list)
+----+----+----+----+----+          +----+---+    +----+---+    +----+---+
| 10 | 20 | 30 | 40 | 50 |          | 10 | *-+--->| 20 | *-+--->| 30 | / |
+----+----+----+----+----+          +----+---+    +----+---+    +----+---+
 [0]  [1]  [2]  [3]  [4]             data next
address of [i] = base + i * size    find [i] = follow i pointers

• Contiguous: elements sit side by side. Jumping to any index is one multiplication, and the CPU cache loves it. Inserting in the middle means shifting everything after it.
• Linked: each element points to the next. Inserting next to a node you already hold is a couple of pointer writes. Reaching the i-th element means walking there.

Stacks, queues, hash maps, heaps and graphs are all built from these two pieces. Knowing which one is underneath tells you what is cheap and what is not.

Array and dynamic array

A fixed block of equal-sized slots: int a[100], or malloc(n * sizeof(int)) when the size is known only at run time. A dynamic array keeps a capacity bigger than its size and, when it runs out, allocates a block twice as big and copies everything over. That doubling is why push is O(1) amortized. In C it is a dozen lines:

typedef struct {
    int *data;
    int size, cap;
} Vec;

void vec_push(Vec *v, int x) {
    if (v->size == v->cap) {
        v->cap = v->cap ? v->cap * 2 : 4;
        v->data = realloc(v->data, v->cap * sizeof *v->data);   /* the O(n) copy lives here */
    }
    v->data[v->size++] = x;
}

Reach for it when you need index access, when the input is already an array (most of the time), or when sorting first makes the problem easy. Most array tricks are about avoiding the O(n) shift: write from the end, keep a write pointer, or swap instead of delete.

Chapters: Array / String, Two Pointers, Sliding Window, Matrix (a 2D array), Intervals, Binary Search, Kadane's Algorithm, 1D DP.

String

In C a string is just an array of char that ends with a '\0' byte. There is no length stored anywhere: strlen walks the whole thing to find the end, so it is O(n). Put it in a loop condition and a linear scan quietly becomes quadratic. strcat has the same trap, it walks to the end before it appends.

/* O(n²): strlen runs on every iteration */
for (int i = 0; i < strlen(s); i++) { ... }

/* O(n): measure once */
int n = strlen(s);
for (int i = 0; i < n; i++) { ... }

• Keep the length yourself and write into a buffer with an index: out[len++] = c;, then out[len] = '\0'; once at the end. Remember the extra byte for '\0' when you malloc.
• A substring does not need a copy: a pointer and a length (s + i, k) is enough. Copying means malloc plus memcpy.
• For lowercase English letters a fixed array of 26 counts is the hash map:

int count[26] = {0};
for (const char *p = s; *p; p++)
    count[*p - 'a']++;

Palindromes, reversals and "valid" checks are two pointers walking towards each other.

Chapters: Array / String, Two Pointers, Sliding Window, Hashmap, Trie, Multidimensional DP.

Linked list

Nodes holding a value and a pointer to the next node (and, for a doubly linked list, the previous one). You only ever hold the head; everything else is reached by walking.

Three patterns solve almost every linked list problem in the plan:

• Dummy head: put a fake node before the head so deleting or inserting at the front is not a special case. In C it lives on the stack, no malloc: struct ListNode dummy = { .next = head }; and return dummy.next.
• Fast and slow pointers: one moves two steps, one moves one. They meet if there is a cycle; when fast reaches the end, slow is in the middle.
• Reverse in place: walk with prev, cur, next and flip one pointer per step.

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *reverseList(struct ListNode *head) {
    struct ListNode *prev = NULL, *cur = head;
    while (cur) {
        struct ListNode *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

Chapters: Linked List, and LRU Cache, which combines a hash map with a doubly linked list.

Stack

Last in, first out. Push on top, pop from the top, peek at the top, all O(1). A dynamic array with operations only at its end is already a stack.

push 1, push 2, push 3        pop -> 3

  | 3 |  <- top                 | 2 |  <- top
  | 2 |                         | 1 |
  | 1 |                         +---+
  +---+

In C a stack is an array and one index. That is all a stack ever is:

char stack[10000];
int top = 0;

stack[top++] = '(';          /* push  */
char c = stack[--top];       /* pop   */
char t = stack[top - 1];     /* peek  */
int empty = top == 0;

Reach for it when the most recent unfinished thing is the one you deal with next:

• matching brackets: push openers, pop when a closer arrives;
• evaluating expressions and Reverse Polish Notation;
• simplifying a path: push folder names, pop on ..;
• turning recursion into a loop, for example iterative DFS or tree traversal;
• a monotonic stack, kept increasing or decreasing, answers "next greater element" in one pass.

Chapters: Stack, Binary Tree General (iterative traversal), Graph General (iterative DFS).

Queue and deque

First in, first out. Enqueue at the back, dequeue at the front, both O(1). Built on a linked list or on a circular array where front and rear wrap around with % capacity. A deque lets you push and pop at both ends.

enqueue -> [ 4 | 3 | 2 | 1 ] -> dequeue
           rear          front

Reach for it for breadth-first search. A queue visits things in the order they were discovered, so it explores level by level and the first time BFS reaches a node is the shortest path in an unweighted graph. Process a tree level at a time by reading the queue size before the inner loop.

struct TreeNode *queue[10000];
int head = 0, tail = 0;
if (root) queue[tail++] = root;

while (head < tail) {
    int level = tail - head;                /* nodes on this level */
    for (int i = 0; i < level; i++) {
        struct TreeNode *node = queue[head++];
        if (node->left)  queue[tail++] = node->left;
        if (node->right) queue[tail++] = node->right;
    }
}

Chapters: Binary Tree BFS, Graph BFS, Graph General.

Hash map and hash set

The most used structure in interviews. A hash function turns a key into a bucket index; the value is stored in that bucket. Two keys landing in the same bucket is a collision, usually handled by chaining (each bucket is a small linked list). When the table gets too full it grows and rehashes, just like a dynamic array.

hash("cat") % 8 = 3
hash("dog") % 8 = 3      <- collision

bucket   0    1    2    3    4    5    6    7
         .    .    .    |    .    .    .    .
                        v
                     [cat:1] -> [dog:2]      chained in bucket 3

C has no hash map, so you see the whole machine: an array of buckets, a hash function, and a linked list in each bucket.

typedef struct Entry {
    int key, val;
    struct Entry *next;
} Entry;

#define BUCKETS 4096
Entry *table[BUCKETS];

unsigned hash(int key) { return (unsigned)key * 2654435761u % BUCKETS; }

Entry *find(int key) {
    for (Entry *e = table[hash(key)]; e; e = e->next)
        if (e->key == key) return e;
    return NULL;
}

A hash set is a hash map with keys only: "have I seen this?" in O(1). When the keys are small, skip all of this: bool seen[128] or int count[26] is a hash table whose hash function is the value itself.

Reach for it whenever you catch yourself writing a nested loop to find something. Two Sum is the classic: instead of checking every pair, store each number as you go and ask whether target - x is already in the map. O(n²) becomes O(n).

• counting: letters, words, frequencies, anagrams (sorted word or count tuple as the key);
• remembering a position: value → index;
• detecting repeats and cycles;
• caching results: memoization in DP is a hash map from state to answer.

Chapters: Hashmap, Sliding Window, Array / String, Graph General (visited set), 1D DP (memo).

Binary tree and binary search tree

A binary tree is nodes with at most two children, left and right. Almost every tree problem is solved by recursion: answer the question for the left subtree, answer it for the right, combine at the node.

struct TreeNode {
    int val;
    struct TreeNode *left, *right;
};

void inorder(struct TreeNode *node, int *out, int *n) {
    if (!node) return;
    inorder(node->left, out, n);
    out[(*n)++] = node->val;
    inorder(node->right, out, n);
}

        8
      /   \
     3     10
    / \      \
   1   6      14

preorder  (node, left, right): 8 3 1 6 10 14
inorder   (left, node, right): 1 3 6 8 10 14   <- sorted, because this is a BST
postorder (left, right, node): 1 6 3 14 10 8
level order (BFS):             8 | 3 10 | 1 6 14

A binary search tree adds one rule: everything in the left subtree is smaller than the node, everything in the right subtree is larger. That gives you:

• search, insert and delete in O(h), where h is the height: O(log n) when balanced, O(n) when it degrades into a line;
• an inorder traversal returns the values sorted, the key to most BST problems in the plan (k-th smallest, validate a BST, minimum difference).

Depth-first traversal uses the call stack, so it costs O(h) extra space. Breadth-first uses a queue and costs up to the width of the widest level.

Chapters: Binary Tree General, Binary Tree BFS, Binary Search Tree, Divide & Conquer.

Heap (priority queue)

A complete binary tree stored in a plain array, where every parent is smaller than its children (a min-heap) or larger (a max-heap). The smallest element is always at index 0. The children of index i are at 2i + 1 and 2i + 2, so no pointers are needed. C has no priority queue, so you write the sift yourself, and it is short:

void heap_push(int *h, int *n, int x) {
    int i = (*n)++;
    h[i] = x;
    while (i > 0 && h[(i - 1) / 2] > h[i]) {
        int p = (i - 1) / 2, t = h[p];
        h[p] = h[i];
        h[i] = t;
        i = p;
    }
}

Reach for it when you repeatedly need the smallest or largest of a changing set: the k-th largest element (keep a min-heap of size k), merging k sorted lists, the median of a stream (two heaps, one for each half).

Chapters: Heap, Divide & Conquer (merge k sorted lists).

Graph

Vertices joined by edges, directed or not, weighted or not. Trees, grids and linked lists are all special graphs. Two ways to store one:

• Adjacency list: for each vertex, the list of its neighbours. O(V + E) space, the default in interviews.
• Adjacency matrix: a V × V grid of booleans. O(V²) space, edge check in O(1), only worth it for small dense graphs.

A 2D grid is a graph too: each cell is a vertex and its up, down, left and right cells are the neighbours. Number of Islands is just "count the connected components" on that graph, and the grid itself can be the visited set:

void sink(char **grid, int rows, int cols, int r, int c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] != '1') return;
    grid[r][c] = '0';                       /* visited */
    sink(grid, rows, cols, r + 1, c);
    sink(grid, rows, cols, r - 1, c);
    sink(grid, rows, cols, r, c + 1);
    sink(grid, rows, cols, r, c - 1);
}

• DFS (stack or recursion): connected components, flood fill, cycle detection.
• BFS (queue): shortest path when every edge costs the same.
• Topological sort: order tasks with dependencies; if it cannot finish, there is a cycle (Course Schedule).
• Always keep a visited set, or a graph with a cycle loops forever.

BFS and DFS both touch every vertex and edge once: O(V + E).

Chapters: Graph General, Graph BFS, Backtracking.

Trie (prefix tree)

A tree where each edge is a character and each path from the root spells a prefix. A flag on the node marks the end of a full word.

insert "car", "cat", "do"

        (root)
        /    \
       c      d
       |      |
       a      o*
      / \
     r*  t*        * = end of a word

typedef struct Trie {
    struct Trie *next[26];
    bool end;
} Trie;

void trie_insert(Trie *t, const char *w) {
    for (; *w; w++) {
        int i = *w - 'a';
        if (!t->next[i]) t->next[i] = calloc(1, sizeof(Trie));
        t = t->next[i];
    }
    t->end = true;
}

Insert and lookup cost O(L) for a word of length L, no matter how many words are stored. Reach for it for "starts with" queries, autocomplete, and searching many words at once on a board (Word Search II).

Chapters: Trie, Backtracking.

Cheat sheet

* amortized   † when you already hold the node   ‡ average case

Which one to reach for

The wording of a problem usually gives the structure away.

See them move: dsa-visual-c

Reading about a hash collision is one thing; watching a key land in an occupied bucket and chain behind another is another. jrzayev/dsa-visual-c is a small C library I wrote, in the same language as this book, that runs each structure in the terminal and prints every step in colour: the resize when a dynamic array doubles, the bucket a key hashes to, the subtree a BST search walks into, the order BFS and DFS visit a graph.

git clone https://github.com/jrzayev/dsa-visual-c
cd dsa-visual-c
make
./dsa_demo

Pick a demo from the menu, or use it as a library in your own program:

#include "dsa_visual.h"

int main(void) {
    LinkedList *list = ll_create();
    ll_insert_back(list, 10);
    ll_insert_back(list, 20);
    ll_insert_front(list, 5);
    ll_visualize(list);
    ll_free(list);
    return 0;
}

What it covers, mapped to this chapter:

Heap and trie are not in the library yet; their chapters come with their own walkthroughs. You need a terminal with ANSI colours, and the animation speed is set by the usleep() calls in the source.

Next

Chapter 2 starts the plan with Array / String: 24 problems on the structure you will use the most. Most of them are one pass over the array with a pointer or two, and the cost table above is what tells you whether your idea is fast enough before you write it.