Count the Number of Good Subarrays

Count the Number of Good Subarrays

What is this problem about?

In the Count the Number of Good Subarrays coding problem, you are given an array nums and an integer k. A subarray is considered "good" if it contains at least k pairs of indices $(i, j)$ such that $i < j$ and $nums[i] == nums[j]$.

You need to find the total number of such good subarrays.

Why is this asked in interviews?

This is a classic sliding window interview pattern question asked by Uber and Meta. It tests whether a candidate can maintain a complex running state (the count of pairs) as the window moves. It also requires the insight that if a subarray is "good," then any larger subarray containing it is also "good," which is the fundamental prerequisite for an efficient two-pointer solution.

Algorithmic pattern used

The problem uses Sliding Window and a Frequency Map.

1. Maintain a left and right pointer and a current_pairs count.
2. Expand right. When adding nums[right], the number of new pairs formed is the current count of nums[right] in the window.
3. While current_pairs >= k:
   • Every subarray starting at left and ending at any index from right to the end of the array is "good."
   • Increment result by n - right.
   • Shrink left. When removing nums[left], decrement current_pairs by the count of nums[left] remaining in the window.

Example explanation

nums = [1, 1, 1, 1], k = 2

1. right = 0: "1". Pairs = 0.
2. right = 1: "1, 1". Pairs = 1.
3. right = 2: "1, 1, 1". Pairs = 3 (which is $\ge k=2$).
   • Count += $4 - 2 = 2$ (Subarrays starting at 0: [1,1,1] and [1,1,1,1]).
   • Shrink left: remove nums[0]. Pairs = $3 - 2 = 1$. (Now < k).
4. right = 3: "1, 1, 1". (Window is indices 1 to 3). Pairs = 3 ($\ge 2$).
   • Count += $4 - 3 = 1$ (Subarray [1,1,1] at the end).
   • Shrink left: remove nums[1]. Pairs = 1. Total = 3.

Common mistakes candidates make

• Miscalculating pairs: Not realizing that adding the $X$-th instance of a number adds $X-1$ new pairs.
• Incorrect counting logic: Adding only 1 to the result when a window becomes good, rather than adding the number of possible extensions to the right.
• Hash Table updates: Failing to update the frequency map before or after the pair count logic correctly.

Interview preparation tip

Practice the logic of "At least $K$." For subarrays, if a condition is satisfied for nums[i..j], it is usually satisfied for nums[i..j+1]. This allows you to count all future right-endpoints in one step.