LeetCode Solutions Blog

Maximum Frequency Score of a Subarray

Number: 2667

Difficulty: Hard

Paid? Yes

Companies: PayPal

Problem Description

Given an integer array nums and a positive integer k, a subarray’s frequency score is defined as the sum (modulo 10^9 + 7) of each distinct value raised to the power of its frequency in that subarray. For example, the frequency score of [5,4,5,7,4,4] is computed as (4^3 + 5^2 + 7^1) mod (10^9+7) = 96. The task is to return the maximum frequency score among all contiguous subarrays of length k in nums. Note that when comparing scores, we maximize the value as computed under the modulo, not the true large integer value.

Key Insights

Use a sliding window of size k to traverse the array.
Maintain a hash table (or dictionary) to track frequencies of each element in the current window.
Update the frequency score on-the-fly by adjusting only the elements that leave or enter the window.
On frequency change of an element x from f to f+1, update the score by subtracting x^f and adding x^(f+1) (all operations done modulo 10^9+7).
Built-in fast modular exponentiation (such as using pow(x, exp, mod)) is used for computing powers efficiently.

Space and Time Complexity

Time Complexity: O(n * log(k)) – each window update computes two modular exponentiations (each taking O(log(k)) time) and there are O(n) windows. Space Complexity: O(k) – used for the frequency hash table for the current window.

Solution

We use a sliding window approach with a hash table to maintain the frequency of each element in the current window. For each window, the frequency score is defined as the sum over distinct numbers x of (x^(frequency)) modulo the mod value. When sliding the window by one element, we update the frequency of the element that is removed and the element that is added. For each update, we subtract the old contribution (x raised to the old frequency) and add the new contribution (x raised to the new frequency). We keep the score modulo 10^9+7 and update the maximum score encountered. This approach efficiently recalculates the frequency score without having to recompute from scratch in each step.

Code Solutions

# Define the modulo constant
MOD = 10**9 + 7

def maxFrequencyScore(nums, k):
    # Dictionary to store the frequency of each element in the window
    freq = {}
    current_score = 0

    # Build the initial window of size k
    for i in range(k):
        x = nums[i]
        # Get the current frequency of element x
        current_freq = freq.get(x, 0)
        # If x is already present, subtract its previous contribution
        if current_freq > 0:
            current_score = (current_score - pow(x, current_freq, MOD)) % MOD
        # Increase the frequency
        freq[x] = current_freq + 1
        # Add the new contribution for x with updated frequency
        current_score = (current_score + pow(x, freq[x], MOD)) % MOD

    # Set the max score as the score of the first window
    max_score = current_score

    # Slide the window through the array
    for i in range(1, len(nums) - k + 1):
        # Element leaving the window
        leaving = nums[i - 1]
        leaving_freq = freq[leaving]
        # Remove the leaving element's old contribution
        current_score = (current_score - pow(leaving, leaving_freq, MOD)) % MOD
        # Decrease the frequency
        freq[leaving] = leaving_freq - 1
        # If leaving element still exists in the window, add its new contribution
        if freq[leaving] > 0:
            current_score = (current_score + pow(leaving, freq[leaving], MOD)) % MOD

        # Element entering the window
        entering = nums[i + k - 1]
        entering_freq = freq.get(entering, 0)
        # If entering element already present, remove its current contribution
        if entering_freq > 0:
            current_score = (current_score - pow(entering, entering_freq, MOD)) % MOD
        # Increase its frequency
        freq[entering] = entering_freq + 1
        # Add the new contribution for the entering element
        current_score = (current_score + pow(entering, freq[entering], MOD)) % MOD

        # Update the max score if needed
        max_score = max(max_score, current_score)

    return max_score

# Example test cases:
print(maxFrequencyScore([1,1,1,2,1,2], 3))  # Expected output: 5
print(maxFrequencyScore([1,1,1,1,1,1], 4))    # Expected output: 1