DSA —
Zero to Interview
Ready

// O(1) — constant, no matter size of input
const get = (arr, i) => arr[i];
const setMap = (map, k, v) => map.set(k, v);

// O(n) — one pass through array
const sum = (arr) => arr.reduce((a, b) => a + b, 0);

// O(n²) — nested loops over same input
function hasDupe(arr) {
  for (let i = 0; i < arr.length; i++)         // n
    for (let j = i + 1; j < arr.length; j++)   // n-1, n-2...
      if (arr[i] === arr[j]) return true;        // → O(n²)
  return false;
}
// Better: O(n) with HashSet
const hasDupeO1 = (arr) => arr.length !== new Set(arr).size;

// O(log n) — halving the input each step
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);     // avoid overflow
    if (arr[mid] === target) return mid;
    arr[mid] < target ? lo = mid + 1 : hi = mid - 1;
  }
  return -1;
}                                               // → O(log n) time, O(1) space

// Space complexity — memory used
// O(1): variables only. O(n): array/map proportional to input.
// Recursive calls use O(depth) stack space!

// ─── Prefix Sum — range query in O(1) after O(n) prep ─────
function buildPrefix(arr) {
  const prefix = [0];
  for (const n of arr) prefix.push(prefix.at(-1) + n);
  return prefix;
}
// rangeSum(i, j) = prefix[j+1] - prefix[i]  → O(1) per query!

// ─── Kadane's Algorithm — Maximum Subarray Sum O(n) ───────
function maxSubarray(nums) {
  let maxSum = -Infinity, curr = 0;
  for (const n of nums) {
    curr = Math.max(n, curr + n);      // extend or restart
    maxSum = Math.max(maxSum, curr);
  }
  return maxSum;
}

// ─── Dutch National Flag — sort 0,1,2 in O(n) one pass ────
function sortColors(nums) {
  let lo = 0, mid = 0, hi = nums.length - 1;
  while (mid <= hi) {
    if (nums[mid] === 0) [nums[lo++], nums[mid++]] = [nums[mid], nums[lo]];
    else if (nums[mid] === 2) [nums[mid], nums[hi--]] = [nums[hi], nums[mid]];
    else mid++;
  }
}

// ─── String: Anagram check O(n) ───────────────────────────
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - 97]++;
    count[t.charCodeAt(i) - 97]--;
  }
  return count.every(c => c === 0);
}

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

// ─── Reverse Linked List O(n) ─────────────────────────────
function reverse(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;  // save
    curr.next = prev;         // reverse pointer
    prev = curr;              // advance prev
    curr = next;              // advance curr
  }
  return prev;
}

// ─── Detect Cycle — Floyd's Tortoise & Hare O(n) O(1) ────
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast?.next) {
    slow = slow.next;          // 1 step
    fast = fast.next.next;     // 2 steps
    if (slow === fast) return true;   // they meet → cycle!
  }
  return false;
}

// ─── Find Middle — slow/fast pointers ────────────────────
function findMiddle(head) {
  let slow = head, fast = head;
  while (fast?.next) { slow = slow.next; fast = fast.next.next; }
  return slow;  // slow is at middle when fast reaches end
}

// ─── Merge Two Sorted Lists O(n+m) ───────────────────────
function mergeSorted(l1, l2) {
  const dummy = new ListNode(0);  // dummy head trick
  let curr = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
    else { curr.next = l2; l2 = l2.next; }
    curr = curr.next;
  }
  curr.next = l1 ?? l2;
  return dummy.next;
}

// ─── Remove Nth From End — two-pointer gap trick ──────────
function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);
  let fast = dummy, slow = dummy;
  for (let i = 0; i <= n; i++) fast = fast.next;  // gap of n+1
  while (fast) { fast = fast.next; slow = slow.next; }
  slow.next = slow.next.next;          // skip the nth node
  return dummy.next;
}

// ─── Valid Parentheses — classic stack problem ────────────
function isValid(s) {
  const stack = [], map = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if ('([{'.includes(ch)) stack.push(ch);
    else if (stack.pop() !== map[ch]) return false;
  }
  return stack.length === 0;
}

// ─── Monotonic Stack — Next Greater Element O(n) ──────────
// TEMPLATE: maintains stack in decreasing order
function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = [];    // stores INDICES
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[i] > nums[stack.at(-1)]) {
      result[stack.pop()] = nums[i];   // current is next greater for popped
    }
    stack.push(i);
  }
  return result;
}
// Same pattern: Largest Rectangle in Histogram, Daily Temperatures, Stock Span

// ─── Queue with two stacks (implement queue using stacks) ─
class MyQueue {
  in = []; out = [];
  push(x) { this.in.push(x); }
  pop() {
    if (!this.out.length) while (this.in.length) this.out.push(this.in.pop());
    return this.out.pop();
  }
}

// ─── Sliding Window Maximum — deque O(n) ─────────────────
function maxSlidingWindow(nums, k) {
  const deque = [], result = [];
  for (let i = 0; i < nums.length; i++) {
    if (deque[0] < i - k + 1) deque.shift();  // remove out-of-window
    while (deque.length && nums[deque.at(-1)] < nums[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

// ─── Two Sum — the canonical HashMap problem O(n) ─────────
function twoSum(nums, target) {
  const seen = new Map();   // 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);
  }
}
// Key insight: store what you've SEEN, look for what you NEED

// ─── Frequency counting — group anagrams O(n*k) ──────────
function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = [...s].sort().join('');   // sorted string = canonical form
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

// ─── LRU Cache — HashMap + Doubly Linked List O(1) ────────
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();  // Map preserves INSERTION ORDER in JS!
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key); this.map.set(key, val); // move to end = most recent
    return val;
  }
  put(key, value) {
    this.map.delete(key);
    if (this.map.size === this.cap) this.map.delete(this.map.keys().next().value);
    this.map.set(key, value);
  }
}

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

// ─── DFS Traversals (recursive) ───────────────────────────
const preorder  = node => node ? [node.val, ...preorder(node.left), ...preorder(node.right)] : [];
const inorder   = node => node ? [...inorder(node.left), node.val, ...inorder(node.right)] : [];
const postorder = node => node ? [...postorder(node.left), ...postorder(node.right), node.val] : [];
// BST inorder = SORTED array (crucial property!)

// ─── BFS / Level Order Traversal ──────────────────────────
function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const level = [], size = queue.length;
    for (let i = 0; i < size; 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;
}

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

// ─── Lowest Common Ancestor (LCA) ────────────────────────
function lca(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lca(root.left, p, q);
  const right = lca(root.right, p, q);
  return left && right ? root : left ?? right;  // both found = LCA
}

// ─── 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);
}

// ─── Diameter of Binary Tree ──────────────────────────────
function diameterOfBinaryTree(root) {
  let max = 0;
  function depth(node) {
    if (!node) return 0;
    const l = depth(node.left), r = depth(node.right);
    max = Math.max(max, l + r);   // path through this node
    return 1 + Math.max(l, r);    // height from this node
  }
  depth(root); return max;
}

// ─── Kth Largest — min-heap of size k ─────────────────────
// Keep a min-heap. If size > k, pop the min.
// After all elements, root = kth largest.
// O(n log k) time — better than sort O(n log n) for small k

// ─── Top K Frequent Elements O(n log k) ───────────────────
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
  // Bucket sort by frequency — O(n) approach!
  const buckets = new Array(nums.length + 1).fill(null).map(() => []);
  freq.forEach((count, num) => buckets[count].push(num));
  const result = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--)
    result.push(...buckets[i]);
  return result.slice(0, k);
}

// ─── Median of Data Stream — two heaps trick ──────────────
// Lower half: max-heap (top = max of lower)  
// Upper half: min-heap (top = min of upper)
// Balance sizes: |lowerHeap| - |upperHeap| ≤ 1
// Median = avg of tops (even) or top of larger heap (odd)

// ─── Graph representation ─────────────────────────────────
const graph = new Map();  // adjacency list — most common
graph.set('A', ['B', 'C']);
graph.set('B', ['A', 'D']);

// ─── BFS — shortest path in UNWEIGHTED graph O(V+E) ───────
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

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

// ─── Number of Islands — DFS on grid O(m*n) ──────────────
function numIslands(grid) {
  let count = 0;
  function dfs(r, c) {
    if (r<0||c<0||r>=grid.length||c>=grid[0].length||grid[r][c]!=='1') return;
    grid[r][c] = '0';   // mark visited by mutating
    [[1,0],[-1,0],[0,1],[0,-1]].forEach(([dr,dc]) => dfs(r+dr, c+dc));
  }
  for (let r=0; r<grid.length; r++)
    for (let c=0; c<grid[0].length; c++)
      if (grid[r][c]==='1') { dfs(r,c); count++; }
  return count;
}

// ─── Topological Sort (Kahn's BFS) — for DAG dependencies ─
function topoSort(n, edges) {
  const adj = Array.from({length: n}, () => []);
  const inDegree = new Array(n).fill(0);
  edges.forEach(([u,v]) => { adj[u].push(v); inDegree[v]++; });
  const queue = [], result = [];
  for (let i=0; i<n; i++) if (!inDegree[i]) queue.push(i);
  while (queue.length) {
    const node = queue.shift(); result.push(node);
    for (const next of adj[node]) if (!--inDegree[next]) queue.push(next);
  }
  return result.length === n ? result : [];  // empty = cycle exists
}

// ─── Merge Sort — stable, O(n log n) guaranteed ───────────
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}
function merge(l, r) {
  const result = []; let i = 0, j = 0;
  while (i < l.length && j < r.length)
    result.push(l[i] <= r[j] ? l[i++] : r[j++]);
  return [...result, ...l.slice(i), ...r.slice(j)];
}

// ─── Quick Sort — fastest in practice, O(n log n) avg ─────
function quickSort(arr, lo=0, hi=arr.length-1) {
  if (lo < hi) {
    const pi = partition(arr, lo, hi);
    quickSort(arr, lo, pi-1);
    quickSort(arr, pi+1, hi);
  }
  return arr;
}
function partition(arr, lo, hi) {
  const pivot = arr[hi]; let i = lo;
  for (let j = lo; j < hi; j++)
    if (arr[j] < pivot) [arr[i++], arr[j]] = [arr[j], arr[i]];
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

// ─── Template 1: Basic — find exact target ────────────────
function search(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] === target) return mid;
    arr[mid] < target ? lo = mid + 1 : hi = mid - 1;
  }
  return -1;
}

// ─── Template 2: Find first position satisfying condition ─
function firstTrue(arr, condition) {
  let lo = 0, hi = arr.length - 1, ans = -1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (condition(arr[mid])) { ans = mid; hi = mid - 1; }  // found, go left for first
    else lo = mid + 1;
  }
  return ans;
}

// ─── Search in Rotated Sorted Array ──────────────────────
function searchRotated(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {   // left half is sorted
      nums[lo] <= target && target < nums[mid] ? hi = mid-1 : lo = mid+1;
    } else {                        // right half is sorted
      nums[mid] < target && target <= nums[hi] ? lo = mid+1 : hi = mid-1;
    }
  }
  return -1;
}

// ─── Binary search on ANSWER — minimize max / maximize min
// "What is the minimum capacity to ship packages in D days?"
// lo = max(packages), hi = sum(packages)
// Binary search on capacity, check if feasible in D days
// Pattern: can(mid) → search in answer space, not array space!

// ─── Two Pointers — sorted array pair sum ─────────────────
function twoSumSorted(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const sum = nums[lo] + nums[hi];
    if (sum === target) return [lo, hi];
    sum < target ? lo++ : hi--;
  }
}

// ─── 3Sum — reduce to 2Sum with outer loop O(n²) ─────────
function threeSum(nums) {
  nums.sort((a,b) => a-b); const result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i-1]) continue;  // skip duplicates
    let lo = i+1, 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--]]); }
      else if (sum < 0) lo++; else hi--;
    }
  }
  return result;
}

// ─── Sliding Window TEMPLATE — variable size ──────────────
function slidingWindow(s, target) {
  let lo = 0, best = Infinity;
  const window = {};  // track window state

  for (let hi = 0; hi < s.length; hi++) {
    // 1. Expand: add s[hi] to window
    window[s[hi]] = (window[s[hi]] ?? 0) + 1;

    // 2. Shrink: while condition violated, remove s[lo] and advance lo
    while (/* condition violated */ false) {
      window[s[lo]]--;
      if (!window[s[lo]]) delete window[s[lo]];
      lo++;
    }
    // 3. Update answer
    best = Math.min(best, hi - lo + 1);
  }
  return best;
}
// Apply to: Minimum Window Substring, Longest Without Repeating,
//           Longest Repeating After Replacement, Fruit Into Baskets

// ─── BACKTRACKING TEMPLATE ────────────────────────────────
function backtrack(result, current, ...params) {
  if (baseCaseReached) { result.push([...current]); return; }
  for (const choice of choices) {
    current.push(choice);     // CHOOSE
    backtrack(result, current, ...newParams);  // EXPLORE
    current.pop();             // UNCHOOSE (backtrack)
  }
}

// ─── Permutations — O(n * n!) ─────────────────────────────
function permute(nums) {
  const result = [];
  const bt = (curr, used) => {
    if (curr.length === nums.length) { result.push([...curr]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used.has(i)) continue;
      curr.push(nums[i]); used.add(i);
      bt(curr, used);
      curr.pop(); used.delete(i);
    }
  };
  bt([], new Set()); return result;
}

// ─── Subsets — O(n * 2ⁿ) ─────────────────────────────────
function subsets(nums) {
  const result = [];
  const bt = (start, curr) => {
    result.push([...curr]);
    for (let i = start; i < nums.length; i++) {
      curr.push(nums[i]);
      bt(i + 1, curr);
      curr.pop();
    }
  };
  bt(0, []); return result;
}

// ─── Combination Sum — O(n^(target/min)) ─────────────────
function combinationSum(candidates, target) {
  const result = [];
  const bt = (start, curr, remaining) => {
    if (remaining === 0) { result.push([...curr]); return; }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) continue;  // prune!
      curr.push(candidates[i]);
      bt(i, curr, remaining - candidates[i]);    // can reuse same index
      curr.pop();
    }
  };
  candidates.sort((a,b) => a-b);  // sort enables pruning
  bt(0, [], target); return result;
}

// ─── Fibonacci — both approaches ─────────────────────────
// Top-down:
const memo = new Map();
const fib = n => n <= 1 ? n : (memo.get(n) ?? memo.set(n, fib(n-1) + fib(n-2)) && memo.get(n));
// Bottom-up O(n) time O(1) space:
function fibDP(n) {
  if (n<=1) return n; let [a,b] = [0,1];
  for (let i=2; i<=n; i++) [a,b] = [b, a+b];
  return b;
}

// ─── 0/1 Knapsack — O(n*W) ───────────────────────────────
function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = new Array(W+1).fill(0);          // space optimized to 1D
  for (let i=0; i<n; i++)
    for (let w=W; w>=weights[i]; w--)           // iterate BACKWARDS for 0/1
      dp[w] = Math.max(dp[w], dp[w-weights[i]] + values[i]);
  return dp[W];
}

// ─── Longest Common Subsequence O(m*n) ───────────────────
function lcs(s1, s2) {
  const m=s1.length, n=s2.length;
  const dp = Array.from({length:m+1}, () => new Array(n+1).fill(0));
  for (let i=1; i<=m; i++)
    for (let j=1; j<=n; j++)
      dp[i][j] = s1[i-1]===s2[j-1] ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j],dp[i][j-1]);
  return dp[m][n];
}

// ─── Coin Change — minimum coins O(amount * coins) ────────
function coinChange(coins, amount) {
  const dp = new Array(amount+1).fill(Infinity);
  dp[0] = 0;
  for (const coin of coins)
    for (let i=coin; i<=amount; i++)
      dp[i] = Math.min(dp[i], dp[i-coin]+1);
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// ─── Activity Selection / Non-overlapping Intervals ───────
function eraseOverlapIntervals(intervals) {
  intervals.sort((a,b) => a[1]-b[1]);  // sort by END time
  let removed = 0, prevEnd = -Infinity;
  for (const [start, end] of intervals) {
    if (start < prevEnd) removed++;   // overlap → remove
    else prevEnd = end;               // no overlap → keep
  }
  return removed;
}

// ─── Jump Game II — minimum jumps O(n) ───────────────────
function jump(nums) {
  let jumps = 0, curEnd = 0, farthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === curEnd) { jumps++; curEnd = farthest; }
  }
  return jumps;
}

// ─── Task Scheduler — greedy with counting ────────────────
// Sort tasks by frequency. Most frequent fills the "frames".
// Answer = max(tasks.length, (maxFreq-1) * (n+1) + tasksWithMaxFreq)