Skip to content

← leetcode

Count the Number of Good Subarrays

· Medium

LeetCode problem 2537

A classic two pointers / sliding window question.

Simply iterate the r index of the sliding window until there are at least k pairs, keeping track of the number of occurences of a number in the sliding window using the hash-map mp. When iterating through the array nums, we can simply increment mp[nums[r]] and then consequently add mp[nums[i]]-1 pairs (since logically speaking, the addition of the new value into the sliding window adds mp[nums[i]]-1 pairs).

Then, if there are more than k pairs, we can add nums.size() - r + 1 to the number of feasible subarrays. Finally, before we increment our l index, we decrement mp[nums[l]] and then remove mp[nums[i]] pairs, before repeating this all over again until either the r index exceeds the length of the array or the number of pairs is smaller than k.

code

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        int l = 0, r = 0, counter = 0;
        long long ans = 0;
        for (; r < nums.size() || counter >= k;) {
            for (; r < nums.size() && counter < k; ++r) {
                ++mp[nums[r]];
                counter += (mp[nums[r]]-1);
            }
            if (counter >= k) {
                ans += nums.size()-r+1;
            }
            --mp[nums[l]];
            counter -= mp[nums[l]];
            ++l;
        }
        return ans;
    }
};

complexity

  • Time: O(n) where n is the size of the array nums
  • Space: O(n)