Count the Number of Good Subarrays

medium sliding window two pointers hash table

Problem

Given an integer array nums and an integer k, return the number of good subarrays. A subarray is good if it contains at least k pairs of indices (i, j) with i < j and arr[i] == arr[j]. A subarray is a contiguous non-empty slice of the array.

Inputnums = [3,1,4,3,2,2,4], k = 2

Output4

The 4 good subarrays each contain at least 2 equal-value pairs, e.g. [3,1,4,3,2,2] has pairs (3,3) and (2,2).

Inputnums = [1,1,1,1,1], k = 10

Output1

Only the whole array has 10 equal pairs, so it is the single good subarray.

nums (comma-separated)

k (pairs threshold)

def count_good(nums, k):
    freq = {}
    ans = 0
    pairs = 0
    left = 0
    for right in range(len(nums)):
        pairs += freq.get(nums[right], 0)
        freq[nums[right]] = freq.get(nums[right], 0) + 1
        while pairs >= k:
            freq[nums[left]] -= 1
            pairs -= freq[nums[left]]
            left += 1
        ans += left
    return ans

function countGood(nums, k) {
  const freq = new Map();
  let ans = 0, pairs = 0, left = 0;
  for (let right = 0; right < nums.length; right++) {
    const vr = nums[right];
    pairs += freq.get(vr) || 0;
    freq.set(vr, (freq.get(vr) || 0) + 1);
    while (pairs >= k) {
      const vl = nums[left];
      freq.set(vl, freq.get(vl) - 1);
      pairs -= freq.get(vl);
      left++;
    }
    ans += left;
  }
  return ans;
}

long countGood(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    long ans = 0;
    int pairs = 0, left = 0;
    for (int right = 0; right < nums.length; right++) {
        int vr = nums[right];
        pairs += freq.getOrDefault(vr, 0);
        freq.put(vr, freq.getOrDefault(vr, 0) + 1);
        while (pairs >= k) {
            int vl = nums[left];
            freq.put(vl, freq.get(vl) - 1);
            pairs -= freq.get(vl);
            left++;
        }
        ans += left;
    }
    return ans;
}

long long countGood(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    long long ans = 0;
    int pairs = 0, left = 0;
    for (int right = 0; right < nums.size(); right++) {
        int vr = nums[right];
        pairs += freq[vr];
        freq[vr]++;
        while (pairs >= k) {
            freq[nums[left]]--;
            pairs -= freq[nums[left]];
            left++;
        }
        ans += left;
    }
    return ans;
}

Explanation

The key observation is monotonicity: if a window already has at least k equal-value pairs, then extending it to the right can only add pairs, never remove them. So for every right endpoint, the set of valid left starts forms a prefix [0, left) of the array.

We sweep right from left to right keeping a frequency map of the current window's values and a running pairs count. Adding nums[right] creates as many new pairs as there are existing copies of that value, so we do pairs += freq[nums[right]] before incrementing its count.

Then we shrink from the left as long as the window still has pairs >= k. Removing nums[left] destroys freq[nums[left]] - 1 pairs — after decrementing the count, that remaining count is exactly how many pairs we lose. We advance left to the first position where the window is no longer good.

At that moment, every start in [0, left) produces a window ending at right that is still good, so we add left to the answer. Each window-end contributes its own count of valid starts.

Because left only moves forward and right scans once, the two pointers traverse the array a total of O(n) times. The answer can exceed 32-bit range, so we accumulate it in a 64-bit integer.

Time: O(n) Space: O(n)