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.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Counting, Sliding Window
- 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 <= 500001 <= nums[i] <= 10000000001 <= k <= 1000000000
Hints for Count the Number of Good Subarrays
Hint 1
Widening a subarray never removes a pair, so 'good' is monotone in the window's left edge.
Hint 2
When a value joins the window, it forms one new pair with each existing copy — so add its current count.
Hint 3
Once
[l, r]is good, every start beforelis good too; countlof 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
- For each
r, addcnt[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 advancel. - Add
lto the answer: every start in0 … l-1gives a good subarray ending atr.
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^9at the upper limit — anint, 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 resJava
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