Subarray Sum Equals K - Video Solutions

Problem Overview: Given an integer array nums and an integer k, count how many continuous subarrays sum exactly to k. The array can contain negative numbers, so sliding window techniques do not work reliably. You need a method that checks every possible subarray sum efficiently.

Approach 1: Brute Force with Running Sum (O(n²) time, O(1) space)

Iterate over every possible starting index of a subarray. From each start position, extend the subarray to the right while maintaining a running sum. Each time the running sum equals k, increment the count. This avoids recomputing sums from scratch but still checks all O(n²) subarrays. The approach relies only on simple iteration over the array, so space usage remains constant.

This method is straightforward and useful when explaining the problem during an interview. It clearly shows how subarrays are formed and evaluated. However, it becomes slow for large inputs because every start index expands across the remaining array.

Approach 2: Prefix Sum with HashMap (O(n) time, O(n) space)

The optimal approach uses a running prefix sum combined with a frequency map. As you iterate through the array, maintain the cumulative sum up to the current index. If the current prefix sum is curr, then any earlier prefix sum equal to curr - k forms a subarray ending at the current index with sum k. Store counts of prefix sums in a hash table so each lookup runs in O(1).

Initialize the map with {0:1} to handle cases where the subarray starting at index 0 equals k. For each element, update the running sum, check how many times curr - k has appeared, and add that to the result. Then update the frequency of the current prefix sum in the map. This transforms the nested loop into a single linear pass through the array.

Recommended for interviews: Interviewers expect the prefix sum + hash map solution because it reduces the problem from O(n²) to O(n). Starting with the brute force explanation shows you understand the problem space. Moving to prefix sums demonstrates algorithmic optimization and familiarity with hash-based counting patterns that appear in many array problems.