Coding

Count subarrays with given sum

Asked at

Amazon

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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

Input: nums = [1, 1, 1], k = 2 Output: 2 Explanation: In the given array [1, 1, 1], there are two subarrays that sum up to 2: [1, 1] and [1, 1]. Hence, the output is 2.

Input: nums = [1, 2, 3], k = 3 Output: 2 Explanation: In the given array [1, 2, 3], there are two subarrays that sum up to 3: [1, 2] and [3]. Hence, the output is 2.

Input: nums = [3, 1, 2, 4], k = 6

1 <= nums.length <= 105
-1000 <= nums[i] <= 1000
-107 <= k <= 107

cpp

class Solution{
public:
    int subarraySum(vector<int> &nums, int k){
        
    }
};

java

class Solution {
    public int subarraySum(int[] nums, int k) {
        
    }
}

python

class Solution:
    def subarraySum(self, nums, k):

javascript

class Solution {
    subarraySum(nums, k) {
      
    }
}

csharp

public class Solution
{
    public int SubarraySum(int[] nums, int k)
    {
        
    }
}

func subarraySum(nums []int, k int) int {
	
}

Stuck? Show a way to structure it+

01Maintain the running prefix sum and frequencies of all earlier prefix sums.
02For current prefix p, add the number of earlier prefixes equal to p - k.
03Record the current prefix after counting, starting with frequency zero-sum equal to one.
04Use frequencies rather than a set to count all earlier matching prefixes.

Reference answer

Let the running prefix sum at index i be p. A subarray ending at i has sum k when an earlier prefix equals p - k. Maintain a frequency map of prefix sums seen before the current position. Initialize frequency[0] = 1 so a subarray beginning at index zero is counted. For each number, update p, add frequency[p - k] to the answer, then increment frequency[p]. Frequencies rather than a set are necessary because the same prefix sum may occur at several indices, each defining a different subarray. Time is O(n) on average and space is O(n). A variable sliding window is not generally correct because negative numbers destroy the monotonic relationship between expanding a window and increasing its sum.

Then expect these follow-ups

Why does frequency[p-k] count subarrays ending here?
Tests: prefix proof
How would you find the longest subarray with sum k?
Tests: prefix variant

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question