Given an integer array nums and an integer k, return the number of good subarrays of nums.
A subarray arr is good if there are at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j].
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1,1,1], k = 10 Output: 1 Explanation: The only good subarray is the array nums itself.
Example 2:
Input: nums = [3,1,4,3,2,2,4], k = 2 Output: 4 Explanation: There are 4 different good subarrays: - [3,1,4,3,2,2] that has 2 pairs. - [3,1,4,3,2,2,4] that has 3 pairs. - [1,4,3,2,2,4] that has 2 pairs. - [4,3,2,2,4] that has 2 pairs.
Constraints:
1 <= nums.length <= 1051 <= nums[i], k <= 109This approach employs a sliding window technique along with a hash map to efficiently count the pairs in any subarray. The idea is to expand the window by moving the right pointer and add elements to the hash map until enough pairs are formed. If the number of pairs is at least k, increment the count of valid subarrays and shrink the window from the left to try shorter subarrays. This method effectively narrows down the potential subarrays without the need to explicitly check each one.
This Python code initializes a sliding window using two pointers, 'left' and 'right'. A hash map tracks the frequency of numbers within the window. As we extend the 'right' pointer, the current number contributes to the count of pairs if it was already encountered within the window. We then check if the number of pairs meets or exceeds k, and try to increment the 'good_subarrays' by attempting to shrink the window from the left.
Java
C#
Time Complexity: O(n), where n is the length of the array, since each element is processed at most twice (once when 'right' pointer expands and once when 'left' pointer contracts).
Space Complexity: O(m), where m is the number of unique elements in the array due to the hash map.
Another efficient approach involves using prefix sums and a map to account for pairs of elements. By prefixing the occurrence of numbers and counting pairs, you can dynamically build the count of valid pairs as you iterate through the array. This method relies on recognizing repeat occurrences as part of its summation process.
This C++ solution uses an unordered_map to track the frequency of elements appearing in the subarray defined by the sliding window margin from left to right. With each iteration of the right index, the count of pairs is updated if the same element appears before this position. When the counter for pairs meets or beats k, the current and succeeding elements form valid subarrays. The solution is efficient because it shifts focus from checks to counters.
JavaScript
Time Complexity: O(n), where n is the number of elements in nums. The sliding window advances and retracts strategically limiting unnecessary iterations.
Space Complexity: O(m), requiring a hashmap to only remember prevalent elements at any time during the loop's execution.
| Approach | Complexity |
|---|---|
| Use Sliding Window and Hash Map | Time Complexity: O(n), where n is the length of the array, since each element is processed at most twice (once when 'right' pointer expands and once when 'left' pointer contracts). Space Complexity: O(m), where m is the number of unique elements in the array due to the hash map. |
| Use Prefix Sum and Pair Counting | Time Complexity: O(n), where n is the number of elements in nums. The sliding window advances and retracts strategically limiting unnecessary iterations. Space Complexity: O(m), requiring a hashmap to only remember prevalent elements at any time during the loop's execution. |
L10. Count number of Nice subarrays | 2 Pointers and Sliding Window Playlist • take U forward • 98,734 views views
Watch 9 more video solutions →Practice Count the Number of Good Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor