FastPrepCount Subarrays with at Least K Equal-Fruit Pairs

Count Subarrays with at Least K Equal-Fruit Pairs

TikTok logoTikTok● MediumNEW GRADOA
Learn

Problem statement

You are given an integer array fruits and an integer k. A pair consists of two equal fruit values, and each array position may belong to at most one pair.

For a subarray, a fruit value that appears count times contributes floor(count / 2) disjoint pairs. Return the number of contiguous subarrays whose total number of pairs across all fruit values is at least k.

Function

countFruitPairSubarrays(fruits: int[], k: int) → long

Examples

Example 1

fruits = [1,1,2,2]k = 2return = 1

Only the complete subarray contains one pair of 1s and one pair of 2s.

Example 2

fruits = [1,1,1,1]k = 1return = 6

Every subarray of length at least two contains a pair. There are 3 + 2 + 1 = 6 such subarrays.

Constraints

  • 2 <= fruits.length <= 10^5
  • 1 <= fruits[i] <= 10^9
  • 1 <= k <= floor(fruits.length / 2)

More TikTok problems

See TikTok hiring insights
public long countFruitPairSubarrays(int[] fruits, int k) {
  // write your code here
}
fruits[1,1,2,2]
k2
expected1
Checking account…