Medium

Continuous Subarray Sum

046

Return true if nums has a contiguous subarray of length at least two whose sum is a multiple of k.

EXAMPLES

Example 1

Input
{
  "nums": [
    23,
    2,
    4,
    6,
    7
  ],
  "k": 6
}

Output
true

FUNCTION SHAPE

nums: intArrayk: int→bool

SOLUTION NOTE

Instead of a frequency count, we want an existence check. So our map values are the indices rather than frequency counts.

Key: Only update the prefix index map with the earliest index with that prefix sum. We want to greedily check for the largest possible subarray.

Reveal reference solution +

pythonREFERENCE

def checkSubarraySum(self, nums: List[int], k: int) -> bool:
    prefix_index = {0: -1}
    pref = 0
    for i in range(len(nums)):
        pref = (pref + nums[i]) % k

        if pref in prefix_index:
            if i - prefix_index[pref] >= 2:
                return True
        else:
            prefix_index[pref] = i  # store EARLIEST index

    return False

TimeO(n)

SpaceO(min(n,k))

Open on LeetCode ↗