Data Structures Cheatsheet

Complexity Reference

All Structures at a Glance

* with reference to the node; O(n) otherwise

Arrays

Two-Pointer Template

let l = 0, r = arr.length - 1;
while (l < r) {
  // process arr[l] and arr[r]
  if (condition) l++;
  else           r--;
}

Sliding Window Template

let l = 0, window = /* initial state */;
for (let r = 0; r < arr.length; r++) {
  // expand window: add arr[r]
  while (/* window invalid */) {
    // shrink window: remove arr[l]
    l++;
  }
  // update answer with current window
}

Prefix Sum

// Build: O(n)
const prefix = [0];
for (const n of arr) prefix.push(prefix.at(-1) + n);

// Range sum [l, r] inclusive: O(1)
const rangeSum = prefix[r+1] - prefix[l];

Linked List

// Reverse: O(n) time, O(1) space
function reverse(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next  = prev;
    prev       = curr;
    curr       = next;
  }
  return prev;
}

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

// Find middle node (slow/fast pointers)
function findMiddle(head) {
  let slow = head, fast = head;
  while (fast?.next) { slow = slow.next; fast = fast.next.next; }
  return slow;
}

Stack & Queue

// Stack (LIFO)
const s = [];
s.push(x);     // O(1)
s.pop();       // O(1) — removes and returns top
s.at(-1);      // O(1) — peek without removing

// Queue (FIFO) — simple
const q = [];
q.push(x);     // enqueue O(1)
q.shift();     // dequeue O(n) — acceptable for small queues

// Monotonic stack — next greater element
function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack  = []; // indices
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack.at(-1)] < nums[i]) {
      result[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

Hash Map

const map = new Map();
map.set(key, value);
map.get(key);                    // undefined if missing
map.has(key);                    // boolean
map.delete(key);
map.size;

// Frequency counter pattern
const freq = new Map();
for (const x of arr) freq.set(x, (freq.get(x) ?? 0) + 1);

// Group by key
const groups = new Map();
for (const item of items) {
  const key = getKey(item);
  if (!groups.has(key)) groups.set(key, []);
  groups.get(key).push(item);
}

// Set — unique values, O(1) lookup
const seen = new Set();
seen.add(x);
seen.has(x);    // O(1)
seen.delete(x);

Trees

// DFS traversals
const inorder  = (n, r=[]) => n ? (inorder(n.left,r), r.push(n.val), inorder(n.right,r), r) : r;
const preorder = (n, r=[]) => n ? (r.push(n.val), preorder(n.left,r), preorder(n.right,r), r) : r;

// BFS — level order
function bfs(root) {
  if (!root) return [];
  const q = [root], res = [];
  while (q.length) {
    const level = [];
    for (let i = q.length; i--; ) {
      const n = q.shift();
      level.push(n.val);
      if (n.left)  q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(level);
  }
  return res;
}

// Height / max depth
const height = n => n ? 1 + Math.max(height(n.left), height(n.right)) : 0;

// Validate BST
function isValidBST(node, min=-Infinity, max=Infinity) {
  if (!node) return true;
  if (node.val <= min || node.val >= max) return false;
  return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
}

Graphs

// Build adjacency list from edge list
function buildGraph(n, edges, directed = false) {
  const g = Array.from({length: n}, () => []);
  for (const [u, v] of edges) {
    g[u].push(v);
    if (!directed) g[v].push(u);
  }
  return g;
}

// BFS template
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue   = [start];
  while (queue.length) {
    const node = queue.shift();
    for (const nb of graph[node]) {
      if (!visited.has(nb)) { visited.add(nb); queue.push(nb); }
    }
  }
}

// DFS template (iterative)
function dfs(graph, start) {
  const visited = new Set();
  const stack   = [start];
  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    for (const nb of graph[node]) stack.push(nb);
  }
}

// Union-Find (Disjoint Set) — O(α(n)) ≈ O(1) per operation
class UnionFind {
  constructor(n) { this.parent = Array.from({length:n},(_,i)=>i); this.rank = new Array(n).fill(0); }
  find(x) { return this.parent[x] === x ? x : (this.parent[x] = this.find(this.parent[x])); }
  union(x, y) {
    const [px, py] = [this.find(x), this.find(y)];
    if (px === py) return false;
    this.rank[px] >= this.rank[py] ? (this.parent[py]=px, this.rank[px]+=this.rank[px]===this.rank[py]?1:0) : (this.parent[px]=py);
    return true;
  }
}

Quick Choices