Data Structures Cheat Sheet for Coding Interviews (with Big-O)

This is the reference guide you keep open during practice. Every data structure you'll encounter in a FAANG coding interview — with time complexity, space complexity, common use cases, and the patterns that unlock each one.

How to Use This Guide

For each data structure, memorize:

1. The access/search/insert/delete complexities
2. The one or two problems it's the best tool for
3. The language-specific implementation in your language of choice

Don't memorize every operation cold. Understand why each structure has its complexity — that understanding transfers to novel problems.

Arrays

Space: O(n)

Best for: Random access by index, sliding window problems, two-pointer techniques, problems where order matters.

Key patterns:

• Two pointers: left/right pointers converging from both ends (Two Sum on sorted array, Valid Palindrome)
• Sliding window: fixed or variable-size window moving across the array (Maximum Subarray, Minimum Window Substring)
• Prefix sum: precompute cumulative sums to answer range queries in O(1)

Both Python and JavaScript handle arrays well, but implementation details differ in interviews.

Python implementation:

# Dynamic array (list) basics
arr = [1, 2, 3, 4, 5]
arr.append(6)          # O(1) amortized
arr.insert(2, 99)      # O(n) - shifts elements
arr.pop()              # O(1)
arr.pop(0)             # O(n) - shifts elements
arr[3]                 # O(1) - random access

# Sliding window pattern
def max_subarray_sum(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

# Two pointer pattern
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1
        else:
            right -= 1
    return []

JavaScript implementation:

// Array basics
const arr = [1, 2, 3, 4, 5];
arr.push(6);           // O(1) amortized
arr.splice(2, 0, 99);  // O(n)
arr.pop();             // O(1)
arr[3];                // O(1)

// Sliding window pattern
function maxSubarraySum(arr, k) {
  let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

// Prefix sum pattern
function prefixSum(arr) {
  const prefix = [0];
  for (let i = 0; i < arr.length; i++) {
    prefix.push(prefix[i] + arr[i]);
  }
  return prefix;
}

Hash Maps (Dictionaries)

Space: O(n)

Best for: Counting frequencies, checking existence in O(1), caching results, grouping elements by key.

Key patterns:

• Frequency count: count occurrences of each element (collections.Counter in Python, Map in JS)
• Two Sum pattern: store value → index mapping, then for each element check if target - element exists in the map
• Group by: group elements sharing a property (anagram grouping uses sorted string as key)

Python implementation:

# Basic operations
d = {}
d["key"] = "value"       # O(1)
val = d.get("key", None) # O(1) with default
del d["key"]              # O(1)
"key" in d                # O(1)

# Frequency count
from collections import Counter
words = ["apple", "banana", "apple", "cherry"]
freq = Counter(words)  # {'apple': 2, 'banana': 1, 'cherry': 1}

# Two Sum pattern
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Group anagrams
def group_anagrams(strs):
    groups = {}
    for s in strs:
        key = ''.join(sorted(s))
        groups.setdefault(key, []).append(s)
    return list(groups.values())

JavaScript implementation:

// Basic operations
const map = new Map();
map.set("key", "value");     // O(1)
map.get("key");              // O(1)
map.delete("key");           // O(1)
map.has("key");              // O(1)

// Frequency count using plain object
function frequencyCount(arr) {
  const freq = {};
  for (const item of arr) {
    freq[item] = (freq[item] || 0) + 1;
  }
  return freq;
}

// Two Sum pattern
function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }
    seen.set(nums[i], i);
  }
  return [];
}

Hash Sets

Space: O(n)

Best for: Deduplication, cycle detection (Floyd's isn't always needed), checking if an element was seen before.

Key patterns:

• Visited tracking: in graph/matrix traversal, mark visited nodes to prevent revisiting
• Duplicate detection: add to set; if already present, it's a duplicate

Python implementation:

# Basic operations
s = set()
s.add(42)       # O(1)
s.remove(42)    # O(1) - raises KeyError if missing
s.discard(42)   # O(1) - no error if missing
42 in s         # O(1)

# Deduplication
def remove_duplicates(arr):
    return list(set(arr))

# Cycle detection in linked list using set
def has_cycle(head):
    visited = set()
    current = head
    while current:
        if current in visited:
            return True
        visited.add(current)
        current = current.next
    return False

JavaScript implementation:

// Basic operations
const s = new Set();
s.add(42);       // O(1)
s.delete(42);    // O(1)
s.has(42);       // O(1)

// Deduplication
const arr = [1, 2, 2, 3, 3, 3];
const unique = [...new Set(arr)]; // [1, 2, 3]

// Set operations (intersection, union)
const setA = new Set([1, 2, 3]);
const setB = new Set([2, 3, 4]);
const intersection = new Set([...setA].filter(x => setB.has(x)));
const union = new Set([...setA, ...setB]);

Linked Lists

Space: O(n)

Best for: Problems that require frequent insertion/deletion from arbitrary positions. Less common in FAANG interviews than arrays, but appear in Reverse Linked List, Merge K Sorted Lists, LRU Cache.

Key patterns:

• Fast & slow pointers: detect cycles, find the middle node
• Dummy head: simplify edge cases at the head of the list
• Reversal in-place: reverse the next pointers iteratively

Python implementation:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Reverse linked list
def reverse_list(head):
    prev, current = None, head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

# Detect cycle (Floyd's algorithm)
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Find middle node
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

JavaScript implementation:

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// Reverse linked list
function reverseList(head) {
  let prev = null, current = head;
  while (current) {
    const nextNode = current.next;
    current.next = prev;
    prev = current;
    current = nextNode;
  }
  return prev;
}

// Detect cycle (Floyd's algorithm)
function hasCycle(head) {
  let slow = fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Stacks

Space: O(n)

Best for: Problems involving matching pairs, tracking "last seen", or converting recursive solutions to iterative ones.

Key patterns:

• Bracket matching: push open brackets, pop and verify on close brackets (Valid Parentheses)
• Monotonic stack: maintain an increasing or decreasing stack to find next greater/smaller elements (Daily Temperatures, Largest Rectangle in Histogram)
• DFS iteratively: use a stack instead of recursion to avoid stack overflow

Python implementation:

# Valid Parentheses
def is_valid_parentheses(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:
            stack.append(char)
    return len(stack) == 0

# Monotonic stack - Next Greater Element
def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []
    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    return result

JavaScript implementation:

// Valid Parentheses
function isValid(s) {
  const stack = [];
  const mapping = { ')': '(', '}': '{', ']': '[' };
  for (const char of s) {
    if (char in mapping) {
      if (!stack.length || stack[stack.length - 1] !== mapping[char]) {
        return false;
      }
      stack.pop();
    } else {
      stack.push(char);
    }
  }
  return stack.length === 0;
}

Queues

Space: O(n)

Best for: BFS traversal, level-order processing, sliding window maximum.

Key patterns:

• BFS: enqueue starting node, dequeue and process level by level
• Deque (double-ended queue): use for sliding window maximum (monotonic deque pattern)

Python implementation:

from collections import deque

# BFS level-order traversal
def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

# Sliding window maximum using deque
def max_sliding_window(nums, k):
    dq = deque()
    result = []
    for i in range(len(nums)):
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Binary Trees

Space: O(n) for the tree, O(h) for recursion stack where h = height

Best for: Hierarchical data, range queries on sorted data, recursive problem decomposition.

Traversal patterns:

• Inorder (left-root-right): produces sorted output for BSTs
• Preorder (root-left-right): useful for copying trees, serialize/deserialize
• Postorder (left-right-root): useful for deletion, computing size
• Level-order (BFS): use a queue, process node by node per level

Python implementation:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# BST insert
def insert_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    return root

# Inorder traversal (recursive)
def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

# Lowest Common Ancestor
def lca(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root
    return left or right

JavaScript implementation:

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// BST insert
function insertBST(root, val) {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insertBST(root.left, val);
  else root.right = insertBST(root.right, val);
  return root;
}

// Inorder traversal iterative
function inorder(root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }
  return result;
}

Heaps (Priority Queues)

Space: O(n)

Best for: Finding the k-th largest/smallest element, streaming data problems, merging sorted lists.

Key patterns:

• Top-K elements: use a min-heap of size K; push elements and pop when size exceeds K
• Merge K sorted lists: push the first element of each list into a min-heap; pop the smallest and push its successor
• Two-heap pattern: one max-heap + one min-heap to maintain a running median

Python implementation:

import heapq

# Top-K largest elements
def top_k_largest(nums, k):
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return sorted(min_heap)

# Merge K sorted lists using heap
def merge_k_sorted(lists):
    min_heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(min_heap, (lst[0], i, 0))
    result = []
    while min_heap:
        val, list_idx, elem_idx = heapq.heappop(min_heap)
        result.append(val)
        if elem_idx + 1 < len(lists[list_idx]):
            heapq.heappush(min_heap, (lists[list_idx][elem_idx + 1], list_idx, elem_idx + 1))
    return result

# Running median using two heaps
import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (invert values)
        self.hi = []  # min-heap

    def add_num(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def find_median(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2.0

Graphs

Use adjacency list for sparse graphs (most interview problems). Use adjacency matrix when you need O(1) edge existence checks.

Key traversal patterns:

• BFS: shortest path in unweighted graphs, level-by-level exploration
• DFS: cycle detection, topological sort, connected components
• Union-Find: detect cycles, find connected components efficiently

Graphs also appear in system design interviews at a larger scale.

Python implementation:

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.adj = defaultdict(list)

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def bfs(self, start):
        visited = {start}
        queue = deque([start])
        order = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in self.adj[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return order

    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        order = [start]
        for neighbor in self.adj[start]:
            if neighbor not in visited:
                order.extend(self.dfs(neighbor, visited))
        return order

    # Cycle detection (undirected)
    def has_cycle(self):
        visited = set()
        def dfs(node, parent):
            visited.add(node)
            for neighbor in self.adj[node]:
                if neighbor not in visited:
                    if dfs(neighbor, node):
                        return True
                elif neighbor != parent:
                    return True
            return False
        for node in self.adj:
            if node not in visited:
                if dfs(node, -1):
                    return True
        return False

# Topological sort (Directed Acyclic Graph)
def topological_sort(num_courses, prerequisites):
    adj = defaultdict(list)
    in_degree = [0] * num_courses
    for dest, src in prerequisites:
        adj[src].append(dest)
        in_degree[dest] += 1
    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == num_courses else []

JavaScript implementation:

class Graph {
  constructor() {
    this.adj = new Map();
  }

  addEdge(u, v) {
    if (!this.adj.has(u)) this.adj.set(u, []);
    if (!this.adj.has(v)) this.adj.set(v, []);
    this.adj.get(u).push(v);
    this.adj.get(v).push(u);
  }

  bfs(start) {
    const visited = new Set([start]);
    const queue = [start];
    const order = [];
    while (queue.length) {
      const node = queue.shift();
      order.push(node);
      for (const neighbor of (this.adj.get(node) || [])) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    return order;
  }

  dfs(start) {
    const visited = new Set();
    const order = [];
    const stack = [start];
    while (stack.length) {
      const node = stack.pop();
      if (!visited.has(node)) {
        visited.add(node);
        order.push(node);
        for (const neighbor of (this.adj.get(node) || [])) {
          if (!visited.has(neighbor)) stack.push(neighbor);
        }
      }
    }
    return order;
  }
}

Tries (Prefix Trees)

Space: O(n × m) where n = number of words

Best for: Autocomplete, prefix matching, word search problems.

Python implementation:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# Word search in grid using Trie
def find_words(board, words):
    trie = Trie()
    for word in words:
        trie.insert(word)

    result = set()
    def dfs(node, i, j, path):
        if node.is_end:
            result.add(path)
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
            return
        char = board[i][j]
        if char not in node.children:
            return
        board[i][j] = '#'
        for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(node.children[char], i+di, j+dj, path+char)
        board[i][j] = char

    for i in range(len(board)):
        for j in range(len(board[0])):
            dfs(trie.root, i, j, "")
    return list(result)

JavaScript implementation:

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) node.children[char] = new TrieNode();
      node = node.children[char];
    }
    node.isEnd = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEnd;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true;
  }
}

Big-O Quick Reference

Understanding Big-O complexity is fundamental to choosing the right data structure. For an in-depth breakdown of time and space complexity across all common algorithms, see the Big-O Cheat Sheet.

When to Use Each Data Structure

Time Complexity Cheat Sheet

* Amortized O(1) for dynamic array append

Space Complexity Comparison

Rules of thumb:

• If you only need existence checks, use a set not a map
• If order doesn't matter, an array may beat a linked list
• For dense graphs, adjacency matrix uses less total memory than adjacency list

Real Interview Scenarios: Choosing the Right Data Structure

Scenario 1: "Given an array, find two numbers that add up to a target."

→ Hash Map. Store value → index, check for complement in O(1). Don't sort and use two pointers unless the problem guarantees sorted input.

Scenario 2: "Find the longest substring without repeating characters."

→ Hash Map + Sliding Window. Map each character to its latest index. When you see a repeat, jump the left pointer past the duplicate.

Scenario 3: "Merge k sorted lists."

→ Heap. Push the head of each list into a min-heap. Pop the smallest, push its next node. This runs in O(N log k) where N is total elements.

Scenario 4: "Is this graph bipartite?"

→ BFS/DFS with coloring. Use a hash map or array to track node colors (0 = uncolored, 1 = color A, -1 = color B). If any edge connects same-colored nodes, it's not bipartite.

Scenario 5: "Implement an LRU Cache."

→ Hash Map + Doubly Linked List. Map keys to nodes. Move accessed nodes to the front. Delete from tail when capacity exceeded. Both operations are O(1).

Scenario 6: "Find the median of a data stream."

→ Two Heaps. Max-heap for lower half, min-heap for upper half. Rebalance after each insert. Median is either the top of one heap or the average of both.

Scenario 7: "Word break — can the string be segmented into dictionary words?"

→ Trie or Dynamic Programming with Set. Insert all dictionary words into a Trie (or HashSet). Use DP where dp[i] = True if s[0:i] can be segmented.

Scenario 8: "Find all anagram substrings in a string."

→ Hash Map + Sliding Window. Compare frequency maps of the pattern and each window of the same size. Increment count when maps match.

Scenario 9: "Serialize and deserialize a binary tree."

→ Preorder traversal + Queue. Convert tree to string using preorder with null markers. Deserialize by reading values sequentially and rebuilding.

Scenario 10: "Detect if a linked list has a cycle."

→ Fast & Slow Pointers (Floyd's). O(1) space, O(n) time. No hash set needed. This is the optimal solution.

Implementation Gotchas

Arrays

• Off-by-one errors: In sliding window, make sure your loop range includes the last valid window start.
• Modifying while iterating: Removing elements during iteration shifts indices. Iterate backwards or collect indices first.
• Integer overflow in prefix sums: In languages like Java/C++, prefix sums on large arrays can overflow. Use long/BigInt.

Hash Maps

• Using mutable objects as keys: In Python, lists can't be dict keys. Use tuples. In JS, objects aren't valid Map keys (use primitive keys or Sets).
• Key collision misconception: O(1) is amortized. In worst case (all keys collide), lookup is O(n). Interviewers may ask about this.
• Default values: In Python, dict[key] += 1 raises KeyError. Use collections.defaultdict(int) or dict.get(key, 0).

Linked Lists

• Losing the head pointer: Always keep a reference to head. Use a dummy node (sentinel) when modifying the list to avoid special-casing head operations.
• Forgetting to handle None: Check if not node before accessing node.next or node.val.
• Circular references: When reversing, ensure the old next is captured before overwriting.

Stacks

• Empty stack pop: Always check if stack before stack.pop(). Empty stack pop is undefined behavior in many implementations.
• Monotonic stack direction: For "next greater element," iterate left-to-right. For "previous greater," iterate right-to-left.

Trees

• Null checks everywhere: Tree problems are null-safety problems. Always handle if not node before recursion.
• Off-by-one in height: Height of empty tree is typically -1 or 0 — be consistent with what the problem asks.
• Recursion depth: Python default recursion limit is ~1000. For deep trees, use iterative traversal or increase the limit.

Graphs

• Directed vs undirected: Forgetting to add edges in both directions for undirected graphs. This causes DFS/BFS to miss nodes.
• Visited set timing: Mark nodes as visited when you enqueue/push them, not when you process them. Otherwise you'll visit the same node multiple times.
• Self-loops: Check if u == v before adding edges if the problem says self-loops aren't allowed.

Heaps

• Max-heap in Python: Python only has heapq (min-heap). For max-heap, negate values: heapq.heappush(heap, -val).
• Custom sort in heap: To store tuples and sort by a specific field, use (priority, object). Python compares tuples element-by-element.
• Heapify is O(n), not O(n log n): Building a heap from an array using heapq.heapify(arr) is linear time.

Union Find

• Path compression + union by rank: Always use both optimizations. Without path compression, find can degrade to O(n).
• 1-indexed vs 0-indexed: Be careful whether your node IDs start at 0 or 1. Initialize the parent array accordingly.

Advanced Data Structures

Trie (Prefix Tree)

Tries store strings character-by-character in a tree. Each node represents a character, and paths from root to marked nodes form complete words.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.count = 0  # For counting words with this prefix

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.count += 1  # Increment prefix count
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def count_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.count

    def autocomplete(self, prefix, limit=10):
        results = []
        node = self.root
        for char in prefix:
            if char not in node.children:
                return results
            node = node.children[char]
        self._collect(node, list(prefix), results, limit)
        return results

    def _collect(self, node, path, results, limit):
        if len(results) >= limit:
            return
        if node.is_end:
            results.append(''.join(path))
        for char, child in sorted(node.children.items()):
            path.append(char)
            self._collect(child, path, results, limit)
            path.pop()

When to use: Autocomplete systems, spell checkers, IP routing tables, word games (Boggle, Word Search II).

Segment Tree

A Segment Tree allows efficient range queries (sum, min, max, GCD) and point updates on an array.

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        self._build(data, 2 * node, start, mid)
        self._build(data, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) // 2
        if idx <= mid:
            self._update(2 * node, start, mid, idx, val)
        else:
            self._update(2 * node + 1, mid + 1, end, idx, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def update(self, idx, val):
        self._update(1, 0, self.n - 1, idx, val)

    def _query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        left_sum = self._query(2 * node, start, mid, l, r)
        right_sum = self._query(2 * node + 1, mid + 1, end, l, r)
        return left_sum + right_sum

    def query(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

When to use: Range sum queries with updates, inversions count, interval scheduling, problems like "Count of Smaller Numbers After Self".

Union Find (Disjoint Set Union)

Union Find efficiently tracks connected components and supports union operations.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False  # Already in same component
        # Union by rank
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        self.components -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

    def get_components(self):
        return self.components

When to use: Detecting cycles in undirected graphs, counting connected components, Redundant Connection, Accounts Merge, Number of Islands II.

Practice Problems by Data Structure

Arrays (8 problems)

1. Two Sum — hash map pattern
2. Best Time to Buy and Sell Stock — single pass max tracking
3. Contains Duplicate — set check
4. Maximum Subarray (Kadane's) — running sum
5. Product of Array Except Self — prefix/suffix products
6. Rotate Array — reverse technique
7. Sliding Window Maximum — deque pattern
8. Trapping Rain Water — two pointers

Hash Maps (6 problems)

1. Two Sum — complement lookup
2. Group Anagrams — sorted string key
3. Top K Frequent Elements — frequency map + heap
4. Subarray Sum Equals K — prefix sum + map
5. Longest Consecutive Sequence — set-based consecutive chain
6. Ransom Note — character frequency check

Linked Lists (5 problems)

1. Reverse Linked List — pointer reversal
2. Merge Two Sorted Lists — dummy head pattern
3. Linked List Cycle — fast & slow pointers
4. Remove Nth Node From End — two-pass or two-pointer gap
5. LRU Cache — hash map + doubly linked list

Stacks (5 problems)

1. Valid Parentheses — bracket matching
2. Min Stack — auxiliary stack
3. Daily Temperatures — monotonic stack
4. Largest Rectangle in Histogram — stack + width tracking
5. Evaluate Reverse Polish Notation — operand stack

Trees (7 problems)

1. Maximum Depth of Binary Tree — recursive DFS
2. Validate Binary Search Tree — in-order with bounds
3. Lowest Common Ancestor — recursive LCA
4. Binary Tree Level Order Traversal — BFS with queue
5. Serialize and Deserialize Binary Tree — preorder + null markers
6. Construct Binary Tree from Preorder and Inorder — recursive split
7. Kth Smallest Element in BST — in-order traversal

Graphs (7 problems)

1. Number of Islands — DFS/BFS on grid
2. Clone Graph — BFS + hash map
3. Course Schedule — topological sort
4. Pacific Atlantic Water Flow — reverse BFS from borders
5. Word Ladder — BFS shortest path
6. Detect Cycle in Undirected Graph — Union Find or DFS
7. Redundant Connection — Union Find

Heaps (4 problems)

1. Kth Largest Element in Array — min-heap of size k
2. Find Median from Data Stream — two heaps
3. Merge K Sorted Lists — heap-based merge
4. Task Scheduler — greedy + heap

Tries (3 problems)

1. Implement Trie — basic trie operations
2. Word Search II — trie + DFS on grid
3. Design Add and Search Words — trie with wildcard search

Advanced (3 problems)

1. Range Sum Query - Mutable — Segment Tree
2. Number of Provinces — Union Find
3. Count of Smaller Numbers After Self — Segment Tree or BST with count

Quick Reference Card

Data Structure Selection Flowchart

Need O(1) lookup by key? → Hash Map or Hash Set
Need ordered data + O(log n) search? → BST (use built-in TreeMultiset or sortedcontainers)
Need k-th min/max? → Heap
Need range queries + updates? → Segment Tree
Need connected components? → Union Find
Need prefix/autocomplete? → Trie
Need shortest path? → Graph + BFS
Need DFS cycle detection? → Graph + DFS with visited set
Need bracket matching / monotonic pattern? → Stack
Need FIFO processing? → Queue
Need fast random access? → Array

Complexity at a Glance

O(1)     : Hash Map/Set insert/lookup, Array access, Stack/Queue push/pop, Heap peek
O(log n) : BST search/insert/delete, Heap insert/delete, Segment Tree query/update
O(n)     : Array search, Linked List search, Graph BFS/DFS, Array/traversal
O(n log n): Merge sort, Heap sort, building heap from array
O(n²)    : Nested loops, Floyd-Warshall, naive graph algorithms

One-Liner Pattern Recognition

Practice These Patterns With Alex

Knowing a data structure and knowing when to reach for it in a live interview are different skills. Practice on LeetCode helps build pattern recognition, but interview mistakes often happen when candidates pick the wrong structure for the problem. If you're wondering how LeetCode stacks up against mock interview platforms, see our InterviewSkool vs LeetCode comparison. Alex, the AI interviewer on InterviewSkool, gives you real problems and asks you to justify your data structure choices in real time — exactly what happens in a FAANG interview.

Start a practice session →

Frequently Asked Questions