deepSWE.io

Continuous Subarray Sum

Prefix SumHash Map

25 min

Problem Statement

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

Example

Example 1:

Input: nums = [23,2,4,6,7], k = 6

nums: [23, 2, 4, 6, 7], k: 6

Output: true

Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Solution

The key insight is that if a subarray sum is a multiple of `k`, then the prefix sums at the start and end of the subarray have the same remainder when divided by `k`. We can use a hash map to store the first occurrence of each remainder.

Algorithm Steps

Initialize a hash map with a remainder of 0 at index -1.
Initialize a `prefixSum` to 0.
Iterate through the array.
Update `prefixSum` and calculate the remainder when divided by `k`.
If the remainder is already in the map, and the current index is at least 2 greater than the stored index, we have found a valid subarray.
Otherwise, add the remainder and its index to the map.

Continuous Subarray Sum

Prefix Sum with Hash Map

Input: nums = [23, 2, 4, 6, 7], k = 6

Output: false

Progress1 / 1

Ready to start the visualization

Nums

Remainder Map

0: -1

Continuous Subarray Sum Solution


class Solution:
    def checkSubarraySum(self, nums: list[int], k: int) -> bool:
        remainder = { 0: -1 }
        total = 0
        for i, n in enumerate(nums):
            total += n
            r = total % k
            if r not in remainder:
                remainder[r] = i
            elif i - remainder[r] > 1:
                return True
        return False