Count the Number of Good Subarrays

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.

For example:

Input: nums = [1,1,1,1,1], k = 10 Output: 1 Explanation: The only good subarray is the array nums itself.

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.

def count_good_subarrays(nums, k):
    n = len(nums)
    count = 0

    for i in range(n):
        for j in range(i, n):
            subarray = nums[i:j+1]
            pairs = 0
            
            for x in range(len(subarray)):
                for y in range(x + 1, len(subarray)):
                    if subarray[x] == subarray[y]:
                        pairs += 1
            
            if pairs >= k:
                count += 1

    return count

# Example usage:
nums1 = [1, 1, 1, 1, 1]
k1 = 10
print(f"Input: nums = {nums1}, k = {k1}\nOutput: {count_good_subarrays(nums1, k1)}")

nums2 = [3, 1, 4, 3, 2, 2, 4]
k2 = 2
print(f"Input: nums = {nums2}, k = {k2}\nOutput: {count_good_subarrays(nums2, k2)}")

Explanation:

1. count_good_subarrays(nums, k) Function:

   • Takes an integer array nums and an integer k as input.
   • Initializes a count variable to 0, which will store the number of good subarrays.
   • Iterates through all possible subarrays using nested loops:
     • The outer loop starts at index i = 0 and goes up to n-1.
     • The inner loop starts at index j = i and goes up to n-1.
     • This ensures that each subarray nums[i:j+1] is considered.
   • For each subarray:
     • Initializes a pairs variable to 0.
     • Counts the number of pairs in the subarray by iterating through all possible pairs of indices (x, y) such that x < y.
     • If subarray[x] == subarray[y], it increments the pairs count.
     • After counting the pairs, it checks if pairs >= k. If it is, it means the subarray is good, so the count variable is incremented.
   • Finally, it returns the count.

2. Example Usage:

   • Two examples are provided to demonstrate the function's usage with different inputs.
   • The output for each example shows the number of good subarrays found.

Big(O) Run-time Analysis:

The time complexity of the count_good_subarrays function can be analyzed as follows:

• Outer loop: The outer loop iterates n times.
• Inner loop: The inner loop iterates n - i times, which is O(n) in the worst case.
• Counting pairs: The nested loops for counting pairs iterate up to m times, where m is the length of the subarray. In the worst case, m can be equal to n. The number of iterations will be ( m * (m - 1) / 2 ), which is ( O(m^2) ). Therefore, it's (O(n^2)) in the worst case.

So, the overall time complexity is ( O(n * n * n^2) = O(n^4) ). This is because for each of the ( O(n^2) ) subarrays, we iterate ( O(n^2) ) to calculate the number of pairs.

Big(O) Space Usage Analysis:

The space complexity of the count_good_subarrays function is ( O(n) ) in the worst case, due to the space used by the subarray variable, which can have a maximum length of n. The other variables used (count, pairs, i, j, x, y) take up constant space, so they do not affect the overall space complexity.