Day 14: Week 2 Review

DAY 14 / 30 · 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.

current range [lo, hi] pivot comparing to pivot swapped, or eliminated once a round ends found — the answer
Running example: arr = [9, 3, 7, 1, 8, 4, 2], find the 2nd largest

Press Play or Step to begin.

Step 0 / 30

▶ Play⏭ Step↺ Reset🔀 Shuffle

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

Round	lo	hi	pivot	Pivot’s final index	Action
1	0	6	2	1	1 < target(5) → discard indices 0–1, lo=2
2	2	6	3	2	2 < target(5) → discard index 2, lo=3
3	3	6	7	4	4 < target(5) → discard indices 3–4, lo=5
4	5	6	8	5	5 === target(5) → found! Answer = 8

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

Algorithm	Time	Space	Note
Bubble / Insertion Sort (Day 8/8c)	O(n) best, O(n²) worst	O(1)	Stable — early-exits on already-sorted input.
Selection Sort (Day 8b)	O(n²) always	O(1)	Not stable — always fully scans, no fast path.
Merge Sort (Day 10)	O(n log n) always	O(n)	Stable, but needs auxiliary arrays to merge into.
Quick Sort (Day 11)	O(n log n) avg, O(n²) worst	O(log n)	In-place, not stable; space is recursion depth.
Binary Search — exact match (Day 12)	O(log n)	O(1)	Needs a sorted array (or a monotonic predicate).
Binary Search — boundary / search on answer (Day 13)	O(log n) or O(n log m)	O(1)	Narrows to a boundary instead of stopping at a match.
Quickselect (today’s synthesis)	O(n) avg, O(n²) worst	O(1) extra	Recurses into only the side containing the answer.

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

1. First Bad Version

Easy — LeetCode: First Bad Version

You’re given n versions [1, 2, ..., n] and an API isBadVersion(version). Once a version is bad, every version after it is also bad. Find the first bad version using as few API calls as possible.

Show hint

This is Day 13’s search-on-answer idea in miniature — isBadVersion is exactly the monotonic false-then-true check. Binary search over the version numbers directly, using the narrowing/boundary template, not the exact-match one.

Show solution

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;
  };
};

2. Intersection of Two Arrays II

Easy — LeetCode: Intersection of Two Arrays II

Given two integer arrays, return their intersection — unlike Day 7’s version, each shared value must appear in the result as many times as it appears in both arrays.

Show hint

Sort both arrays, then walk them with two pointers — the exact same “advance whichever side is smaller” move as Day 10’s merge() step, just collecting matches instead of merging everything.

Show solution

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;
}

3. Search a 2D Matrix

Medium — LeetCode: Search a 2D Matrix

Each row of an m x n matrix is sorted ascending, and the first value of each row is greater than the last value of the previous row. Determine if a target exists, in O(log(m·n)) time.

Show hint

The whole matrix is really one sorted array of m·n elements in disguise. Binary search a single index from 0 to m·n − 1 using Day 12’s exact template unchanged, and only convert that one index into (row, col) — row = Math.floor(mid / n), col = mid % n — right before reading the value.

Show solution

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;
}

4. H-Index

Medium — LeetCode: H-Index

Given a researcher’s citation counts, return their h-index: the largest h such that at least h papers have each been cited at least h times.

Show hint

Sort the citations in descending order first (any Week 2 sort works). Then walk the sorted list looking for the crossover point where the citation count drops below its 1-indexed position — that position is the h-index.

Show solution

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;
}

5. Kth Smallest Element in a Sorted Matrix

Medium — LeetCode: Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where every row and every column is sorted ascending, find the kth smallest element in the whole matrix.

Show hint

This is search on answer again (Day 13), but the answer space is values, not indices — binary search the value range from matrix[0][0] to matrix[n-1][n-1]. Your feasibility check counts how many entries are ≤ a candidate value in O(n) (walk each row from the last column backward, like a staircase), then narrow toward the smallest value where that count ≥ k.

Show solution

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

1. Which Week 2 sort is both stable AND guarantees O(n log n) even in the worst case?

Merge sort

Quick sort’s worst case is O(n²) and its in-place partition isn’t stable; merge sort is the only Week 2 sort with both a worst-case O(n log n) guarantee and stability.

2. Quickselect gets its average O(n) time (versus quick sort’s O(n log n)) by:

Recursing into only the one side of the partition that contains the answer

Recursing into only the side of the partition that contains the target index — throwing the other side away unsorted — is what drops quickselect’s average time to O(n), below quick sort’s O(n log n).

3. What’s the key structural difference between Day 12’s search() and Day 13’s findBound()?

findBound() doesn’t return immediately on a match — it saves the result and keeps narrowing

Both search() and findBound() use the same lo <= hi loop shape and check for an exact match at mid — the real difference is what happens on a match: search() returns immediately, findBound() saves it as a candidate and keeps narrowing toward the boundary instead of stopping.

4. For a small, nearly-sorted array where simplicity matters most, which Day 8 sort is the best fit?

Insertion sort

Insertion sort’s inner while loop does almost no shifting when the array is already close to sorted, giving it a genuine O(n) best case. Selection sort always fully scans the remaining range regardless of input order.

5. What property must a “search on answer” feasibility check have — whether it’s Koko Eating Bananas or today’s Kth Smallest in a Sorted Matrix?

It must be monotonic — false-then-true (or vice versa) with a single flip point

A search-on-answer feasibility check must be monotonic — false for every candidate below some threshold, true for every candidate at or above it (or vice versa) — exactly one flip point across the answer space.