Leetcode 2537: Count the Number of Good Subarrays
Given an integer array
nums and an integer k, return the number of “good” subarrays. A subarray is good if it contains at least k pairs of indices (i, j) such that i < j and nums[i] == nums[j]. A subarray is a contiguous non-empty sequence of elements within the array.Problem
Approach
Steps
Complexity
Input: The input consists of an integer array `nums` and an integer `k`. The task is to count how many subarrays satisfy the good subarray condition.
Example: nums = [5, 2, 7, 5, 3, 3, 7], k = 2
Constraints:
• 1 <= nums.length <= 10^5
• 1 <= nums[i], k <= 10^9
Output: The output should be the number of good subarrays that meet the condition of containing at least `k` pairs of equal elements.
Example: 4
Constraints:
• The result should be an integer indicating the number of good subarrays.
Goal: Efficiently count the number of good subarrays by checking the number of valid pairs for each subarray.
Steps:
• Iterate through the array and for each subarray, count how many pairs of equal elements exist.
• Use a map to track the frequency of each element, then calculate how many pairs can be formed from these frequencies.
• Count the number of subarrays that have at least `k` pairs.
Goal: The solution must efficiently handle arrays of size up to `10^5` and element values as large as `10^9`.
Steps:
• The solution should work within the time limits for large arrays (up to 10^5 elements).
• Handle cases where `k` is large, ensuring the solution scales with larger values.
Assumptions:
• The input array `nums` is always valid and non-empty.
• The value of `k` is always a positive integer.
• Input: [5, 2, 7, 5, 3, 3, 7], k = 2
• Explanation: In this example, there are 4 different subarrays that contain at least 2 pairs of equal elements.
• Input: [2, 2, 2, 2, 2], k = 10
• Explanation: In this example, the only good subarray is the entire array itself, which has exactly 10 pairs.
Approach: The approach involves calculating the number of pairs of equal elements in each subarray and checking if it meets the threshold `k`.
Observations:
• The number of good subarrays depends on the number of pairs formed by equal elements.
• By tracking the frequency of each element as we iterate through the array, we can count the pairs efficiently.
Steps:
• Initialize a map to keep track of element frequencies and another variable to count the pairs.
• Iterate through the array while adjusting the count of pairs as each new element is added.
• If the number of pairs exceeds or equals `k`, count the subarrays from the current index to the end of the array.
Empty Inputs:
• The input array will always have at least one element.
Large Inputs:
• Ensure the algorithm can handle arrays with up to 10^5 elements efficiently.
Special Values:
• Handle cases where `k` is large relative to the number of elements in the array.
Constraints:
• The solution should avoid brute force techniques, as they would be inefficient for large arrays.
long long countGood(vector<int>& nums, int k) {
long long res = 0, tmp = 0;
int n = nums.size();
map<int, int> mp, cnt;
int j = 0;
for(int i = 0; i < n; i++) {
tmp += (cnt[nums[i]]);
cnt[nums[i]]++;
while(j <= i && tmp >= k) {
res+= (n - i);
cnt[nums[j]]--;
tmp -= cnt[nums[j]];
j++;
}
}
return res;
}
1 : Function Definition
long long countGood(vector<int>& nums, int k) {
The function 'countGood' is defined, which takes a vector of integers 'nums' and an integer 'k' as input and returns a long long result.
2 : Variable Initialization
long long res = 0, tmp = 0;
Two variables 'res' and 'tmp' are initialized to 0. 'res' will store the count of good subarrays, and 'tmp' tracks the frequency condition within the sliding window.
3 : Array Size
int n = nums.size();
The variable 'n' is set to the size of the input array 'nums'.
4 : Map Initialization
map<int, int> mp, cnt;
Two maps, 'mp' and 'cnt', are initialized. 'mp' will be used for storing elements of the array (though it's not used in this code), and 'cnt' will track the frequency of elements within the sliding window.
5 : Pointer Initialization
int j = 0;
The pointer 'j' is initialized to 0. It represents the left boundary of the sliding window.
6 : Outer Loop
for(int i = 0; i < n; i++) {
An outer loop starts from 'i = 0' to 'i < n', iterating over each element of the 'nums' array.
7 : Frequency Update
tmp += (cnt[nums[i]]);
The variable 'tmp' is updated by adding the current frequency of 'nums[i]' from the 'cnt' map. This tracks the frequency condition within the window.
8 : Count Update
cnt[nums[i]]++;
The frequency count of the current element 'nums[i]' is incremented in the 'cnt' map.
9 : Inner Loop Condition
while(j <= i && tmp >= k) {
A while loop is initiated as long as the frequency condition 'tmp >= k' holds, and the left pointer 'j' is less than or equal to the right pointer 'i'.
10 : Result Update
res += (n - i);
The result variable 'res' is updated by adding the count of valid subarrays from 'i' to the end of the array. This is part of the sliding window approach.
11 : Count Decrease
cnt[nums[j]]--;
The frequency of the element 'nums[j]' at the left boundary of the sliding window is decreased in the 'cnt' map.
12 : Frequency Decrease
tmp -= cnt[nums[j]];
The variable 'tmp' is updated by subtracting the updated frequency of 'nums[j]', reflecting the change in the window's frequency condition.
13 : Pointer Increment
j++;
The left boundary pointer 'j' is incremented to shrink the window.
14 : Return Result
return res;
The function returns the final result 'res', which is the count of all valid subarrays that meet the frequency condition.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) due to a single pass through the array and efficient use of a map to track frequencies.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we store the frequencies of elements in a map.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus