Skip to content

← leetcode

Count of Interesting Subarrays

· Medium

LeetCode problem 2845

The key to this question is to utilise the power of prefix-sum arrays.

Example:

  • for [3, 2, 4, 5, 7, 2, 3], we can pre-compute values satisfying nums[i] % modulo == k
    • as a result, we get the array [1, 0, 0, 1, 1, 0, 1]
  • however, if we want to check what the cnt is between any 2 indices, we can compute a prefix-sum array, ps_array,
    • the prefix-sum array will thus be [1, 1, 1, 2, 3, 3, 4]
    • then, calculate the cnt using (ps_array[j] - ps_array[i]) % modulo == k for index i and j where i < j
      • note, however, that we can rewrite this equation to (ps_array[j] - k) == ps_array[i] (mod modulo), implying that we can create a hash-map to hash the number of times ps_array[i] % modulo has appeared previously
      • that implies that we can just calculate (ps_array[j] - k) % modulo to check the previous count in the hashmap

code

class Solution {
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1; // for the cases, where the entire array is `cnt % modulo``
        long long counter = 0;
        long long ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            counter += (nums[i] % modulo == k);
            ans += mp[(counter + modulo - k)%modulo];
            ++mp[counter%modulo];
        }
        return ans;
    }
};

complexity

  • Time: O(n) where n denotes the length of the array
  • Space: O(n)

learnings

  • using a vector instead of an unordered_map makes you TLE; arrays are not always better