Week 1 Instructor Guide

Teaching flow

Use problem definition, manual tracing, implementation, independent work, and explanation/debugging in each session. Adjust pacing to learner responses. Open student exercises before hints.

1: Arrays and hashed state

Opening prompt: A sensor retransmits events at short intervals. Can recent duplicates be detected without comparing every past pair? Store values and latest positions to retain only relevant history.

Flow: ask the learner to restate inputs/outputs and compare a baseline with the improved state. Reveal the lecture trace one row at a time after predictions. Execute the companion implementation and compare with a simple baseline.

LeetCode 1: Two Sum · Easy

Reasoning: At loop entry, the map contains only earlier positions. At the later position of the unique answer, its partner is present. This reuses information instead of checking all O(n²) pairs.

Debugging activity: Recording first can reuse one index on [3,3], target=6.

LeetCode 219: Contains Duplicate II · Easy

Reasoning: The latest occurrence minimizes distance to the current index. If it is too far, all older occurrences are too far. Updating preserves this property.

Debugging activity: Keeping only the first position misses the last pair in [4,7,4,4], k=1. No distinct-index pair qualifies when k=0.

Concept check: Is the first occurrence enough?

Instructor answer: No. Updating at index 2 exposes its distance 1 from index 3.

Independent activity: implement this session’s problems in the student workspace. For correct outputs, still ask for the invariant and elimination argument. For failures, find the earliest divergent state on a small counterexample.

2: Sorted order and two pointers

Opening prompt: Choose two sorted part lengths totaling a target. Explain why a too-small left candidate can be discarded, then extend to three values.

Flow: ask the learner to restate inputs/outputs and compare a baseline with the improved state. Reveal the lecture trace one row at a time after predictions. Execute the companion implementation and compare with a simple baseline.

LeetCode 167: Two Sum II - Input Array Is Sorted · Medium

Reasoning: If the sum is small, no partner at or below right works with left. If large, no partner at or above left works with right. Each elimination preserves any answer.

Debugging activity: Outside the sorted contract, [3,1,4], target=5 defeats this rule. left==right reuses one element.

LeetCode 15: 3Sum · Medium

Reasoning: Every ordered triplet is examined when its smallest value is fixed. Sorted elimination is valid; skipping duplicates removes repeated value combinations only.

Debugging activity: [0,0,0,0] yields one triplet. Equal values at distinct positions remain allowed.

Concept check: If original indices are required, is sorting values alone enough?

Instructor answer: No; retain original indices with values. Problem 167 asks for positions in its already sorted input.

Independent activity: implement this session’s problems in the student workspace. For correct outputs, still ask for the invariant and elimination argument. For failures, find the earliest divergent state on a small counterexample.

Week 1 answer checks

  1. List membership searches values; dictionary membership tests keys.
  2. Recording the first 3 at index 0 before lookup finds that same index. Lookup must precede recording so the next 3 finds earlier index 0.
  3. Without updating latest[4] at index 2, index 3 compares with index 0 and misses the distance-one pair.
  4. Copying a growing dictionary every iteration takes O(n²) total time. Discarding each snapshot gives O(n) peak additional space; retaining all gives O(n²) space.