DAY 7 / 30 · WEEK 1 REVIEW

Week 1 Review

Goal of the day

• Connect Days 1–6 into one decision process: given a new problem, know which pattern to reach for first.
• Solve 5 mixed practice problems that draw on more than one pattern from this week.
• Walk away with a one-page cheat sheet of every template and complexity from Week 1.

Concept

Think back to the four analogies from this week: the librarians walking toward each other on a sorted shelf, the picture frame sliding along a strip of numbers, the coat-check ticket that jumps straight to your coat. Different pictures, but the same move every time: a brute-force nested loop (O(n²)) collapsed to one pass (O(n)) by remembering something as you go — a running number, two positions, or a full lookup table. The skill that actually matters in an interview isn't memorizing five templates — it's recognizing which thing you need to remember for the problem in front of you. That recognition is what today trains.

Diagram: which pattern do I reach for?

Interactive visualization: combining two patterns

Subarray Sum Equals K blends this week's two biggest ideas: a running sum (like sliding window) AND a hash map of sums seen so far (like Day 6) — this is what "mixed" problems look like in real interviews.

Week 1 cheat sheet — code templates

// ARRAY BASICS (Day 1): push/pop O(1) end, unshift/shift O(n) front
arr.push(x); arr.pop(); arr.unshift(x); arr.shift();

// STRINGS (Day 3): immutable — always build a new one
const newStr = 'x' + str.slice(1);

// TWO POINTER — converging (Day 4): array must be SORTED
let left = 0, right = arr.length - 1;
while (left < right) {
  const sum = arr[left] + arr[right];
  if (sum === target) { /* found */ break; }
  else if (sum < target) left++;
  else right--;
}

// TWO POINTER — read/write (Day 4): in-place compaction
let write = 0;
for (let read = 1; read < arr.length; read++) {
  if (arr[read] !== arr[write]) { write++; arr[write] = arr[read]; }
}

// SLIDING WINDOW — fixed size (Day 5)
let windowSum = 0;
for (let i = 0; i < k; i++) windowSum += arr[i];
for (let i = k; i < arr.length; i++) windowSum += arr[i] - arr[i - k];

// SLIDING WINDOW — variable size (Day 5)
let left = 0;
for (let right = 0; right < arr.length; right++) {
  // expand: fold arr[right] into your running state
  while (/* window invalid */ false) { left++; /* shrink */ }
}

// HASH MAP — "have I seen this?" (Day 6)
const seen = new Map();
for (let i = 0; i < arr.length; i++) {
  const complement = target - arr[i];
  if (seen.has(complement)) { /* found pair */ }
  seen.set(arr[i], i);
}

Dry run: subarraySum([1, 2, 3], k = 3)

Two subarrays sum to 3: [1,2] and [3] — found by checking, at each point, whether the running sum minus k has been seen before. The {0: 1} starting entry handles subarrays that start at index 0 exactly.

Complexity — everything from Week 1, at a glance

Interview corner

• What's the single most common Week 1 mistake? Reaching for two-pointer (converging) on data that isn't sorted, or forgetting a variable window needs a while — not an if — to shrink correctly. Both fail silently, not loudly.
• If a problem could use either sliding window or a hash map, which do you pick? If the question is about a contiguous range, sliding window is usually leaner (often O(1) extra space). If order/contiguity doesn't matter — just "have I seen this" — a hash map is the more direct tool.
  ↳ Common follow-up: "Can this problem use both?" — Subarray Sum Equals K, above, is exactly that: a running-sum idea from sliding window, combined with a hash map to make lookups O(1).
• How do you avoid freezing when you don't recognize a problem instantly? Work backwards from the brute force. State the O(n²) or O(n³) solution out loud first — it's always a safe starting point — then ask "what am I recomputing that I could remember instead?" That question leads you to whichever pattern fits.
  ⚠ Trap: don't skip straight to guessing a pattern name. Interviewers can tell the difference between pattern recognition and pattern matching by keyword — always justify why.

How to talk through it out loud: on a review problem, narrate the elimination, not just the answer — "this isn't sorted, so converging two-pointer is out; it's asking about a contiguous range, so I'll reach for sliding window first." Showing the patterns you ruled out, and why, proves you're recognizing the problem rather than pattern-matching a keyword you memorized.

5 mixed practice problems

function moveZeroes(nums) {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write++;
    }
  }
  return nums;
}

function missingNumber(nums) {
  const n = nums.length;
  const expected = (n * (n + 1)) / 2;
  const actual = nums.reduce((a, b) => a + b, 0);
  return expected - actual;
}

function intersection(nums1, nums2) {
  const set1 = new Set(nums1);
  const result = new Set();
  for (const n of nums2) if (set1.has(n)) result.add(n);
  return [...result];
}

function characterReplacement(s, k) {
  const counts = {};
  let left = 0, maxCount = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    counts[s[right]] = (counts[s[right]] || 0) + 1;
    maxCount = Math.max(maxCount, counts[s[right]]);
    while ((right - left + 1) - maxCount > k) {
      counts[s[left]]--;
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

function subarraySum(nums, k) {
  const seenSums = new Map([[0, 1]]);
  let sum = 0, count = 0;
  for (const n of nums) {
    sum += n;
    if (seenSums.has(sum - k)) count += seenSums.get(sum - k);
    seenSums.set(sum, (seenSums.get(sum) || 0) + 1);
  }
  return count;
}

Quiz