Count subarrays with at least k fruit pairs
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.
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.