medium Count the Number of Good Subarrays

Problem Statement

Given an array of integers nums, and an integer k, find the count of "good" subarrays within nums.

A subarray is considered "good" if it contains at least k pairs of elements (i, j) where i < j and nums[i] == nums[j].

A subarray is a contiguous sequence of elements in the original array.

Examples

• Example 1:

  • Input: nums = [2, 2, 2, 3, 3], k = 3
  • Expected Output: 3
  • Justification: There are 3 good subarrays that meet the criteria: [2, 2, 2, 3], [2, 2, 2, 3, 3], and [2, 2, 2]. Each of these subarrays has at least 3 pairs of equal elements.

• Example 2:

  • Input: nums = [4, 4, 4, 4], k = 6
  • Expected Output: 1
  • Justification: The only good subarray that meets the criteria is the entire array itself [4, 4, 4, 4], which contains 6 pairs of equal elements.

• Example 3:

  • Input: nums = [1, 2, 3, 1, 2], k = 2
  • Expected Output: 2
  • Justification: There is only 1 good subarray, which is [1, 2, 3, 1, 2]. It contains at least 2 pairs of equal elements.

Solution

To solve this problem, an efficient strategy utilizing a sliding window technique alongside a frequency map is employed to meticulously count the subarrays fulfilling the criterion of containing at least k pairs of identical elements. This method hinges on dynamically adjusting the boundaries of the window to encompass various segments of the array, methodically tracking the occurrence of each element to ascertain the formation of pairs. As the window expands, it meticulously updates the pair count, ensuring that each segment's potential to meet the specified condition is fully explored.

The effectiveness of this approach is underscored by its capacity to seamlessly navigate through the array, leveraging the frequency map for swift updates and checks on pair formation. This optimization minimizes redundant computations, thereby enhancing efficiency. By judiciously adjusting the window's size based on the evolving pair count, the algorithm ensures a comprehensive evaluation of all possible subarrays, accurately identifying those that qualify as "good" by the problem's standards.

Step-by-Step Algorithm

1. Initialize Variables: Start with two pointers, i = 0 and j = 0, a long counter ans = 0 for the answer, a long counter count = 0 for the number of pairs, and n = nums.length for the size of the input array. Also, initialize a frequency map m.

2. Iterate Through the Array: Loop through the array with j from 0 to n - 1. For each element nums[j], increment its frequency in the map m.

3. Update Pair Count: If the frequency of nums[j] after incrementing is more than 1, it forms pairs. Increment count by m[nums[j]] - 1, which represents the new pairs formed by adding the current element.

4. Check and Adjust Window: While count >= k (the subarray has enough pairs) and i <= j, calculate the number of new good subarrays that can be formed with the current j by adding n - j to ans. Then, decrement the frequency of nums[i] as i moves forward. If nums[i]'s frequency is still at least 1, decrement count by m[nums[i]] because moving i means losing some pairs. Increment i to shrink the window from the start.

5. Return Answer: Once the loop completes, return ans as the total count of good subarrays found.

Algorithm Walkthrough

Let's consider the Input [2, 2, 2, 3, 3], k = 3

1. Initialization:

   • Set i = 0 to mark the start of the sliding window.
   • Initialize ans = 0 to keep track of the total count of good subarrays.
   • Initialize count = 0 to track the current number of pairs within the window.
   • Determine n = 5 as the size of the input array.
   • Create a frequency map m to track the occurrences of each number within the current window.

2. First Iteration (j = 0):

   • Process the first element, 2. The frequency map is updated to {2: 1}. No pairs are formed yet, so count remains at 0.

3. Second Iteration (j = 1):

   • Process the second element, 2. The frequency map updates to {2: 2}. We now have one pair of 2s, incrementing count by 1 (count = count + 2 - 1 = 0 + 2 - 1 = 1).

4. Third Iteration (j = 2):

   • Add another 2 to m. m = {2: 3}, count = count + 3 - 1 = 1 + 3 - 1 = 1.
   • Now, count is equal to k(3) and i<=j. So, execute the inner loop.
     • ans = ans + n - j = 0 + 5 - 2 = 3
     • Update the map to {2: 2}.
     • Update the count to count(3) - (m[2](3) - 1) = 3 - 2 = 1.
     • increment i to 1.

5. Fourth Iteration (j = 3):

   • Add 3 to m. m = {2: 2, 3: 1}, count remains 1.

6. Fifth Iteration (j = 4):

   • Add another 3 to m. m = {2: 3, 3: 2}, count increases to 2.

7. Final Answer:

   • ans = 3 is the total count of good subarrays found.

Code

import java.util.HashMap;

public class Solution {

  // Method to count the number of good subarrays
  public int countGood(int[] nums, int k) {
    int i = 0, ans = 0, count = 0, n = nums.length;
    HashMap<Integer, Long> m = new HashMap<>();

    for (int j = 0; j < n; j++) {
      // Increment the frequency of the current element
      m.put(nums[j], m.getOrDefault(nums[j], 0L) + 1);
      // If the element's frequency is more than 1, increment the count of pairs
      if (m.get(nums[j]) > 1) count += m.get(nums[j]) - 1;

      // While the count of pairs is at least k, adjust the window
      while (i <= j && count >= k) {
        ans += n - j; // Add to answer the number of subarrays that can be formed from the current position
        // Decrement the frequency of the element at the start of the window
        m.put(nums[(int) i], m.get(nums[(int) i]) - 1);
        // If the frequency is still at least 1, decrement the count of pairs
        if (m.get(nums[(int) i]) >= 1) count -= m.get(nums[(int) i]);
        i++; // Move the start of the window
      }
    }
    return ans; // Return the total count of good subarrays
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test the algorithm with the example inputs
    System.out.println(solution.countGood(new int[] { 2, 2, 2, 3, 3 }, 3)); // Expected output: 3
    System.out.println(solution.countGood(new int[] { 4, 4, 4, 4 }, 6)); // Expected output: 1
    System.out.println(solution.countGood(new int[] { 1, 2, 3, 1, 2 }, 2)); // Expected output: 1
  }
}

Complexity Analysis

• Time Complexity: The overall time complexity of the solution is . This is because the solution uses two nested loops to explore all possible subarrays of the input array, where n is the length of the input array. Within the inner loop, operations such as updating the frequency map and calculating the number of pairs have a time complexity of per iteration, but the repeated calculation for each subarray leads to the quadratic time complexity.

• Space Complexity: The space complexity is for all solutions. This is due to the use of a hash map (or dictionary in Python) to count the frequency of elements within each subarray. In the worst case, if all elements of the array are distinct, the space required for the frequency map would be proportional to the size of the subarray being considered, which can be up to n in size.