Hashing

Longest Subarray Sum K

Prefix hashing stores previous prefix states so subarray sums and window patterns can be answered immediately.

Kind

subarray

Time

O(N) expected

Space

O(N)

Steps

Input Keys

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Hash Table / State

bucket 0

0:1

bucket 1

empty

bucket 2

empty

bucket 3

empty

bucket 4

empty

bucket 5

empty

bucket 6

empty

bucket 7

empty

bucket 8

empty

Step Timeline

Code + Variables

1prefix += value

2need = prefix - k

3answer += count[need]

4count[prefix]++

prefix0

k10

Loading Lab...