LeetCode 2537. Count the Number of Good Subarrays Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: Hash Table + Two Pointers

If a subarray contains k pairs of identical elements, then this subarray must contain at least k pairs of identical elements.

We use a hash table cnt to count the occurrences of elements within the sliding window, a variable cur to count the number of identical pairs within the window, and a pointer i to maintain the left boundary of the window.

As we iterate through the array nums, we treat the current element x as the right boundary of the window. The number of identical pairs in the window increases by cnt[x], and we increment the count of x by 1, i.e., cnt[x] ← cnt[x] + 1. Next, we repeatedly check if the number of identical pairs in the window is greater than or equal to k after removing the leftmost element. If it is, we decrement the count of the leftmost element, i.e., cnt[nums[i]] ← cnt[nums[i]] - 1, reduce the number of identical pairs in the window by cnt[nums[i]], i.e., cur ← cur - cnt[nums[i]], and move the left boundary to the right, i.e., i ← i + 1. At this point, all elements to the left of and including the left boundary can serve as the left boundary for the current right boundary, so we add i + 1 to the answer.

Finally, we return the answer.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.

PythonJavaC++GoTypeScriptRust

class Solution: def countGood(self, nums: List[int], k: int) -> int: cnt = Counter() ans = cur = 0 i = 0 for x in nums: cur += cnt[x] cnt[x] += 1 while cur - cnt[nums[i]] + 1 >= k: cnt[nums[i]] -= 1 cur -= cnt[nums[i]] i += 1 if cur >= k: ans += i + 1 return ans(code-box)

class Solution { public long countGood(int[] nums, int k) { Map<Integer, Integer> cnt = new HashMap<>(); long ans = 0, cur = 0; int i = 0; for (int x : nums) { cur += cnt.merge(x, 1, Integer::sum) - 1; while (cur - cnt.get(nums[i]) + 1 >= k) { cur -= cnt.merge(nums[i++], -1, Integer::sum); } if (cur >= k) { ans += i + 1; } } return ans; } }(code-box)

class Solution { public: long long countGood(vector<int>& nums, int k) { unordered_map<int, int> cnt; long long ans = 0; long long cur = 0; int i = 0; for (int& x : nums) { cur += cnt[x]++; while (cur - cnt[nums[i]] + 1 >= k) { cur -= --cnt[nums[i++]]; } if (cur >= k) { ans += i + 1; } } return ans; } };(code-box)

func countGood(nums []int, k int) int64 { cnt := map[int]int{} ans, cur := 0, 0 i := 0 for _, x := range nums { cur += cnt[x] cnt[x]++ for cur-cnt[nums[i]]+1 >= k { cnt[nums[i]]-- cur -= cnt[nums[i]] i++ } if cur >= k { ans += i + 1 } } return int64(ans) }(code-box)

function countGood(nums: number[], k: number): number { const cnt: Map<number, number> = new Map(); let [ans, cur, i] = [0, 0, 0]; for (const x of nums) { const count = cnt.get(x) || 0; cur += count; cnt.set(x, count + 1); while (cur - (cnt.get(nums[i])! - 1) >= k) { const countI = cnt.get(nums[i])!; cnt.set(nums[i], countI - 1); cur -= countI - 1; i += 1; } if (cur >= k) { ans += i + 1; } } return ans; }(code-box)

use std::collections::HashMap; impl Solution { pub fn count_good(nums: Vec<i32>, k: i32) -> i64 { let mut cnt = HashMap::new(); let (mut ans, mut cur, mut i) = (0i64, 0i64, 0); for &x in &nums { cur += *cnt.get(&x).unwrap_or(&0); *cnt.entry(x).or_insert(0) += 1; while cur - (cnt[&nums[i]] - 1) >= k as i64 { *cnt.get_mut(&nums[i]).unwrap() -= 1; cur -= cnt[&nums[i]]; i += 1; } if cur >= k as i64 { ans += (i + 1) as i64; } } ans } }(code-box)