Week 2 Instructor Guide

3: Window state and aggregate movements

Opening prompt: Find a repeat-free log interval and a shortest interval reaching a total. Recopying windows repeats work; update only incoming and outgoing data.

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 3: Longest Substring Without Repeating Characters · Medium

Reasoning: After insertion, the set represents the unique-character window. Its left boundary is the earliest feasible one for that right endpoint. Each pointer advances at most n times.

Debugging activity: A single removal on “abba” leaves b duplicated. Empty text gives 0; one space gives 1.

LeetCode 209: Minimum Size Subarray Sum · Medium

Reasoning: Positivity makes shrinking decrease the sum. Record each valid window before shrinking. A discarded left boundary can only produce longer later windows.

Debugging activity: Outside the positive-only contract, target=3, [1,-1,3] can make this rule miss length 1.

Concept check: Does a while inside a for always imply O(n2)?

Instructor answer: No. Each pointer advances at most n times, so total removals and insertions are O(n).

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.

4: Stacks and subexpressions

Opening prompt: Undo and postfix evaluation consume the most recent unresolved information first. Preserve per-depth state to restore the current minimum as well.

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 155: Min Stack · Medium

Reasoning: Induction on depth gives the correct prefix minimum; popping the last pair restores the previous prefix minimum.

Debugging activity: Calling min over the stack costs O(d). A single current minimum loses its predecessor after a pop.

LeetCode 150: Evaluate Reverse Polish Notation · Medium

Reasoning: The stack preserves completed subexpression values in order. Each operator combines the final two; a valid complete expression leaves one value.

Debugging activity: 5//-2 is -3, but truncation toward zero gives -2. Reversing operands changes subtraction.

Concept check: Does popping a repeated minimum remove every minimum?

Instructor answer: No; the previous depth retains its own minimum.

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.