2537

2537. Count the Number of Good Subarrays (Medium)

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A subarray arr is good if it 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 <= 105
• 1 <= nums[i], k <= 109

Related Topics:
Array, Hash Table, Sliding Window

Similar Questions:

• Count Number of Homogenous Substrings (Medium)
• Maximum Sum of Distinct Subarrays With Length K (Medium)

Solution 1. Find Minimum Sliding Window

// OJ: https://leetcode.com/problems/count-the-number-of-good-subarrays
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    long long countGood(vector<int>& A, int k) {
        unordered_map<int, int> cnt;
        long long N = A.size(), ans = 0, sum = 0, valid = 0;
        for (int i = 0, j = 0; j < N; ++j) {
            sum += cnt[A[j]]++;
            valid = valid || sum >= k;
            while (sum >= k) sum -= --cnt[A[i++]]; // shift the left edge until the window becomes invalid
            if (valid) ans += i; // once the window has ever became valid, 0~(i-1) can be used as the starting point of a valid subarray
        }
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/count-the-number-of-good-subarrays
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    long long countGood(vector<int>& A, int k) {
        unordered_map<int, int> cnt;
        long long N = A.size(), ans = 0, sum = 0;
        for (int i = 0, j = 0; i < N; ++i) {
            while (j < N && sum < k) {
                sum += cnt[A[j++]]++;
            }
            if (sum < k) break;
            ans += N - j + 1;
            sum -= --cnt[A[i]];
        }
        return ans;
    }
};