Day 7: Week 1 Review

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

nums = [1, 2, 3], k = 3 — Subarray Sum Equals K blends sliding window (running sum) with a hash map (count occurrences of prefix sums).

Press Play or Step to begin.

sum = 0, count = 0, map = { 0→1 }

Step 0 / 5

▶ Play⏭ Step↺ Reset🔀 Shuffle

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)

i	num	sum	sum − k	In map?	count
—	—	0	—	map = {0: 1}	0
0	1	1	−2	No	0
1	2	3	0	Yes (count 1)	1
2	3	6	3	Yes (count 1)	2

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

Pattern	Time	Space	Replaces
Array index / push / pop	O(1)	O(1)	—
Array unshift / shift / splice(middle)	O(n)	O(1)	—
Two pointer (either shape)	O(n)	O(1)	O(n²) nested loop
Sliding window, fixed size	O(n)	O(1)	O(n·k) resumming
Sliding window, variable size	O(n)	O(1) or O(window)	O(n²) or worse substring checks
Hash map / set lookup	O(1) average	O(n)	O(n) linear scan per lookup

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

1. Move Zeroes

Difficulty: Easy — LeetCode: Move Zeroes

Move all zeroes in an array to the end, in place, while keeping the relative order of the non-zero elements.

Hint

This is Day 4’s read/write pattern — but instead of overwriting, swap the read and write slots.

Solution

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

2. Missing Number

Difficulty: Easy — LeetCode: Missing Number

Given an array containing n distinct numbers from 0 to n, find the one number missing from the range.

Hint

You don’t need a hash set here — the sum of 0..n has a closed-form formula. What’s left over after subtracting the actual sum?

Solution

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

3. Intersection of Two Arrays

Difficulty: Easy — LeetCode: Intersection of Two Arrays

Given two arrays, return their intersection — each element in the result must be unique.

Hint

Put one array’s values in a Set for O(1) lookup, then scan the other array checking membership.

Solution

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

4. Longest Repeating Character Replacement

Difficulty: Medium — LeetCode: Longest Repeating Character Replacement

Given a string and an integer k, you may replace up to k characters with any other character. Find the length of the longest substring of a single repeated character you can achieve.

Hint

Variable window + frequency map, combined. A window is valid if (window length − count of its most frequent character) ≤ k — that’s exactly how many characters you’d need to replace.

Solution

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

5. Subarray Sum Equals K

Difficulty: Medium — LeetCode: Subarray Sum Equals K

Given an array of integers and an integer k, return the total number of contiguous subarrays whose sum equals k.

Hint

This is today’s interactive visualization, exactly. Track a running sum and a map of “how many times has each running sum occurred?”

Solution

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

Quiz: “Find the longest substring with at most 2 distinct characters” is a signal for which pattern?

Sliding window

A contiguous-range question, with no sortedness requirement, is the classic sliding-window signal.

Quiz: “Does this array contain any duplicate values?” is best solved with:

A hash set

Order doesn’t matter here — you just need O(1) membership checks, which is exactly what a hash set gives you.

Quiz: Converging two pointers for a pair-sum problem requires the input to be:

Sorted

Converging two pointers relies on knowing which direction to move — that guarantee only holds on sorted data.

Quiz: Subarray Sum Equals K (today’s visualization) combines which two ideas?

A running sum + a hash map

Subarray Sum Equals K tracks a running sum (a sliding-window-style idea) inside a hash map of sums seen so far — a genuine combination of two patterns.

Quiz: When you don’t instantly recognize a problem’s pattern, what’s the safest first move?

State the brute-force solution out loud, then ask what you’re recomputing

Stating the brute force out loud first is always safe, and ‘what am I recomputing?’ is what leads you to the right pattern.