Count subarrays with ≥k identical pairs

Question

LeetCode 2537. Count the Number of Good Subarrays – Given an integer array nums and an integer k, return the number of contiguous subarrays in which there are at least k pairs of equal elements (each value contributes at most one pair, regardless of multiplicity).

leetcode.com/problems/count-the-number-of-good-subarrays/description/

Count subarrays with ≥k duplicated values

Given an integer array nums and an integer k, return the number of contiguous subarrays in which there are at least k pairs of equal elements, where each value contributes at most one pair regardless of how many times it appears.

In other words, a subarray is good if the number of distinct values that appear two or more times inside it is at least k. Each such value counts once toward the pair total no matter its multiplicity.

This is the “at-most-one-pair-per-value” variant of LeetCode 2537 (Count the Number of Good Subarrays).

Example 1

nums = [1, 1, 2, 2, 3, 3], k = 3
Output: 1

Only the full array [1,1,2,2,3,3] contains 3 distinct duplicated values (1, 2, and 3), so exactly one subarray qualifies.

Example 2

nums = [3, 1, 4, 3, 2, 2, 4], k = 2
Output: 4

Four subarrays contain at least 2 distinct values that each appear twice.

Example 3

nums = [1, 1, 1, 1], k = 1
Output: 6

Value 1 is duplicated, so every subarray of length ≥ 2 is good — there are 6 of them.

Constraints

• 1 <= nums.length <= 10^5 (the array may also be empty in edge tests)
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^9
• The answer can exceed 32-bit range; use a 64-bit integer accumulator

Hints

1. A subarray is 'good' if the count of distinct values appearing >= 2 times is at least k. Track that count as a running quantity called pairs.
2. Use a sliding window: when a value's frequency goes from 1 to 2, increment pairs; when it drops from 2 to 1 as the left edge shrinks, decrement pairs.
3. Monotonicity: if a window [left, right] already has pairs >= k, then EVERY window [left', right] with left' <= left also qualifies. So count n - right subarrays and advance left while the window stays good, summing as you go.