Count the Number of Good Subarrays — Medium Problem & Solution

A subarray is good when it contains at least k pairs of indices (i, j) with i < j and arr[i] == arr[j]. Return the number of good subarrays of nums.

Difficulty: Medium
Topics: Arrays, Hash Table, Sliding Window, Counting
Asked at: Amazon, Google, PhonePe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A subarray is good when it contains at least k pairs of indices (i, j) with i < j and arr[i] == arr[j].

Return the number of good subarrays of nums.

Example 1

Input: nums = [1,1,1,1,1], k = 10
Output: 1
Explanation: Only the whole array reaches ten equal pairs.

Example 2

Input: nums = [3,1,4,3,2,2,4], k = 2
Output: 4
Explanation: The subarrays [3,1,4,3,2,2], [3,1,4,3,2,2,4], [1,4,3,2,2,4] and [4,3,2,2,4].

Example 3

Input: nums = [7,7], k = 1
Output: 1

Constraints

1 <= nums.length <= 50000
1 <= nums[i] <= 1000000000
1 <= k <= 1000000000

How to solve Count the Number of Good Subarrays

Maintain the pair count of the window incrementally, and shrink from the left as soon as the window is good. The number of good subarrays ending at r is then exactly the number of starts strictly left of the current l.

Approach

For each r, add cnt[nums[r]] to the pair total before incrementing the tally — the new element pairs with each existing copy.
While the pair total reaches k, decrement the leftmost element's tally, subtract the new tally from the pair total, and advance l.
Add l to the answer: every start in 0 … l-1 gives a good subarray ending at r.

Why it works

Removing an element destroys one pair per remaining copy, which is exactly the tally after decrementing — so the running count stays exact. Because adding elements never lowers the pair count, the minimal good window for each r has a well-defined left boundary and l never moves backwards.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Incrementing the tally before adding to the pair count counts the element paired with itself.
Subtracting the tally before decrementing it in the shrink step is off by one.
The answer reaches about 1.25 · 10^9 at the upper limit — an int, but only just.

Reference solution

Python

from typing import List

def countGood(nums: List[int], k: int) -> int:
    cnt = {}
    l = 0
    pairs = 0
    res = 0
    for r, v in enumerate(nums):
        pairs += cnt.get(v, 0)
        cnt[v] = cnt.get(v, 0) + 1
        while pairs >= k:
            cnt[nums[l]] -= 1
            pairs -= cnt[nums[l]]
            l += 1
        res += l
    return res

JavaScript

var countGood = function(nums, k) {
    var cnt = {};
    var l = 0, pairs = 0, res = 0;
    for (var r = 0; r < nums.length; r++) {
        var v = nums[r];
        pairs += cnt[v] || 0;
        cnt[v] = (cnt[v] || 0) + 1;
        while (pairs >= k) {
            cnt[nums[l]]--;
            pairs -= cnt[nums[l]];
            l++;
        }
        res += l;
    }
    return res;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue