Crack the Coding Interview in 100 Hours

function groupAnagrams(strs) {
  const groups = new Map();          // sortedKey -> list of words
  for (const s of strs) {
    // Two words are anagrams iff their sorted letters match.
    const key = [...s].sort().join("");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(s);
  }
  return [...groups.values()];
}
// groupAnagrams(["eat","tea","tan","ate","nat","bat"])
//   -> [["eat","tea","ate"], ["tan","nat"], ["bat"]]

// Bucket sort by frequency: no sorting needed, O(n) overall.
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);

  // buckets[f] = numbers that appear exactly f times. Max f is nums.length.
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [n, f] of freq) buckets[f].push(n);

  const out = [];
  for (let f = buckets.length - 1; f >= 0 && out.length < k; f--) {
    for (const n of buckets[f]) {
      out.push(n);
      if (out.length === k) break;
    }
  }
  return out;
}
// topKFrequent([1,1,1,2,2,3], 2) -> [1, 2]

function isPalindrome(s) {
  let l = 0, r = s.length - 1;
  const ok = (c) => /[a-z0-9]/i.test(c);   // alphanumeric only
  while (l < r) {
    while (l < r && !ok(s[l])) l++;        // skip junk from the left
    while (l < r && !ok(s[r])) r--;        // skip junk from the right
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
    l++; r--;
  }
  return true;
}
// isPalindrome("A man, a plan, a canal: Panama") -> true

function threeSum(nums) {
  nums.sort((a, b) => a - b);      // sort enables the two-pointer sweep
  const res = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) break;                    // all positive from here
    if (i > 0 && nums[i] === nums[i - 1]) continue; // skip dup anchor
    let l = i + 1, r = nums.length - 1;
    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r];
      if (sum < 0) l++;
      else if (sum > 0) r--;
      else {
        res.push([nums[i], nums[l], nums[r]]);
        l++; r--;
        while (l < r && nums[l] === nums[l - 1]) l++;   // skip dup
        while (l < r && nums[r] === nums[r + 1]) r--;   // skip dup
      }
    }
  }
  return res;
}
// threeSum([-1,0,1,2,-1,-4]) -> [[-1,-1,2], [-1,0,1]]

function maxProfit(prices) {
  let minSoFar = prices[0], best = 0;
  for (const p of prices) {
    minSoFar = Math.min(minSoFar, p);   // cheapest buy day seen
    best = Math.max(best, p - minSoFar); // best sell-today profit
  }
  return best;
}
// maxProfit([7,1,5,3,6,4]) -> 5   (buy at 1, sell at 6)

function lengthOfLongestSubstring(s) {
  const lastSeen = new Map();   // char -> last index
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    // If we've seen c inside the current window, jump left past it.
    if (lastSeen.has(c) && lastSeen.get(c) >= left) {
      left = lastSeen.get(c) + 1;
    }
    lastSeen.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
// lengthOfLongestSubstring("abcabcbb") -> 3  ("abc")

function isValid(s) {
  const stack = [];
  const pairs = { ")": "(", "]": "[", "}": "{" };
  for (const c of s) {
    if (c in pairs) {
      // Closing bracket must match the most recent opener.
      if (stack.pop() !== pairs[c]) return false;
    } else {
      stack.push(c);   // opener
    }
  }
  return stack.length === 0;   // nothing left unclosed
}
// isValid("([]{})") -> true ;  isValid("(]") -> false

function dailyTemperatures(temps) {
  const res = new Array(temps.length).fill(0);
  const stack = [];   // indices of days awaiting a warmer day (decreasing temps)
  for (let i = 0; i < temps.length; i++) {
    // While today is warmer than the day on top, we've found its answer.
    while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
      const j = stack.pop();
      res[j] = i - j;
    }
    stack.push(i);
  }
  return res;
}
// dailyTemperatures([73,74,75,71,69,72,76,73]) -> [1,1,4,2,1,1,0,0]

function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);   // avoids overflow; >>1 is /2
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
// search([-1,0,3,5,9,12], 9) -> 4

function minEatingSpeed(piles, h) {
  // Feasibility is monotonic: if speed k works, so does any speed > k.
  // So binary-search the SMALLEST k in [1, max(piles)] that fits in h hours.
  const hoursAt = (k) =>
    piles.reduce((sum, p) => sum + Math.ceil(p / k), 0);

  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (hoursAt(mid) <= h) hi = mid;   // fast enough -> try slower
    else lo = mid + 1;                 // too slow  -> must go faster
  }
  return lo;
}
// minEatingSpeed([3,6,7,11], 8) -> 4

// ListNode = { val, next }
function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;   // save the rest of the list
    curr.next = prev;         // flip the pointer
    prev = curr;              // advance prev
    curr = next;              // advance curr
  }
  return prev;                // new head
}
// 1->2->3->null  becomes  3->2->1->null

// Floyd's tortoise & hare: slow moves 1 step, fast moves 2.
// If there's a loop, fast eventually laps slow and they meet.
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;   // fast fell off the end -> no cycle
}

// TreeNode = { val, left, right }
function maxDepth(root) {
  if (!root) return 0;                    // base case: empty subtree
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// The whole shape of tree recursion: base case, recurse both sides, combine.

function levelOrder(root) {
  const res = [];
  if (!root) return res;
  let queue = [root];                 // BFS, one level at a time
  while (queue.length) {
    const level = [], next = [];
    for (const node of queue) {
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    res.push(level);
    queue = next;                     // whole next level at once
  }
  return res;
}
// A tree [3,9,20,null,null,15,7] -> [[3], [9,20], [15,7]]

class TrieNode {
  children = {};       // char -> TrieNode
  isEnd = false;       // does a word end here?
}

class Trie {
  root = new TrieNode();

  insert(word) {
    let node = this.root;
    for (const c of word) {
      node.children[c] ??= new TrieNode();   // create branch if missing
      node = node.children[c];
    }
    node.isEnd = true;
  }

  search(word) {
    const node = this._find(word);
    return node !== null && node.isEnd;      // must be a full word
  }

  startsWith(prefix) {
    return this._find(prefix) !== null;      // any node is enough
  }

  _find(str) {
    let node = this.root;
    for (const c of str) {
      if (!node.children[c]) return null;
      node = node.children[c];
    }
    return node;
  }
}

// Keep a MIN-heap of the k largest seen so far. Its root is the answer.
// (Reusing the MinHeap from Foundations.)
function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();   // evict the smallest -> keep top k
  }
  return heap.peek();                  // kth largest = smallest of the top k
}
// findKthLargest([3,2,1,5,6,4], 2) -> 5

// Two heaps: a MAX-heap for the lower half, a MIN-heap for the upper half.
// Keep them balanced; the median is a root (or the average of both roots).
class MedianFinder {
  low = new MaxHeap();    // lower half (max at root)
  high = new MinHeap();   // upper half (min at root)

  addNum(num) {
    this.low.push(num);
    this.high.push(this.low.pop());        // funnel largest-of-low into high
    if (this.high.size() > this.low.size())
      this.low.push(this.high.pop());      // rebalance: low keeps the extra
  }

  findMedian() {
    if (this.low.size() > this.high.size()) return this.low.peek();
    return (this.low.peek() + this.high.peek()) / 2;
  }
}

function subsets(nums) {
  const res = [], path = [];
  const backtrack = (start) => {
    res.push([...path]);              // every node is a valid subset
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);             // choose
      backtrack(i + 1);              // explore (i+1: no reuse, no dup order)
      path.pop();                    // un-choose
    }
  };
  backtrack(0);
  return res;
}
// subsets([1,2,3]) -> [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

function combinationSum(candidates, target) {
  const res = [], path = [];
  const backtrack = (start, remaining) => {
    if (remaining === 0) { res.push([...path]); return; }
    if (remaining < 0) return;                  // overshot: prune
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      backtrack(i, remaining - candidates[i]);  // i, not i+1: reuse allowed
      path.pop();
    }
  };
  backtrack(0, target);
  return res;
}
// combinationSum([2,3,6,7], 7) -> [[2,2,3], [7]]

function numIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;

  const sink = (r, c) => {                     // DFS flood-fill
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] !== "1") return;
    grid[r][c] = "0";                          // mark visited (sink the land)
    sink(r + 1, c); sink(r - 1, c);
    sink(r, c + 1); sink(r, c - 1);
  };

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

  return count;
}

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [course, pre] of prerequisites) {
    graph[pre].push(course);   // pre -> course
    indeg[course]++;
  }

  // Kahn's algorithm: repeatedly take a course with no remaining prereqs.
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) queue.push(i);

  let taken = 0, head = 0;
  while (head < queue.length) {
    const c = queue[head++];
    taken++;
    for (const next of graph[c]) {
      if (--indeg[next] === 0) queue.push(next);
    }
  }
  return taken === numCourses;   // all taken => no cycle
}
// canFinish(2, [[1,0]]) -> true ;  canFinish(2, [[1,0],[0,1]]) -> false

// Dijkstra with a min-heap of [dist, node]. Returns the time for the
// signal to reach ALL nodes, or -1 if some are unreachable.
function networkDelayTime(times, n, k) {
  const graph = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) graph[u].push([v, w]);

  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;
  const heap = [[0, k]];                 // [distance, node], min by distance

  while (heap.length) {
    heap.sort((a, b) => a[0] - b[0]);    // simplest correct PQ (small inputs)
    const [d, u] = heap.shift();
    if (d > dist[u]) continue;           // stale entry
    for (const [v, w] of graph[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        heap.push([dist[v], v]);
      }
    }
  }

  let ans = 0;
  for (let i = 1; i <= n; i++) ans = Math.max(ans, dist[i]);
  return ans === Infinity ? -1 : ans;
}
// networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2) -> 2

function climbStairs(n) {
  // Ways to reach step i = ways to i-1 (one step) + ways to i-2 (two steps).
  // That's Fibonacci. Keep only the last two values -> O(1) space.
  let oneBack = 1, twoBack = 1;
  for (let i = 2; i <= n; i++) {
    [twoBack, oneBack] = [oneBack, oneBack + twoBack];
  }
  return oneBack;
}
// climbStairs(5) -> 8

function rob(nums) {
  // At each house: skip it (keep prev best) or rob it (best before last + this).
  let prev = 0, prev2 = 0;
  for (const n of nums) {
    const take = prev2 + n;
    [prev2, prev] = [prev, Math.max(prev, take)];
  }
  return prev;
}
// rob([2,7,9,3,1]) -> 12   (rob houses 2 + 9 + 1)

function uniquePaths(m, n) {
  // Paths to a cell = paths from above + paths from the left.
  // One row is enough: row[j] += row[j-1] rolls the 2-D table into 1-D.
  const row = new Array(n).fill(1);
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++)
      row[j] += row[j - 1];
  return row[n - 1];
}
// uniquePaths(3, 7) -> 28