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.

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

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.