FastPrepCount the Number of Good Subarrays
Problem · Array

Count the Number of Good Subarrays

Learn this problem
● MediumUber logoUberFULLTIMEOA
See Uber hiring insights

Problem statement

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A subarray arr is good if there are at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j].

A subarray is a contiguous non-empty sequence of elements within an array.

Function

countGoodSubarrays(nums: int[], k: int) → int

Examples

Example 1

nums = [1,1,1,1,1]k = 10return = 1

The only good subarray is the array nums itself.

Example 2

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

There are 4 different good subarrays:

  • [3,1,4,3,2,2] that has 2 pairs.
  • [3,1,4,3,2,2,4] that has 3 pairs.
  • [1,4,3,2,2,4] that has 2 pairs.
  • [4,3,2,2,4] that has 2 pairs.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i], k <= 10^9

More Uber problems

drafts saved locally
public int countGoodSubarrays(int[] nums, int k) {
  // write your code here (You may want to refer to LC 2537 :)
}
nums[1,1,1,1,1]
k10
expected1
checking account