Daily Question – 2958. Length of Longest Subarray With at Most K Frequency

Description: https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-frequency/description/

Notes:

The first solution that came to my mind was brute force: scanning each subarray, checking the frequency of each number, and then returning the result. However, this would undoubtedly exceed the time limit. To reduce time complexity, I utilized a HashMap to store the frequency of each number and implemented a sliding window algorithm for the check.

Code:

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        if (nums.length <= k) return nums.length;
        int left = 0,right = 0,max = 0,result = 0, maxKey = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        // step 1: find the first slide window
        while (max <= k && right<nums.length) {
            map.put( nums[right], map.getOrDefault(nums[right],0)+1);
            if (map.get(nums[right]) > max ) {
                max = map.get(nums[right]);
                maxKey = nums[right];
            }
            if (max > k) break;
            right++;
        }
        if (right-left > result) result = right - left;
        // step 2: start sliding
        for (left = 1; left < nums.length;left++) {
            map.put( nums[left-1], map.get(nums[left-1])-1);
            if (nums[left-1] == maxKey) max--;
            while (max <= k && right<nums.length) {
                right++;
                if (right == nums.length) break;
                map.put( nums[right], map.getOrDefault(nums[right],0)+1);
                if (map.get(nums[right]) > max ) {
                    max = map.get(nums[right]);
                    maxKey = nums[right];
                }
                if (max > k) break;
            }
            if (right-left > result) result = right - left;
        }
        return result;
    }
}

Simplify by chatGPT:

We can merge two loop to make the code more clear.

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        if (nums.length <= k) return nums.length;
        
        int left = 0, right = 0, max = 0, result = 0, maxKey = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        
        while (right < nums.length) {
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            if (map.get(nums[right]) > max) {
                max = map.get(nums[right]);
                maxKey = nums[right];
            }
            if (max > k) {
                map.put(nums[left], map.get(nums[left]) - 1);
                if (nums[left] == maxKey) max--;
                left++;
            }
            result = Math.max(result, right - left + 1);
            right++;
        }
        
        return result;
    }
}