Skip to main content

Prefix-Sum + HashMap

Learn Prefix-Sum + HashMap (Hashing, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Combining Prefix Sum with a HashMap Plain prefix sum answers "what's the sum of range [l, r]?" in O(1), but only when you already know l and r. Pairing it with a HashMap unlocks a different question: "does ANY subarray sum to exactly k?" - answered in a single O(n) pass, no nested loop needed. Track a running sum as you scan left to right. At each step, check whether (runningSum - k) was seen as a PAST prefix sum - if so, everything between that past point and now sums to exactly k.

More lessons in Hashing