Overview

Session 8 opened with two spaced-repetition reviews — Coin Change and Unique Paths II — before finishing the Edit Distance implementation deferred from session 7. The session closed with an introduction to the Sliding Window pattern, culminating in the monotonic deque technique for O(n) sliding window maximum.

Concept

Edit Distance

editDistance(s, t) is the minimum number of insert / delete / replace operations to transform s into t. The DP table is (s.length+1) × (t.length+1), where dp[i][j] = edit distance between s[0..i) and t[0..j).

Base cases:

• dp[0][j] = j — j insertions to build t[0..j) from empty
• dp[i][0] = i — i deletions to reduce s[0..i) to empty

Recurrence:

if s[i-1] == t[j-1]:
  dp[i][j] = dp[i-1][j-1]          # free diagonal (match)
else:
  dp[i][j] = min(
    dp[i-1][j-1],  # replace
    dp[i-1][j],    # delete from s
    dp[i][j-1],    # insert into s
  ) + 1

Each of the three neighbors maps to one operation. Time: O(m·n), Space: O(m·n).

Sliding Window

Two flavors:

• Fixed size — window of size k slides forward; drop left element when size exceeds k.
• Variable size — expand r until constraint breaks, shrink l until it holds again.

Both are O(n): each element enters and exits the window at most once.

Monotonic deque enables O(n) sliding window maximum. The deque stores indices (not values) in decreasing order of nums[index]. Two invariants:

1. Pop from back any index whose value is ≤ nums[r] before pushing r — those elements are beaten by nums[r] and expire sooner.
2. Pop from front any index that has left the window (index < r - k + 1).

Front of deque is always the current window maximum.

Implementation

Edit Distance

editDistance(s: string, t: string): int {
  dp = new Array[][](s.length + 1, t.length + 1)
  dp[0][j] = j for j in [0..t.length]
  dp[i][0] = i for i in [0..s.length]

  for (i = 1; i <= s.length; ++i) {
    for (j = 1; j <= t.length; ++j) {
      fromDiagonal = s[i-1] == t[j-1] ? dp[i-1][j-1] : dp[i-1][j-1] + 1
      fromAbove = dp[i-1][j] + 1
      fromLeft = dp[i][j-1] + 1
      dp[i][j] = min(fromDiagonal, fromAbove, fromLeft)
    }
  }

  dp.last.last
}

Key bugs caught: base-case loops used s.length/t.length with swapped axes, and used i+1 instead of i as the value — overwriting dp[0][0] = 0 with 1. The rule: the index is the value when seeding a running-count base case.

Sliding Window Maximum

slidingWindowMax(nums: int[], k: int): int[] {
  if (k < 1 || nums.empty || k > nums.length) return []

  deque: int[] = []   // stores indices; value = nums[index]
  result: int[] = []

  for (r = 0; r < nums.length; ++r) {
    // drop back elements that can never be max
    while (deque.at(-1) != null && nums[deque.at(-1)] <= nums[r])
      deque.pop()

    deque.push(r)

    // drop front elements outside the window
    while (deque[0] < r - k + 1)
      deque.shift()

    if (r >= k - 1) result.push(nums[deque[0]])
  }

  return result
}

Key bugs caught: operator precedence — ?? has lower precedence than <, so deque.at(-1)?.value ?? Infinity < nums[r] parses as deque.at(-1)?.value ?? (Infinity < nums[r]). Always parenthesize: (deque.at(-1)?.value ?? Infinity) < nums[r]. Also: store indices only; value is always recoverable as nums[index].

Problems

Coin Change (spaced rep)

Return minimum coins to make amount, or -1.

Approach: 1D DP. dp[i] = min coins to make i. For each amount, map each coin to dp[i - c] (null if out of range or unreachable), filter nulls, take min + 1.

Solution: Clean from memory. Using null instead of Infinity elegantly sidesteps the Infinity + 1 sentinel issue. The null filter handles both range and reachability in one pass.

Unique Paths II (spaced rep)

Grid with obstacles (1 = blocked). Count paths from top-left to bottom-right moving only right or down.

Approach: In-place 2D DP. Obstacle cells → null. Otherwise sum reachable neighbors.

Bug repeated from session 7: Missing seed for grid[0][0] = 1. When both neighbors are null, the origin is incorrectly marked unreachable. Fix: if (i === 0 && j === 0) { grid[0][0] = 1; next }.

Edit Distance

Transform string s into string t with minimum insert/delete/replace operations.

Approach: 2D DP as described above.

Bugs: Base-case row/col used swapped bounds (s.length vs t.length) and i+1 values starting from i=0, overwriting the dp[0][0] = 0 seed.

Sliding Window Maximum

Given nums and window size k, return max of each window.

Approach: Monotonic decreasing deque of indices. O(n) time, O(k) space.

Key insight: Any element smaller than the current nums[r] and to its left can never be a future maximum — it’s dominated and expires sooner. Discard it immediately from the back.