2537. Count the Number of Good Subarrays LeetCode Solution
In this guide, you will get 2537. Count the Number of Good Subarrays LeetCode Solution with the best time and space complexity. The solution to Count the Number of Good Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count the Number of Good Subarrays
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 <= 105
1 <= nums[i], k <= 109
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2537. Count the Number of Good Subarrays LeetCode Solution in C++
class Solution {
public:
long long countGood(vector<int>& nums, int k) {
long ans = 0;
int pairs = 0;
unordered_map<int, int> count;
for (int l = 0, r = 0; r < nums.size(); ++r) {
// Since there're count[r] nums[r]s, including nums[r] to the window will
// increase the number of good subarrays by count[r].
pairs += count[nums[r]]++;
while (pairs >= k)
pairs -= --count[nums[l++]];
// nums[0..r], nums[1..r], ..., nums[l - 1..r] are good subarrays, so add
// l to `ans`.
ans += l;
}
return ans;
}
}; /* code provided by PROGIEZ */
2537. Count the Number of Good Subarrays LeetCode Solution in Java
N/A // code provided by PROGIEZ
2537. Count the Number of Good Subarrays LeetCode Solution in Python
