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:
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] <= 1091 <= modulo <= 1090 <= k < moduloProblem 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.
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.
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.
Python
JavaScript
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.
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.
The C implementation performs a nested loop over the nums array to check and count the indices that satisfy nums[i] % modulo == k for every possible subarray, adjusting count when the interesting condition is met, i.e., cnt % modulo == k.
Time Complexity: O(n^2), where n is the length of nums, due to double iteration over the array.
Space Complexity: O(1), no additional space is used beyond count variables.
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.
| 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), where n is the length of |
| Hash Table + Prefix Sum | — |
| 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 |
Count of Interesting Subarrays | Using Studied Concept | Dry Run | Leetcode 2845 | codestorywithMIK • codestorywithMIK • 11,092 views views
Watch 9 more video solutions →Practice Count of Interesting Subarrays with our built-in code editor and test cases.
Practice on FleetCode