Count the Number of Good Subarrays

Medium
796.

Count the Number of Good Subarrays

Count the Number of Good Subarrays is a medium coding problem on arrays, hash table and counting, asked in Amazon, Google and PhonePe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countGood = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count the Number of Good Subarrays — Problem & Solution

Count the Number of Good Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count the Number of Good Subarrays is a medium coding problem on arrays, hash table and counting, asked in Amazon, Google and PhonePe interviews.

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

Hints for Count the Number of Good Subarrays

  1. Hint 1

    Widening a subarray never removes a pair, so 'good' is monotone in the window's left edge.

  2. Hint 2

    When a value joins the window, it forms one new pair with each existing copy — so add its current count.

  3. Hint 3

    Once [l, r] is good, every start before l is good too; count l of them for this right end.

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

  1. For each r, add cnt[nums[r]] to the pair total before incrementing the tally — the new element pairs with each existing copy.
  2. While the pair total reaches k, decrement the leftmost element's tally, subtract the new tally from the pair total, and advance l.
  3. 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

Java

public static int countGood(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    int l = 0;
    long pairs = 0, res = 0;
    for (int r = 0; r < nums.length; r++) {
        int v = nums[r];
        int have = cnt.getOrDefault(v, 0);
        pairs += have;
        cnt.put(v, have + 1);
        while (pairs >= k) {
            int u = nums[l];
            int left = cnt.get(u) - 1;
            cnt.put(u, left);
            pairs -= left;
            l++;
        }
        res += l;
    }
    return (int) res;
}

C++

int countGood(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    int l = 0;
    long long pairs = 0, res = 0;
    for (int r = 0; r < (int) nums.size(); r++) {
        int v = nums[r];
        pairs += cnt[v];
        cnt[v]++;
        while (pairs >= k) {
            cnt[nums[l]]--;
            pairs -= cnt[nums[l]];
            l++;
        }
        res += l;
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets