2626. Count The Number Of Good Subarrays¶

LeetCode Problem View on GitHub

2626. 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 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

Solution¶

class Solution {
    public long countGood(int[] nums, int k) {
        long res = 0L;
        Map<Integer, Integer> count = new HashMap<>();
        for(int i = 0, j = 0; j < nums.length; ++j){
            k -= count.getOrDefault(nums[j],0);
            count.put(nums[j],count.getOrDefault(nums[j],0)+1);
            while(k <= 0){
                count.put(nums[i],count.get(nums[i])-1);
                k += count.get(nums[i++]);
            }
            res += i;
        }
        return res;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here