2537. Count the Number of Good Subarrays


Problem Description

Given an integer array called nums and an integer k, the task is to determine the number of 'good' subarrays in nums. A subarray is a continuous part of the original array, and it is considered 'good' if there are at least k pairs (i, j) within it where i < j and the values at positions i and j are equal (i.e., arr[i] == arr[j]). The goal of the problem is to count and return how many such 'good' subarrays exist.

Intuition

The intuition behind the solution comes from recognizing that a subarray is 'good' if it contains a certain number of duplicated elements. For each new element we add to a subarray while iterating through the array, we increase the potential number of pairs that this element can form with previous elements (if there are duplicates).

The solution uses a moving window approach to check subarrays. We use the window defined by the indices i and the current index of the element being considered, growing from the start of the array to the end.

A Counter is used to track the number of times each element appears within the current window. For each new element x considered, we increase the count for that element in the Counter, and we add to cur, which keeps track of the current number of pairs within the window that satisfy the condition of being a 'good' subarray.

As we move the window forward by increasing i, we need to check if the window still has at least k good pairs after potentially removing an element (since the window might shrink). If the number of good pairs is still at least k after this potential removal, then every subarray that ends with the current element is 'good'. We then calculate how many such subarrays are there, which is i + 1, and add it to the overall count ans.

By using this approach, every time we find a window where the count cur is at least k, we ensure that we accumulate the number of good subarrays that end at the current index, resulting in a running total that gives the final answer: the number of good subarrays in the initial array.

Learn more about Sliding Window patterns.

Solution Approach

The implementation of the solution employs a sliding window pattern coupled with a hash map (Counter in Python) to keep track of the counts of each element within the current window. The approach works as follows:

  1. Initialize a Counter object cnt, which will map each number to the number of times it has occurred in the current subarray.

  2. Set up two accumulator variables: ans to store the total count of 'good' subarrays, and cur to keep track of the current count of pairs within the window that can potentially form a 'good' subarray.

  3. Set up an index i to represent the start of the current window, initially set to 0.

  4. Loop through the nums array with a variable x representing the current number.

    • For each x, add the current count of x in cnt to cur, increasing the number of pairs that match the condition (since x could form pairs with the earlier occurrences of itself).

    • Increment the count of x in cnt (since we are considering x as part of the current window).

    • While the current number of pairs (cur), minus the count of the element at the start of the window (nums[i]), plus one (as we are considering the case where we might exclude nums[i] from the array), is still greater than or equal to k, it means we can shrink the window from the left by doing the following:

      • Decrement the count of nums[i] in cnt (since we are removing it from the window).
      • Update cur by subtracting the updated count of nums[i] (since the potential pairs involving nums[i] are now reduced).
      • Increment i to shrink the window from the left.
    • If the current number of pairs cur is greater than or equal to k, there are i + 1 new 'good' subarrays ending with the current element, and we add this to our answer ans.

  5. After the loop completes, ans contains the total number of 'good' subarrays, and we return it.

In conclusion, the sliding window, along with the counter map, efficiently keeps track of the number of pairs that are duplicated within each window. By adjusting the start of the window (i), we ensure that the property of each subarray having at least k good pairs is maintained while accumulating the total number of such subarrays.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Example Walkthrough

Let's say we are provided with an integer array nums = [1, 2, 2, 1] and an integer k = 2. We want to count the number of 'good' subarrays where a 'good' subarray is one that contains at least k pairs with the same value.

We would approach this example with our sliding window pattern and a Counter for tracking the occurrences of each element.

  1. Start with our data structures: cnt is empty, ans is 0, and cur is 0. The index i is set to 0.

  2. As we loop through the nums array:

    • Element x = 1. We add cnt[1] (which is 0) to cur (now cur is also 0). We then increment cnt[1] by 1. cur remains less than k so ans remains 0.

    • Element x = 2. We add cnt[2] (which is 0) to cur (still 0). Increment cnt[2]. Since cur is still less than k, ans stays 0.

    • Element x = 2. Now, cnt[2] is 1, so we add this to cur, making cur = 1. We increment cnt[2], making cnt[2] = 2. With cur now 1, we still don't have enough pairs, so we don't change ans or i.

    • Element x = 1. We add cnt[1] (which is 1) to cur (now cur is 2). We increment cnt[1] by 1. Now cur equals k, and so we can begin checking if we can shrink the window. Since removing nums[i] (which is 1) would bring cur below k, we don't shrink the window. Therefore, we add i + 1 (which is 1) subarrays to ans, making ans = 1.

  3. We continue to try and shrink the window, but since subtracting nums[i] (which is 1) would drop cur below k, we cannot.

  4. We move to the next index, but since we're at the end of our array, we stop the loop.

We conclude that there are ans = 1 subarrays that meet the 'good' criteria. The subarray [2, 2] within nums is the one that meets the condition of having at least k = 2 pairs (i, j) with i < j such that nums[i] == nums[j].

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def countGood(self, nums: List[int], k: int) -> int:
5        # Initialize a counter to track the count of each number
6        num_counter = Counter()
7        # Initialize the result and current sum and the starting index
8        result = current_sum = start_index = 0
9      
10        # Iterate over the list of numbers
11        for num in nums:
12            # Update the current sum with the number of times we have seen the current number
13            current_sum += num_counter[num]
14            # Increment the count of the current number in the counter
15            num_counter[num] += 1
16          
17            # If the current sum exceeds the limit, adjust the window from the left
18            while current_sum - num_counter[nums[start_index]] + 1 >= k:
19                # Decrease the count of the starting number
20                num_counter[nums[start_index]] -= 1
21                # Deduct the excess from the current sum
22                current_sum -= num_counter[nums[start_index]]
23                # Move the starting index to the right
24                start_index += 1
25          
26            # If the current sum meets the requirement, count the subarrays
27            if current_sum >= k:
28                result += start_index + 1
29              
30        # Return the total count of "good" subarrays
31        return result
32
1class Solution {
2    public long countGood(int[] nums, int k) {
3        // HashMap to store the frequency of each number in the current subarray
4        Map<Integer, Integer> frequencyCounter = new HashMap<>();
5        long totalCount = 0; // Total count of good subarrays
6        long currentSize = 0; // Number of times a number has been repeated in the current subarray
7        int startIndex = 0; // Start index for the sliding window
8
9        // Iterate over the array using 'num' as the current element
10        for (int num : nums) {
11            // Update currentSize for the current value
12            currentSize += frequencyCounter.getOrDefault(num, 0);
13            // Increase the frequency counter for num
14            frequencyCounter.merge(num, 1, Integer::sum);
15
16            // Shrink the window from the left until the number of repeated elements is less than k
17            while (currentSize - frequencyCounter.get(nums[startIndex]) + 1 >= k) {
18                // Decrease the currentSize by the number of times the number at startIndex is in the window
19                currentSize -= frequencyCounter.merge(nums[startIndex], -1, Integer::sum);
20                // Move the start index of the subarray window to the right
21                startIndex++;
22            }
23          
24            // If the number of repeated elements is at least k, we count this as a 'good' subarray
25            if (currentSize >= k) {
26                // Add to the total number (startIndex + 1 indicates that we have a 'good' subarray up to the current index i)
27                totalCount += startIndex + 1;
28            }
29        }
30
31        // Return the total count of good subarrays
32        return totalCount;
33    }
34}
35
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    // Function to count the number of good subarrays.
8    long long countGood(vector<int>& nums, int k) {
9        unordered_map<int, int> elementCount; // Hashmap to count the occurrences of each integer.
10        long long totalCount = 0; // The total count of good subarrays.
11        long long currentCount = 0; // Current number of pairs with the same value.
12        int startIndex = 0; // The start index for the current subarray.
13
14        // Loop through the elements in the array.
15        for (int& num : nums) {
16            // Increment the current count by the number of occurrences before incrementing the count for the current number.
17            currentCount += elementCount[num]++;
18
19            // If the current count is greater than or equal to k, we need to adjust the start index of the subarray.
20            while (currentCount - elementCount[nums[startIndex]] + 1 >= k) {
21                // Reduce the number of pairs by the number of occurrences of the start element.
22                currentCount -= --elementCount[nums[startIndex++]];
23            }
24
25            // If the current count is greater than or equal to k after adjusting the start index, we increment the total count.
26            // The '+1' accounts for the single element as a subarray.
27            if (currentCount >= k) {
28                totalCount += startIndex + 1;
29            }
30        }
31
32        // Return the total number of good subarrays.
33        return totalCount;
34    }
35};
36
1// Importing the necessary module for dictionary-like data structure.
2import { Map } from "es6-shim";
3
4// Function to count the number of good subarrays.
5function countGood(nums: number[], k: number): number {
6    // Map to store the frequency of each element in the current window
7    let elementCount: Map<number, number> = new Map();
8  
9    // Initialize the total count of good subarrays as a number.
10    let totalCount: number = 0;
11  
12    // Variable to store the current count of pairs with the same value within the window.
13    let currentCount: number = 0;
14  
15    // The start index for the current subarray window.
16    let startIndex: number = 0;
17
18    // Iterating over each number in the array.
19    for (let num of nums) {
20        // If the number is already in the map, increase its count, otherwise add it with count 1.
21        elementCount.set(num, (elementCount.get(num) || 0) + 1);
22      
23        // Increment the current count of pairs by the previous count of 'num'.
24        currentCount += elementCount.get(num) - 1;
25
26        // Adjust the start index of the window if there are k or more pairs with the same value.
27        while (currentCount - (elementCount.get(nums[startIndex]) - 1) >= k) {
28            // Reduce the number of pairs by the occurrences of the nums[startIndex].
29            currentCount -= elementCount.get(nums[startIndex]) - 1;
30          
31            // Decrease the count of the start number as we're moving the window forward.
32            elementCount.set(nums[startIndex], elementCount.get(nums[startIndex]) - 1);
33          
34            // Move the window's start index forward.
35            startIndex++;
36        }
37
38        // If the current count window has k or more pairs, add to the total count.
39        // The '+1' accounts for the individual element as a subarray.
40        if (currentCount >= k) {
41            totalCount += startIndex + 1;
42        }
43    }
44
45    // Return the total count of good subarrays.
46    return totalCount;
47}
48

Time and Space Complexity

Time Complexity

The given code has two nested loops. However, the inner loop (while-loop) only decreases cur down to a point where it is less than k, and since elements can only be added to cur when the outer loop (for-loop) runs, the inner loop can run at most as many times as the outer loop throughout the whole execution.

Because the inner loop pointer i is only incremented and never reset, each element is processed once by both the outer and inner loops together. This leads to a linear relationship with the number of elements in nums. Therefore, the overall time complexity is O(n), where n is the length of nums.

Space Complexity

The space complexity is driven by the use of the Counter object that stores counts for elements in nums. In the worst case, if all elements are unique, the counter would require space proportional to n. Hence, the space complexity is also O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄