523. Continuous Subarray Sum

Intuition

The problem involves finding a subarray of at least two elements whose sum is a multiple of a given integer \( k \). A key observation is that if the cumulative sum up to two different indices has the same remainder when divided by \( k \), then the sum of the elements between these two indices is a multiple of \( k \). This is because the difference between two sums with the same remainder is divisible by \( k \).

Approach

1. Initialize a map: Use a dictionary to store the remainder of the cumulative sum divided by \( k \) and its corresponding index. Initialize this map with a remainder of 0 at index -1 to handle cases where the subarray starts from index 0.
2. Iterate through the array: Calculate the cumulative sum as you iterate through the array.
3. Calculate remainder: Compute the remainder of the cumulative sum divided by \( k \).
4. Check the map: - If the remainder is already in the map and the length of the subarray (current index - stored index) is at least 2, return true. - If the remainder is not in the map, store the current index for this remainder.
5. Return false: If no such subarray is found by the end of the iteration, return false.

Complexity

• Time Complexity: \(O(n)\), where \(n\) is the length of the input array. We iterate through the array once and perform constant-time operations within the loop.
• Space Complexity: \( O(min(n, k)) \), for the dictionary storing the remainders. In the worst case, we store each unique remainder in the dictionary, which can be at most \(min(n, k)\) unique remainders.

Code

C++

class Solution {
public:
    bool checkSubarraySum(vector& nums, int k) {
        unordered_map map = {{0, -1}};
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            int rem = sum % k;
            if (map.find(rem) != map.end()) {
                if (i - map[rem] >= 2) {
                    return true;
                }
            } else {
                map[rem] = i;
            }
        }
        return false;
    }
};

Python

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

Java

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int rem = sum % k;
            if (map.containsKey(rem)) {
                if (i - map.get(rem) >= 2) {
                    return true;
                }
            } else {
                map.put(rem, i);
            }
        }
        return false;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var checkSubarraySum = function (nums, k) {
    let map = new Map([[0, -1]]);
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        let rem = sum % k;
        if (map.has(rem)) {
            if (i - map.get(rem) >= 2) {
                return true;
            }
        }
        else {
            map.set(rem, i);
        }
    }
    return false;
};