Log inSign up
mediumLeetCodeNot Started

Count Number of Good Subarrays

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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.

Example 1:

Input: nums = [1,1,1,1,1], k = 10
Output: 1
Explanation: The only subarray with at least 10 pairs of identical values is the entire array itself, which has 5 * 4 / 2 = 10 pairs.

Example 2:

Input: nums = [3,1,4,3,2,2,4], k = 2
Output: 4
Explanation: There are 4 good 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 = [1,2,3], k = 1
Output: 0
Explanation: No identical pairs exist in any subarray, so 0 good subarrays.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Sliding Window & Two Pointers technique
  • Hash Map frequency tracking
  • Combinatorics formula for pairs — C(n, 2) = n(n-1)/2

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master incremental frequency-to-pair dynamic state updates (O(1) per addition/removal).
  • Understand why satisfying "at least K" allows adding (n - right) valid subarrays in one step.
  • Implement the two-pointer sliding window pattern with hash map frequency tracking.
  • Handle 64-bit integer overflow when accumulating large subarray counts.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Counting subarrays satisfying a monotonic condition ("at least K pairs").
  • Incremental state update (pairs formed by identical values).
  • Expanding right pointer and shrinking left pointer.

Algorithmic Decision Tree:

  • If checking all subarrays independently -> O(N2) or O(N3) TLE.
  • If condition is monotonic ("at least K") -> Sliding Window (Two Pointers) with running count in O(N).
  • If pairs can be large -> Use 64-bit integer (long long in C++, long in Java).

Connected Patterns:

Subarray Product Less Than KCount Number of Nice SubarraysSubarrays with K Different Integers

1. Brute Force (Nested Loop Subarray Inspection)

Intuition

Fix starting index i. Expand right index j, keeping a hash map of frequencies for the current subarray. When a number is added, add its prior count to pairs. If pairs >= k, increment total.

Algorithm

  1. Step 1: Initialize ans = 0.
  2. Step 2: For each i from 0 to n - 1:
  3. - Initialize frequency map freq and pairs = 0.
  4. - For each j from i to n - 1:
  5. - Add freq[nums[j]] to pairs.
  6. - Increment freq[nums[j]].
  7. - If pairs >= k, increment ans.
  8. Step 3: Return ans.

Brute Force (Nested Loop Subarray Inspection) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 3, 1, 2, 4, 3]
Current operationSTEP 1 OF 6
Phase 1 — Window Initialization: Both left and right pointers anchor at index 0
Visual state
Values and pointers at this exact step
pointers
S
2
3
1
2
4
3
0
↑ L↑ R
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Window Value
2
Window Length
1
Best Metric
Evaluating...
Check / comparison
Current element arr[0]=2. Window span [0..0].
Decision / next transition
Initialize window state and evaluate target constraint.
Why this step matters

Phase 1 — Window Initialization: Both left and right pointers anchor at index 0. Initial window length is 1 with sum/metric=2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5class Solution {
6public:
7 long long countGood(std::vector<int>& nums, int k) {
8 int n = nums.size();
9 long long ans = 0;
10
11 for (int i = 0; i < n; i++) {
12 std::unordered_map<int, int> freq;
13 long long pairs = 0;
14 for (int j = i; j < n; j++) {
15 pairs += freq[nums[j]];
16 freq[nums[j]]++;
17 if (pairs >= k) {
18 ans++;
19 }
20 }
21 }
22 return ans;
23 }
24};
25
26int main() {
27 Solution sol;
28 std::vector<int> nums = {3, 1, 4, 3, 2, 2, 4};
29 std::cout << "Good Subarrays: " << sol.countGood(nums, 2) << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force (Nested Loop Subarray Inspection).
  • Space complexity: O(1) — Space complexity for Brute Force (Nested Loop Subarray Inspection).

Why Brute Force Doesn't Scale:

For N = 100,000, N2 = 1010 operations, causing TLE. Two pointers ensures each element is added and removed from the frequency map at most once, reducing operations from 1010 to 200,000.

With N = 100,000: Brute force takes ~10 billion operations (> 10 seconds); Sliding Window finishes in ~200,000 operations (< 15 ms).

2. Better (Early Break on First Valid Index)

Intuition

Since appending more elements to a subarray with >= k pairs will only add more pairs, once index j qualifies, all subarrays from j to n-1 also qualify. We add (n - j) and break immediately.

Algorithm

  1. Step 1: Initialize ans = 0.
  2. Step 2: For each i from 0 to n - 1:
  3. - Initialize frequency map freq and pairs = 0.
  4. - For each j from i to n - 1:
  5. - pairs += freq[nums[j]]++.
  6. - If pairs >= k: ans += (n - j) and break.
  7. Step 3: Return ans.

Better (Early Break on First Valid Index) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 3, 1, 2, 4, 3]
Current operationSTEP 1 OF 6
Phase 1 — Window Initialization: Both left and right pointers anchor at index 0
Visual state
Values and pointers at this exact step
pointers
S
2
3
1
2
4
3
0
↑ L↑ R
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Window Value
2
Window Length
1
Best Metric
Evaluating...
Check / comparison
Current element arr[0]=2. Window span [0..0].
Decision / next transition
Initialize window state and evaluate target constraint.
Why this step matters

Phase 1 — Window Initialization: Both left and right pointers anchor at index 0. Initial window length is 1 with sum/metric=2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5class Solution {
6public:
7 long long countGood(std::vector<int>& nums, int k) {
8 int n = nums.size();
9 long long ans = 0;
10
11 for (int i = 0; i < n; i++) {
12 std::unordered_map<int, int> freq;
13 long long pairs = 0;
14 for (int j = i; j < n; j++) {
15 pairs += freq[nums[j]];
16 freq[nums[j]]++;
17 if (pairs >= k) {
18 ans += (n - j);
19 break;
20 }
21 }
22 }
23 return ans;
24 }
25};
26
27int main() {
28 Solution sol;
29 std::vector<int> nums = {3, 1, 4, 3, 2, 2, 4};
30 std::cout << "Better Good Subarrays: " << sol.countGood(nums, 2) << std::endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better (Early Break on First Valid Index).
  • Space complexity: O(N) — Space complexity for Better (Early Break on First Valid Index).

3. Optimal (Two-Pointer Sliding Window)

Intuition

1. Initialize freq map, currentPairs = 0, left = 0, ans = 0. 2. Iterate right from 0 to n - 1: - currentPairs += freq[nums[right]] - freq[nums[right]]++ - While currentPairs >= k: - All subarrays starting at left and ending at right...n-1 are good! - ans += (n - right) - freq[nums[left]]-- - currentPairs -= freq[nums[left]] - left++ 3. Return ans.

Algorithm

  1. Step 1: Initialize ans = 0, currentPairs = 0, left = 0, and frequency hash map freq.
  2. Step 2: Loop right from 0 to nums.length - 1:
  3. - Add freq[nums[right]] to currentPairs.
  4. - Increment freq[nums[right]].
  5. - While currentPairs >= k:
  6. - Add (n - right) to ans.
  7. - Decrement freq[nums[left]].
  8. - Subtract freq[nums[left]] from currentPairs.
  9. - Increment left.
  10. Step 3: Return ans.

Sliding Window on [3, 1, 4, 3, 2, 2, 4], k = 2

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [nums = [3, 1, 4, 3, 2, 2, 4], k = 2]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1
Visual state
Values and pointers at this exact step
array
S
nums = [3, 1, 4, 3, 2, 2, 4], k = 2
0
↑ i (Step 1)
Variables at this step
Current Phase
1
Inspected Value
nums = [3, 1, 4, 3, 2, 2, 4], k = 2
Condition Met
false
Running Status
Evaluating
Why this step matters

Phase 1 — Step 1: Step 1

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5class Solution {
6public:
7 long long countGood(std::vector<int>& nums, int k) {
8 int n = nums.size();
9 std::unordered_map<int, int> freq;
10 long long currentPairs = 0;
11 long long ans = 0;
12 int left = 0;
13
14 for (int right = 0; right < n; right++) {
15 currentPairs += freq[nums[right]];
16 freq[nums[right]]++;
17
18 while (currentPairs >= k) {
19 ans += (n - right);
20 freq[nums[left]]--;
21 currentPairs -= freq[nums[left]];
22 left++;
23 }
24 }
25 return ans;
26 }
27};
28
29int main() {
30 Solution sol;
31 std::vector<int> nums = {3, 1, 4, 3, 2, 2, 4};
32 std::cout << "Optimal Good Subarrays: " << sol.countGood(nums, 2) << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal (Two-Pointer Sliding Window).
  • Space complexity: O(1) — Space complexity for Optimal (Two-Pointer Sliding Window).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Evaluate Every Subarray)O(N^2)O(N)For every starting index i, expand j and maintain frequency map to count pairs. If pairs >= k, increment answer.Nested iteration over all O(N2) subarrays.
2.Better (Binary Search on Prefix Endpoints)O(N log N)O(N)For each left index, binary search the minimum right index where pairs >= k.Binary search overhead over dynamic frequency updates.
3.Optimal (Sliding Window with Dynamic Pair Tracking)OptimalO(N)O(N)Maintain window [left, right] and frequency map. For each valid left, add (n - right) and shrink left.Single pass scan bound.

Common Pitfalls & Crucial Edge Cases

Using 32-bit integer for `ans`

An array of size 105 with identical elements has up to N(N+1)/2 ≈ 5 × 109 good subarrays, overflowing 32-bit signed integer limits. Always use long long in C++ and long in Java.

Incorrect pair subtraction on left shrink

When decrementing freq[nums[left]] from count to count - 1, the number of destroyed pairs is count - 1 (not count).

Adding 1 instead of `(n - right)`

Once nums[left...right] has >= k pairs, every extension to nums[left...right'] for right <= right' < n is also valid.

Crucial Edge Cases to Validate:

  • No duplicate elements (nums = [1, 2, 3, 4, 5], k = 1): currentPairs stays 0, returns 0.
  • All elements identical (nums = [1, 1, 1, 1, 1], k = 10): Window must encompass the entire array of 5 elements (C(5,2)=10), yielding exactly 1.
  • Large k impossible to satisfy (k = 10^9): Loop runs in O(N), returns 0 safely without integer overflow.
  • Single element array (nums = [42], k = 1): Cannot form pairs, returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the return type size immediately: since answer can be up to N(N+1)/2 ≈ 5 × 109, use 64-bit integer (long long).
  2. Explain the incremental pair update formula: currentPairs += freq[x] on addition, and currentPairs -= (freq[x] - 1) on deletion.
  3. Emphasize how monotonicity allows the ans += (n - right) batch counting trick.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When a subarray nums[left...right] reaches at least k pairs, why can we add (n - right) to the answer in a single step?

2.If a number already appeared 4 times in the window, how many new pairs are created when it appears a 5th time?

3.What is the time and space complexity of the optimal Two-Pointer Sliding Window approach?

Back to DSA Sheet