Big O notation describes the upper bound of an algorithm's time or space complexity as input size (n) grows. It helps compare algorithms independently of hardware. Common complexities from fastest to slowest: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).

• Array — contiguous memory; O(1) random access; O(n) insertion/deletion in the middle; fixed size (static) or resizable (dynamic).
• Linked List — non-contiguous nodes with pointers; O(n) access; O(1) insertion/deletion at head; dynamic size.
• Use arrays for frequent reads; linked lists for frequent insertions/deletions at the front.

// Singly linked list node
class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

// Prepend: O(1)
function prepend(head, val) {
  const node = new ListNode(val);
  node.next = head;
  return node;
}

• Stack — LIFO (Last In, First Out); operations: push (add to top), pop (remove from top), peek. Used for: function call stack, undo/redo, DFS.
• Queue — FIFO (First In, First Out); operations: enqueue (add to back), dequeue (remove from front). Used for: BFS, task scheduling, print queues.

// Stack using array
const stack = [];
stack.push(1); stack.push(2); stack.push(3);
console.log(stack.pop()); // 3

// Queue using array
const queue = [];
queue.push(1); queue.push(2); queue.push(3);
console.log(queue.shift()); // 1

Binary search finds a target in a sorted array by repeatedly halving the search space. Time complexity: O(log n). Requires the array to be sorted.

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // not found
}
console.log(binarySearch([1,3,5,7,9,11], 7)); // 3

• Bubble Sort — O(n²) avg/worst; O(n) best; stable; simple but inefficient.
• Selection Sort — O(n²) all cases; not stable; minimises swaps.
• Insertion Sort — O(n²) avg/worst; O(n) best; stable; efficient for small/nearly sorted arrays.
• Merge Sort — O(n log n) all cases; stable; O(n) extra space.
• Quick Sort — O(n log n) avg; O(n²) worst; in-place; not stable; fastest in practice.

// Merge Sort
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left  = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}
function merge(l, r) {
  const res = [];
  let i = 0, j = 0;
  while (i < l.length && j < r.length)
    res.push(l[i] <= r[j] ? l[i++] : r[j++]);
  return [...res, ...l.slice(i), ...r.slice(j)];
}

A hash table maps keys to values using a hash function. Average O(1) for insert/search/delete. Collisions (two keys mapping to the same bucket) are handled by:

• Chaining — each bucket holds a linked list of entries.
• Open addressing — probe for the next available slot (linear probing, quadratic probing, double hashing).

// JavaScript Map (hash table)
const map = new Map();
map.set("name", "Alice");
map.set("age", 25);
console.log(map.get("name")); // Alice
console.log(map.has("age"));  // true
console.log(map.size);        // 2

A BST is a binary tree where for each node: all values in the left subtree are smaller, and all values in the right subtree are larger. Average O(log n) for search/insert/delete; O(n) worst case (unbalanced).

class TreeNode {
  constructor(val) { this.val = val; this.left = this.right = null; }
}
function insert(root, val) {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left  = insert(root.left,  val);
  else                root.right = insert(root.right, val);
  return root;
}

• Inorder (Left → Root → Right) — visits BST nodes in sorted order.
• Preorder (Root → Left → Right) — useful for copying/serialising a tree.
• Postorder (Left → Right → Root) — useful for deleting a tree or evaluating expressions.

function inorder(node, result = []) {
  if (!node) return result;
  inorder(node.left, result);
  result.push(node.val);
  inorder(node.right, result);
  return result;
}
// For BST [5,3,7,1,4]: inorder → [1,3,4,5,7]

• BFS (Breadth-First Search) — explores level by level using a queue; finds shortest path in unweighted graphs; O(V+E).
• DFS (Depth-First Search) — explores as deep as possible using a stack (or recursion); useful for cycle detection, topological sort, connected components; O(V+E).

// BFS
function bfs(root) {
  const queue = [root], result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node.val);
    if (node.left)  queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

• Undirected graph — edges have no direction; if A connects to B, B connects to A.
• Directed graph (digraph) — edges have direction; A → B does not imply B → A.
• Weighted graph — edges have associated costs/distances.
• Graphs are represented as adjacency lists (space-efficient) or adjacency matrices (O(1) edge lookup).

// Adjacency list representation
const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C"]
};

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It uses a priority queue (min-heap) and runs in O((V + E) log V).

// Simplified Dijkstra using a sorted array as priority queue
function dijkstra(graph, start) {
  const dist = {};
  for (const node in graph) dist[node] = Infinity;
  dist[start] = 0;
  const pq = [[0, start]]; // [distance, node]
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift();
    for (const [v, w] of graph[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push([dist[v], v]);
      }
    }
  }
  return dist;
}

Dynamic programming (DP) solves complex problems by breaking them into overlapping subproblems and storing results to avoid redundant computation. Two approaches:

• Memoization (top-down) — recursive with a cache; compute only needed subproblems.
• Tabulation (bottom-up) — iterative; fill a table from base cases up.

// Fibonacci — memoization
function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  return (memo[n] = fib(n-1, memo) + fib(n-2, memo));
}

// Fibonacci — tabulation
function fibTab(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
  return dp[n];
}

A greedy algorithm makes the locally optimal choice at each step, hoping to find a global optimum. It is simpler and faster than DP but does not always produce the optimal solution. Examples: coin change (with standard denominations), activity selection, Huffman coding, Dijkstra's algorithm.

The two-pointer technique uses two indices that move toward each other (or in the same direction) to solve array/string problems in O(n) instead of O(n²).

// Check if array has a pair summing to target (sorted array)
function hasPairSum(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return true;
    if (sum < target) left++;
    else right--;
  }
  return false;
}

The sliding window technique maintains a window (subarray/substring) that slides over the data to find an optimal subarray in O(n) instead of O(n²).

// Maximum sum subarray of size k
function maxSumSubarray(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;
}
console.log(maxSumSubarray([2,1,5,1,3,2], 3)); // 9

A trie is a tree data structure used to store strings where each node represents a character. It enables O(m) search, insert, and prefix queries (m = string length). Used in autocomplete, spell checkers, and IP routing.

class TrieNode {
  constructor() { this.children = {}; this.isEnd = false; }
}
class Trie {
  constructor() { this.root = new TrieNode(); }
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }
  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return node.isEnd;
  }
}

A heap is a complete binary tree satisfying the heap property: in a max-heap, every parent is ≥ its children; in a min-heap, every parent is ≤ its children. A priority queue uses a heap to always dequeue the highest (or lowest) priority element in O(log n).

// Min-heap operations (conceptual)
// insert: add to end, bubble up — O(log n)
// extractMin: swap root with last, remove, bubble down — O(log n)
// peek: return root — O(1)

// JavaScript does not have a built-in heap, but:
// Use a sorted array or a library like @datastructures-js/priority-queue

• Recursion — a function calls itself; elegant for tree/graph problems; uses call stack (risk of stack overflow for deep recursion).
• Iteration — uses loops; more memory-efficient; no stack overflow risk; sometimes less readable.
• Any recursive solution can be converted to iterative using an explicit stack.

• Array: access O(1), search O(n), insert/delete O(n)
• Linked List: access O(n), search O(n), insert/delete at head O(1)
• Hash Table: search/insert/delete O(1) avg, O(n) worst
• BST (balanced): search/insert/delete O(log n)
• Heap: insert O(log n), extractMin/Max O(log n), peek O(1)
• Stack/Queue: push/pop/enqueue/dequeue O(1)

A balanced binary tree keeps the height at O(log n), ensuring efficient operations. An unbalanced BST degrades to O(n). Self-balancing trees like AVL trees and Red-Black trees automatically maintain balance through rotations.

Topological sort orders the vertices of a directed acyclic graph (DAG) such that for every directed edge u → v, u comes before v. Used for task scheduling, build systems, and dependency resolution. Implemented via DFS or Kahn's algorithm (BFS with in-degree tracking).

// Kahn's algorithm (BFS-based)
function topoSort(numNodes, edges) {
  const inDegree = Array(numNodes).fill(0);
  const adj = Array.from({length: numNodes}, () => []);
  for (const [u, v] of edges) { adj[u].push(v); inDegree[v]++; }
  const queue = [];
  for (let i = 0; i < numNodes; i++) if (inDegree[i] === 0) queue.push(i);
  const result = [];
  while (queue.length) {
    const u = queue.shift();
    result.push(u);
    for (const v of adj[u]) if (--inDegree[v] === 0) queue.push(v);
  }
  return result.length === numNodes ? result : []; // empty = cycle
}

• Array — ordered data with frequent random access.
• Linked List — frequent insertions/deletions at the front.
• Hash Map — fast key-value lookups, frequency counting.
• Stack — undo/redo, balanced parentheses, DFS.
• Queue — BFS, task scheduling, sliding window.
• Heap/Priority Queue — finding k-th largest/smallest, Dijkstra's.
• Trie — prefix search, autocomplete.
• Graph — network problems, shortest path, connectivity.

• Tree — a connected, acyclic undirected graph; has exactly n-1 edges for n nodes; has a root; hierarchical structure.
• Graph — can have cycles, disconnected components, and multiple edges between nodes; more general than a tree.
• All trees are graphs, but not all graphs are trees.

The 0/1 Knapsack problem: given items with weights and values, find the maximum value that fits in a knapsack of capacity W. Each item can be taken (1) or left (0). Solved with a 2D DP table in O(n × W) time.

function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({length: n+1}, () => Array(W+1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      dp[i][w] = dp[i-1][w]; // skip item i
      if (weights[i-1] <= w)
        dp[i][w] = Math.max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1]);
    }
  }
  return dp[n][W];
}