974. Subarray Sums Divisible by K

Tags:

• Medium
• prefix
• hash
• recommand

Link

Combination of prefix + freq table

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:

        N = len(nums)
        M = defaultdict(int)
        M[0] = 1

        # we can use just O(1) space instead
        P = [0] * N

        res = 0

        for i in range(N):
            P[i] = (P[i-1] + nums[i]) % k

            res += M[P[i]]

            M[P[i]] += 1

        return res