LeetCode 2524: Maximum Frequency Score of a Subarray Solution

Master LeetCode problem 2524 (Maximum Frequency Score of a Subarray), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2524. Maximum Frequency Score of a Subarray

Hard

Array Hash Table Math Stack Sliding Window

Problem Explanation

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:

countMap to store the frequency of each element in the current window.
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:

Initialize variables maxScore to store the maximum score seen so far, and left to 0.
Iterate over the array using a sliding window of size k.
Update the frequency counts in countMap and freqMap for each element in the current window.
Calculate the score for the current window as the product of the most frequent element's frequency and the window size.
Update maxScore if the current score is greater.
Slide the window by incrementing left and updating the frequency counts accordingly.
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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2524 (Maximum Frequency Score of a Subarray)?

This page provides optimized solutions for LeetCode problem 2524 (Maximum Frequency Score of a Subarray) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2524 (Maximum Frequency Score of a Subarray)?

The time complexity for LeetCode 2524 (Maximum Frequency Score of a Subarray) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2524 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2524 in Java, C++, or Python.

Back to LeetCode Solutions