Problem Description

Given an integer array nums and an integer k, determine if the array contains a continuous subarray of at least size two whose elements sum up to a multiple of k (i.e., the sum is n * k for some integer n where n >= 1). Return true if such a subarray exists, otherwise return false.

• The subarray must be continuous (elements are consecutive in nums).
• The length of the subarray must be at least two.
• It's possible for k to be zero; in this case, look for a subarray whose sum is zero.
• Elements may be negative, zero, or positive.

Constraints:

• 1 <= nums.length <= 10⁵
• 0 <= nums[i] <= 10⁹
• 0 <= k <= 2³¹ - 1

Thought Process

At first glance, it seems we need to check all possible subarrays of length at least two and see if their sum is a multiple of k. However, this brute-force approach would be very slow for large arrays, since there are O(N²) subarrays.

To optimize, we can remember that the sum of a subarray from index i to j can be computed as prefixSum[j+1] - prefixSum[i]. If we want this difference to be a multiple of k, then (prefixSum[j+1] - prefixSum[i]) % k == 0, which means prefixSum[j+1] % k == prefixSum[i] % k.

This insight allows us to use a hash map to quickly check if we've seen the same remainder before, and if so, whether the subarray is at least length two.

Solution Approach

• Step 1: Compute the running sum (prefix sum) as we iterate through the array.
• Step 2: For each index i, compute prefixSum % k (if k != 0).
  • If k == 0, then just use the running sum (since we want the sum itself to be zero).
• Step 3: Use a hash map to store the first index where each remainder was seen.
  • If we see the same remainder at a later index, and the distance between indices is at least 2, then the subarray sum between those indices is a multiple of k.
• Step 4: If we find such a subarray, return true. If we finish the loop without finding one, return false.
• Special Case: For the initial prefix sum (before any elements), we set the remainder 0 to index -1. This allows subarrays starting at index 0 to be considered.

We use a hash map for O(1) lookups of previously seen remainders, making the solution efficient.

Example Walkthrough

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

1. Initialize prefixSum = 0, modMap = {0: -1}.
2. i = 0: prefixSum = 23, remainder = 23 % 6 = 5
   • Add 5:0 to map.
3. i = 1: prefixSum = 25, remainder = 25 % 6 = 1
   • Add 1:1 to map.
4. i = 2: prefixSum = 29, remainder = 29 % 6 = 5
   • 5 is already in map at index 0.
   • Distance = 2 (2 - 0) >= 2, so subarray [2, 4] sums to a multiple of 6.
   Return true.

This demonstrates how the hash map allows us to find a valid subarray efficiently.

Time and Space Complexity

• Brute-force:
  • Time: O(N²) — Checking all subarrays of length at least 2.
  • Space: O(1) — Only a few variables needed.
• Optimized (Hash Map) Approach:
  • Time: O(N) — Each element is processed once; hash map lookups and inserts are O(1).
  • Space: O(min(N, k)) — In the worst case, we store up to N different remainders (or up to k, since remainders are in [0, k-1]).

The optimized approach is efficient enough for large input sizes.

Summary

The key insight is to use prefix sums and modular arithmetic to reduce the problem to checking for repeated remainders. By remembering the first index where each remainder is seen, we can quickly determine if a valid subarray exists. This approach is both elegant and efficient, allowing us to solve the problem in linear time with minimal extra space.

Code Implementation

class Solution:
    def checkSubarraySum(self, nums, k):
        mod_map = {0: -1}
        prefix_sum = 0
        for i, num in enumerate(nums):
            prefix_sum += num
            remainder = prefix_sum if k == 0 else prefix_sum % k
            if remainder in mod_map:
                if i - mod_map[remainder] > 1:
                    return True
            else:
                mod_map[remainder] = i
        return False
      

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mod_map;
        mod_map[0] = -1;
        int prefix_sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            prefix_sum += nums[i];
            int remainder = (k == 0) ? prefix_sum : prefix_sum % k;
            if (mod_map.count(remainder)) {
                if (i - mod_map[remainder] > 1) return true;
            } else {
                mod_map[remainder] = i;
            }
        }
        return false;
    }
};
      

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> modMap = new HashMap<>();
        modMap.put(0, -1);
        int prefixSum = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            int remainder = (k == 0) ? prefixSum : prefixSum % k;
            if (modMap.containsKey(remainder)) {
                if (i - modMap.get(remainder) > 1) {
                    return true;
                }
            } else {
                modMap.put(remainder, i);
            }
        }
        return false;
    }
}
      

var checkSubarraySum = function(nums, k) {
    const modMap = new Map();
    modMap.set(0, -1);
    let prefixSum = 0;
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        let remainder = (k === 0) ? prefixSum : prefixSum % k;
        if (modMap.has(remainder)) {
            if (i - modMap.get(remainder) > 1) {
                return true;
            }
        } else {
            modMap.set(remainder, i);
        }
    }
    return false;
};