Subarray Sum Equals K

Given an integer array nums and an integer k, return the total number of non-empty contiguous subarrays whose sum equals k.

Return 0 when no valid subarray exists or when nums is empty.

Brute Force Approach

The most direct idea is to generate every possible contiguous subarray and calculate the complete sum of each selected range.

Every pair of starting and ending indices defines one valid subarray. Checking all such ranges guarantees the correct count, but overlapping subarrays repeatedly add many of the same elements.

Algorithm

• Store the array size in n. If n == 0, return 0 because no non-empty subarray can be formed.

• Initialize count with 0, where it stores the number of subarrays found whose sum is exactly k.

• Treat every index start as the beginning of a possible subarray and every index end from start to n - 1 as its ending position.

• For each selected range [start, end], initialize currentSum with 0 and add all elements from start through end to calculate that subarray's complete sum.

• If currentSum == k, increment count because the selected range forms one valid subarray.

• Return count after every possible contiguous subarray has been examined.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N³), where N represents the array size. Two loops select the starting and ending indices, while a third traversal calculates the sum of every selected range.

Space Complexity: O(1), because only loop indices, currentSum, and count require auxiliary storage.

Better Approach

The Brute Force Approach calculates every selected range sum from the beginning.

For a fixed starting index, the next subarray contains the previous range plus one additional ending element. Keeping a running sum removes the repeated range traversal and reduces the solution to two loops.

Algorithm

• Store the array size in n. If the array is empty, return 0.

• Initialize count with 0 to keep track of how many subarrays have a sum equal to k.

• Treat every index start as the beginning of a new group of subarrays and initialize currentSum with 0 for that starting position.

• Move end from start to n - 1 and add nums[end] to currentSum. This extends the previous range by one element instead of recalculating its complete sum.

• Increment count whenever currentSum == k. Continue extending the range even if the sum becomes greater than k, because a later negative value may reduce it again.

• Return count after all starting and ending positions have been processed.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N²), where N represents the array size. Every starting index extends through all possible ending positions, while each extension requires one addition.

Space Complexity: O(1), because only loop indices, currentSum, and count require auxiliary storage.

Optimal Approach

A prefix sum represents the total of all elements from the beginning of the array through the current index.

Suppose the current prefix sum is prefixSum. A subarray ending at the current index has sum k when an earlier prefix sum equals:

prefixSum - k

The same prefix sum may appear at multiple earlier positions. Every occurrence creates a different valid subarray, so the frequency of each prefix sum must be stored.

Algorithm

• Create a hash map prefixCount and store {0: 1}. This initial frequency represents the empty prefix before index 0, allowing subarrays that begin at index 0 to be counted.

• Initialize prefixSum with 0 to store the running sum and count with 0 to store the total number of valid subarrays.

• Traverse the array from left to right and add the current element to prefixSum.

• Calculate neededSum = prefixSum - k. If this prefix sum occurred earlier, removing it from the current prefix leaves a subarray whose sum is exactly k.

• Add the frequency of neededSum to count, since every earlier occurrence produces a different valid subarray ending at the current index. Then increase the frequency of prefixSum for future positions.

• Return count after the complete array has been processed. If the array is empty, the loop does not run and the result naturally remains 0.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N) on average, where N represents the array size. Every element requires one hash-map lookup and one hash-map update.

Space Complexity: O(N), because the hash map may store up to N + 1 distinct prefix sums.

FAQs

Q1. Why are prefix-sum frequencies stored instead of only checking whether a prefix exists?

The same prefix sum may occur at multiple earlier positions. Every occurrence creates a different valid subarray ending at the current index.

Q2. Why is prefixCount initialized with {0: 1}?

The initial zero represents the empty prefix before the array begins. This allows a subarray starting at index 0 to be counted when its sum directly equals k.

Q3. Why is the current prefix sum stored after checking neededSum?

Only earlier prefix sums should create subarrays ending at the current index. Storing the current prefix first could incorrectly use the same position as both boundaries.

Q4. Why cannot the Better Approach stop when currentSum becomes greater than k?

Negative values may appear later and reduce the running sum. A sum greater than k can still become equal to k after further extension.

Q5. Can a sliding-window approach solve this problem?

A standard sliding window works reliably when all values are non-negative. Negative values make window expansion and contraction unpredictable, so prefix sums with a hash map are preferred.

Q6. How does the solution change when the longest subarray with sum k is required?

Store the earliest index of each prefix sum instead of its frequency. The distance between the current index and the earliest matching prefix determines the longest valid length.