Problem Description

You are given an integer array nums and an integer k. Your task is to find the number of good subarrays in nums.

A subarray is considered good if it contains at least k pairs of indices (i, j) where:

• i < j
• arr[i] == arr[j] (the elements at these indices are equal)

A subarray is a contiguous non-empty sequence of elements within the array.

For example, if we have a subarray [1, 2, 1, 2, 1]:

• The pairs with equal elements are: indices (0, 2), (0, 4), (2, 4) for element 1, and indices (1, 3) for element 2
• This gives us a total of 4 pairs

The problem asks you to count how many subarrays of nums have at least k such pairs of equal elements.

Intuition

The key observation is that if a subarray already has at least k pairs of identical elements, then extending this subarray to the right will only add more pairs (or keep the same number), never decrease them. This means once we find a good subarray, all its extensions to the right are also good.

When we add a new element to a subarray, how many new pairs does it create? If the element x already appears cnt[x] times in the subarray, adding one more x creates exactly cnt[x] new pairs (pairing with each existing occurrence of x).

This suggests using a sliding window approach with two pointers. We can expand the window to the right by adding elements one by one. For each new element, we calculate how many new pairs it creates with existing elements in the window.

The clever part is determining the leftmost valid position. Once we have at least k pairs in our window, we want to find the rightmost left boundary where the window still has at least k pairs. We can do this by shrinking from the left: keep removing the leftmost element as long as the remaining window still has at least k pairs.

Why does this work? Because if removing the leftmost element still leaves us with at least k pairs, then that element (and all elements to its left) can serve as valid starting points for subarrays ending at the current position. This is because adding back those elements would only increase the number of pairs.

For counting, once we've found the rightmost valid left boundary at position i, all positions from 0 to i can be valid starting points for good subarrays ending at the current position. So we add i + 1 to our answer.

Learn more about Sliding Window patterns.

Solution Approach

We implement a sliding window approach using two pointers with a hash table to track element frequencies.

Data Structures:

• cnt: A Counter (hash table) to track the frequency of each element in the current window
• cur: An integer tracking the total number of identical pairs in the current window
• i: The left pointer of the sliding window
• ans: The cumulative count of good subarrays

Algorithm Steps:

1. Expand the window to the right: For each element x in nums, we treat it as the right boundary of our window:

   • Before adding x, we have cnt[x] occurrences of x in the window
   • Adding one more x creates cnt[x] new pairs (pairing with each existing x)
   • Update: cur += cnt[x] to add these new pairs
   • Update: cnt[x] += 1 to increment the count of x

2. Shrink from the left to find the optimal left boundary: We want to find the rightmost position i where removing nums[i] would make the window have fewer than k pairs:

   while cur - cnt[nums[i]] + 1 >= k:

   This condition checks: if we remove nums[i], would we still have at least k pairs?

   • Removing nums[i] would eliminate cnt[nums[i]] - 1 pairs (pairs between this element and other occurrences of the same value)
   • If yes, we can safely remove it:
     • cnt[nums[i]] -= 1 (decrement the count)
     • cur -= cnt[nums[i]] (remove the pairs - note we use the updated count)
     • i += 1 (move the left boundary right)

3. Count valid subarrays: After finding the optimal left boundary:

   if cur >= k:
       ans += i + 1

   If the current window has at least k pairs, then all positions from 0 to i can serve as valid starting points for good subarrays ending at the current position, giving us i + 1 valid subarrays.

The time complexity is O(n) since each element is added and removed at most once. The space complexity is O(n) in the worst case for the hash table.

Example Walkthrough

Let's walk through the algorithm with nums = [1, 1, 1, 2, 2] and k = 3.

We'll track the window [i, j], the counter cnt, current pairs cur, and running answer ans.

Initial state: i = 0, cnt = {}, cur = 0, ans = 0

Step 1: j = 0, element = 1

• Before adding: cnt[1] = 0, so adding creates 0 new pairs
• Update: cur = 0, cnt = {1: 1}
• Check shrinking: cur - cnt[nums[0]] + 1 = 0 - 1 + 1 = 0 < 3, so don't shrink
• Since cur < k, don't add to answer
• Window: [1], pairs: 0

Step 2: j = 1, element = 1

• Before adding: cnt[1] = 1, so adding creates 1 new pair (indices 0,1)
• Update: cur = 1, cnt = {1: 2}
• Check shrinking: cur - cnt[nums[0]] + 1 = 1 - 2 + 1 = 0 < 3, so don't shrink
• Since cur < k, don't add to answer
• Window: [1, 1], pairs: 1

Step 3: j = 2, element = 1

• Before adding: cnt[1] = 2, so adding creates 2 new pairs (indices 0,2 and 1,2)
• Update: cur = 3, cnt = {1: 3}
• Check shrinking: cur - cnt[nums[0]] + 1 = 3 - 3 + 1 = 1 < 3, so don't shrink
• Since cur >= k, add i + 1 = 1 to answer. ans = 1
• Window: [1, 1, 1], pairs: 3
• This means subarray [1,1,1] starting at index 0 is good

Step 4: j = 3, element = 2

• Before adding: cnt[2] = 0, so adding creates 0 new pairs
• Update: cur = 3, cnt = {1: 3, 2: 1}
• Check shrinking: cur - cnt[nums[0]] + 1 = 3 - 3 + 1 = 1 < 3, so don't shrink
• Since cur >= k, add i + 1 = 1 to answer. ans = 2
• Window: [1, 1, 1, 2], pairs: 3
• This means subarray [1,1,1,2] starting at index 0 is good

Step 5: j = 4, element = 2

• Before adding: cnt[2] = 1, so adding creates 1 new pair (indices 3,4)
• Update: cur = 4, cnt = {1: 3, 2: 2}
• Check shrinking:
  • cur - cnt[nums[0]] + 1 = 4 - 3 + 1 = 2 < 3? No, it equals 2 which is less than 3
  • So we don't shrink
• Since cur >= k, add i + 1 = 1 to answer. ans = 3
• Window: [1, 1, 1, 2, 2], pairs: 4
• This means subarray [1,1,1,2,2] starting at index 0 is good

Final answer: 3

The good subarrays are:

1. [1, 1, 1] - has 3 pairs
2. [1, 1, 1, 2] - has 3 pairs
3. [1, 1, 1, 2, 2] - has 4 pairs

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the array nums.

The algorithm uses a two-pointer approach with a sliding window technique. The outer loop iterates through each element in nums exactly once, contributing O(n) operations. The inner while loop might seem to add complexity, but each element can only be removed from the window once. Specifically, the variable i only moves forward and can increment at most n times throughout the entire execution. Therefore, the total number of operations across all iterations is bounded by O(n) for the outer loop and O(n) for all executions of the inner loop combined, resulting in an overall time complexity of O(n).

Space Complexity: O(n) where n is the length of the array nums.

The space complexity is determined by the Counter object cnt, which stores the frequency of elements in the current window. In the worst case, when all elements in nums are distinct, the counter would need to store up to n unique keys and their corresponding counts, requiring O(n) space. The remaining variables (ans, cur, i, x) use constant space O(1), so the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Order of Operations When Updating Pairs

The Problem: A critical mistake occurs when updating the pair_count after modifying the frequency map. The order matters significantly:

# WRONG - This will use the updated frequency incorrectly
frequency_map[num] += 1
pair_count += frequency_map[num]  # This adds one too many pairs!

When a new element is added to the window, it forms pairs with all existing occurrences of the same value. If we increment the frequency first, we're incorrectly counting a pair between the element and itself.

The Solution: Always update pair_count before updating frequency_map:

# CORRECT
pair_count += frequency_map[num]  # Add pairs with existing occurrences
frequency_map[num] += 1            # Then increment the frequency

Similarly, when removing an element:

# CORRECT
frequency_map[nums[left]] -= 1              # Decrement first
pair_count -= frequency_map[nums[left]]     # Then subtract remaining pairs

Pitfall 2: Off-by-One Error in the While Loop Condition

The Problem: The condition for shrinking the window can be confusing:

# This might seem intuitive but is WRONG
while pair_count - (frequency_map[nums[left]] - 1) >= k:

The confusion arises from mixing up "pairs that would be removed" with "pairs that would remain."

The Solution: Think of it as: "After removing nums[left], how many pairs would that element still contribute?"

• Before removal: frequency_map[nums[left]] occurrences
• After removal: frequency_map[nums[left]] - 1 occurrences
• Pairs after removal: frequency_map[nums[left]] - 1 pairs

# CORRECT - Check if we'd still have k pairs after removal
while pair_count - (frequency_map[nums[left]] - 1) >= k:

Pitfall 3: Not Handling Empty Frequency Map Entries

The Problem: Using a regular dictionary instead of Counter can lead to KeyError:

# WRONG - Will raise KeyError for new elements
frequency_map = {}
pair_count += frequency_map[num]  # KeyError if num not in map!

The Solution: Use Counter which returns 0 for missing keys, or explicitly handle missing keys:

# Option 1: Use Counter (recommended)
frequency_map = Counter()

# Option 2: Use defaultdict
frequency_map = defaultdict(int)

# Option 3: Explicit checking (not recommended, more verbose)
frequency_map = {}
pair_count += frequency_map.get(num, 0)