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^41 <= nums[i] <= 10^91 <= modulo <= 10^90 <= k < modulo
Hints for Count of Interesting Subarrays
Hint 1
Turn the array into 0/1 flags: 1 where
nums[i] % modulo == k. Thencntfor a subarray is a difference of two prefix sums of the flags.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).Hint 3
Sweep
r, keeping a hash map fromP[l] % moduloto 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
- Keep a running count
cntof qualifying elements seen so far and a mapseenwithseen[0] = 1(the empty prefix). - For each element, increment
cntifnums[i] % modulo == k, then letr = cnt % modulo. - The needed earlier residue is
(r - k + modulo) % modulo; addseen[needed]to the answer. - 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
kcan be 0: then subarrays with no qualifying element at all are interesting (their count 0 is ≡ 0).modulocan be huge, so the residues are just the counts themselves — never allocate an array of sizemodulo. Counts never exceedn, so an array of sizen + 1also 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 ansJava
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