Solving Length of Longest Subarray at Most K Frequency

The problem of finding the length of the longest subarray with at most K frequency is a common challenge in coding interviews and technical assessments. Understanding how to tackle this problem efficiently can significantly enhance your problem-solving skills. In this article, we will delve into the intricacies of this problem, explore different approaches, and provide a detailed solution using Java code.

Understanding the Problem

We are given an integer array, nums, and an integer K. The goal is to find the length of the longest contiguous subarray such that no element appears more than K times. This means that a subarray is considered “good” if the frequency of each element within it does not exceed K.

For example, consider the following inputs:

Input: nums = [1, 2, 3, 1, 2, 3], K = 2
Output: 6
Input: nums = [1, 2, 1, 2, 1, 2], K = 1
Output: 2
Input: nums = [5, 5, 5, 5], K = 4
Output: 4

These examples illustrate the essence of the problem and how varying values of K can impact the maximum length of the good subarray.

Constraints

The constraints for this problem state that:

The length of the array can be between 1 to 100,000.
The elements in the array can range from 1 to 1,000,000,000.
K can vary from 1 to the length of the array.

Approach to Solve the Problem

To tackle this problem efficiently, we can utilize a sliding window technique. The sliding window approach allows us to maintain a dynamic subarray and adjust its boundaries based on the frequency of elements within it.

Sliding Window Technique

The sliding window technique involves two pointers, start and end, which represent the current window in the array. The idea is to expand the end pointer to include new elements and adjust the start pointer when the frequency of any element exceeds K.

Steps to Implement the Sliding Window

Initialize a map to store the frequency of elements.
Set the start and end pointers to 0.
Iterate through the array using the end pointer.
Update the frequency of the current element.
If the frequency of any element exceeds K, increment the start pointer until the frequency is valid.
Calculate the current window length and update the maximum length found.

Java Implementation

Here’s a Java implementation of the above approach:

import java.util.HashMap;

public class LongestSubarrayAtMostKFrequency {
    public static int longestSubarray(int[] nums, int k) {
        HashMap frequencyMap = new HashMap<>();
        int start = 0, maxLength = 0;

        for (int end = 0; end < nums.length; end++) {
            frequencyMap.put(nums[end], frequencyMap.getOrDefault(nums[end], 0) + 1);

            while (frequencyMap.get(nums[end]) > k) {
                frequencyMap.put(nums[start], frequencyMap.get(nums[start]) - 1);
                if (frequencyMap.get(nums[start]) == 0) {
                    frequencyMap.remove(nums[start]);
                }
                start++;
            }

            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1, 2, 3};
        int k = 2;
        System.out.println("Length of longest subarray: " + longestSubarray(nums, k)); // Output: 6
    }
}

Time and Space Complexity

The time complexity of this solution is O(N), where N is the length of the array. This is because each element is processed at most twice (once when expanding the end and once when moving the start).

The space complexity is O(N) in the worst case, where all elements are unique and stored in the frequency map.

Conclusion

The problem of finding the length of the longest subarray with at most K frequency can be efficiently solved using the sliding window approach. By keeping track of element frequencies and adjusting the window boundaries dynamically, we can ensure optimal performance. This method not only helps in solving this specific problem but also builds a strong foundation for tackling similar problems in the future.

Length of Longest Subarray at Most K Frequency