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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Length of Longest Subarray With at Most K Frequency

Number: 3225

Difficulty: Medium

Paid? No

Companies: Citadel, TikTok, Uber, Google, Apple, MakeMyTrip

Problem Description

Given an integer array nums and an integer k, we define a subarray as "good" if the frequency of each element in the subarray is at most k. The goal is to find the length of the longest good subarray.

Key Insights

  • Utilize a sliding window approach, maintaining a window that represents a contiguous subarray.
  • Use a hash table (or dictionary) to count the frequency of elements within the current window.
  • Expand the window by moving the right pointer, and when any element's frequency exceeds k, shrink the window from the left until the condition is met.
  • The maximum valid window size encountered during the process is the solution.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the nums array, as each element is processed at most twice. Space Complexity: O(m), where m is the number of distinct elements in the current window (in worst-case, m ≈ n).

Solution

The solution leverages the sliding window technique combined with a frequency hash table. Initialize two pointers (left and right) to represent the window boundaries. As the right pointer iterates over the array, add the element into the frequency counter. If the newly added element's frequency exceeds k, increment the left pointer to reduce the window size until all element frequencies are at most k. Simultaneously track the maximum window length. This approach ensures we explore all possible good subarrays with linear time complexity.

Code Solutions

# Python Implementation with line-by-line comments

def longest_good_subarray(nums, k):
    # Dictionary to track the frequency of elements in the current window
    freq = {}
    left = 0  # left pointer for the sliding window
    max_length = 0  # variable to track the maximum subarray length

    # Iterate with right pointer over the entire array
    for right in range(len(nums)):
        # Increment the frequency count for the current element
        freq[nums[right]] = freq.get(nums[right], 0) + 1

        # While current element's frequency exceeds k, shrink the window from the left
        while freq[nums[right]] > k:
            freq[nums[left]] -= 1  # Decrease frequency for the leftmost element
            left += 1  # Move left pointer to right

        # Update maximum length using the size of the current valid window
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example usage
print(longest_good_subarray([1,2,3,1,2,3,1,2], 2))
← Back to All Questions