Problem Statement in English

You’re given an integer array nums and an integer k. A subarray is a contiguous part of an array.

Return the number of non-empty subarrays that have a sum divisible by k.

Approach

The idea is to eliminate the need to check every possible subarray by using prefix sums and a hashmap to store the frequency of remainders when the prefix sums are divided by k.

If you think about it, every subarray is basically a subarray that starts from index 0 to index j minus a subarray that starts from index 0 to index i-1 (where i is the starting index of the subarray and j is the ending index, and i-1 < j).

So we exploit that. For the current subarray, the number of subarrays that we can remove from it are the number of subarays that we’ve seen so far, whose sum when divided by k gives the same remainder as the current subarray.

And that’s pretty much it. We also need to remember to update the hashmap with the current remainder after processing it.

Solution in Python


class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        hm = defaultdict(int)
        hm[0] = 1
        curr = res = 0

        for num in nums:
            curr += num
            res += hm[curr % k]
            hm[curr % k] += 1

        return res

Complexity

  • Time: $O(n)$

  • Space: $O(k)$
    Since we are storing at most k different remainders in the hashmap.

Mistakes I Made

I had to watch NeetCode’s video solution.

And we are done.