Length of Longest Subarray With at Most K Frequency - LeetCode Daily Challenge

Problem Statement

You are given an integer array nums and an integer k.

The frequency of an element x is the number of times it occurs in an array.

An array is called good if the frequency of each element in this array is less than or equal to k.

Return the length of the longest good subarray of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1

Input: nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6
Explanation: The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good.
It can be shown that there are no good subarrays with length more than 6.

Example 2

Input: nums = [1,2,1,2,1,2,1,2], k = 1
Output: 2
Explanation: The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good.
It can be shown that there are no good subarrays with length more than 2.

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        int start = 0, maxLength = 0;

        for(int end = 0; end < nums.length; end++) {
            int curr = nums[end];
            frequencyMap.put(curr, frequencyMap.getOrDefault(curr, 0) + 1);
            
            while(frequencyMap.get(curr) > k) {
                int left = nums[start];
                frequencyMap.put(left, frequencyMap.get(left) - 1);
                start += 1;
            }

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

        return maxLength;
    }
}

C++ Code

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        unordered_map<int, int> frequencyMap;
        int start = 0, maxLength = 0;

        for (int end = 0; end < nums.size(); end++) {
            int curr = nums[end];
            frequencyMap[curr]++;

            while (frequencyMap[curr] > k) {
                int left = nums[start];
                frequencyMap[left]--;
                start++;
            }

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

        return maxLength;
    }
};

Python Code

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        frequencyMap = defaultdict(int)
        start = 0
        maxLength = 0

        for end in range(len(nums)):
            curr = nums[end]
            frequencyMap[curr] += 1

            while frequencyMap[curr] > k:
                left = nums[start]
                frequencyMap[left] -= 1
                start += 1

            maxLength = max(maxLength, end - start + 1)

        return maxLength

Javascript Code

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxSubarrayLength = function(nums, k) {
    const frequencyMap = new Map();
    let start = 0, maxLength = 0;

    for (let end = 0; end < nums.length; end++) {
        const curr = nums[end];
        frequencyMap.set(curr, (frequencyMap.get(curr) || 0) + 1);

        while (frequencyMap.get(curr) > k) {
            const left = nums[start];
            frequencyMap.set(left, frequencyMap.get(left) - 1);
            start++;
        }

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

    return maxLength;
};

Go Code

func maxSubarrayLength(nums []int, k int) int {
    frequencyMap := make(map[int]int)
    start := 0
    maxLength := 0

    for end := 0; end < len(nums); end++ {
        curr := nums[end]
        frequencyMap[curr]++

        for frequencyMap[curr] > k {
            left := nums[start]
            frequencyMap[left]--
            start++
        }

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

    return maxLength
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Complexity Analysis

Time Complexity: O(N)
Space Complexity: O(N)