How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

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

Input: ([1, 2, 3, 4], 1)

Expected Output: 0

Explanation: All elements are distinct, so no subarray has even one duplicated value.

Input: ([5, 5, 5], 1)

Expected Output: 3

Explanation: The subarrays [5,5] (twice) and [5,5,5] each contain the duplicated value 5 -> 3 good subarrays.

Input: ([], 1)

Expected Output: 0

Explanation: Empty array has no subarrays.

Input: ([7], 1)

Expected Output: 0

Explanation: A single element can never form a duplicate, so 0 good subarrays.

Input: ([2, 2, 2, 2], 1)

Expected Output: 6

Explanation: Every subarray of length >= 2 contains the duplicated value 2; there are 6 of them.

Input: ([1, 1, 2, 2, 3, 3], 3)

Expected Output: 1

Explanation: Only the full array has 3 distinct values (1, 2, 3) that each appear twice.

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.

Quick Overview

This question evaluates proficiency in array algorithms, frequency-based counting and combinatorial reasoning for identifying equal-element pairs within contiguous subarrays.