LeetCode 2845 - Count of Interesting Subarrays

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem is asking us to count the number of interesting subarrays in a given array nums. An interesting subarray is defined by a modular counting condition: within any subarray nums[l..r], count the number of elements nums[i] where nums[i] % modulo == k. If this count, cnt, also satisfies cnt % modulo == k, then the subarray is interesting. The inputs are the array nums, the integer modulo, and the integer k. The output is a single integer representing how many subarrays meet this condition.

The constraints are significant: nums can have up to 10^5 elements, and each element can be as large as 10^9. The modulo can also be large, up to 10^9. These constraints rule out naive solutions that check every subarray explicitly because such an approach would be O(n²) in time complexity and infeasible for large arrays.

Important edge cases include:

Small arrays (length 1) where the subarray is the element itself.
Cases where k = 0, which requires correctly handling zero modular arithmetic.
Arrays where no element satisfies nums[i] % modulo == k, which should still correctly count subarrays where cnt % modulo == k.

Understanding these nuances ensures the algorithm handles both trivial and complex inputs.

Approaches

Brute Force Approach

The brute-force approach would enumerate all possible subarrays, count the number of elements in each subarray that satisfy nums[i] % modulo == k, and then check if cnt % modulo == k. This method is correct because it explicitly checks every subarray, but it is too slow for the maximum constraints because it has a time complexity of O(n²) for iterating over subarrays and O(n) for counting elements within each subarray, resulting in O(n³) overall in the naive implementation. Even optimizing the count inside each subarray to O(1) using prefix sums still results in O(n²), which is excessive for n = 10^5.

Optimal Approach

The key observation is that we can reduce the problem to a prefix sum modulo problem. We define a transformed array where each element is 1 if nums[i] % modulo == k and 0 otherwise. Let prefix[i] denote the cumulative sum of this transformed array up to index i. The problem then becomes counting pairs (i, j) where:

(prefix[j] - prefix[i-1]) % modulo == k

This can be rewritten using modular arithmetic properties as:

prefix[j] % modulo == (prefix[i-1] + k) % modulo

Using a hash map to store the frequency of each prefix[i] % modulo value as we iterate through the array allows us to efficiently count the number of valid subarrays ending at each index. This reduces the time complexity to O(n) and space complexity to O(min(n, modulo)) because at most modulo different remainders exist.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Enumerate all subarrays and count occurrences
Optimal	O(n)	O(min(n, modulo))	Use prefix sum with modular arithmetic and hash map

Algorithm Walkthrough

Transform the input array nums into a binary array transformed where each element is 1 if nums[i] % modulo == k and 0 otherwise. This simplifies counting elements that satisfy the modular condition.
Initialize a hash map count_map with {0: 1} to account for subarrays starting at index 0. This keeps track of frequencies of prefix sums modulo modulo.
Initialize a variable prefix_sum = 0 to store the running sum of the transformed array.
Initialize a variable result = 0 to store the number of interesting subarrays.
Iterate through the transformed array:
Add the current element to prefix_sum.
Compute needed = (prefix_sum - k) % modulo. This represents the prefix sum that would satisfy the modular condition for a subarray ending at the current index.
Add count_map.get(needed, 0) to result.
Increment count_map[prefix_sum % modulo] by 1.
Return result as the final count of interesting subarrays.

Why it works: By maintaining counts of prefix sums modulo modulo, we efficiently find all previous positions that can form a valid subarray with the current index. Modular arithmetic ensures correctness because (prefix[j] - prefix[i-1]) % modulo == k is equivalent to checking (prefix[i-1] + k) % modulo == prefix[j] % modulo.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        transformed = [1 if num % modulo == k else 0 for num in nums]
        count_map = defaultdict(int)
        count_map[0] = 1
        prefix_sum = 0
        result = 0
        
        for val in transformed:
            prefix_sum += val
            needed = (prefix_sum - k) % modulo
            result += count_map.get(needed, 0)
            count_map[prefix_sum % modulo] += 1
        
        return result

In this Python implementation, we first transform the array into 0/1 values to simplify counting. We then iterate through the array, updating a running prefix sum and using a hash map to count the number of valid subarrays ending at each position. The use of defaultdict allows us to handle keys that are not yet in the map without extra checks.

Go Solution

func countInterestingSubarrays(nums []int, modulo int, k int) int64 {
    n := len(nums)
    transformed := make([]int, n)
    for i, num := range nums {
        if num % modulo == k {
            transformed[i] = 1
        } else {
            transformed[i] = 0
        }
    }
    
    countMap := make(map[int]int64)
    countMap[0] = 1
    var prefixSum int
    var result int64
    
    for _, val := range transformed {
        prefixSum += val
        needed := (prefixSum - k) % modulo
        if needed < 0 {
            needed += modulo
        }
        result += countMap[needed]
        countMap[prefixSum % modulo]++
    }
    
    return result
}

In Go, we handle negative modular results explicitly because % in Go can produce negative numbers. The rest of the logic mirrors the Python version, using a map to track prefix sums and counting valid subarrays.

Worked Examples

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

i	nums[i]	transformed[i]	prefix_sum	count_map	result
0	3	1	1	{0:1}	1
1	2	0	1	{0:1,1:1}	2
2	4	0	1	{0:1,1:2}	3

Final result = 3

Example 2: nums = [3,1,9,6], modulo = 3, k = 0

i	nums[i]	transformed[i]	prefix_sum	needed	count_map	result
0	3	1	1	1	{0:1,1:1}	0
1	1	0	1	1	{0:1,1:2}	1
2	9	1	2	2	{0:1,1:2,2:1}	1
3	6	1	3	0	{0:1,1:2,2:1,0:1}	2

Final result = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the array once, performing constant-time operations per element.
Space	O(min(n, modulo))	We store counts of prefix sums modulo `modulo`, which is bounded by `modulo` or `n` if smaller.

This complexity is optimal for the problem constraints.

Test Cases

# Basic examples
assert Solution().countInterestingSubarrays([3,2,4], 2, 1) == 3  # example 1
assert Solution().countInterestingSubarrays([3,1,9,6], 3, 0) == 2  # example 2

# Edge cases
assert Solution().countInteresting