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 at least k fruit pairs

Quick Overview

This question evaluates algorithmic problem-solving focused on frequency-based counting and efficient enumeration of subarrays, testing competence in designing subquadratic solutions and selecting appropriate data representations within the Coding & Algorithms domain.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Given an integer array nums where each value denotes a fruit type, and an integer k: For any subarray, define a 'pair' for fruit value v if its frequency in the subarray is at least 2; each fruit contributes at most one pair regardless of appearing more than twice. Return the number of subarrays whose number of such pairs is at least k. Example: nums = [0, 1, 0, 1, 0], k = 2 → 3 (valid subarrays are [0, 1, 0, 1], [1, 0, 1, 0], and [0, 1, 0, 1, 0]). Design an algorithm better than O(n^ 2), explain your approach (e.g., sliding window or two pointers), and analyze complexity.

Quick Answer: This question evaluates algorithmic problem-solving focused on frequency-based counting and efficient enumeration of subarrays, testing competence in designing subquadratic solutions and selecting appropriate data representations within the Coding & Algorithms domain.

Given an integer array `nums` where each value denotes a fruit type, and an integer `k`. For any subarray, a fruit value `v` contributes a 'pair' if its frequency within that subarray is at least 2; each distinct fruit contributes at most one pair regardless of how many times it appears (3 or more occurrences still count as a single pair). Return the number of subarrays whose total number of such pairs is at least `k`. Example: `nums = [0, 1, 0, 1, 0], k = 2` returns `3`. The qualifying subarrays are `[0, 1, 0, 1]`, `[1, 0, 1, 0]`, and `[0, 1, 0, 1, 0]` — each contains fruit 0 at least twice and fruit 1 at least twice (2 pairs). Design an algorithm better than O(n^2). Approach: The pair count of a window is non-decreasing as the window's right endpoint moves right and non-increasing as the left endpoint moves right (extending a window can only add occurrences, never remove them). So for each right endpoint `r`, the set of left endpoints `l` for which `[l, r]` has at least `k` pairs is a prefix `l in [0, left-1]`. Maintain a sliding window: expand `r`, update a frequency map and a running pair count (incrementing when a count reaches exactly 2), then advance `left` as far as possible while the window `[left, r]` still has at least `k` pairs. After shrinking, exactly `left` subarrays ending at `r` (those starting at indices `0..left-1`) satisfy the condition, so add `left` to the answer.

Constraints

0 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
1 <= k <= nums.length (k may exceed the maximum achievable pairs, in which case the answer is 0)

Examples

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

Expected Output: 3

Explanation: Qualifying subarrays: [0,1,0,1], [1,0,1,0], [0,1,0,1,0] — each has fruit 0 twice and fruit 1 twice (2 pairs).

Input: ([1, 1], 1)

Expected Output: 1

Explanation: Only [1,1] has fruit 1 appearing twice, giving 1 pair >= k.

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

Expected Output: 0

Explanation: All fruits are distinct, so no subarray ever forms a pair.

Input: ([], 1)

Expected Output: 0

Explanation: Empty array has no subarrays.

Input: ([5], 1)

Expected Output: 0

Explanation: A single element can never reach a frequency of 2.

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

Expected Output: 3

Explanation: Subarrays [2,2] (idx 0-1), [2,2] (idx 1-2), and [2,2,2] each have fruit 2 with count >= 2, contributing one pair each.

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

Expected Output: 1

Explanation: Only the full array [0,0,1,1] has two distinct fruits each appearing twice, giving 2 pairs.

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

Expected Output: 0

Explanation: Only one fruit type exists, so the pair count can never reach 2 regardless of frequency.

Hints

The number of pairs in a window never decreases when you extend the window to the right, and never increases when you advance the left endpoint. This monotonicity is what makes a sliding window correct.
For a fixed right endpoint r, the valid left endpoints form a prefix [0, left-1]. Find the smallest window [left, r] that still has at least k pairs; then every start index 0..left-1 yields a qualifying subarray.
Track 'pairs' incrementally: increment it only when a fruit's count rises to exactly 2 (extra occurrences add nothing), and decrement only when a count drops back to exactly 1 during shrinking.
Add `left` to the running answer at each step — that is exactly how many qualifying subarrays end at index r.

Quick Overview