Is Maximum Frequency Score of a Subarray easy or hard?

Maximum Frequency Score of a Subarray is classified as Hard on LeetCode. The difficulty comes from maintaining the score efficiently while the window slides and handling exponentiation with large numbers under modular arithmetic.

Maximum Frequency Score of a Subarray Python/Java solution

Implement a sliding window of length k and store frequencies in a dictionary (Python) or HashMap (Java). Maintain a running score and update it using modular fast power whenever frequencies change. The same logic works in C++ and Go with unordered_map or map structures.

How to solve Maximum Frequency Score of a Subarray in O(n)?

Use a sliding window of size k and maintain a hash map storing frequencies of elements in the window. Track the score dynamically by replacing the previous contribution x^f with x^(f+1) when adding an element, and reversing the update when removing it. With efficient modular exponentiation, the window moves through the array in near linear time.

What is the best approach for Maximum Frequency Score of a Subarray?

The optimal approach uses a sliding window with a hash table to track element frequencies and modular fast power to compute value^frequency contributions. The score is updated incrementally whenever an element enters or leaves the window. This reduces repeated work and runs in O(n log k) time with O(k) extra space.

Is Maximum Frequency Score of a Subarray asked at Google/Amazon/Meta?

Problems combining sliding window, frequency counting, and modular arithmetic appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test the ability to maintain aggregate values while a window moves across an array.

What data structure is used in Maximum Frequency Score of a Subarray?

The primary data structure is a hash table (or hashmap) that stores the frequency of each element in the current window. Combined with a sliding window over the array, it allows constant-time updates when elements are added or removed.

What is the time complexity of Maximum Frequency Score of a Subarray?

The optimized solution runs in O(n log k) time because each element enters and leaves the sliding window once, and each update requires a fast exponentiation operation. Space complexity is O(k) due to the frequency map storing elements inside the current window.

Description Hints 2 Solution Video 11:51

2524. Maximum Frequency Score of a Subarray

Hard35.7% acceptance1 companyPremium elsewhere, free here

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

The frequency score of an array is the sum of the distinct values in the array raised to the power of their frequencies, taking the sum modulo 10⁹ + 7.

For example, the frequency score of the array [5,4,5,7,4,4] is (4³ + 5² + 7¹) modulo (10⁹ + 7) = 96.

Return the maximum frequency score of a subarray of size k in nums. You should maximize the value under the modulo and not the actual value.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,1,1,2,1,2], k = 3
Output: 5
Explanation: The subarray [2,1,2] has a frequency score equal to 5. It can be shown that it is the maximum frequency score we can have.

Example 2:

Input: nums = [1,1,1,1,1,1], k = 4
Output: 1
Explanation: All the subarrays of length 4 have a frequency score equal to 1.

Constraints:

1 <= k <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Asked at 1 company

PayPal

Topics

Hints open one at a time

Hint 1

Calculate the frequency score of each subarray of size k and return the maximum one.

Hint 2

Use the sliding window technique to keep the frequency scores.

11:51

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,1,1,2,1,2]
3

Input

[1,1,1,1,1,1]
4

Your code is saved on this device.Solution