Data Structures & Algorithms Cheat Sheet (2026): The Complete Technical Interview Masterclass

// Master Array Complexities & In-Place Two-Pointer Pattern
// Access by Index: O(1)
// Search (Unsorted): O(n)
// Insert / Delete at End: O(1) amortized
// Insert / Delete in Middle: O(n) due to element shifting

export function twoSumTwoPointersSorted(numbers: number[], target: number): number[] {
  let left = 0;
  let right = numbers.length - 1;

  while (left < right) {
    const currentSum = numbers[left] + numbers[right];
    if (currentSum === target) {
      return [left, right];
    } else if (currentSum < target) {
      left++; // Increase sum by moving left pointer forward
    } else {
      right--; // Decrease sum by moving right pointer backward
    }
  }
  return [];
}

// Stack Complexities:
// Push: O(1) | Pop: O(1) | Top / Peek: O(1) | Size: O(1) | Search: O(n)

export function isValidParentheses(s: string): boolean {
  const stack: string[] = [];
  const bracketMap: Record<string, string> = {
    ')': '(',
    '}': '{',
    ']': '['
  };

  for (const char of s) {
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char);
    } else if (char in bracketMap) {
      if (stack.length === 0 || stack.pop() !== bracketMap[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

// Linked List Complexities:
// Access / Search by Index: O(n)
// Insert / Delete (with known pointer): O(1)
// Append (with known tail pointer): O(1)

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

// Floyd's Tortoise and Hare Cycle Detection Algorithm: O(n) time, O(1) space
export function hasCycle(head: ListNode | null): boolean {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true; // Cycle detected
    }
  }
  return false;
}

// Queue Complexities:
// Enqueue (Insert at Rear): O(1)
// Dequeue (Remove from Front): O(1)
// Peek Front: O(1) | Search: O(n)

export function levelOrderTraversal(root: { val: number; left: any; right: any } | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: any[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift(); // Dequeue from front
      currentLevel.push(node.val);

      if (node.left) queue.push(node.left); // Enqueue left child
      if (node.right) queue.push(node.right); // Enqueue right child
    }

    result.push(currentLevel);
  }

  return result;
}

// Hash Map Complexities:
// Insert / Lookup / Delete / ContainsKey: Average O(1) | Worst O(n) on full collisions
// Space Complexity: O(n) memory overhead for bucket table

export function twoSumHashMap(nums: number[], target: number): number[] {
  const seenMap = new Map<number, number>(); // Value -> Index

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seenMap.has(complement)) {
      return [seenMap.get(complement)!, i];
    }
    seenMap.set(nums[i], i);
  }

  return [];
}

// BST Complexities:
// Search / Insert / Delete (Balanced): O(log n) | Skewed Worst-Case: O(n)
// Tree Traversals (In-Order, Pre-Order, Post-Order): O(n) time visiting all nodes

export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

export function isValidBST(root: TreeNode | null, min: number = -Infinity, max: number = Infinity): boolean {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;

  return (
    isValidBST(root.left, min, root.val) &&
    isValidBST(root.right, root.val, max)
  );
}

// Heap / Priority Queue Complexities:
// Peek Min/Max: O(1)
// Insert / Extract Min/Max: O(log n)
// Build Heap (Heapify): O(n)
// Arbitrary Element Search: O(n) (Heaps are only partially ordered!)

// Find Kth Largest Element using a Min-Heap of size K: O(n log k) time, O(k) space
export class SimpleMinHeap {
  private data: number[] = [];

  push(val: number): void {
    this.data.push(val);
    this.bubbleUp(this.data.length - 1);
  }

  pop(): number | undefined {
    if (this.data.length === 0) return undefined;
    const min = this.data[0];
    const last = this.data.pop()!;
    if (this.data.length > 0) {
      this.data[0] = last;
      this.siftDown(0);
    }
    return min;
  }

  peek(): number { return this.data[0]; }
  size(): number { return this.data.length; }

  private bubbleUp(idx: number): void {
    while (idx > 0) {
      const parentIdx = Math.floor((idx - 1) / 2);
      if (this.data[idx] < this.data[parentIdx]) {
        [this.data[idx], this.data[parentIdx]] = [this.data[parentIdx], this.data[idx]];
        idx = parentIdx;
      } else break;
    }
  }

  private siftDown(idx: number): void {
    const length = this.data.length;
    while (true) {
      let smallest = idx;
      const left = 2 * idx + 1;
      const right = 2 * idx + 2;

      if (left < length && this.data[left] < this.data[smallest]) smallest = left;
      if (right < length && this.data[right] < this.data[smallest]) smallest = right;

      if (smallest !== idx) {
        [this.data[idx], this.data[smallest]] = [this.data[smallest], this.data[idx]];
        idx = smallest;
      } else break;
    }
  }
}

// Graph Complexities:
// BFS / DFS Traversal: O(V + E)
// Cycle Detection: O(V + E)
// Topological Sort (Kahn's / DFS): O(V + E)
// Dijkstra's Shortest Path: O((V + E) log V) | Bellman-Ford: O(V * E)

// Course Schedule (Topological Sort / Cycle in Directed Acyclic Graph)
export function canFinishCourses(numCourses: number, prerequisites: number[][]): boolean {
  const inDegree = new Array(numCourses).fill(0);
  const adjList = new Map<number, number[]>();

  for (const [course, prereq] of prerequisites) {
    if (!adjList.has(prereq)) adjList.set(prereq, []);
    adjList.get(prereq)!.push(course);
    inDegree[course]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  let completedCount = 0;
  while (queue.length > 0) {
    const current = queue.shift()!;
    completedCount++;

    const neighbors = adjList.get(current) || [];
    for (const neighbor of neighbors) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  return completedCount === numCourses;
}

// Trie Complexities:
// Insert Word: O(m) where m = word length
// Search Word: O(m)
// StartsWith (Prefix Exists): O(m)
// Space Complexity: O(ALPHABET_SIZE * m * N) where N = number of keys

export class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

export class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let curr = this.root;
    for (const char of word) {
      if (!curr.children.has(char)) {
        curr.children.set(char, new TrieNode());
      }
      curr = curr.children.get(char)!;
    }
    curr.isEndOfWord = true;
  }

  search(word: string): boolean {
    let curr = this.root;
    for (const char of word) {
      if (!curr.children.has(char)) return false;
      curr = curr.children.get(char)!;
    }
    return curr.isEndOfWord;
  }

  startsWith(prefix: string): boolean {
    let curr = this.root;
    for (const char of prefix) {
      if (!curr.children.has(char)) return false;
      curr = curr.children.get(char)!;
    }
    return true;
  }
}

// MASTER DATA STRUCTURE COMPLEXITY MATRIX (Cheat Sheet Reference)
// ------------------------------------------------------------------------------------------------
// Data Structure   | Access      | Search      | Insertion   | Deletion    | Space Overhead
// ------------------------------------------------------------------------------------------------
// Array            | O(1)        | O(n)        | O(n) mid    | O(n) mid    | O(1) Contiguous
// Stack (LIFO)     | O(n) / O(1)T| O(n)        | O(1) push   | O(1) pop    | O(n)
// Queue (FIFO)     | O(n) / O(1)F| O(n)        | O(1) rear   | O(1) front  | O(n)
// Linked List      | O(n)        | O(n)        | O(1) ref    | O(1) ref    | O(n) Pointers
// Hash Map         | N/A         | O(1) avg    | O(1) avg    | O(1) avg    | O(n) Buckets
// BST (Balanced)   | O(log n)    | O(log n)    | O(log n)    | O(log n)    | O(n) Pointers
// Heap (Min/Max)   | O(1) root   | O(n)        | O(log n)    | O(log n)    | O(1) Array-backed
// Graph (Adj List) | N/A         | O(V + E)    | O(1) edge   | O(E) edge   | O(V + E)
// Trie             | N/A         | O(m) word   | O(m) word   | O(m) word   | O(Alphabet * m * N)
// ------------------------------------------------------------------------------------------------