DAY 14 / 30 · WEEK 2 REVIEW

Week 2 Review

Goal of the day

• Connect Days 8–13 into one decision process: given a new problem, know whether you need to sort, search, or recurse — and which specific algorithm fits the constraints.
• Solve 5 mixed practice problems that draw on more than one Week 2 idea at once.
• Walk away with a one-page cheat sheet of every sort/search template and complexity from Week 2.

Concept

Week 2 looks like six separate topics, but almost everything reduces to one move: take a problem of size n and shrink it, every step, by throwing away work you can prove doesn't matter. Merge sort shrinks by splitting in half and recombining (Day 10). Quick sort shrinks by partitioning around a pivot so one side never needs to be touched again relative to the other (Day 11). Binary search shrinks by halving a sorted range using one comparison (Day 12), and its variations shrink toward a boundary instead of an exact match (Day 13). Recursion (Day 9) is the mechanism that makes "shrink and repeat" possible without a hand-written loop stack. Even the three O(n²) sorts from Day 8 fit this frame in miniature — they just shrink the unsorted region by one element per pass instead of by half.

The skill this review trains: given a new problem, recognize which kind of shrinking it needs — half the array (search), one side of a partition (quick sort family), or the whole thing split and remerged (merge sort family) — before you write a single line.

Diagram: which Week 2 approach do I reach for?

Interactive visualization: quickselect — sorting and searching combined

Finding the kth largest element blends this week's two biggest ideas: Day 11's partition step (split around a pivot) AND Day 12/13's halving discipline (only chase the ONE side that can contain the answer, throw the rest away without ever recursing into it). That combination drops the average time from quick sort's O(n log n) down to O(n) — you never sort the side you don't need.

Dry run: 2nd largest of [9, 3, 7, 1, 8, 4, 2]

Target index = 7 elements − k(2) = index 5 in ascending sorted order. Four partition rounds, but each round only ever recurses into ONE side — exactly the halving discipline from binary search, just applied to an unsorted partition boundary instead of a sorted midpoint.

Week 2 cheat sheet — code templates

// BUBBLE SORT (Day 8) — O(n) best / O(n²) worst, O(1) space, stable
function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted — stop early
  }
  return arr;
}

// SELECTION SORT (Day 8b) — O(n²) always, O(1) space, NOT stable
function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    if (minIdx !== i) [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  return arr;
}

// INSERTION SORT (Day 8c) — O(n) best / O(n²) worst, O(1) space, stable
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
    arr[j + 1] = key;
  }
  return arr;
}

// MERGE SORT (Day 10) — O(n log n) always, O(n) space, 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 i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
  return result;
}

// QUICK SORT (Day 11) — O(n log n) avg / O(n²) worst, O(log n) space, NOT stable
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}
function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

// BINARY SEARCH — exact match (Day 12) — O(log n), O(1)
function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    else if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// BINARY SEARCH — narrowing/boundary (Day 13) — O(log n), O(1)
function findBound(nums, target, isFirst) {
  let lo = 0, hi = nums.length - 1, result = -1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) {
      result = mid;                     // record, then keep narrowing
      if (isFirst) hi = mid - 1; else lo = mid + 1;
    } else if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return result;
}

Complexity — everything from Week 2, at a glance

Interview corner

• If you can only remember one sort for an interview, which one — and why? Merge sort. It's the only one of Week 2's sorts that guarantees O(n log n) in the worst case AND is stable — quick sort can degrade to O(n²) on unlucky pivots, and the O(n²) sorts don't scale. The tradeoff you should be ready to name is merge sort's O(n) auxiliary space, versus quick sort's in-place O(log n).
  ↳ Common follow-up: "When would you pick quick sort anyway?" — when average-case speed and in-place memory matter more than a worst-case guarantee, e.g. sorting large in-memory arrays where you control (or can randomize) the pivot choice to make the O(n²) case unlikely.
• How is quickselect different from running quick sort and reading off an index? Quick sort recurses into both sides of every partition to fully sort the array — O(n log n) average. Quickselect partitions once, checks which side the target index falls in, and recurses into only that one side — the other side is thrown away unsorted, because you never needed it. That single change is what drops the average time to O(n).
• Does "binary search needs a sorted array" still hold this week? Not as an absolute rule. Day 13's search-on-answer problems run binary search over a range of candidate answers, not over a literal array — the real requirement is a monotonic predicate (false-then-true, or vice versa) with exactly one flip point.
  ⚠ Trap: don't dismiss binary search just because the input "isn't sorted" — check whether there's a monotonic yes/no question hiding underneath, the way Koko Eating Bananas (Day 13) and quickselect's partition boundary (today) both do.
• Why does recursion show up in merge sort and quick sort, but not in bubble, selection, or insertion sort? Merge and quick sort both work by splitting the problem into smaller versions of itself (a sub-array to sort) — that's exactly what recursion (Day 9) is for. The O(n²) sorts never break the problem into a smaller independent subproblem; they just do one more linear pass over a slightly smaller range, which a simple loop already expresses cleanly.

How to talk through it out loud: on a mixed problem, name the constraint that decides your algorithm before you name the algorithm — "this needs the array sorted first, and since I also need stability for ties, that pushes me toward merge sort over quick sort" or "this is asking for a boundary, not an exact match, so I need Day 13's narrowing template, not Day 12's." Interviewers are listening for the reasoning chain from constraint to choice, not a memorized algorithm name — that's exactly what separates "I've seen this before" from "I know why this is the right tool."

5 mixed practice problems

var solution = function(isBadVersion) {
  return function(n) {
    let lo = 1, hi = n;
    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (isBadVersion(mid)) hi = mid;      // mid is bad — answer is at or before mid
      else lo = mid + 1;                    // mid is good — answer is after mid
    }
    return lo;
  };
};

function intersect(nums1, nums2) {
  const a = nums1.slice().sort((x, y) => x - y);
  const b = nums2.slice().sort((x, y) => x - y);
  let i = 0, j = 0;
  const result = [];
  while (i < a.length && j < b.length) {
    if (a[i] === b[j]) { result.push(a[i]); i++; j++; }
    else if (a[i] < b[j]) i++;
    else j++;
  }
  return result;
}

function searchMatrix(matrix, target) {
  const m = matrix.length, n = matrix[0].length;
  let lo = 0, hi = m * n - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    const row = Math.floor(mid / n), col = mid % n;
    const val = matrix[row][col];
    if (val === target) return true;
    else if (val < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return false;
}

function hIndex(citations) {
  const sorted = citations.slice().sort((a, b) => b - a);
  let h = 0;
  for (let i = 0; i < sorted.length; i++) {
    if (sorted[i] >= i + 1) h = i + 1;
    else break; // citations only get smaller from here — no point continuing
  }
  return h;
}

function kthSmallest(matrix, k) {
  const n = matrix.length;
  let lo = matrix[0][0], hi = matrix[n - 1][n - 1];

  function countLessEqual(x) {
    let count = 0, col = n - 1;
    for (let row = 0; row < n; row++) {
      while (col >= 0 && matrix[row][col] > x) col--;
      count += col + 1; // every entry in this row up to `col` is <= x
    }
    return count;
  }

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (countLessEqual(mid) < k) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Quiz