Count of Interesting Subarrays

MEDIUM

Description

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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= modulo <= 10⁹
0 <= k < modulo

Approaches

Checkout 3 different approaches to solve Count of Interesting Subarrays. Click on different approaches to view the approach and algorithm in detail.

Brute Force Enumeration of Subarrays

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to store counts.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Very inefficient and will not pass the time limits for larger inputs.

Code Solutions

Checking out 3 solutions in different languages for Count of Interesting Subarrays. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Count of Interesting Subarrays

Patterns:

Prefix Sum

Data Structures:

ArrayHash Table