Count the Number of Good Subarrays

Med

#2317Time: O(N^2), where N is the number of elements in the input array. The two nested loops iterate through all `N * (N + 1) / 2` subarrays, and the operations inside the inner loop take constant time on average.Space: O(N), where N is the number of elements in the input array. In the worst-case scenario, the frequency map for a subarray can store up to N distinct elements.

Patterns

Sliding Window

Data structures

Array Hash Table

Prompt

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 good subarray is the array nums itself.

Example 2:

Input: nums = [3,1,4,3,2,2,4], k = 2
Output: 4
Explanation: There are 4 different good subarrays:
- [3,1,4,3,2,2] that has 2 pairs.
- [3,1,4,3,2,2,4] that has 3 pairs.
- [1,4,3,2,2,4] that has 2 pairs.
- [4,3,2,2,4] that has 2 pairs.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i], k <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible contiguous subarray of nums. For each subarray, we calculate the number of pairs (i, j) where i < j and nums[i] == nums[j]. If this count is at least k, we increment our result. To avoid recomputing the pair count from scratch for every subarray, we can optimize it by fixing the start of the subarray and extending the end one element at a time, updating the pair count incrementally.

Algorithm

Initialize a counter for good subarrays, count, to 0.
Iterate through the array with a pointer i from 0 to n-1 to select the starting element of a subarray.
For each i, start a nested loop with a pointer j from i to n-1 to select the ending element of the subarray.
For each subarray nums[i...j], maintain a frequency map and a running count of pairs, currentPairs.
As the inner loop for j progresses, update the frequency of nums[j] and recalculate currentPairs.
The number of new pairs added by nums[j] is equal to its frequency in nums[i...j-1].
If currentPairs is greater than or equal to k, it means nums[i...j] is a good subarray, so increment count.
After both loops complete, return the total count.

Walkthrough

We use two nested loops to generate all subarrays. The outer loop with index i determines the start of the subarray, and the inner loop with index j determines the end. For each starting index i, we initialize a hash map to store element frequencies and a variable currentPairs to count the pairs for subarrays starting at i.

As we iterate with j from i to the end of the array, we consider the element nums[j]. The number of new pairs this element forms is equal to its current frequency in the subarray nums[i...j-1]. We add this number to currentPairs and then update the frequency of nums[j] in the map. If at any point currentPairs becomes greater than or equal to k, we've found a good subarray nums[i...j], and we increment our total count of good subarrays.

1class Solution {2    public long countGood(int[] nums, int k) {3        long goodSubarraysCount = 0;4        int n = nums.length;5        for (int i = 0; i < n; i++) {6            java.util.Map<Integer, Integer> frequencyMap = new java.util.HashMap<>();7            long currentPairs = 0;8            for (int j = i; j < n; j++) {9                int num = nums[j];10                int freq = frequencyMap.getOrDefault(num, 0);11                currentPairs += freq;12                frequencyMap.put(num, freq + 1);13                if (currentPairs >= k) {14                    goodSubarraysCount++;15                }16            }17        }18        return goodSubarraysCount;19    }20}

Complexity

Time

O(N^2), where N is the number of elements in the input array. The two nested loops iterate through all `N * (N + 1) / 2` subarrays, and the operations inside the inner loop take constant time on average.

Space

O(N), where N is the number of elements in the input array. In the worst-case scenario, the frequency map for a subarray can store up to N distinct elements.

Trade-offs

Pros

Simple and straightforward to understand and implement.
Correctly solves the problem for smaller input sizes.

Cons

The O(n^2) time complexity is too slow for the given constraints (n up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.

A much more efficient solution uses the sliding window technique. The core idea relies on a monotonic property: if a subarray is 'good' (has at least k pairs), any subarray that contains it is also 'good'. This allows us to efficiently count subarrays without checking each one individually.

We maintain a window [left, right] and expand it by moving right. Once the window becomes 'good', we know that all subarrays starting at left and ending at or after right are also good. We add the count of these subarrays to our total and then shrink the window from the left to find the next minimal good subarray.

Algorithm

Initialize count = 0, left = 0, currentPairs = 0, and an empty frequencyMap.
Iterate through the array with a right pointer from 0 to n-1.
In each iteration, add nums[right] to the current window. Update currentPairs by adding the old frequency of nums[right]. Then, increment its frequency in the map.
After expanding the window, check if currentPairs >= k.
If it is, it means the subarray nums[left...right] is good. Consequently, any subarray starting at left and ending at right or later (i.e., nums[left...right], nums[left...right+1], ..., nums[left...n-1]) is also good. There are n - right such subarrays. Add n - right to count.
Now, shrink the window from the left by incrementing left. Remove nums[left] from the window by updating its frequency and currentPairs. The number of pairs lost is the new frequency of nums[left].
Repeat the shrinking step as long as currentPairs remains >= k.
Continue iterating with the right pointer until the end of the array.
Return count.

Walkthrough

This approach uses two pointers, left and right, to define a sliding window. We also maintain a hash map for element frequencies and a long variable currentPairs for the number of pairs within the window.

The right pointer iterates from the beginning to the end of the array, expanding the window. For each element nums[right] added, we update currentPairs. The number of new pairs created is equal to the frequency of nums[right] before it was added.

Once currentPairs reaches k, we've found a good subarray nums[left...right]. Any subarray that starts at left and ends at right or a later index will also be good. The number of such subarrays is n - right. We add this to our total count.

Having counted all good subarrays starting at left, we can shrink the window by moving left one step to the right. When removing nums[left], we update the frequency map and currentPairs. We continue shrinking the window as long as it remains good, adding n - right to the count at each step. This process ensures that each good subarray is counted exactly once.

1class Solution {2    public long countGood(int[] nums, int k) {3        long count = 0;4        int left = 0;5        long currentPairs = 0;6        java.util.Map<Integer, Integer> frequencyMap = new java.util.HashMap<>();7        int n = nums.length;8 9        for (int right = 0; right < n; right++) {10            int num = nums[right];11            currentPairs += frequencyMap.getOrDefault(num, 0);12            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);13 14            while (currentPairs >= k) {15                count += (n - right);16                17                int leftNum = nums[left];18                frequencyMap.put(leftNum, frequencyMap.get(leftNum) - 1);19                currentPairs -= frequencyMap.get(leftNum);20                left++;21            }22        }23        return count;24    }25}

Complexity

Time

O(N), where N is the number of elements in the input array. Both the `left` and `right` pointers traverse the array at most once, leading to a linear time complexity.

Space

O(N) in the worst case, where N is the number of elements. The space is used by the hash map to store frequencies of elements in the current window. If the number of distinct elements is `D`, the space complexity is `O(D)`.

Trade-offs

Pros

Optimal time complexity, making it very efficient for large inputs.
Processes each element a constant number of times.

Cons

Requires careful handling of window shrinking and pair count updates.
Uses extra space for the frequency map, which could be large if there are many distinct numbers.

Solutions

Solution

1class Solution {2public3  long countGood(int[] nums, int k) {4    Map<Integer, Integer> cnt = new HashMap<>();5    long ans = 0, cur = 0;6    int i = 0;7    for (int x : nums) {8      cur += cnt.getOrDefault(x, 0);9      cnt.merge(x, 1, Integer : : sum);10      while (cur - cnt.get(nums[i]) + 1 >= k) {11        cur -= cnt.merge(nums[i++], -1, Integer : : sum);12      }13      if (cur >= k) {14        ans += i + 1;15      }16    }17    return ans;18  }19}

1class Solution {2public:3  long long countGood(vector<int> &nums, int k) {4    unordered_map<int, int> cnt;5    long long ans = 0;6    long long cur = 0;7    int i = 0;8    for (int &x : nums) {9      cur += cnt[x]++;10      while (cur - cnt[nums[i]] + 1 >= k) {11        cur -= --cnt[nums[i++]];12      }13      if (cur >= k) {14        ans += i + 1;15      }16    }17    return ans;18  }19};

1class Solution:2    def countGood(self, nums: List[int], k: int) -> int: cnt = Counter() ans = cur = 0 i = 0 for x in nums: cur += cnt[x] cnt[x] += 1 while cur - cnt[nums[i]] + 1 >= k: cnt[nums[i]] -= 1 cur -= cnt[nums[i]] i += 1 if cur >= k: ans += i + 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem