#2845

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count of Interesting Subarrays

Count all subarrays where the number of elements satisfying a modulo condition equals a target k using efficient prefix sums.

array hash table prefix sum

Problem Statement

You are given a 0-indexed integer array nums, an integer modulo, and an integer k. A subarray nums[l..r] is considered interesting if the number of indices i in the range [l, r] where nums[i] % modulo == k satisfies cnt % modulo == k.

Return the total count of interesting subarrays. For example, with nums = [3,2,4], modulo = 2, and k = 1, the interesting subarrays are [3], [3,2], and [3,2,4], giving an output of 3. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9, 1 <= modulo <= 10^9, 0 <= k < modulo.

Examples

Example 1

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

Output: 3

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

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

Solution Approach

Prefix Sum Transformation

Transform the array into a count array where each element is 1 if nums[i] % modulo == k and 0 otherwise. Compute prefix sums of this array to simplify checking subarray counts against the modulo condition.

Hash Map Frequency Tracking

Use a hash map to track the frequency of each prefix sum modulo modulo. For each new prefix sum, check how many previous prefix sums satisfy the condition prefixSum[i] - prefixSum[j] % modulo == k. Increment the answer accordingly.

Single Pass Computation

Scan the array once while updating prefix sums and hash map counts. This ensures O(n) time complexity and avoids nested loops, directly counting interesting subarrays during traversal.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(\min(n, \textit{modulo}))

Time complexity is O(n) because each element is processed once. Space complexity is O(min(n, modulo)) since the hash map stores counts of prefix sums modulo modulo, limited by the smaller of array length or modulo.

What Interviewers Usually Probe

You are expected to identify that brute force checking of all subarrays is too slow for large arrays.
Look for the connection between counting elements satisfying a modulo condition and prefix sums.
Using a hash map to track prefix sum frequencies is a strong hint for an efficient solution.

Common Pitfalls or Variants

Common pitfalls

Forgetting to transform the array to a 0/1 count based on the modulo condition, which breaks prefix sum logic.
Incorrectly computing prefix sum differences modulo the given value, leading to wrong subarray counts.
Not initializing the hash map with the base case prefix sum of 0, which misses subarrays starting at index 0.

Follow-up variants

Count subarrays where the sum of elements modulo a given number equals k instead of counting individual indices.
Handle arrays with negative numbers where modulo operation behaves differently, requiring adjustment in prefix sums.
Find the longest interesting subarray instead of counting all subarrays, adapting the same prefix sum plus hash map technique.

FAQ

What does an interesting subarray mean in Count of Interesting Subarrays?

An interesting subarray is one where the count of elements satisfying nums[i] % modulo == k also satisfies cnt % modulo == k.

Can this problem be solved without a hash map?

Yes, but using a hash map to track prefix sum frequencies allows O(n) time instead of O(n^2) brute force checks.

Why use a prefix sum transformation here?

Prefix sums convert counting elements over subarrays into a simple subtraction problem, enabling fast frequency checks for the modulo condition.

How do large modulo values affect the solution?

Large modulo values increase the possible range of prefix sums, but the hash map ensures space is only proportional to min(n, modulo).

What is the key pattern in this problem?

The key pattern is array scanning plus hash lookup, using prefix sums to count subarrays efficiently without nested loops.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

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

Continue Practicing

#2848 points that intersect with cars #2875 minimum size subarray in infinite array #3026 maximum good subarray sum