Problem

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

Examples

Example 1:

1
2
3

Input: nums = [1,1,1,1,1], k = 10
Output: 1
Explanation: The only good subarray is the array nums itself.

Example 2:

1
2
3
4
5
6
7

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 <= 10^5
  • 1 <= nums[i], k <= 10^9

Solution

Method 1 - Sliding window technique

To solve the problem efficiently, we can use the sliding window approach combined with a hash map to track the frequency of elements in the current subarray window. The idea involves expanding the window to form valid subarrays (those with at least k good pairs) and contracting the window once the condition is violated.

Here is the approach:

  1. Use two pointers (start and end) to maintain the sliding window.
  2. Maintain a frequency count of elements in the current window using a hash map.
  3. For each new element added to the window (end pointer increment), calculate the number of new good pairs added based on its frequency and update the total count.
  4. Keep shrinking the window (increment the start pointer) when the count of good pairs in the window meets or exceeds k. During shrinking, adjust frequencies and good pairs accordingly.
  5. Accumulate the number of good subarrays across all valid windows.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {

    public long countGood(int[] nums, int k) {
        long ans = 0; // Use long as the return type
        int start = 0;
        long pairs = 0; // Track the number of pairs
        Map<Integer, Integer> freq = new HashMap<>(); // Frequency map

        for (int end = 0; end < nums.length; end++) {
            int curr = nums[end];
            freq.put(curr, freq.getOrDefault(curr, 0) + 1);

            // Calculate pairs formed by current element
            pairs += freq.get(curr) - 1;

            // Shrink the window while condition is met
            while (pairs >= k) {
                ans += nums.length - end; // Count all subarrays ending at 'end'
                int left = nums[start];
                pairs -= freq.get(left) - 1; // Remove pairs formed by 'left'
                freq.put(left, freq.get(left) - 1);
                start++;
            }
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        ans = 0
        start = 0
        pairs = 0
        freq: dict[int, int] = {}
        
        for end, curr in enumerate(nums):
            freq[curr] = freq.get(curr, 0) + 1
            
            # Calculate pairs formed by current element
            pairs += freq[curr] - 1
            
            # Shrink window
            while pairs >= k:
                ans += len(nums) - end  # Count good subarrays ending at `end`
                left = nums[start]
                pairs -= freq[left] - 1  # Remove pairs formed by `left`
                freq[left] -= 1
                start += 1
        
        return ans

Complexity

  • ⏰ Time complexity: O(n). The start and end pointers both traverse the nums array once, making the time complexity O(n).
  • Operations on the hash map (freq) such as updating and accessing elements are O(1) due to average-case behaviour.
  • 🧺 Space complexity: O(u). - The hash map (freq) stores counts of unique elements in the array. In the worst case, all elements are unique, making it O(u), where u is the number of unique elements.