DSA Patterns — The Complete Guide

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>(); // value → index

  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 []; // no pair found
}
// Time: O(n) — single pass
// Space: O(n) — hash map stores up to n entries

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const result: number[][] = [];

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicates

    let lo = i + 1;
    let hi = nums.length - 1;

    while (lo < hi) {
      const sum = nums[i] + nums[lo] + nums[hi];
      if (sum === 0) {
        result.push([nums[i], nums[lo], nums[hi]]);
        while (lo < hi && nums[lo] === nums[lo + 1]) lo++;  // skip dupes
        while (lo < hi && nums[hi] === nums[hi - 1]) hi--;  // skip dupes
        lo++;
        hi--;
      } else if (sum < 0) {
        lo++;
      } else {
        hi--;
      }
    }
  }

  return result;
}
// Time: O(n²) — sort is O(n log n), two-pointer scan is O(n) per fixed element
// Space: O(1) — ignoring the output array

function lengthOfLongestSubstring(s: string): number {
  const seen = new Set<string>();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}
// Time: O(n) — each character is added and removed from the set at most once
// Space: O(min(n, alphabet)) — the set holds at most the alphabet size

function subarraySum(nums: number[], k: number): number {
  const prefixCount = new Map<number, number>();
  prefixCount.set(0, 1); // empty prefix
  let sum = 0;
  let count = 0;

  for (const num of nums) {
    sum += num;
    const target = sum - k;
    if (prefixCount.has(target)) {
      count += prefixCount.get(target)!;
    }
    prefixCount.set(sum, (prefixCount.get(sum) ?? 0) + 1);
  }

  return count;
}
// Time: O(n) — single pass with O(1) map operations
// Space: O(n) — hash map stores up to n distinct prefix sums

function search(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);

    if (nums[mid] === target) return mid;

    // Left half is sorted
    if (nums[lo] <= nums[mid]) {
      if (nums[lo] <= target && target < nums[mid]) {
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    // Right half is sorted
    else {
      if (nums[mid] < target && target <= nums[hi]) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
  }

  return -1;
}
// Time: O(log n) — halve the search space each iteration
// Space: O(1) — only a few pointers

function largestNumber(nums: number[]): string {
  const strs = nums.map(String);

  // Custom comparator: which concatenation order is bigger?
  strs.sort((a, b) => {
    const ab = a + b;
    const ba = b + a;
    return ba.localeCompare(ab); // descending — bigger concatenation first
  });

  // Edge case: all zeros
  if (strs[0] === "0") return "0";

  return strs.join("");
}
// Time: O(n log n) — sorting with string comparisons
// Space: O(n) — storing string representations

function isValid(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = {
    ")": "(",
    "]": "[",
    "}": "{",
  };

  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch);
    } else {
      if (stack.length === 0 || stack.pop() !== pairs[ch]) {
        return false;
      }
    }
  }

  return stack.length === 0;
}
// Time: O(n) — single pass through the string
// Space: O(n) — stack holds up to n/2 opening brackets

function mergeSort(arr: number[]): number[] {
  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(a: number[], b: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;

  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) {
      result.push(a[i++]);
    } else {
      result.push(b[j++]);
    }
  }

  return result.concat(a.slice(i), b.slice(j));
}
// Time: O(n log n) — log n levels of recursion, O(n) merge at each level
// Space: O(n) — temporary arrays during merge

interface ListNode {
  val: number;
  next: ListNode | null;
}

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;

  while (curr !== null) {
    const next = curr.next; // save next before overwriting
    curr.next = prev;       // reverse the pointer
    prev = curr;            // advance prev
    curr = next;            // advance curr
  }

  return prev; // prev is the new head
}
// Time: O(n) — single pass through the list
// Space: O(1) — only three pointers

interface ListNode {
  val: number;
  next: ListNode | null;
}

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;        // move 1 step
    fast = fast.next.next;    // move 2 steps

    if (slow === fast) {
      return true;            // pointers met — cycle exists
    }
  }

  return false; // fast reached the end — no cycle
}
// Time: O(n) — fast pointer traverses at most 2n nodes
// Space: O(1) — only two pointers

function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const result = new Array(n).fill(0);
  const stack: number[] = []; // indices of decreasing temps

  for (let i = 0; i < n; i++) {
    // Pop all indices whose temperature is less than current
    while (
      stack.length > 0 &&
      temperatures[stack[stack.length - 1]] < temperatures[i]
    ) {
      const prevIndex = stack.pop()!;
      result[prevIndex] = i - prevIndex;
    }
    stack.push(i);
  }

  return result;
}
// Time: O(n) — each index is pushed and popped at most once
// Space: O(n) — stack can hold up to n indices

function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = []; // indices, front = max

  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside the current window
    if (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }

    // Remove smaller elements from the back
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }

    deque.push(i);

    // Window is fully formed once i >= k - 1
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}
// Time: O(n) — each element is added/removed from deque at most once
// Space: O(k) — deque holds at most k elements

function findKthLargest(nums: number[], k: number): number {
  // Min-heap approach: maintain a heap of size k
  // The top of the min-heap is the kth largest
  const minHeap: number[] = [];

  const push = (val: number) => {
    minHeap.push(val);
    let i = minHeap.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (minHeap[parent] > minHeap[i]) {
        [minHeap[parent], minHeap[i]] = [minHeap[i], minHeap[parent]];
        i = parent;
      } else break;
    }
  };

  const pop = (): number => {
    const top = minHeap[0];
    const last = minHeap.pop()!;
    if (minHeap.length > 0) {
      minHeap[0] = last;
      let i = 0;
      while (true) {
        let smallest = i;
        const left = 2 * i + 1, right = 2 * i + 2;
        if (left < minHeap.length && minHeap[left] < minHeap[smallest]) smallest = left;
        if (right < minHeap.length && minHeap[right] < minHeap[smallest]) smallest = right;
        if (smallest === i) break;
        [minHeap[i], minHeap[smallest]] = [minHeap[smallest], minHeap[i]];
        i = smallest;
      }
    }
    return top;
  };

  for (const num of nums) {
    push(num);
    if (minHeap.length > k) pop();
  }

  return minHeap[0]; // kth largest
}
// Time: O(n log k) — n insertions into a heap of size k
// Space: O(k) — heap stores at most k elements

function canJump(nums: number[]): boolean {
  let farthest = 0;

  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false; // can't reach this index
    farthest = Math.max(farthest, i + nums[i]);
    if (farthest >= nums.length - 1) return true;
  }

  return true;
}
// Time: O(n) — single pass
// Space: O(1) — only one variable

interface TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
}

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  const queue: TreeNode[] = [root];

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

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}
// Time: O(n) — visit every node once
// Space: O(n) — queue holds up to n/2 nodes at the widest level

interface TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
}

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

    return (
      validate(node.left, min, node.val) &&
      validate(node.right, node.val, max)
    );
  }

  return validate(root, -Infinity, Infinity);
}
// Time: O(n) — visit every node once
// Space: O(h) — recursion stack depth equals tree height

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(start: number, current: number[]) {
    result.push([...current]); // every partial solution is a valid subset

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);       // choose
      backtrack(i + 1, current);   // explore
      current.pop();               // unchoose (backtrack)
    }
  }

  backtrack(0, []);
  return result;
}
// Time: O(n × 2^n) — 2^n subsets, each takes O(n) to copy
// Space: O(n) — recursion depth + current subset

function numIslands(grid: string[][]): number {
  if (grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r: number, c: number) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (grid[r][c] !== "1") return;

    grid[r][c] = "0"; // mark visited

    dfs(r + 1, c); // down
    dfs(r - 1, c); // up
    dfs(r, c + 1); // right
    dfs(r, c - 1); // left
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") {
        count++;
        dfs(r, c); // sink the entire island
      }
    }
  }

  return count;
}
// Time: O(m × n) — visit every cell once
// Space: O(m × n) — recursion stack in worst case

function merge(intervals: number[][]): number[][] {
  if (intervals.length <= 1) return intervals;

  // Sort by start time
  intervals.sort((a, b) => a[0] - b[0]);

  const merged: number[][] = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    const current = intervals[i];

    if (current[0] <= last[1]) {
      // Overlapping — extend the end
      last[1] = Math.max(last[1], current[1]);
    } else {
      // Non-overlapping — add new interval
      merged.push(current);
    }
  }

  return merged;
}
// Time: O(n log n) — dominated by sorting
// Space: O(n) — merged result array

function rangeAddition(
  length: number,
  updates: [number, number, number][] // [startIdx, endIdx, inc]
): number[] {
  const diff = new Array(length).fill(0);

  // Apply each range update in O(1)
  for (const [start, end, inc] of updates) {
    diff[start] += inc;
    if (end + 1 < length) {
      diff[end + 1] -= inc;
    }
  }

  // Prefix sum to reconstruct actual values
  for (let i = 1; i < length; i++) {
    diff[i] += diff[i - 1];
  }

  return diff;
}
// Time: O(n + q) — q updates in O(1) each, one O(n) prefix sum pass
// Space: O(n) — the difference array

function climbStairs(n: number): number {
  if (n <= 2) return n;

  let prev2 = 1; // dp[i-2]
  let prev1 = 2; // dp[i-1]

  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}
// Time: O(n) — single pass
// Space: O(1) — only two variables

function canFinish(
  numCourses: number,
  prerequisites: number[][]
): boolean {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);

  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
    inDegree[course]++;
  }

  // Start with all nodes that have no prerequisites
  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

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

    for (const neighbor of graph[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return processed === numCourses; // false if cycle exists
}
// Time: O(V + E) — visit every node and edge once
// Space: O(V + E) — adjacency list + in-degree array

class UnionFind {
  parent: number[];
  rank: number[];
  count: number; // number of connected components

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n;
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }

  union(x: number, y: number): boolean {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false; // already connected

    // union by rank
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    this.count--;
    return true;
  }
}
// Time: O(α(n)) per find/union — nearly O(1) amortized
// Space: O(n) — parent and rank arrays

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

class Trie {
  root = new TrieNode();

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

  search(word: string): boolean {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix: string): boolean {
    return this._traverse(prefix) !== null;
  }

  private _traverse(s: string): TrieNode | null {
    let node = this.root;
    for (const ch of s) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch)!;
    }
    return node;
  }
}
// Time: O(L) per operation where L = word/prefix length
// Space: O(total characters across all inserted words)

function mergeSort(nums: number[]): number[] {
  if (nums.length <= 1) return nums;

  const mid = Math.floor(nums.length / 2);
  const left = mergeSort(nums.slice(0, mid));
  const right = mergeSort(nums.slice(mid));

  return merge(left, right);
}

function merge(a: number[], b: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;

  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }

  while (i < a.length) result.push(a[i++]);
  while (j < b.length) result.push(b[j++]);

  return result;
}
// Time: O(n log n) — log n levels, O(n) merge per level
// Space: O(n) — temporary arrays during merge

function singleNumber(nums: number[]): number {
  let result = 0;

  for (const num of nums) {
    result ^= num; // XOR: pairs cancel, single remains
  }

  return result;
}
// Time: O(n) — single pass through the array
// Space: O(1) — only one variable

// Key bit tricks to remember:
// n & (n - 1)  → clears the lowest set bit (power-of-2 check)
// n & (-n)     → isolates the lowest set bit
// n ^ n = 0    → XOR cancellation
// n ^ 0 = n    → XOR identity