Count subarrays with ≥k identical pairs
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### 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/
Quick Answer: This question evaluates proficiency in array algorithms, frequency-based counting and combinatorial reasoning for identifying equal-element pairs within contiguous 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**, 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
Examples
Input: ([1, 1, 1, 1], 1)
Expected Output: 6
Explanation: Value 1 is duplicated in any subarray of length >= 2; there are 6 such subarrays out of the 10 total.
Input: ([3, 1, 4, 3, 2, 2, 4], 2)
Expected Output: 4
Explanation: Four subarrays contain at least 2 distinct values that each appear twice (e.g. windows spanning the repeated 3, 2, and 4).
Hints
- 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`.
- 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`.
- 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.