Scale Engineer

Count of Interesting Subarrays

Med
#2544Time: 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.
Patterns
Prefix Sum
Data structures
ArrayHash Table

Prompt

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 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] <= 109
  • 1 <= modulo <= 109
  • 0 <= 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 ans to 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 iterates l from 0 to n-1, and the inner loop iterates r from l to n-1.
  • For each subarray nums[l..r], initialize a counter cnt to 0.
  • Iterate through the subarray from index l to r. For each element nums[i], check if nums[i] % modulo == k. If it is, increment cnt.
  • After counting, check if cnt % modulo == k. If this condition holds, increment ans.
  • 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.

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem