// Two Sum (sorted) — O(n) time, O(1) space
function twoSum(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    sum < target ? left++ : right--;
  }
}

// Valid Palindrome — O(n) time, O(1) space
function isPalindrome(s) {
  s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  let l = 0, r = s.length - 1;
  while (l < r) if (s[l++] !== s[r--]) return false;
  return true;
}

// Container With Most Water — O(n)
function maxArea(heights) {
  let l = 0, r = heights.length - 1, max = 0;
  while (l < r) {
    max = Math.max(max, Math.min(heights[l], heights[r]) * (r - l));
    heights[l] < heights[r] ? l++ : r--;
  }
  return max;
}

// Longest Substring Without Repeating Chars — O(n)
function lengthOfLongestSubstring(s) {
  const seen = new Map();
  let max = 0, left = 0;
  for (let r = 0; r < s.length; r++) {
    if (seen.has(s[r]) && seen.get(s[r]) >= left)
      left = seen.get(s[r]) + 1;
    seen.set(s[r], r);
    max = Math.max(max, r - left + 1);
  }
  return max;
}

// Max Sum Subarray of Size K — O(n)
function maxSumK(arr, k) {
  let sum = arr.slice(0, k).reduce((a,b) => a+b, 0);
  let max = sum;
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];  // add right, remove left
    max = Math.max(max, sum);
  }
  return max;
}

// Two Sum (unsorted) — O(n)
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const comp = target - nums[i];
    if (map.has(comp)) return [map.get(comp), i];
    map.set(nums[i], i);
  }
}

// Valid Anagram — frequency count
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const freq = {};
  for (const c of s) freq[c] = (freq[c] ?? 0) + 1;
  for (const c of t) {
    if (!freq[c]) return false;
    freq[c]--;
  }
  return true;
}

// Group Anagrams — sort key trick
function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = [...s].sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

// Build prefix sum — O(n) setup, O(1) per query
function buildPrefix(arr) {
  const prefix = [0];
  for (const n of arr) prefix.push(prefix.at(-1) + n);
  return prefix;
}
// Sum from i to j: prefix[j+1] - prefix[i]

// Subarray Sum Equals K — O(n)
function subarraySum(nums, k) {
  const counts = new Map([[0, 1]]);
  let sum = 0, result = 0;
  for (const n of nums) {
    sum += n;
    result += counts.get(sum - k) ?? 0;
    counts.set(sum, (counts.get(sum) ?? 0) + 1);
  }
  return result;
}

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

// Build list: 1 → 2 → 3 → null
const head = new ListNode(1, new ListNode(2, new ListNode(3)));

// Traverse — O(n)
let curr = head;
while (curr) { console.log(curr.val); curr = curr.next; }

// Reverse a linked list — 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;  // new head
}

// Detect cycle — O(n) time, O(1) space
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

// Find middle — slow stops at middle when fast reaches end
function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

// Merge two sorted lists — O(n+m)
function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  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;
}

// Stack uses array with push/pop — both O(1)
const stack = [];
stack.push(1);      // add to top
stack.at(-1);       // peek top without removing
stack.pop();        // remove from top

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

// Monotonic Decreasing Stack — Next Greater Element
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];
    }
    stack.push(i);
  }
  return result;
}

// ⚠️ Array.shift() is O(n) — use index pointer for O(1)
class Queue {
  constructor() { this.data = []; this.head = 0; }
  enqueue(val) { this.data.push(val); }
  dequeue() { return this.data[this.head++]; }
  peek()    { return this.data[this.head]; }
  isEmpty() { return this.head >= this.data.length; }
}

// Implement Stack using two Queues (classic interview trick)
// Implement Queue using two Stacks (classic interview trick)
class MyQueue {
  constructor() { this.inbox = []; this.outbox = []; }
  push(x)  { this.inbox.push(x); }
  peek() {
    if (!this.outbox.length)
      while (this.inbox.length) this.outbox.push(this.inbox.pop());
    return this.outbox.at(-1);
  }
  pop()    { this.peek(); return this.outbox.pop(); }
  empty()  { return !this.inbox.length && !this.outbox.length; }
}

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

// Inorder: left → root → right (gives SORTED output for BST!)
function inorder(node, result=[]) {
  if (!node) return result;
  inorder(node.left, result);
  result.push(node.val);
  inorder(node.right, result);
  return result;
}

// Preorder: root → left → right (used for copying tree)
// Postorder: left → right → root (used for deleting tree)

// BFS — Level Order (uses Queue)
function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const level = [];
    const size = queue.length;  // snapshot size for this level
    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;
}

// Max Depth — O(n)
const maxDepth = root =>
  root ? 1 + Math.max(maxDepth(root.left), maxDepth(root.right)) : 0;

// Check Balanced — O(n)
function isBalanced(root) {
  function height(node) {
    if (!node) return 0;
    const l = height(node.left);
    if (l === -1) return -1;
    const r = height(node.right);
    if (r === -1 || Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
  }
  return height(root) !== -1;
}

// Lowest Common Ancestor — O(n)
function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left  = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  return !left ? right : !right ? left : root;
}

// Validate BST — O(n)
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);
}

class MinHeap {
  constructor() { this.heap = []; }

  push(val) {
    this.heap.push(val);
    this._bubbleUp(this.heap.length - 1);
  }

  pop() {
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length) { this.heap[0] = last; this._sinkDown(0); }
    return min;
  }

  peek() { return this.heap[0]; }
  size() { return this.heap.length; }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }

  _sinkDown(i) {
    const n = this.heap.length;
    while (true) {
      let min = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.heap[l] < this.heap[min]) min = l;
      if (r < n && this.heap[r] < this.heap[min]) min = r;
      if (min === i) break;
      [this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
      i = min;
    }
  }
}

// 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);
  // Sort approach for interviews without MinHeap available:
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k).map(e => e[0]);
}

// Adjacency List — O(V+E) space (preferred)
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A'],
  D: ['B']
};

// Build from edge list
function buildGraph(edges) {
  const adj = new Map();
  for (const [u, v] of edges) {
    if (!adj.has(u)) adj.set(u, []);
    if (!adj.has(v)) adj.set(v, []);
    adj.get(u).push(v);
    adj.get(v).push(u);  // remove for directed graph
  }
  return adj;
}

function bfs(graph, start, target) {
  const visited = new Set([start]);
  const queue = [[start, 0]];  // [node, distance]

  while (queue.length) {
    const [node, dist] = queue.shift();
    if (node === target) return dist;

    for (const neighbor of (graph[node] ?? [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }
  return -1;  // not reachable
}

// Number of Islands — BFS on 2D grid
function numIslands(grid) {
  let count = 0;
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1') { bfsIsland(grid, r, c); count++; }
    }
  }
  return count;
}
function bfsIsland(grid, r, c) {
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  const q = [[r,c]]; grid[r][c] = '0';  // mark visited
  while (q.length) {
    const [row, col] = q.shift();
    for (const [dr,dc] of dirs) {
      const nr = row+dr, nc = col+dc;
      if (nr>=0&&nr=0&&nc0].length&&grid[nr][nc]==='1') {
        grid[nr][nc] = '0'; q.push([nr,nc]);
      }
    }
  }
}

// DFS recursive template
function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  // process node here
  for (const neighbor of (graph[node] ?? [])) {
    dfs(graph, neighbor, visited);
  }
}

// Detect cycle in directed graph
function hasCycle(graph, n) {
  const WHITE=0, GRAY=1, BLACK=2;
  const color = new Array(n).fill(WHITE);
  function dfs(node) {
    color[node] = GRAY;  // currently visiting
    for (const nb of graph[node]) {
      if (color[nb] === GRAY) return true;  // back edge = cycle
      if (color[nb] === WHITE && dfs(nb)) return true;
    }
    color[node] = BLACK;  // fully processed
    return false;
  }
  return [...Array(n).keys()].some(i => color[i]===WHITE && dfs(i));
}

Algorithm      Best       Average    Worst      Space  Stable
─────────────────────────────────────────────────────────────
Bubble Sort    O(n)       O(n²)      O(n²)      O(1)   Yes
Selection Sort O(n²)      O(n²)      O(n²)      O(1)   No
Insertion Sort O(n)       O(n²)      O(n²)      O(1)   Yes
Merge Sort     O(n log n) O(n log n) O(n log n) O(n)   Yes
Quick Sort     O(n log n) O(n log n) O(n²)      O(log) No
Heap Sort      O(n log n) O(n log n) O(n log n) O(1)   No
Counting Sort  O(n+k)     O(n+k)     O(n+k)     O(k)   Yes
─────────────────────────────────────────────────────────────
JS Array.sort() uses TimSort → O(n log n) stable

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(left, right) {
  const result = [];
  let l = 0, r = 0;
  while (l < left.length && r < right.length) {
    result.push(left[l] <= right[r] ? left[l++] : right[r++]);
  }
  return [...result, ...left.slice(l), ...right.slice(r)];
}
// Time: O(n log n) guaranteed | Space: O(n)
// Stable: Yes — equal elements keep original order

function quickSort(arr, lo=0, hi=arr.length-1) {
  if (lo >= hi) return;
  const pivot = partition(arr, lo, hi);
  quickSort(arr, lo, pivot - 1);
  quickSort(arr, pivot + 1, hi);
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];  // last element as pivot
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]]; i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}
// Avg: O(n log n) | Worst: O(n²) if already sorted + bad pivot
// Space: O(log n) recursion stack | Not stable

// Template 1: Find exact target
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);  // avoid overflow
    if (arr[mid] === target) return mid;
    arr[mid] < target ? lo = mid + 1 : hi = mid - 1;
  }
  return -1;
}

// Template 2: Find leftmost position (first occurrence)
function leftBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    arr[mid] < target ? lo = mid + 1 : hi = mid;
  }
  return lo;  // insertion point
}

// Binary Search on answer — "Is it possible to do X with Y?"
// Koko eating bananas, split array with minimum largest sum, etc.
function minCapacity(piles, hours) {
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    canFinish(piles, hours, mid) ? hi = mid : lo = mid + 1;
  }
  return lo;
}
function canFinish(piles, hours, speed) {
  return piles.reduce((h, p) => h + Math.ceil(p/speed), 0) <= hours;
}

// Fibonacci — 3 approaches

// Brute force: O(2^n)
const fib1 = n => n <= 1 ? n : fib1(n-1) + fib1(n-2);

// Top-down Memoization: O(n) time + O(n) space
function fib2(n, memo={}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib2(n-1, memo) + fib2(n-2, memo);
  return memo[n];
}

// Bottom-up Tabulation: O(n) time + O(n) space
function fib3(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
  return dp[n];
}

// Space-optimized: O(n) time + O(1) space
function fib4(n) {
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}

// Climbing Stairs (distinct ways to climb n stairs, 1 or 2 steps)
function climbStairs(n) {
  let [a, b] = [1, 1];
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;  // same as fibonacci!
}

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

// House Robber (max rob without adjacent houses)
function rob(nums) {
  let [prev2, prev1] = [0, 0];
  for (const n of nums) {
    [prev2, prev1] = [prev1, Math.max(prev1, prev2 + n)];
  }
  return prev1;
}

// Longest Common Subsequence — 2D DP
function longestCommonSubsequence(text1, text2) {
  const m = text1.length, n = text2.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] = text1[i-1]===text2[j-1]
        ? dp[i-1][j-1]+1
        : Math.max(dp[i-1][j], dp[i][j-1]);
  return dp[m][n];
}

CLUE IN PROBLEM                      → USE THIS PATTERN
─────────────────────────────────────────────────────────────────
"sorted array" + "pair/triplet"      → Two Pointers
"subarray/substring" + "longest/shortest/exactly K" → Sliding Window
"have I seen this before?"           → HashMap / HashSet
"sum of subarray from i to j"        → Prefix Sum
"top K / K largest / K most frequent" → Heap (Min/Max)
"shortest path" / "minimum steps"   → BFS (unweighted graph)
"all paths" / "any path"             → DFS / Backtracking
"tree problem" (most)                → DFS Recursion
"tree level by level"                → BFS
"sorted data" + "search"             → Binary Search
"sorted data" + "O(n²) feels wrong"  → Binary Search on answer
"overlapping subproblems"            → Dynamic Programming
"permutations/combinations/subsets"  → Backtracking (DFS)
"interval overlap"                   → Sort by start, greedy
"next greater/smaller element"       → Monotonic Stack
"connected components"               → Union Find / DFS
─────────────────────────────────────────────────────────────────

// All subsets — O(2^n)
function subsets(nums) {
  const result = [];
  function backtrack(start, current) {
    result.push([...current]);
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);      // choose
      backtrack(i + 1, current); // explore
      current.pop();              // undo (backtrack)
    }
  }
  backtrack(0, []);
  return result;
}

// All permutations — O(n!)
function permute(nums) {
  const result = [];
  function backtrack(current, remaining) {
    if (!remaining.length) { result.push([...current]); return; }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      backtrack(current, [...remaining.slice(0,i),...remaining.slice(i+1)]);
      current.pop();
    }
  }
  backtrack([], nums);
  return result;
}

1. UNDERSTAND: Repeat the problem back.
   "So we need to find... and the output should be...
    Can input be negative? What if array is empty?"

2. EXAMPLES: Walk through given examples + edge cases.
   "For input [2,7,11,15] target 9 → output [0,1]
    Edge case: what if no pair exists?"

3. BRUTE FORCE: Always mention it first.
   "Naive approach: nested loops, O(n²) time.
    But we can do better..."

4. OPTIMIZE: State the pattern you'll use.
   "I'll use a HashMap to reduce to O(n) time, O(n) space."

5. CODE: Talk through what you're writing.
   "I'll initialize a map, then loop through..."

6. VERIFY: Trace through your code with example.
   "For input [2,7,11,15]: i=0, comp=7, not in map...
    i=1, comp=2, found! Return [0,1] ✓"

7. COMPLEXITY: Always state this at the end.
   "Time: O(n), Space: O(n)"