# Count of Interesting Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-of-interesting-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/count-of-interesting-subarrays
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
---
## 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 `cnt` be the number of indices `i` in the range `[l, r]` such that `nums[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 <= 105 `
* `1 <= nums[i] <= 109`
* `1 <= modulo <= 109`
* `0 <= k < modulo`

# Approaches
## Brute Force Enumeration of Subarrays
This approach involves generating every possible subarray, and for each one, counting the number of elements that satisfy the condition `num % modulo == k`. If this count, modulo `modulo`, equals `k`, we increment our total count of interesting subarrays.
**Time:** O(N^3), where N is the number of elements in `nums`. There are `O(N^2)` subarrays, and for each subarray, we iterate through its elements, which can take up to `O(N)` time. This will result in a Time Limit Exceeded (TLE) verdict for the given constraints. · **Space:** O(1), as we only use a few variables to store counts.
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient and will not pass the time limits for larger inputs.
### Explanation
This is the most straightforward but also the most inefficient method. It checks every single subarray by iterating through all possible start and end points. For each of these subarrays, it performs another iteration to count the elements that satisfy the given condition. This leads to a cubic time complexity, which is too slow for the given constraints.

```java
import java.util.List;

class Solution {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        long ans = 0;
        int n = nums.size();
        for (int l = 0; l < n; l++) {
            for (int r = l; r < n; r++) {
                int cnt = 0;
                // Subarray is nums[l..r]
                for (int i = l; i <= r; i++) {
                    if (nums.get(i) % modulo == k) {
                        cnt++;
                    }
                }
                if (cnt % modulo == k) {
                    ans++;
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
- Initialize a variable `ans` to 0 to store the count of interesting subarrays.
- Use a nested loop to define the start (`l`) and end (`r`) of each subarray. The outer loop iterates `l` from 0 to `n-1`, and the inner loop iterates `r` from `l` to `n-1`.
- For each subarray `nums[l..r]`, initialize a counter `cnt` to 0.
- Iterate through the subarray from index `l` to `r`. For each element `nums[i]`, check if `nums[i] % modulo == k`. If it is, increment `cnt`.
- After counting, check if `cnt % modulo == k`. If this condition holds, increment `ans`.
- After all subarrays have been checked, return `ans`.

## Optimized Brute Force
This is an improvement over the first brute-force approach. Instead of recounting for each subarray from scratch, we can maintain a running count as we extend the subarray. For a fixed starting point `l`, as we move the endpoint `r` from `l` to `n-1`, we can update the count in `O(1)` time.
**Time:** O(N^2). We have two nested loops, and the work inside the inner loop is constant time. This is still too slow for N = 10^5. · **Space:** O(1). We only use a few extra variables.
**Pros:** More efficient than the naive `O(N^3)` approach.; Still relatively easy to implement.
**Cons:** Fails for large inputs due to its quadratic time complexity.
### Explanation
We can optimize the naive brute-force approach by observing that when we extend a subarray `nums[l..r]` to `nums[l..r+1]`, the count of special elements is just the count for `nums[l..r]` plus one if `nums[r+1]` is a special element. This avoids the third nested loop, reducing the complexity from cubic to quadratic.

```java
import java.util.List;

class Solution {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        long ans = 0;
        int n = nums.size();
        for (int l = 0; l < n; l++) {
            int cnt = 0;
            for (int r = l; r < n; r++) {
                if (nums.get(r) % modulo == k) {
                    cnt++;
                }
                if (cnt % modulo == k) {
                    ans++;
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
- Initialize `ans` to 0.
- Use an outer loop to iterate through the starting index `l` from 0 to `n-1`.
- Inside the outer loop, initialize a running counter `cnt` to 0.
- Use an inner loop to iterate through the ending index `r` from `l` to `n-1`.
- For each `r`, update `cnt` by checking `nums[r]`. If `nums.get(r) % modulo == k`, increment `cnt`.
- Now, `cnt` holds the count for the subarray `nums[l..r]`. Check if `cnt % modulo == k`. If it is, increment `ans`.
- After the loops complete, return `ans`.

## Prefix Sum with Hash Map
This approach reformulates the problem to use prefix sums. The core idea is that the condition on a subarray `nums[l..r]` depends on the number of elements satisfying a property. This count can be expressed using prefix sums. By applying modular arithmetic, we can find the required subarrays in a single pass.
**Time:** O(N), where N is the number of elements in `nums`. We iterate through the list once, and all operations inside the loop (hash map access, arithmetic) take, on average, `O(1)` time. · **Space:** O(min(N, modulo)). The hash map stores the frequencies of prefix sum moduli. The number of distinct keys is at most `N+1`. The keys themselves are in the range `[0, modulo-1]`. Thus, the size of the map is bounded by both `N+1` and `modulo`.
**Pros:** Highly efficient and optimal solution that passes all test cases within the time limit.
**Cons:** Requires understanding of prefix sums and modular arithmetic, making it slightly more complex to devise than brute-force solutions.
### Explanation
The most efficient solution uses a combination of prefix sums and a hash map. The condition for an interesting subarray `nums[l..r]` is `(count of special elements in nums[l..r]) % modulo == k`. Let `count(i)` be the count of special elements in the prefix `nums[0..i]`. Then the count for `nums[l..r]` is `count(r) - count(l-1)`. The condition becomes `(count(r) - count(l-1)) % modulo == k`.

By rearranging, we get `count(l-1) % modulo == (count(r) - k + modulo) % modulo`. We can iterate through the array with an index `r`, maintaining the running prefix count `count(r)`. For each `r`, we need to find how many indices `l-1` (where `l <= r`) satisfy the rearranged equation. We can do this efficiently by storing the frequencies of `count(j) % modulo` for all `j < r` in a hash map.

```java
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        long ans = 0;
        int prefixSum = 0;
        Map<Integer, Integer> freq = new HashMap<>();
        // An empty prefix has a sum of 0. Its frequency is 1.
        freq.put(0, 1);

        for (int num : nums) {
            // Update prefix sum based on the condition
            if (num % modulo == k) {
                prefixSum++;
            }
            
            // Calculate current prefix sum modulo
            int currentMod = prefixSum % modulo;
            
            // We need (currentMod - prevMod) % modulo == k
            // which means prevMod % modulo == (currentMod - k) % modulo
            int targetMod = (currentMod - k + modulo) % modulo;
            
            // Add the number of times we've seen this targetMod
            ans += freq.getOrDefault(targetMod, 0);
            
            // Update the frequency of the current prefix sum modulo
            freq.put(currentMod, freq.getOrDefault(currentMod, 0) + 1);
        }
        
        return ans;
    }
}
```
### Algorithm
- First, let's simplify the problem. We only care about whether `nums[i] % modulo == k`. Let's create a conceptual binary array `A` where `A[i] = 1` if `nums[i] % modulo == k` and `A[i] = 0` otherwise.
- The count `cnt` for a subarray `nums[l..r]` is the sum of `A[i]` from `l` to `r`.
- Let `P[i]` be the prefix sum of `A` up to index `i-1`. Then the sum for subarray `A[l..r]` is `P[r+1] - P[l]`.
- The condition for an interesting subarray is `(P[r+1] - P[l]) % modulo == k`.
- Rearranging this with modular arithmetic, we get `P[l] % modulo == (P[r+1] - k + modulo) % modulo`.
- We can iterate through the array from left to right, calculating the current prefix sum `P[i+1]`. For each `i`, we need to find how many previous indices `j < i+1` satisfy the condition.
- We use a hash map to store the frequencies of the prefix sum moduli encountered so far.
- Initialize `ans = 0`, `prefix_sum = 0`.
- Initialize a hash map `freq` with `(0, 1)` to represent the empty prefix.
- Iterate through each number `num` in `nums`.
- Update `prefix_sum` if `num % modulo == k`.
- Calculate `current_mod = prefix_sum % modulo`.
- Calculate `target_mod = (current_mod - k + modulo) % modulo`.
- Add the frequency of `target_mod` from the map to `ans`.
- Increment the frequency of `current_mod` in the map.
- Return `ans`.

# Solutions
### Java

```java
class Solution {
public
  long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
    int n = nums.size();
    int[] arr = new int[n];
    for (int i = 0; i < n; ++i) {
      arr[i] = nums.get(i) % modulo == k ? 1 : 0;
    }
    Map<Integer, Integer> cnt = new HashMap<>();
    cnt.put(0, 1);
    long ans = 0;
    int s = 0;
    for (int x : arr) {
      s += x;
      ans += cnt.getOrDefault((s - k + modulo) % modulo, 0);
      cnt.merge(s % modulo, 1, Integer : : sum);
    }
    return ans;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int: arr = [int(x % modulo == k) for x in nums] cnt = Counter() cnt[0] = 1 ans = s = 0 for x in arr: s += x ans += cnt[(s - k) % modulo] cnt[s % modulo] += 1 return ans

```