We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Subarrays Where Max Element Appears at Least K Times

Difficulty: Medium

Problem Description

You are given an integer array nums and a positive integer k. Return the number of subarrays where the maximum element of nums appears at least k times in that subarray. A subarray is a contiguous sequence of elements within an array.

Key Insights

  • A subarray's maximum element must appear at least k times to be counted.
  • The problem can be approached using a sliding window technique to efficiently count subarrays.
  • We need to track the frequency of elements within the current window and determine the maximum element dynamically.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

We will use a sliding window approach to maintain a window of elements in nums. We will keep track of the maximum element and its frequency within this window. As we extend the window to include new elements, we check if the maximum element appears at least k times. If it does, we calculate the number of valid subarrays ending at the current position.

To do this:

  1. Use two pointers to represent the current subarray.
  2. Maintain a frequency map to count the occurrences of each element in the current window.
  3. Update the maximum element and its count as we expand the window.
  4. For each valid position of the right pointer, count the number of valid subarrays that can end at that position.

Code Solutions

def count_subarrays(nums, k):
    from collections import defaultdict
    
    left = 0
    count = 0
    max_count = 0
    freq = defaultdict(int)
    
    for right in range(len(nums)):
        freq[nums[right]] += 1
        max_count = max(max_count, freq[nums[right]])
        
        while max_count >= k:  # check if the max appears at least k times
            count += len(nums) - right  # count valid subarrays
            freq[nums[left]] -= 1
            if freq[nums[left]] == 0:
                del freq[nums[left]]
                max_count = max(freq.values(), default=0)  # recalculate max
            left += 1
            
    return count
← Back to All Questions