Count of Interesting Subarrays solution and explanation
Google
9 more videos on this problem
Count of Interesting Subarrays | Using Studied Concept | Dry Run | Leetcode 2845 | codestorywithMIKcodestorywithMIK · 38:30 · 11K views
Count of Interesting Subarrays | Leetcode 2845Techdose · 22:08 · 8K views
2845. Count of Interesting Subarrays | Weekly Leetcode 361codingMohan · 17:23 · 2K views
2845. Count of Interesting Subarrays || Prefix SumAyush Rao · 12:20 · 1K views
2845. Count of Interesting Subarrays || Weekly Contest 361 || LeetcodeAshish Kumar · 11:37 · 1K views
2845. Count of Interesting Subarrays | Leetcode Daily - PythonLeetcode Daily · 11:42 · 1K views
LeetCode 2845 Count of Interesting Subarrays | Prefix Sum | Detailed Explanation | Asked in GoogleCode Harmony · 34:33 · 1K views
2845. Count of Interesting Subarrays (Leetcode Medium)Programming Live with Larry · 19:36 · 909 views
Daily Leetcode #1851: Apr 25, 2025 - 2845. Count of Interesting SubarraysProgramming Live with Larry · 31:13 · 853 views
Count of Interesting Subarrays - LEETCODE WEEKLY CONTEST 361 (Explanation in details)Joyjit Codes · 9:16 · 624 views
The problem
You are given a 0-indexed integer array nums, an integer modulo, and an integer k.
Your task is to find the count of subarrays that are interesting.
A subarray nums[l..r] is interesting if the following condition holds:
- Let
cntbe the number of indicesiin the range[l, r]such thatnums[i] % modulo == k. Then,cnt % modulo == k.
Return an integer denoting the count of interesting subarrays.
Note: A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [3,2,4], modulo = 2, k = 1 Output: 3 Explanation: In this example the interesting subarrays are: The subarray nums[0..0] which is [3]. - There is only one index, i = 0, in the range [0, 0] that satisfies nums[i] % modulo == k. - Hence, cnt = 1 and cnt % modulo == k. The subarray nums[0..1] which is [3,2]. - There is only one index, i = 0, in the range [0, 1] that satisfies nums[i] % modulo == k. - Hence, cnt = 1 and cnt % modulo == k. The subarray nums[0..2] which is [3,2,4]. - There is only one index, i = 0, in the range [0, 2] that satisfies nums[i] % modulo == k. - Hence, cnt = 1 and cnt % modulo == k. It can be shown that there are no other interesting subarrays. So, the answer is 3.
Example 2:
Input: nums = [3,1,9,6], modulo = 3, k = 0 Output: 2 Explanation: In this example the interesting subarrays are: The subarray nums[0..3] which is [3,1,9,6]. - There are three indices, i = 0, 2, 3, in the range [0, 3] that satisfy nums[i] % modulo == k. - Hence, cnt = 3 and cnt % modulo == k. The subarray nums[1..1] which is [1]. - There is no index, i, in the range [1, 1] that satisfies nums[i] % modulo == k. - Hence, cnt = 0 and cnt % modulo == k. It can be shown that there are no other interesting subarrays. So, the answer is 2.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= modulo <= 1090 <= k < modulo
Approach overview
Problem Overview: You receive an integer array nums, a modulo, and a value k. A subarray is considered interesting if the count of elements where nums[i] % modulo == k satisfies count % modulo == k. The task is to compute how many such subarrays exist.
Approach 1: Brute Force with Optimization (O(n²) time, O(1) space)
Iterate over every possible starting index and expand the subarray one element at a time. Maintain a running counter for elements where nums[j] % modulo == k. After each expansion, check whether count % modulo == k. If true, increment the answer. This avoids recomputing counts from scratch but still evaluates all subarrays. The approach is straightforward and helps verify correctness before implementing the optimized version. It mainly relies on basic array traversal.
Approach 2: Prefix Sum and Hash Map (O(n) time, O(n) space)
The optimized solution transforms the condition using prefix sums. Define a prefix value prefix[i] as the number of elements up to index i where nums[i] % modulo == k. For a subarray (l, r) to be interesting, the equation (prefix[r] - prefix[l-1]) % modulo == k must hold. Rearranging gives prefix[l-1] % modulo = (prefix[r] - k) mod modulo. While scanning the array, compute the prefix count and maintain a frequency map of prefix % modulo values. For each position, check how many previous prefixes satisfy the required remainder using a constant-time hash table lookup. This converts the nested loop into a single pass.
The key insight is treating the problem as a modular prefix difference query. Each prefix remainder represents a state. When a matching previous remainder appears, it forms a valid subarray. This pattern frequently appears in problems involving prefix sums and modular arithmetic.
Recommended for interviews: The prefix sum + hash map approach is what interviewers expect. It demonstrates recognition of modular prefix patterns and the ability to reduce a quadratic scan into a linear pass. Showing the brute force approach first communicates understanding of the condition, but implementing the O(n) solution proves stronger algorithmic skill.
Approach 1: Prefix Sum and Hash Map Approach
This approach leverages the prefix sum technique along with a hash map to efficiently count the interesting subarrays. We utilize a prefix sum that tracks the cumulative count of indices satisfying nums[i] % modulo == k. For each index, we calculate the current prefix modulo and update our hash map to reflect how often each prefix has occurred. Since we are interested in subarrays whose count of such indices cnt satisfies cnt % modulo == k, we can utilize this prefix to quickly find valid subarrays ending at the current index.
def count_interesting_subarrays(nums, modulo, k):
count = 0
prefix_count = {0: 1}
current_prefix = 0
for num in nums:
current_prefix += (num % modulo == k)
current_mod = current_prefix % modulo
target = (current_mod - k + modulo) % modulo
count += prefix_count.get(target, 0)
prefix_count[current_mod] = prefix_count.get(current_mod, 0) + 1
return countfunction countInterestingSubarrays(nums, modulo, k) {
let count = 0;
let prefixCount = {0: 1};
let currentPrefix = 0;
for (let num of nums) {
currentPrefix += (num % modulo === k) ? 1 : 0;
let currentMod = currentPrefix % modulo;
let target = (currentMod - k + modulo) % modulo;
if (prefixCount[target] != null) {
count += prefixCount[target];
}
if (prefixCount[currentMod] == null) prefixCount[currentMod] = 0;
prefixCount[currentMod]++;
}
return count;
}The solution uses a hash map to track the frequency of prefix modulo values. For each number in nums, it updates the current_prefix and uses this to find how many previous prefixes form an interesting subarray ending at the current position. The hash map helps with constant-time lookups for the count of prefixes satisfying the equation derived from the problem.
Time Complexity: O(n), where n is the number of elements in nums, as we iterate over the array once.
Space Complexity: O(min(n, modulo)), primarily due to the storage used by the hash map, which holds at most modulo unique values.
Approach 2: Brute Force Approach with Optimization
This approach checks every possible subarray directly to verify whether it satisfies the interesting condition by counting relevant indices. Although this is not efficient for large nums, improvements can be made by breaking early when certain conditions are met.
public class Solution {
public int countInterestingSubarrays(int[] nums, int modulo, int k) {
int count = 0;
for (int start = 0; start < nums.length; ++start) {
int cnt = 0;
for (int end = start; end < nums.length; ++end) {
if (nums[end] % modulo == k) cnt++;
if (cnt % modulo == k) count++;
}
}
return count;
}
}#include <stdio.h>
int countInterestingSubarrays(int* nums, int numsSize, int modulo, int k) {
int count = 0;
for (int start = 0; start < numsSize; ++start) {
int cnt = 0;
for (int end = start; end < numsSize; ++end) {
if (nums[end] % modulo == k)
cnt++;
if (cnt % modulo == k)
count++;
}
}
return count;
}The Java implementation follows a simple brute-force method, iterating across all subarrays, incrementing the cnt for each index within a subarray that meets the modulo condition, and counting when cnt % modulo == k holds true.
Time Complexity: O(n^2), as a result of the two loops through the array.
Space Complexity: O(1), no extra space is required beyond temporary variable storage.
Approach 3: Hash Table + Prefix Sum
The problem requires the number of indices i in an interval that satisfy nums[i] bmod modulo = k. We can transform the array nums into a 0-1 array arr, where arr[i] = 1 indicates nums[i] bmod modulo = k, otherwise arr[i] = 0.
For an interval [l, r], we can calculate the number of 1s in arr[l..r] through the prefix sum array s, i.e., s[r] - s[l - 1], where s[0] = 0.
We use a hash table cnt to record the number of occurrences of the prefix sum s bmod modulo, initially cnt[0]=1.
Next, we traverse the array arr, calculate the prefix sum s, add the number of occurrences of (s-k) bmod modulo to the answer, and then add 1 to the number of occurrences of s bmod modulo.
After the traversal ends, return the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
class Solution {
public:
long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
int n = nums.size();
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
arr[i] = int(nums[i] % modulo == k);
}
unordered_map<int, int> cnt;
cnt[0] = 1;
long long ans = 0;
int s = 0;
for (int x : arr) {
s += x;
ans += cnt[(s - k + modulo) % modulo];
cnt[s % modulo]++;
}
return ans;
}
};function countInterestingSubarrays(nums: number[], modulo: number, k: number): number {
const arr: number[] = [];
for (const x of nums) {
arr.push(x % modulo === k ? 1 : 0);
}
const cnt: Map<number, number> = new Map();
cnt.set(0, 1);
let ans = 0;
let s = 0;
for (const x of arr) {
s += x;
ans += cnt.get((s - k + modulo) % modulo) || 0;
cnt.set(s % modulo, (cnt.get(s % modulo) || 0) + 1);
}
return ans;
}func countInterestingSubarrays(nums []int, modulo int, k int) (ans int64) {
arr := make([]int, len(nums))
for i, x := range nums {
if x%modulo == k {
arr[i] = 1
}
}
cnt := map[int]int{}
cnt[0] = 1
s := 0
for _, x := range arr {
s += x
ans += int64(cnt[(s-k+modulo)%modulo])
cnt[s%modulo]++
}
return
}use std::collections::HashMap;
impl Solution {
pub fn count_interesting_subarrays(nums: Vec<i32>, modulo: i32, k: i32) -> i64 {
let mut arr: Vec<i32> = nums
.iter()
.map(|&x| if x % modulo == k { 1 } else { 0 })
.collect();
let mut cnt: HashMap<i32, i64> = HashMap::new();
cnt.insert(0, 1);
let mut ans: i64 = 0;
let mut s: i32 = 0;
for x in arr {
s += x;
let key = (s - k).rem_euclid(modulo);
ans += *cnt.get(&key).unwrap_or(&0);
*cnt.entry(s % modulo).or_insert(0) += 1;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum and Hash Map Approach | Time Complexity: O(n), where n is the number of elements in |
| Brute Force Approach with Optimization | Time Complexity: O(n^2), as a result of the two loops through the array. |
| Hash Table + Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Running Count | O(n²) | O(1) | Small arrays or when verifying logic before optimization |
| Prefix Sum + Hash Map | O(n) | O(n) | General case and expected interview solution for large inputs |
Frequently asked questions
Is Count of Interesting Subarrays easy or hard?
Count of Interesting Subarrays is generally considered a medium difficulty problem. The brute force idea is simple, but recognizing the modular prefix sum transformation and using a hash map efficiently requires intermediate algorithm experience.
Count of Interesting Subarrays Python/Java solution
Most implementations compute a running prefix count and use a dictionary or hash map to store remainder frequencies. Python typically uses collections.Counter or defaultdict, while Java uses HashMap to track prefix % modulo counts during a single linear scan.
How to solve Count of Interesting Subarrays in O(n)?
Convert the problem into a prefix sum remainder problem. Maintain a running count of elements where nums[i] % modulo == k, compute prefix % modulo, and store its frequency in a hash map. For each index, look up how many earlier prefixes equal (currentPrefix - k) mod modulo, which directly gives the number of valid subarrays ending at that position.
What is the best approach for Count of Interesting Subarrays?
The optimal solution uses a prefix sum combined with a hash map. Track how many elements satisfy nums[i] % modulo == k while scanning the array, store prefix remainders, and count how many previous prefixes produce the required modular difference. This reduces the complexity to O(n) time with O(n) space.
Is Count of Interesting Subarrays asked at Google/Amazon/Meta?
Problems using prefix sums with modular arithmetic frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that count subarrays with specific modular properties are common because they test hash maps, prefix sums, and mathematical reasoning.
What data structure is used in Count of Interesting Subarrays?
The optimized solution relies on a hash map to store frequencies of prefix sum remainders. Combined with a running prefix counter, this allows constant-time lookups to determine how many previous states form a valid subarray.
What is the time complexity of Count of Interesting Subarrays?
The brute force approach takes O(n^2) time because it evaluates every possible subarray. The optimized prefix sum and hash map solution runs in O(n) time with O(n) auxiliary space for storing remainder frequencies.