Count of Interesting Subarrays
MedPrompt
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
cntbe the number of indicesiin the range[l, r]such thatnums[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 <= 1051 <= nums[i] <= 1091 <= modulo <= 1090 <= k < modulo
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a variable
ansto 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 iterateslfrom 0 ton-1, and the inner loop iteratesrfromlton-1. - For each subarray
nums[l..r], initialize a countercntto 0. - Iterate through the subarray from index
ltor. For each elementnums[i], check ifnums[i] % modulo == k. If it is, incrementcnt. - After counting, check if
cnt % modulo == k. If this condition holds, incrementans. - After all subarrays have been checked, return
ans.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient and will not pass the time limits for larger inputs.
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.
Algorithm
- Initialize
ansto 0. - Use an outer loop to iterate through the starting index
lfrom 0 ton-1. - Inside the outer loop, initialize a running counter
cntto 0. - Use an inner loop to iterate through the ending index
rfromlton-1. - For each
r, updatecntby checkingnums[r]. Ifnums.get(r) % modulo == k, incrementcnt. - Now,
cntholds the count for the subarraynums[l..r]. Check ifcnt % modulo == k. If it is, incrementans. - After the loops complete, return
ans.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- First, let's simplify the problem. We only care about whether
nums[i] % modulo == k. Let's create a conceptual binary arrayAwhereA[i] = 1ifnums[i] % modulo == kandA[i] = 0otherwise. - The count
cntfor a subarraynums[l..r]is the sum ofA[i]fromltor. - Let
P[i]be the prefix sum ofAup to indexi-1. Then the sum for subarrayA[l..r]isP[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 eachi, we need to find how many previous indicesj < i+1satisfy 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
freqwith(0, 1)to represent the empty prefix. - Iterate through each number
numinnums. - Update
prefix_sumifnum % modulo == k. - Calculate
current_mod = prefix_sum % modulo. - Calculate
target_mod = (current_mod - k + modulo) % modulo. - Add the frequency of
target_modfrom the map toans. - Increment the frequency of
current_modin the map. - Return
ans.
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.