Problem Statement in English

You’re given an array nums. Your task is to return the number of subarrays that sum to k.

Approach

Full disclosure: this is not my code, I got this online from NeetCode (brilliant channel by the way, definitely check him out).

You can definitely do this in $O(n^2)$ time, but that’s not the most optimal solution. We can improve this to $O(n)$, using Prefix Sums.

The most optimal solution is to use a hashmap to store the sum of the subarray and the number of times that sum has been seen.

We iterate over the subarray, and calculate the prefix sum for all elements up until the one we’re currently processing, and store the number of times we’ve seen it in a hashmap.

But how do we calculate potential subarrays that don’t start from the beginning of the array?

That’s the clever part. We don’t.

Instead we check the hashmap to see if we’ve encountered any subarray in the past with a sum whose difference with the current sum is equal to k.

If yes, we increment the answer by the number of times we’ve seen that sum.

Solution in Python


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # because we can always have a zero sum by including nothing
        m = {0: 1}

        # to store the final answer
        answer = 0

        # to store the current sum
        currentSum = 0

        for i in range(len(nums)):
            # add the value of the current index to the sum
            currentSum += nums[i]

            # calculate the difference between the current sum and k
            difference = currentSum - k

            # if we've seen this difference before, 
            # increment the answer by the number of times we've seen it
            # but if it doesn't exist, increment the answer by a default: 0
            answer += m.get(difference, 0)
            
            # add the current sum to the hashmap
            # 1 if it doesn't exist as of now
            # increment the value by 1 if it does
            m[currentSum] = 1 + m.get(currentSum, 0)

        # return the final answer
        return answer

Complexity

  • Time: $O(n)$
    Since we process $n$ elements at most.

  • Space: $O(n)$
    Since we store $n$ elements at most in the hashmap.

Mistakes I Made

I had to look this one up :(

And we are done.