Subarray Sum Equals K in Python | Prefix Sum + HashMap Explained (LeetCode 560)

Problem Overview

The problem Subarray Sum Equals K asks us to find the total number of continuous subarrays whose sum is equal to a given value k.

At first glance, this looks like a simple array problem, but it becomes tricky because:

• Subarrays must be continuous
• Elements can be negative
• A brute force approach would be too slow

---

Brute Force Thinking

The most straightforward approach is to try all possible subarrays and check their sums. However, this takes O(n²) time, which leads to a Time Limit Exceeded (TLE) for large inputs.

This forced me to look for an optimized approach that avoids recomputing sums again and again.

---

Key Insight: Prefix Sum

Instead of recalculating subarray sums, we can store cumulative sums. Let prefixSum[i] represent the sum of elements from index 0 to i.

If the sum of a subarray from index j+1 to i is equal to k, then:

prefixSum[i] − prefixSum[j] = k

Rearranging this gives:

prefixSum[j] = prefixSum[i] − k

This means that for every current prefix sum, we just need to know how many times currentSum − k has appeared before.

---

Using a HashMap

We use a hashmap to store how many times each prefix sum has occurred. This allows us to count valid subarrays in constant time.

• Key → prefix sum
• Value → frequency of that prefix sum

We initialize the map with {0: 1} to handle subarrays that start from index 0.

---

Algorithm Steps

1. Initialize current_sum = 0 and total = 0
2. Traverse the array
3. Add the current element to current_sum
4. If current_sum − k exists in the hashmap, add its frequency to total
5. Update the hashmap with the current prefix sum

---

Why This Approach Works

• Counts all valid subarrays, not just one
• Handles negative numbers correctly
• No nested loops
• Uses mathematical insight instead of brute force

---

Time & Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

---

Final Thoughts

This problem is a great example of how prefix sums combined with a hashmap can turn an inefficient solution into an optimal one.

Once the prefix sum equation clicks, the implementation becomes straightforward. This pattern appears frequently in array and subarray problems, so it’s definitely worth mastering.

If you’re revising DSA or preparing for interviews, this is a must-remember pattern.

here is the code link - GitHub Url.