Watch 10 video solutions for Count of Interesting Subarrays, a medium level problem involving Array, Hash Table, Prefix Sum. This walkthrough by codestorywithMIK has 11,092 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |