I started with two pointers — left and right — and used a sliding window approach. As I moved the right pointer forward, I kept track of how many pairs I could form with each number using a frequency map. Every time I added a number to the window, I updated the pair count.
When the number of pairs in the current window reached or exceeded k, I knew that all subarrays starting at left and ending at or after right would be good. So I counted those subarrays as len(nums) - right.
To optimize further, I then shrank the window from the left while still maintaining the condition of having at least k pairs. I continued this process until I had counted all possible good subarrays.
class Solution:
def countGood(self, nums: List[int], k: int) -> int:
n = len(nums)
count = defaultdict(int)
pairs = 0
left = 0
result = 0
for right in range(n):
val = nums[right]
pairs += count[val]
count[val] += 1
while pairs >= k:
result += n - right
count[nums[left]] -= 1
pairs -= count[nums[left]]
left += 1
return result- Time: O(n)
- Space: O(n)
