LeetCode 2524 - Maximum Frequency Score of a Subarray

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, Stack, Sliding Window

Solution

Problem Understanding

The problem asks us to compute the maximum frequency score among all contiguous subarrays of length k from a given integer array nums. A frequency score is defined as the sum of each distinct element raised to the power of its frequency within the subarray, taken modulo 10^9 + 7. For instance, for the array [5,4,5,7,4,4], the frequency of each distinct element is {5:2, 4:3, 7:1}, so the score is calculated as 5^2 + 4^3 + 7^1 = 25 + 64 + 7 = 96 modulo 10^9 + 7.

The input consists of:

nums: an array of integers, with 1 <= nums[i] <= 10^6.
k: the size of the subarray, guaranteed to satisfy 1 <= k <= len(nums).

The expected output is a single integer representing the maximum frequency score among all subarrays of size k.

Constraints and implications:

The array length can be as large as 10^5, which rules out any brute-force solution that checks all O(n*k) possibilities.
Values in nums can be as high as 10^6, which means naive exponentiation without modular arithmetic could overflow.
Every subarray is contiguous, so a sliding window approach is a natural fit.

Important edge cases include:

All elements are identical, e.g., nums = [1,1,1]. Each subarray will have the same score.
Maximum size subarray, k = len(nums). Only one subarray exists.
Elements with high frequency or large values, which tests modular exponentiation.

Approaches

The brute-force approach would involve generating all possible subarrays of size k, counting the frequency of each distinct element, calculating the frequency score, and returning the maximum. This works correctly but is inefficient because for each of the O(n) subarrays, counting frequencies and computing exponentiation can take up to O(k), resulting in O(n*k) time, which is infeasible for n = 10^5.

The optimal approach leverages a sliding window with a frequency map. As we move the window by one element:

Remove the element leaving the window from the frequency map.
Add the element entering the window to the frequency map.
Update the frequency score incrementally rather than recomputing from scratch.

The key insight is that modular exponentiation can be updated incrementally using properties of powers. Specifically, when an element's frequency changes from f to f+1, the contribution to the sum changes from x^f to x^(f+1). Using modular arithmetic, we can compute this efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n*k)	O(k)	Compute frequency score for every subarray of size k
Optimal	O(n*log k)	O(k)	Sliding window with frequency map and incremental modular exponentiation

Algorithm Walkthrough

Initialize a frequency map to count occurrences of each element in the current window of size k.
Compute the initial frequency score for the first window by raising each distinct element to its frequency modulo 10^9 + 7.
Set a variable max_score to this initial score.
Slide the window from left to right by one element at a time:

Decrease the frequency of the element leaving the window. Update the score by subtracting its previous contribution and adding the new contribution.
Increase the frequency of the element entering the window. Update the score similarly.

After updating the score for each new window, compare it with max_score and update max_score if the new score is higher.
Continue until all subarrays of size k have been evaluated.
Return max_score.

Why it works: The sliding window ensures that each subarray of size k is considered exactly once, and the incremental updates guarantee correct frequency scores without recomputing from scratch. Modular arithmetic ensures values do not overflow.

Python Solution

from collections import defaultdict
from typing import List

MOD = 10**9 + 7

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        def mod_pow(a: int, b: int) -> int:
            result = 1
            a %= MOD
            while b > 0:
                if b % 2 == 1:
                    result = (result * a) % MOD
                a = (a * a) % MOD
                b //= 2
            return result

        freq = defaultdict(int)
        score = 0
        # Initialize first window
        for i in range(k):
            freq[nums[i]] += 1
        for num, f in freq.items():
            score = (score + mod_pow(num, f)) % MOD
        max_score = score

        # Slide the window
        for i in range(k, len(nums)):
            left = nums[i - k]
            right = nums[i]

            # Remove left
            old_freq = freq[left]
            score = (score - mod_pow(left, old_freq) + MOD) % MOD
            freq[left] -= 1
            if freq[left] > 0:
                score = (score + mod_pow(left, freq[left])) % MOD
            else:
                del freq[left]

            # Add right
            old_freq = freq.get(right, 0)
            if old_freq > 0:
                score = (score - mod_pow(right, old_freq) + MOD) % MOD
            freq[right] = old_freq + 1
            score = (score + mod_pow(right, freq[right])) % MOD

            max_score = max(max_score, score)

        return max_score

The implementation initializes the frequency map for the first window and computes the initial score. As the window slides, it removes the contribution of the outgoing element, updates its frequency, and adds the new contribution. Similarly, it handles the incoming element. The mod_pow function ensures modular exponentiation efficiently.

Go Solution

package main

func modPow(a, b int) int {
    const MOD = 1_000_000_007
    result := 1
    a %= MOD
    for b > 0 {
        if b%2 == 1 {
            result = (result * a) % MOD
        }
        a = (a * a) % MOD
        b /= 2
    }
    return result
}

func maxFrequencyScore(nums []int, k int) int {
    const MOD = 1_000_000_007
    freq := make(map[int]int)
    score := 0

    for i := 0; i < k; i++ {
        freq[nums[i]]++
    }
    for num, f := range freq {
        score = (score + modPow(num, f)) % MOD
    }
    maxScore := score

    for i := k; i < len(nums); i++ {
        left := nums[i-k]
        right := nums[i]

        oldFreq := freq[left]
        score = (score - modPow(left, oldFreq) + MOD) % MOD
        freq[left]--
        if freq[left] > 0 {
            score = (score + modPow(left, freq[left])) % MOD
        } else {
            delete(freq, left)
        }

        oldFreq = freq[right]
        if oldFreq > 0 {
            score = (score - modPow(right, oldFreq) + MOD) % MOD
        }
        freq[right] = oldFreq + 1
        score = (score + modPow(right, freq[right])) % MOD

        if score > maxScore {
            maxScore = score
        }
    }
    return maxScore
}

In Go, maps are used instead of Python dictionaries. Modular arithmetic and exponentiation follow the same logic. We handle deletion of elements with frequency zero explicitly.

Worked Examples

Example 1: nums = [1,1,1,2,1,2], k = 3

Window	freq map	Score calculation	max_score
[1,1,1]	{1:3}	1^3 = 1	1
[1,1,2]	{1:2,2:1}	1^2 + 2^1 = 1+2=3	3
[1,2,1]	{1:2,2:1}	1^2 + 2^1 = 3	3
[2,1,2]	{1:1,2:2}	1^1 + 2^2 = 1+4=5	5

Maximum score = 5

Example 2: nums = [1,1,1,1,1,1], k = 4

All windows are {1:4}, score = 1^4 = 1. Maximum score = 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n*log(max_val))	Sliding window takes O(n), modular exponentiation per element change takes O(log frequency)