Count of Interesting Subarrays

Medium
1360.

Count of Interesting Subarrays

Count of Interesting Subarrays is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.

You are given an integer array nums and two integers modulo and k.

For a non-empty contiguous subarray nums[l..r], let cnt be the number of indices i in [l, r] with nums[i] % modulo == k. The subarray is interesting when cnt % modulo == k.

Return the number of interesting subarrays.

CodeKairo note: the original allows nums.length up to 10^5 and returns a 64-bit count; here the length is at most 5 * 10^4, so the answer fits in a 32-bit integer.

Example 1

Input
nums = [5,2,7,4], modulo = 3, k = 1
Output
4
Explanation
Only 7 and 4 leave remainder 1. The interesting subarrays are those holding exactly one of them: `[7]`, `[2,7]`, `[5,2,7]` and `[4]`.

Example 2

Input
nums = [6,3,9], modulo = 3, k = 0
Output
1
Explanation
Every element qualifies, so `cnt` is the length; only the whole array has a length divisible by 3.

Example 3

Input
nums = [1,2,3], modulo = 5, k = 4
Output
0

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 10^9
  • 1 <= modulo <= 10^9
  • 0 <= k < modulo
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} modulo
 * @param {number} k
 * @return {number}
 */
var countInterestingSubarrays = function(nums, modulo, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count of Interesting Subarrays — Problem & Solution

Count of Interesting Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count of Interesting Subarrays is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums and two integers modulo and k.

For a non-empty contiguous subarray nums[l..r], let cnt be the number of indices i in [l, r] with nums[i] % modulo == k. The subarray is interesting when cnt % modulo == k.

Return the number of interesting subarrays.

CodeKairo note: the original allows nums.length up to 10^5 and returns a 64-bit count; here the length is at most 5 * 10^4, so the answer fits in a 32-bit integer.

Example 1

Input: nums = [5,2,7,4], modulo = 3, k = 1
Output: 4
Explanation: Only 7 and 4 leave remainder 1. The interesting subarrays are those holding exactly one of them: `[7]`, `[2,7]`, `[5,2,7]` and `[4]`.

Example 2

Input: nums = [6,3,9], modulo = 3, k = 0
Output: 1
Explanation: Every element qualifies, so `cnt` is the length; only the whole array has a length divisible by 3.

Example 3

Input: nums = [1,2,3], modulo = 5, k = 4
Output: 0

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 10^9
  • 1 <= modulo <= 10^9
  • 0 <= k < modulo

Hints for Count of Interesting Subarrays

  1. Hint 1

    Turn the array into 0/1 flags: 1 where nums[i] % modulo == k. Then cnt for a subarray is a difference of two prefix sums of the flags.

  2. Hint 2

    With prefix counts P, the subarray (l, r] is interesting when (P[r] - P[l]) % modulo == k, i.e. P[l] % modulo == (P[r] - k) % modulo (taken non-negative).

  3. Hint 3

    Sweep r, keeping a hash map from P[l] % modulo to how many earlier prefixes have it (start with {0: 1}); add the count of the required residue each step.

How to solve Count of Interesting Subarrays

This is the "subarrays with sum ≡ k (mod m)" pattern on 0/1 flags: count earlier prefix residues that complete the current one.

Approach

  1. Keep a running count cnt of qualifying elements seen so far and a map seen with seen[0] = 1 (the empty prefix).
  2. For each element, increment cnt if nums[i] % modulo == k, then let r = cnt % modulo.
  3. The needed earlier residue is (r - k + modulo) % modulo; add seen[needed] to the answer.
  4. Increment seen[r].

Why it works

For a subarray (l, r], its count is P[r] - P[l], and (P[r] - P[l]) % modulo == k holds exactly when P[l] ≡ P[r] - k (mod modulo). Since 0 <= k < modulo, the residue (P[r] - k) mod modulo is a single well-defined value, and the map holds how many prefixes l < r have it. Every subarray corresponds to one pair (l, r), so each is counted once.

Complexity

  • Time — O(n)
  • Space — O(min(n, modulo))

Pitfalls

  • k can be 0: then subarrays with no qualifying element at all are interesting (their count 0 is ≡ 0).
  • modulo can be huge, so the residues are just the counts themselves — never allocate an array of size modulo. Counts never exceed n, so an array of size n + 1 also works.
  • Make the needed residue non-negative before the lookup; % keeps the dividend's sign in most languages.

Reference solution

Python

from typing import List

def countInterestingSubarrays(nums: List[int], modulo: int, k: int) -> int:
    seen = {0: 1}
    cnt = 0
    ans = 0
    for v in nums:
        if v % modulo == k:
            cnt += 1
        r = cnt % modulo
        ans += seen.get((r - k) % modulo, 0)
        seen[r] = seen.get(r, 0) + 1
    return ans

Java

public static int countInterestingSubarrays(int[] nums, int modulo, int k) {
    int n = nums.length;
    int[] seen = new int[n + 1];
    seen[0] = 1;
    int cnt = 0;
    long ans = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] % modulo == k) cnt++;
        int r = cnt % modulo;
        long want = ((long) r - k + modulo) % modulo;
        if (want <= n) ans += seen[(int) want];
        seen[r]++;
    }
    return (int) ans;
}

C++

int countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
    int n = nums.size();
    vector<int> seen(n + 1, 0);
    seen[0] = 1;
    int cnt = 0;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] % modulo == k) cnt++;
        int r = cnt % modulo;
        long long want = ((long long) r - k + modulo) % modulo;
        if (want <= n) ans += seen[want];
        seen[r]++;
    }
    return (int) ans;
}

JavaScript

var countInterestingSubarrays = function(nums, modulo, k) {
    var seen = new Map();
    seen.set(0, 1);
    var cnt = 0, ans = 0;
    for (var i = 0; i < nums.length; i++) {
        if (nums[i] % modulo === k) cnt++;
        var r = cnt % modulo;
        var want = (r - k + modulo) % modulo;
        ans += seen.get(want) || 0;
        seen.set(r, (seen.get(r) || 0) + 1);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets