The Smart O(n) Trick for Subarray Sum Questions

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;

}

Key Insight

If:

prefixSum−previousPrefix=k

Then:

• A valid subarray exists.

2. Zero Sum Subarray

Problem

Check if any subarray has sum = 0.

public static boolean hasZeroSumSubarray(int[] nums) {
Set set = new HashSet<>();

int sum = 0;

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

    if (sum == 0 || set.contains(sum))
        return true;

    set.add(sum);
}

return false;

}

Why It Works

If the same prefix sum appears twice:

• Middle subarray sum = 0

3. Longest Subarray with Sum K

Idea

Store the first occurrence of each prefix sum.

• Helps maximize length.

The Real Insight

Most subarray problems become easier when you think in terms of:

• Running sums
• Differences between prefix sums

Key Insights

• Prefix sum + HashMap = powerful pattern
• Avoids nested loops
• Many interview problems use this idea

For More: https://www.quipoin.com/tutorial/data-structure-with-java/subarray-sum-problems