LeetCode 2524: Maximum Frequency Score of a Subarray

Explanation:

Given an array of integers nums, the task is to find the maximum possible score of a subarray of nums where the score of a subarray is defined as the product of the frequency of the most frequent element in the subarray and the length of the subarray.

To solve this problem, we can use a sliding window approach. We will maintain two hash maps:

1. countMap to store the frequency of each element in the current window.
2. freqMap to store the frequency of frequencies of elements in the current window.

We will iterate over the array using a sliding window of size k. At each step, we will update the frequency counts in the countMap and freqMap. We will track the maximum score we have seen so far.

Steps:

1. Initialize variables maxScore to store the maximum score seen so far, and left to 0.
2. Iterate over the array using a sliding window of size k.
3. Update the frequency counts in countMap and freqMap for each element in the current window.
4. Calculate the score for the current window as the product of the most frequent element's frequency and the window size.
5. Update maxScore if the current score is greater.
6. Slide the window by incrementing left and updating the frequency counts accordingly.
7. Return the maximum score.

Time Complexity:

The time complexity of this approach is O(n), where n is the number of elements in the input array.

Space Complexity:

The space complexity of this approach is O(n) to store the frequency counts in the hash maps.

:

class Solution {
    public int maxFrequencyScore(int[] nums, int k) {
        int maxScore = 0;
        Map<Integer, Integer> countMap = new HashMap<>();
        Map<Integer, Integer> freqMap = new HashMap<>();
        int left = 0;

        for (int right = 0; right < nums.length; right++) {
            countMap.put(nums[right], countMap.getOrDefault(nums[right], 0) + 1);
            int maxFreq = countMap.get(nums[right]);
            freqMap.put(maxFreq, freqMap.getOrDefault(maxFreq, 0) + 1);

            while ((right - left + 1) - freqMap.get(maxFreq) > k) {
                int leftFreq = countMap.get(nums[left]);
                freqMap.put(leftFreq, freqMap.get(leftFreq) - 1);
                if (freqMap.get(leftFreq) == 0) {
                    freqMap.remove(leftFreq);
                }
                countMap.put(nums[left], countMap.get(nums[left]) - 1);
                left++;
            }

            maxScore = Math.max(maxScore, maxFreq * (right - left + 1));
        }

        return maxScore;
    }
}