Subarray problems are everywhere in coding interviews.

And most beginners solve them using:

Nested loops

O(n²) brute force

But interviewers expect something smarter.

That’s where:

Prefix Sum

HashMap

become powerful together.

Core Idea

Instead of recalculating sums repeatedly:

Store running sums (prefix sums)

Use hashing for quick lookup

This reduces many problems to O(n).

1. Subarray Sum Equals K

Problem

Find number of subarrays whose sum equals k.

public static int subarraySum(int[] nums, int k) {

Map map = new HashMap<>();

map.put(0, 1);

int sum = 0, count = 0;

for (int num : nums) { sum += num;

int diff = sum - k;

count += map.getOrDefault(diff, 0);

map.put(sum, map.getOrDefault(sum, 0) + 1); }

return count;

Enter fullscreen mode

Exit fullscreen mode

}

Key Insight

If:

prefixSum−previousPrefix=k

Then:

A valid subarray exists.

2.…