FastPrepCount Subarrays with at Least K Distinct Values

Count Subarrays with at Least K Distinct Values

Visa logoVisa● MediumINTERNOA
Learn

Problem statement

You are given an integer array nums and an integer k.

Return the number of contiguous subarrays that contain at least k distinct values. Repeated occurrences of the same value count only once toward a subarray's distinct-value total.

Function

countSubarraysWithAtLeastKDistinct(nums: int[], k: int) → long

Examples

Example 1

nums = [1,2,1]k = 2return = 3

The valid subarrays are [1,2], [2,1], and [1,2,1].

Example 2

nums = [1,1,1]k = 2return = 0

Every subarray contains only the value 1, so none has two distinct values.

Constraints

  • 1 <= nums.length <= 2 * 105
  • -109 <= nums[i] <= 109
  • 1 <= k <= nums.length
  • The answer fits in a signed 64-bit integer.

More Visa problems

See Visa hiring insights
public long countSubarraysWithAtLeastKDistinct(int[] nums, int k) {
    // Write your code here.
}
nums[1,2,1]
k2
expected3
Checking account…