Data Structures

Every algorithm in this series depends on a data structure doing its job efficiently — this is the lookup card for the 10 that show up most in interviews.

• Covers arrays, hash structures, stack, queue, heap, linked list, binary tree, trie, graph, and union find with exact Java API and complexity tables
• Each entry has key operations + Big O, when to reach for it, Java usage snippets, real scenario examples, and gotchas
• Use this alongside the pattern guides — patterns tell you the technique, this tells you the mechanics of the structure underneath

Array

A fixed-size contiguous block of memory with O(1) index access. int[] is a true array; ArrayList<Integer> is a resizable wrapper around one.

Operations

Space: O(n)

When to Reach For It

• Input is already an array — work with it in place
• Need O(1) random access by index
• Prefix sum, two pointer, sliding window — all live on arrays
• Fixed-range counting: 26 letters → int[26], digits → int[10]

Java

Copy// Fixed array
int[] arr = new int[5];                         // [0, 0, 0, 0, 0]
int[] filled = {1, 2, 3, 4, 5};
Arrays.sort(arr);                               // O(n log n)
Arrays.fill(arr, -1);                           // fill all with -1

// Dynamic list
List<Integer> list = new ArrayList<>();
list.add(10);
list.get(0);                                    // 10
list.size();
Collections.sort(list);

// 2D array
int[][] grid = new int[3][4];                   // 3 rows, 4 cols

Scenarios

Copy// Prefix sum — build once in O(n), answer range queries in O(1)
int[] prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}
int rangeSum = prefix[r + 1] - prefix[l];       // sum of nums[l..r]

Copy// Frequency count with fixed range
int[] freq = new int[26];
for (char c : s.toCharArray()) {
    freq[c - 'a']++;
}

Gotchas

• int[] cannot be used with generics — use Integer[] or List<Integer> when a collection is needed
• Arrays.sort() on primitives uses dual-pivot quicksort — no worst-case guarantee unlike Collections.sort()
• Assignment copies the reference, not the data — use Arrays.copyOf(arr, arr.length) to clone

HashMap / HashSet

HashMap maps keys to values; HashSet stores unique keys only. Both give O(1) average for all core operations.

Operations

Space: O(n). Worst case O(n) per op occurs with hash collisions — rare in practice with Java's default hash.

When to Reach For It

• Count frequencies of elements
• Check membership or detect duplicates in O(1)
• Cache computed results (memoization in DP)
• Group elements by a computed key (anagram grouping, index grouping)
• Two Sum style: "have I seen the complement before?"

Java

Copy// HashMap
Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.get("a");                                   // 1
map.getOrDefault("b", 0);                       // 0 — always prefer over null check
map.containsKey("a");                           // true
map.remove("a");

for (Map.Entry<String, Integer> e : map.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}

// HashSet
Set<Integer> set = new HashSet<>();
set.add(1);
set.contains(1);                                // true
set.remove(1);

Scenarios

Copy// Frequency count
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.put(c, freq.getOrDefault(c, 0) + 1);
}

Copy// Two Sum complement check
Map<Integer, Integer> seen = new HashMap<>();   // value → index
for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (seen.containsKey(complement)) {
        return new int[]{seen.get(complement), i};
    }
    seen.put(nums[i], i);
}

Copy// Group by computed key
Map<String, List<String>> groups = new HashMap<>();
for (String word : words) {
    char[] chars = word.toCharArray();
    Arrays.sort(chars);
    String key = new String(chars);
    groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}

Gotchas

• Always use getOrDefault — a null check + put is longer and error-prone
• HashMap allows one null key; iteration order is not guaranteed — use LinkedHashMap if insertion order matters
• contains() on a List is O(n) — if you're checking membership in a loop, put it in a HashSet first
• For Map<int[], ...> — arrays don't override equals/hashCode. Use Arrays.toString(arr) as the key instead

Stack

Last-in, first-out. Use Deque<T> backed by ArrayDeque<T> — the legacy Stack<> class is synchronized and slow.

Operations

Space: O(n)

When to Reach For It

• Matching or validating nested structures (brackets, tags)
• "Next greater / smaller element" problems (monotonic stack)
• Iterative DFS as an explicit alternative to recursion
• Undo / redo, call stack simulation, expression evaluation

Java

CopyDeque<Integer> stack = new ArrayDeque<>();
stack.push(1);                                  // addFirst — top of stack
stack.push(2);
stack.peek();                                   // 2 — top, no remove
stack.pop();                                    // 2 — removes top
stack.isEmpty();                                // false

Scenarios

Copy// Bracket matching
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
    if (c == '(') {
        stack.push(c);
    } else if (!stack.isEmpty()) {
        stack.pop();
    } else {
        return false;
    }
}
return stack.isEmpty();

Copy// Monotonic decreasing stack — next greater element
int[] result = new int[nums.length];
Deque<Integer> stack = new ArrayDeque<>();      // stores indices
for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        result[stack.pop()] = nums[i];
    }
    stack.push(i);
}

Copy// Iterative DFS on a tree
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    process(node);
    if (node.right != null) {
        stack.push(node.right);
    }
    if (node.left != null) {
        stack.push(node.left);
    }
}

Gotchas

• push/pop/peek are the stack-style names on Deque — prefer them over offerFirst/pollFirst for clarity
• Always check isEmpty() before peek() or pop() — both throw on an empty deque
• For monotonic stack: store indices not values so you can update a result array by position

Queue

First-in, first-out. Use Deque<T> backed by ArrayDeque<T> — same class as stack, different methods.

Operations

Space: O(n)

When to Reach For It

• BFS on trees (level-order traversal)
• BFS on graphs — shortest path in unweighted graphs
• Sliding window maximum (monotonic deque)
• Any "process in the order received" scenario

Java

CopyDeque<Integer> queue = new ArrayDeque<>();
queue.offer(1);                                 // addLast — enqueue
queue.offer(2);
queue.peek();                                   // 1 — front, no remove
queue.poll();                                   // 1 — removes front
queue.isEmpty();                                // false

Scenarios

Copy// BFS level-order — capture level size before inner loop
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
    int size = queue.size();                    // freeze this level's count
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        if (node.left  != null) { queue.offer(node.left);  }
        if (node.right != null) { queue.offer(node.right); }
    }
}

Copy// BFS shortest path on a grid
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{startR, startC});
visited[startR][startC] = true;
int steps = 0;
while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        int[] curr = queue.poll();
        for (int[] d : dirs) {
            int nr = curr[0] + d[0], nc = curr[1] + d[1];
            if (inBounds(nr, nc) && !visited[nr][nc]) {
                visited[nr][nc] = true;
                queue.offer(new int[]{nr, nc});
            }
        }
    }
    steps++;
}

Gotchas

• Use offer/poll not add/remove — add/remove throw exceptions on failure; offer/poll return null/false
• Always freeze int size = queue.size() BEFORE the inner for-loop — the queue grows as you add children
• For sliding window max: use Deque as a monotonic deque, removing from both ends as needed

Heap (Priority Queue)

A complete binary tree satisfying the heap property — always gives you the min (or max) in O(1). Java's PriorityQueue is a min-heap by default.

Operations

Space: O(n)

When to Reach For It

• Always need the current minimum or maximum
• Top K elements (Kth largest, K most frequent)
• Merge K sorted lists or arrays
• Scheduling problems, meeting rooms
• Dijkstra's shortest path (weighted graph)

Java

Copy// Min-heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3);
minHeap.offer(1);
minHeap.peek();                                 // 1
minHeap.poll();                                 // 1 — removes min

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

// Custom comparator — sort int[] by second element
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

Scenarios

Copy// Top K frequent — min-heap of size K, evict the least frequent
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
    pq.offer(new int[]{e.getKey(), e.getValue()});
    if (pq.size() > k) {
        pq.poll();                              // remove least frequent
    }
}

Copy// Merge K sorted arrays — always pull the globally smallest next
// Each entry: [value, arrayIndex, elementIndex]
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < arrays.length; i++) {
    if (arrays[i].length > 0) {
        pq.offer(new int[]{arrays[i][0], i, 0});
    }
}
while (!pq.isEmpty()) {
    int[] curr = pq.poll();
    result.add(curr[0]);
    int ai = curr[1], ei = curr[2];
    if (ei + 1 < arrays[ai].length) {
        pq.offer(new int[]{arrays[ai][ei + 1], ai, ei + 1});
    }
}

Gotchas

• Java's PriorityQueue is a min-heap — pass (a, b) -> b - a for max-heap
• peek() is O(1) but contains() is O(n) — never use a heap to check membership
• No O(log n) update-in-place — to change a priority, remove the element and re-insert
• For int[] elements, always provide a comparator — arrays have no natural ordering

Linked List

A chain of nodes where each node holds a value and a pointer to the next node. Always built manually in interviews — ListNode is not in the standard library.

Operations

Space: O(n)

When to Reach For It

• Problem gives you a ListNode — you're working with a linked list
• In-place reversal, cycle detection, finding middle
• Merging two sorted lists
• When O(1) insert/delete at a known position matters more than random access

Java

Copyclass ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

// Build: 1 → 2 → 3
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

Scenarios

Copy// Reverse in-place
ListNode prev = null, curr = head;
while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
}
// prev is the new head

Copy// Find middle — slow/fast pointers
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow is the middle node

Copy// Dummy node — simplifies edge cases when head might change
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode curr = dummy;
// ... manipulate list ...
return dummy.next;

Gotchas

• Always use a dummy node when the head itself might be deleted or replaced
• Save curr.next to a temp variable BEFORE overwriting curr.next during reversal
• Cycle detection: fast pointer must check fast != null && fast.next != null — in that order
• Deleting a node requires a pointer to the previous node, not the node to delete

Binary Tree

A hierarchical structure where each node has at most two children — left and right. A BST is a binary tree with one extra rule: left < root < right.

Operations

Space: O(n) for the tree, O(h) for the recursion stack. Balanced: h = O(log n). Skewed: h = O(n).

When to Reach For It

• Problem gives you TreeNode root
• Path problems, depth, height, diameter, LCA
• Level-order output → BFS with a queue
• BST: sorted order, range queries, kth smallest

Java

Copyclass TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

Scenarios

Copy// DFS — post-order (bottom-up): compute children first, combine at current
public int height(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left  = height(root.left);
    int right = height(root.right);
    return Math.max(left, right) + 1;
}

Copy// BFS — level-order with level boundary
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        if (node.left  != null) { queue.offer(node.left);  }
        if (node.right != null) { queue.offer(node.right); }
    }
}

Copy// BST in-order traversal — produces values in sorted order
public void inOrder(TreeNode root, List<Integer> result) {
    if (root == null) {
        return;
    }
    inOrder(root.left, result);
    result.add(root.val);
    inOrder(root.right, result);
}

Copy// BST validation — pass bounds down, not just parent comparison
public boolean isValid(TreeNode root, long min, long max) {
    if (root == null) {
        return true;
    }
    if (root.val <= min || root.val >= max) {
        return false;
    }
    return isValid(root.left, min, root.val)
        && isValid(root.right, root.val, max);
}

Gotchas

• Always check root == null as your base case before accessing .left or .right
• BST validation requires passing min/max bounds through recursion — comparing only with parent misses grandparent violations
• Balanced tree ≠ BST — balanced means even height distribution; BST means ordering guarantee
• BFS uses a queue; DFS uses recursion (implicit stack) or an explicit Deque for iterative version

Trie

A tree where each path from root to a node spells out a prefix. Each node represents one character, not one word.

Operations

L = length of the string. Space: O(total characters inserted across all words).

When to Reach For It

• Prefix matching or autocomplete
• "Does any word in the set start with this prefix?"
• Word search on a board — prune paths that match no prefix early
• Replacing a HashSet<String> when prefix queries are needed alongside membership

Java

Copyclass TrieNode {
    TrieNode[] children = new TrieNode[26]; // lowercase a-z only
    boolean isEnd;
}

TrieNode root = new TrieNode();

Scenarios

Copy// Insert a word
TrieNode node = root;
for (char c : word.toCharArray()) {
    int i = c - 'a';
    if (node.children[i] == null) {
        node.children[i] = new TrieNode();
    }
    node = node.children[i];
}
node.isEnd = true;

Copy// Search exact word
TrieNode node = root;
for (char c : word.toCharArray()) {
    int i = c - 'a';
    if (node.children[i] == null) {
        return false;
    }
    node = node.children[i];
}
return node.isEnd;                              // must reach a word-end marker

Copy// Prefix check — identical to search but drop the isEnd requirement
TrieNode node = root;
for (char c : prefix.toCharArray()) {
    int i = c - 'a';
    if (node.children[i] == null) {
        return false;
    }
    node = node.children[i];
}
return true;                                    // any node reachable = valid prefix

Gotchas

• children = new TrieNode[26] assumes lowercase a–z — use 128 for full ASCII
• isEnd must be set explicitly — reaching the last character is not enough to confirm a complete word
• Prefix match and exact search differ only in the final isEnd check — easy to mix up under pressure

Graph

A set of nodes (vertices) connected by edges. Can be directed or undirected, weighted or unweighted.

Adjacency List vs Matrix

When to Reach For It

• List: connectivity, BFS/DFS, course schedule, clone graph, islands
• Matrix: when edge existence lookup is the core operation, or graph is given as a matrix

Java

Copyint n = 5;

// Adjacency list
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
    adj.add(new ArrayList<>());
}
adj.get(0).add(1);                              // directed edge 0 → 1
adj.get(1).add(0);                              // add both for undirected

// Adjacency matrix
int[][] matrix = new int[n][n];
matrix[0][1] = 1;                               // directed edge 0 → 1
matrix[1][0] = 1;                               // add both for undirected

// Weighted adjacency list — [neighbor, weight]
List<List<int[]>> wAdj = new ArrayList<>();
for (int i = 0; i < n; i++) {
    wAdj.add(new ArrayList<>());
}
wAdj.get(0).add(new int[]{1, 5});              // edge 0→1 weight 5

Scenarios

Copy// DFS — connectivity, flood fill
private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
    visited[node] = true;
    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
}

Copy// BFS — shortest path on unweighted graph
Deque<Integer> queue = new ArrayDeque<>();
boolean[] visited = new boolean[n];
queue.offer(start);
visited[start] = true;
int steps = 0;
while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        int node = queue.poll();
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
    steps++;
}

Copy// 3-state DFS — cycle detection in a directed graph
// 0 = unvisited, 1 = on current path, 2 = fully processed
private boolean hasCycle(int node, List<List<Integer>> adj, int[] state) {
    state[node] = 1;
    for (int neighbor : adj.get(node)) {
        if (state[neighbor] == 1) {
            return true;                        // back edge = cycle
        }
        if (state[neighbor] == 0 && hasCycle(neighbor, adj, state)) {
            return true;
        }
    }
    state[node] = 2;
    return false;
}

Copy// Grid as implicit graph — 4-directional DFS
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

private void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
            || grid[r][c] != '1') {
        return;
    }
    grid[r][c] = '0';                           // mark visited in-place
    for (int[] d : dirs) {
        dfs(grid, r + d[0], c + d[1]);
    }
}

Gotchas

• Mark visited when adding to queue/stack, not when popping — prevents re-processing the same node
• Undirected graphs: add edges in both directions or you'll miss connections
• Directed graph cycle detection needs 3 states — 2-state visited only works for undirected
• Grid problems are implicit graphs — no adjacency list needed, 4-direction array is your neighbor lookup

Union Find

Tracks which nodes belong to the same connected component. Supports near-constant-time union and find with path compression and union by rank.

Operations

α(n) = inverse Ackermann — effectively constant for all practical n. Space: O(n)

When to Reach For It

• "Are these two nodes in the same component?"
• Merging components dynamically as edges are added
• Counting connected components
• Detecting cycles in an undirected graph
• Kruskal's minimum spanning tree

Java — Basic

Copyint[] parent = new int[n];
for (int i = 0; i < n; i++) {
    parent[i] = i;                              // each node is its own root
}

int find(int[] parent, int x) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

void union(int[] parent, int x, int y) {
    parent[find(parent, x)] = find(parent, y);
}

boolean connected(int[] parent, int x, int y) {
    return find(parent, x) == find(parent, y);
}

Java — Optimized (Path Compression + Union by Rank)

Copyint[] parent, rank;

void init(int n) {
    parent = new int[n];
    rank   = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);           // path compression — flatten the tree
    }
    return parent[x];
}

void union(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) {
        return;
    }
    if (rank[px] < rank[py]) {
        parent[px] = py;                        // attach shorter tree under taller
    } else if (rank[px] > rank[py]) {
        parent[py] = px;
    } else {
        parent[py] = px;
        rank[px]++;
    }
}

Scenarios

Copy// Count connected components — start at n, decrement per successful union
int components = n;
for (int[] edge : edges) {
    if (find(edge[0]) != find(edge[1])) {
        union(edge[0], edge[1]);
        components--;
    }
}

Copy// Cycle detection in undirected graph — if two nodes share a root, adding the edge creates a cycle
for (int[] edge : edges) {
    if (find(edge[0]) == find(edge[1])) {
        return true;                            // cycle detected
    }
    union(edge[0], edge[1]);
}
return false;

Gotchas

• Always use path compression — without it, find degrades to O(n) on a chain-shaped tree
• union must call find on both nodes — never union raw node indices directly
• Count components by starting at n and decrementing each time two different roots merge

Quick Reference