w-12-monotonic-deque.yml · YAML

# Monotonic deque (sliding window extremum)
# Single-panel widget for chapter 4.1.

id: w-12-monotonic-deque
title: "Monotonic deque (sliding window maximum)"
type: single-panel
level: 1
modes: [preset, randomize, edit]

caps:
  array_length: { min: 4, max: 24 }
  values: { min: -99, max: 99 }
  window_k: { min: 1, max: "array_length" }

commands:
  - name: dropFront
    payload: { dropped: 'integer' }
    description: "Front index has fallen out of [i-k+1..i]; pop it."
  - name: popTail
    payload: { popped_index: 'integer', popped_value: 'integer' }
    description: "Tail value <= incoming; the tail can never be window-max while the incoming is alive. Pop it."
  - name: push
    payload: { index: 'integer', value: 'integer' }
    description: "Append the new index to the back; deque is again strictly decreasing."
  - name: emit
    payload: { window_max: 'integer' }
    description: "Window has its first k elements; output the front-of-deque value."

static_fallback:
  generator: jsdom
  output: site/static/widgets/w-12-monotonic-deque-fallback.svg
  keyframes_used: [0, "n_steps/4", "n_steps/2", "n_steps-1"]
  # Override: every drop-front transition is forced as a keyframe so the
  # fallback shows the moment a witness leaves the window.

panels:
  default:
    chapter: "4.1"
    label: "Sliding window maximum (LC 239)"
    canonical_input: |
      nums = [1, 3, -1, -3, 5, 3, 6, 7]
      k = 3
    presets:
      - id: lc239_canonical
        label: "LC 239 example 1"
        input: { nums: [1, 3, -1, -3, 5, 3, 6, 7], k: 3 }
      - id: monotone_decreasing
        label: "Strictly decreasing input (deque length = k)"
        input: { nums: [7, 6, 5, 4, 3, 2, 1], k: 3 }
      - id: all_equal
        label: "All-equal input (every push pops one tail)"
        input: { nums: [5, 5, 5, 5, 5], k: 3 }
    n_steps: 23
    keyframes:
      - step: 0
        kind: init
        state: { i: -1, deque_indices: [], deque_values: [], output: [] }
        narration: "Init. nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. Deque holds indices in strictly decreasing order of nums[idx]; front is the running window-max."
      - step: 1
        kind: push
        payload: { index: 0, value: 1 }
        state: { i: 0, deque_indices: [0], deque_values: [1], output: [] }
        narration: "i=0: push index 0 (value 1). Deque holds [1]."
      - step: 2
        kind: popTail
        payload: { popped_index: 0, popped_value: 1 }
        state: { i: 1, deque_indices: [], deque_values: [], output: [] }
        narration: "i=1, x=3: tail value 1 <= 3. The 1 can never be the window-max while 3 is alive in the window. Pop it."
      - step: 3
        kind: push
        payload: { index: 1, value: 3 }
        state: { i: 1, deque_indices: [1], deque_values: [3], output: [] }
        narration: "i=1: push index 1 (value 3). Deque holds [3]."
      - step: 4
        kind: push
        payload: { index: 2, value: -1 }
        state: { i: 2, deque_indices: [1, 2], deque_values: [3, -1], output: [] }
        narration: "i=2: push index 2 (value -1). -1 < 3 so monotonicity holds. Deque holds [3, -1]."
      - step: 5
        kind: emit
        payload: { window_max: 3 }
        state: { i: 2, deque_indices: [1, 2], deque_values: [3, -1], output: [3] }
        narration: "Window [0..2] is full. Front of deque is index 1, nums[1] = 3. Append to output."
      - step: 6
        kind: push
        payload: { index: 3, value: -3 }
        state: { i: 3, deque_indices: [1, 2, 3], deque_values: [3, -1, -3], output: [3] }
        narration: "i=3: push index 3 (value -3). Deque holds [3, -1, -3]."
      - step: 7
        kind: emit
        payload: { window_max: 3 }
        state: { i: 3, deque_indices: [1, 2, 3], deque_values: [3, -1, -3], output: [3, 3] }
        narration: "Window [1..3]. Front is still index 1, value 3. Append."
      - step: 8
        kind: dropFront
        payload: { dropped: 1 }
        state: { i: 4, deque_indices: [2, 3], deque_values: [-1, -3], output: [3, 3] }
        narration: "i=4: front index 1 has age i-k = 1, equals the cutoff. Drop it. The witness 3 has left the window."
      - step: 9
        kind: popTail
        payload: { popped_index: 3, popped_value: -3 }
        state: { i: 4, deque_indices: [2], deque_values: [-1], output: [3, 3] }
        narration: "i=4, x=5: tail value -3 <= 5. Dominated. Pop."
      - step: 10
        kind: popTail
        payload: { popped_index: 2, popped_value: -1 }
        state: { i: 4, deque_indices: [], deque_values: [], output: [3, 3] }
        narration: "i=4, x=5: tail value -1 <= 5. Dominated. Pop. Deque empty."
      - step: 11
        kind: push
        payload: { index: 4, value: 5 }
        state: { i: 4, deque_indices: [4], deque_values: [5], output: [3, 3] }
        narration: "i=4: push index 4 (value 5). Deque holds [5]."
      - step: 12
        kind: emit
        payload: { window_max: 5 }
        state: { i: 4, deque_indices: [4], deque_values: [5], output: [3, 3, 5] }
        narration: "Window [2..4]. Front is index 4, value 5. Append."
      - step: 13
        kind: push
        payload: { index: 5, value: 3 }
        state: { i: 5, deque_indices: [4, 5], deque_values: [5, 3], output: [3, 3, 5] }
        narration: "i=5: push index 5 (value 3). 3 < 5, monotonicity holds. Deque holds [5, 3]."
      - step: 14
        kind: emit
        payload: { window_max: 5 }
        state: { i: 5, deque_indices: [4, 5], deque_values: [5, 3], output: [3, 3, 5, 5] }
        narration: "Window [3..5]. Front is index 4, value 5. Append."
      - step: 15
        kind: popTail
        payload: { popped_index: 5, popped_value: 3 }
        state: { i: 6, deque_indices: [4], deque_values: [5], output: [3, 3, 5, 5] }
        narration: "i=6, x=6: tail value 3 <= 6. Dominated. Pop."
      - step: 16
        kind: popTail
        payload: { popped_index: 4, popped_value: 5 }
        state: { i: 6, deque_indices: [], deque_values: [], output: [3, 3, 5, 5] }
        narration: "i=6, x=6: tail value 5 <= 6. Dominated. Pop. Deque empty. The previous max is gone, but it was about to age out anyway."
      - step: 17
        kind: push
        payload: { index: 6, value: 6 }
        state: { i: 6, deque_indices: [6], deque_values: [6], output: [3, 3, 5, 5] }
        narration: "i=6: push index 6 (value 6). Deque holds [6]."
      - step: 18
        kind: emit
        payload: { window_max: 6 }
        state: { i: 6, deque_indices: [6], deque_values: [6], output: [3, 3, 5, 5, 6] }
        narration: "Window [4..6]. Front is index 6, value 6. Append."
      - step: 19
        kind: popTail
        payload: { popped_index: 6, popped_value: 6 }
        state: { i: 7, deque_indices: [], deque_values: [], output: [3, 3, 5, 5, 6] }
        narration: "i=7, x=7: tail value 6 <= 7. Dominated. Pop."
      - step: 20
        kind: push
        payload: { index: 7, value: 7 }
        state: { i: 7, deque_indices: [7], deque_values: [7], output: [3, 3, 5, 5, 6] }
        narration: "i=7: push index 7 (value 7). Deque holds [7]."
      - step: 21
        kind: emit
        payload: { window_max: 7 }
        state: { i: 7, deque_indices: [7], deque_values: [7], output: [3, 3, 5, 5, 6, 7] }
        narration: "Window [5..7]. Front is index 7, value 7. Append."
      - step: 22
        kind: done
        state: { i: 7, deque_indices: [7], deque_values: [7], output: [3, 3, 5, 5, 6, 7] }
        narration: "Done. Output = [3, 3, 5, 5, 6, 7]. Each index was pushed once and popped at most once across the run; total work is O(n)."

selector_default: default

notes: |
  4.1 monotonic deque (signature problem LC 239). The keyframes lift the
   step buffer verbatim. Three presets: the LC 239 canonical
  example, a strictly-decreasing input that fills the deque to length k
  (no tail pops, drop-front does all eviction), and an all-equal input
  that exercises the strict-inequality pop rule on every push.