2537. Count-The-Number-Of-Good-Subarrays

Classic sliding window problem… We keep track of the number of pairs within our current window (to do this we want to keep track of the count of each element inside the window). Until our current window is valid, we keep expanding our window by moving our right pointer forwards. While our current window is valid, we can keep moving our left pointer forwards, shrinking our window and calculating the number of subarrays that were valid given l and r.

For updates:

• when we move the right pointer and add a new number to the window, we check if the number already exists in the window. If it doesn’t, it does not increase the number of pairs. If the number already exists, it increases the number of pairs in our window by how many of that number already existed in the window. For example, if there were 3 “6”s and we added another “6”, we would add 3 to the number of pairs.

• when we move the left pointer and remove a number, we do the opposite where we decrease the number of pairs by how many of that number re removed exists in the window. For example, if there were 3 “6”s in the window and we removed a “6”, we would decrease the number of pairs by 2.

• when the window is valid, we will add n - (r - 1) to the number of good subarrays as that is how many subarrays exist given the l and r. (All subarrays that start from l and end at any index after and including r will be good).

class Solution(object):
    def countGood(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        n = len(nums)
        l = 0
        r = 0
        res = 0

        count = {}
        no_of_pairs = 0
        for l in range(n):
            while no_of_pairs < k and r < n:
                if nums[r] not in count:
                    count[nums[r]] = 1
                else:
                    no_of_pairs += count[nums[r]]
                    count[nums[r]] += 1
                r += 1

            if no_of_pairs >= k:
                res += n - (r - 1)
            count[nums[l]] -= 1
            no_of_pairs -= count[nums[l]]

        return res

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 14m 51s