Subarray Sum Equals K

Practice Link

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Brute Force#

Try every possible subarray by fixing the start index i and extending the end index j rightward. Accumulate the running sum and count whenever it equals k. This is correct — it simply checks all O(n²) subarrays — but is slow because we recompute overlapping sums repeatedly from scratch.

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int resultCnt =0;
        
        for(int i=0;i<nums.size();i++)
        {
            int sum = 0;
            for(int j=i;j<nums.size();j++)
            {
                sum += nums[j];
                if(sum==k)
                    resultCnt++;
            }
        }
        return resultCnt;
    }
};

Time Complexity: O(n^2)

Space Complexity: O(1)

Prefix Sum#

The key insight is that a subarray nums[i..j] has sum k if and only if prefixSum[j] - prefixSum[i-1] == k, meaning we need prefixSum[i-1] == prefixSum[j] - k. By storing previously seen prefix sums in a hash map, we can check in O(1) how many earlier subarrays satisfy this condition for the current index. A single linear pass is enough — at each step, look up prefixSum - k in the map (counting valid subarrays ending here), then insert the current prefix sum. This brings time from O(n²) to O(n) at the cost of O(n) space for the map.

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> prefixSum(n);

        prefixSum[0] = nums[0];
        for(int i=1;i<n;i++)
            prefixSum[i] = prefixSum[i-1] + nums[i];
        
        int count = 0;
        unordered_map<int,int> mp;
        for(int i=0;i<n;i++)
        {
            if(prefixSum[i]==k)
                count++;

            int val = prefixSum[i]-k;
            if(mp.find(val) != mp.end())
                count += mp[val];
            
            mp[prefixSum[i]]++;
        }
        return count;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Optimal — Single Pass (No Prefix Array)#

The previous approach pre-builds a prefixSum vector before doing the map pass. We can collapse it into a single loop by maintaining a running sum and seeding the map with prefixSumCount[0] = 1 upfront.

Why the seed matters: when the running prefix sum itself equals k, the "complement" we look up is prefixSum - k = 0. Without the seed, that lookup would return 0 even though the subarray nums[0..i] is valid. Pre-inserting 0 → 1 lets the general cnt += prefixSumCount[prefixSum - k] path handle it automatically — no special-case if (prefixSum == k) check required.

This eliminates the extra O(n) prefix-sum vector, leaving only the hash map, and keeps the code noticeably shorter.

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();

        unordered_map<int,int> prefixSumCount;
        prefixSumCount[0] = 1;   // seed: empty prefix has sum 0

        int prefixSum = 0, cnt = 0;

        for(int i = 0; i < n; i++)
        {
            prefixSum += nums[i];

            // how many earlier prefixes make nums[?..i] sum to k?
            if(prefixSumCount.find(prefixSum - k) != prefixSumCount.end())
                cnt += prefixSumCount[prefixSum - k];

            prefixSumCount[prefixSum]++;
        }
        return cnt;
    }
};

Time Complexity: O(n)

Space Complexity: O(n) — map only; no separate prefix-sum array

Follow-up: Longest Subarray with Sum K#

Instead of counting subarrays, find the length of the longest one whose sum equals k.

This changes the map's purpose: instead of storing how many times a prefix sum was seen, we store the earliest index at which each prefix sum first appeared. The longer the gap between that stored index and the current index, the longer the subarray — so we only record a prefix sum when it's seen for the first time.

Key difference from the count problem:

class Solution {
  public:
    int longestSubarray(vector<int>& arr, int k) {
        int n = arr.size();

        int prefixSum = 0;
        int len = 0;

        unordered_map<int,int> seenIdxMap;
        seenIdxMap[0] = -1;   // seed: empty prefix "ends" before index 0

        for(int i = 0; i < n; i++){
            prefixSum += arr[i];

            if(seenIdxMap.find(prefixSum - k) != seenIdxMap.end())
                len = max(len, i - seenIdxMap[prefixSum - k]);

            // only record first occurrence — earlier index = longer subarray
            if(seenIdxMap.find(prefixSum) == seenIdxMap.end())
                seenIdxMap[prefixSum] = i;
        }
        return len;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Why we skip duplicate prefix sums: if the same prefix sum occurs at indices j and j' where j < j', using j always gives a longer subarray nums[j+1..i] than using j'. So we insert only on first sight and never update.