w-35-prefix-sum-hash-combo.yml · YAML
YAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAML
# Prefix-sum + hash-map combo
# Single-panel chapter widget. Reuses w-10's array row + w-02's hash row.
id: w-35-prefix-sum-hash-combo
title: "Prefix-sum + hash-map combo"
type: single-panel
level: 1
modes: [preset, randomize, edit]
caps:
array_length: { min: 4, max: 32 }
values: { min: -99, max: 99 }
target_k: { min: -999, max: 999 }
commands:
- name: cumulate
payload: { index: 'integer', runningSum: 'integer' }
description: "Reuses w-10's command; appends running sum to middle row."
- name: lookupHash
payload: { key: 'integer', found: 'boolean', index: 'integer | null', count: 'integer | null' }
description: "Highlight hash row; flash existing entry if found."
- name: recordPair
payload: { l: 'integer', r: 'integer' }
description: "Mark the matched (l, r) range on the input array; bump pair counter."
static_fallback:
generator: jsdom
output: site/static/widgets/w-35-prefix-sum-hash-combo-fallback.svg
keyframes_used: [0, "first_match", "n_steps/2", "n_steps-1"]
panels:
default:
chapter: "3.5"
label: "Prefix sum + hash combo"
canonical_input: |
nums = [1, 1, 1]
k = 2
presets:
- id: subarray_sum_equals_k
label: "Subarray sum equals k (LC 560)"
input: { nums: [1, 1, 1], k: 2 }
- id: continuous_subarray_sum
label: "Continuous subarray sum (LC 523, multiples of k)"
input: { nums: [23, 2, 4, 6, 7], k: 6, hash_key: "runningSum mod k" }
- id: count_nice_subarrays
label: "Count number of nice subarrays (LC 1248)"
input: { nums: [1, 1, 2, 1, 1], k: 3, hash_key: "count(odd) mod 2" }
n_steps: 19
keyframes:
- step_id: 0
action: init
highlights: ["map-cell-0"]
state_snapshot:
i: null
prefix: 0
lookup_key: null
answer: 0
counts: {"0": 1}
narration: |
Seed counts with {0: 1}. The empty-prefix entry is what lets a
subarray starting at index 0 register as a hit when its sum
equals k. Without this single entry, the algorithm undercounts.
- step_id: 1
action: advance_pointer
highlights: ["array-cell-0"]
state_snapshot:
i: 0
prefix: 0
lookup_key: null
answer: 0
counts: {"0": 1}
narration: "Advance to index 0; nums[0] = 1."
- step_id: 2
action: update_prefix
highlights: ["array-cell-0", "prefix-cell"]
state_snapshot:
i: 0
prefix: 1
lookup_key: null
answer: 0
counts: {"0": 1}
narration: "prefix = 0 + 1 = 1."
- step_id: 3
action: compute_lookup_key
highlights: ["prefix-cell", "lookup-cell"]
state_snapshot:
i: 0
prefix: 1
lookup_key: -1
answer: 0
counts: {"0": 1}
narration: "lookup key = prefix - k = 1 - 2 = -1."
- step_id: 4
action: check_map_miss
highlights: ["lookup-cell"]
state_snapshot:
i: 0
prefix: 1
lookup_key: -1
answer: 0
counts: {"0": 1}
found: false
narration: |
Look up -1 in counts: not present. No subarray ending at index 0
sums to k.
- step_id: 5
action: update_map
highlights: ["map-cell-1"]
state_snapshot:
i: 0
prefix: 1
lookup_key: -1
answer: 0
counts: {"0": 1, "1": 1}
narration: "Insert prefix value 1 with count 1 into counts."
- step_id: 6
action: advance_pointer
highlights: ["array-cell-1"]
state_snapshot:
i: 1
prefix: 1
lookup_key: null
answer: 0
counts: {"0": 1, "1": 1}
narration: "Advance to index 1; nums[1] = 1."
- step_id: 7
action: update_prefix
highlights: ["array-cell-1", "prefix-cell"]
state_snapshot:
i: 1
prefix: 2
lookup_key: null
answer: 0
counts: {"0": 1, "1": 1}
narration: "prefix = 1 + 1 = 2."
- step_id: 8
action: compute_lookup_key
highlights: ["prefix-cell", "lookup-cell"]
state_snapshot:
i: 1
prefix: 2
lookup_key: 0
answer: 0
counts: {"0": 1, "1": 1}
narration: "lookup key = prefix - k = 2 - 2 = 0."
- step_id: 9
action: check_map_hit
highlights: ["lookup-cell", "map-cell-0"]
state_snapshot:
i: 1
prefix: 2
lookup_key: 0
answer: 0
counts: {"0": 1, "1": 1}
found: true
value: 1
narration: |
Look up 0 in counts: HIT, count = 1. This is the seeded
{0: 1} entry doing its job. The earlier "prefix" with value 0
is the empty prefix before index 0, so the matching subarray is
nums[0..1] = [1, 1], summing to 2. Drop the seed and this
lookup would miss; the answer would stay at 0.
- step_id: 10
action: increment_count
highlights: ["answer-cell"]
state_snapshot:
i: 1
prefix: 2
lookup_key: 0
answer: 1
counts: {"0": 1, "1": 1}
narration: "answer += 1 -> 1."
- step_id: 11
action: update_map
highlights: ["map-cell-2"]
state_snapshot:
i: 1
prefix: 2
lookup_key: 0
answer: 1
counts: {"0": 1, "1": 1, "2": 1}
narration: "Insert prefix value 2 with count 1 into counts."
- step_id: 12
action: advance_pointer
highlights: ["array-cell-2"]
state_snapshot:
i: 2
prefix: 2
lookup_key: null
answer: 1
counts: {"0": 1, "1": 1, "2": 1}
narration: "Advance to index 2; nums[2] = 1."
- step_id: 13
action: update_prefix
highlights: ["array-cell-2", "prefix-cell"]
state_snapshot:
i: 2
prefix: 3
lookup_key: null
answer: 1
counts: {"0": 1, "1": 1, "2": 1}
narration: "prefix = 2 + 1 = 3."
- step_id: 14
action: compute_lookup_key
highlights: ["prefix-cell", "lookup-cell"]
state_snapshot:
i: 2
prefix: 3
lookup_key: 1
answer: 1
counts: {"0": 1, "1": 1, "2": 1}
narration: "lookup key = prefix - k = 3 - 2 = 1."
- step_id: 15
action: check_map_hit
highlights: ["lookup-cell", "map-cell-1"]
state_snapshot:
i: 2
prefix: 3
lookup_key: 1
answer: 1
counts: {"0": 1, "1": 1, "2": 1}
found: true
value: 1
narration: |
Look up 1 in counts: HIT, count = 1. The earlier prefix of value 1
was recorded after index 0, so the matching subarray is
nums[1..2] = [1, 1], summing to 2.
- step_id: 16
action: increment_count
highlights: ["answer-cell"]
state_snapshot:
i: 2
prefix: 3
lookup_key: 1
answer: 2
counts: {"0": 1, "1": 1, "2": 1}
narration: "answer += 1 -> 2."
- step_id: 17
action: update_map
highlights: ["map-cell-3"]
state_snapshot:
i: 2
prefix: 3
lookup_key: 1
answer: 2
counts: {"0": 1, "1": 1, "2": 1, "3": 1}
narration: "Insert prefix value 3 with count 1 into counts."
- step_id: 18
action: answer
highlights: ["answer-cell"]
state_snapshot:
i: null
prefix: 3
lookup_key: null
answer: 2
counts: {"0": 1, "1": 1, "2": 1, "3": 1}
narration: |
Loop done. Final answer = 2 subarrays sum to k = 2. The two hits
were nums[0..1] (found via the seeded {0: 1} entry) and
nums[1..2] (found via the prefix-value-1 entry).
notes: |
Three stacked rows: input (top), prefix-sum (middle, from w-10), hash map
of {prefix sum: leftmost index} (bottom, from w-02). Net new code:
~180 LOC of join layer + the running-pair counter overlay.
The widget's lesson: *the hash insertion happens AFTER the lookup, so
we never count a zero-length subarray*, is the visual.
Edit-mode validator: |k| ≤ Σ|nums[i]|.From The Engineering Handbook (source), CC BY-SA 4.0.