Facebook Pixel

2524. Maximum Frequency Score of a Subarray 🔒

HardStackArrayHash TableMathSliding Window
Leetcode Link

Problem Description

You have an integer array nums and a positive integer k. Your task is to find a contiguous subarray of exactly size k that has the maximum possible frequency score.

The frequency score of an array is calculated as follows:

  1. Count the frequency of each distinct value in the array
  2. For each distinct value, raise it to the power of its frequency
  3. Sum all these powers together
  4. Take the result modulo 10^9 + 7

For example, given the array [5,4,5,7,4,4]:

  • The value 4 appears 3 times, contributing 4^3 = 64
  • The value 5 appears 2 times, contributing 5^2 = 25
  • The value 7 appears 1 time, contributing 7^1 = 7
  • The frequency score is (64 + 25 + 7) mod (10^9 + 7) = 96

You need to examine all possible subarrays of length k in nums and return the maximum frequency score among them. Note that you should maximize the value after applying the modulo operation, not the actual mathematical value before modulo.

A subarray is a contiguous sequence of elements from the original array, meaning the elements must appear consecutively in their original order.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The naive approach would be to calculate the frequency score for every possible subarray of size k, but this would be inefficient since we'd be recounting frequencies from scratch for each window.

The key insight is that consecutive windows of size k share most of their elements. When we slide the window one position to the right, we only remove one element from the left and add one element from the right. This means we can maintain the frequency score incrementally rather than recalculating it entirely.

Consider what happens to the frequency score when we modify a single element's frequency:

  • When an element x with frequency f gets its frequency increased to f+1, the contribution changes from x^f to x^(f+1). The difference is x^(f+1) - x^f = x^f * (x - 1).
  • Similarly, when frequency decreases from f to f-1, the contribution changes by x^(f-1) * (x - 1) in the opposite direction.

This observation allows us to update the score efficiently. When sliding the window:

  1. If we remove element a and add element b, and they're different:
    • The frequency of a decreases by 1
    • The frequency of b increases by 1
    • We can update the current score by adjusting these two contributions

We can maintain a hash table to track frequencies and use fast power computation with modulo to handle the large numbers. Starting with the first window of size k, we calculate its initial score, then slide the window through the array, updating the score incrementally and keeping track of the maximum score encountered.

The sliding window technique combined with incremental updates reduces the time complexity significantly compared to recalculating the score for each window from scratch.

Learn more about Stack, Math and Sliding Window patterns.

Solution Approach

The solution uses a hash table with sliding window technique combined with fast power computation.

Step 1: Initialize the first window

  • Create a Counter (hash table) cnt to store the frequency of each element in the first k elements
  • Calculate the initial frequency score using the formula: sum(pow(k, v, mod) for k, v in cnt.items())
  • Store this as both the current score cur and the maximum score ans

Step 2: Slide the window through the array Starting from index k, process each element by:

  • Identifying the element to remove a = nums[i - k] (leftmost element of previous window)
  • Identifying the element to add b = nums[i] (new rightmost element)

Step 3: Update the score incrementally When a != b (only need to update when they're different):

For adding element b:

  • If cnt[b] = 0 (new element): contribution is simply b^1 = b
  • If cnt[b] > 0 (element already exists): the contribution changes from b^cnt[b] to b^(cnt[b]+1)
  • The difference is: b^(cnt[b]+1) - b^cnt[b] = b^cnt[b] * (b - 1)
  • Update: cur += (b - 1) * pow(b, cnt[b], mod) if cnt[b] else b

For removing element a:

  • If cnt[a] = 1 (last occurrence): we remove contribution of a^1 = a
  • If cnt[a] > 1 (multiple occurrences): the contribution changes from a^cnt[a] to a^(cnt[a]-1)
  • The difference is: a^cnt[a] - a^(cnt[a]-1) = a^(cnt[a]-1) * (a - 1)
  • Update: cur -= (a - 1) * pow(a, cnt[a] - 1, mod) if cnt[a] > 1 else a

Step 4: Update frequencies and track maximum

  • Increment cnt[b] by 1
  • Decrement cnt[a] by 1
  • Apply modulo to keep cur within bounds: cur %= mod
  • Update the maximum score: ans = max(ans, cur)

Step 5: Return the result After sliding through all possible windows, return ans as the maximum frequency score.

The use of fast power with modulo (pow(base, exp, mod)) ensures efficient computation while preventing integer overflow. The sliding window approach reduces time complexity from O(n*k) to O(n) for the window updates.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with nums = [1, 1, 2, 2, 3] and k = 3.

Step 1: Initialize the first window [1, 1, 2]

  • Build frequency counter: cnt = {1: 2, 2: 1}
  • Calculate initial score:
    • Element 1 appears 2 times: contribution = 1^2 = 1
    • Element 2 appears 1 time: contribution = 2^1 = 2
    • Initial score cur = 1 + 2 = 3
  • Set ans = 3

Step 2: Slide to window [1, 2, 2] (remove nums[0]=1, add nums[3]=2)

  • Element to remove: a = 1 (currently has frequency 2)
  • Element to add: b = 2 (currently has frequency 1)
  • Since a ≠ b, we update incrementally:

For adding b = 2:

  • Current frequency of 2 is 1, will become 2
  • Old contribution: 2^1 = 2
  • New contribution: 2^2 = 4
  • Change: (2 - 1) * 2^1 = 1 * 2 = 2
  • Update: cur += 2

For removing a = 1:

  • Current frequency of 1 is 2, will become 1

  • Old contribution: 1^2 = 1

  • New contribution: 1^1 = 1

  • Change: (1 - 1) * 1^1 = 0

  • Update: cur -= 0

  • New score: cur = 3 + 2 - 0 = 5

  • Update frequencies: cnt = {1: 1, 2: 2}

  • Update maximum: ans = max(3, 5) = 5

Step 3: Slide to window [2, 2, 3] (remove nums[1]=1, add nums[4]=3)

  • Element to remove: a = 1 (currently has frequency 1)
  • Element to add: b = 3 (currently has frequency 0, new element)

For adding b = 3:

  • New element, frequency 0 → 1
  • Contribution: 3^1 = 3
  • Update: cur += 3

For removing a = 1:

  • Last occurrence, frequency 1 → 0

  • Removes contribution: 1^1 = 1

  • Update: cur -= 1

  • New score: cur = 5 + 3 - 1 = 7

  • Update frequencies: cnt = {1: 0, 2: 2, 3: 1}

  • Update maximum: ans = max(5, 7) = 7

Result: The maximum frequency score is 7, achieved by the subarray [2, 2, 3] where:

  • Element 2 appears 2 times: 2^2 = 4
  • Element 3 appears 1 time: 3^1 = 3
  • Total: 4 + 3 = 7

Solution Implementation

1class Solution:
2    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
3        # Define modulo constant for large number handling
4        MOD = 10**9 + 7
5      
6        # Initialize frequency counter for the first window of size k
7        frequency_map = Counter(nums[:k])
8      
9        # Calculate initial score: sum of (value^frequency) for each unique value
10        current_score = sum(pow(value, freq, MOD) for value, freq in frequency_map.items()) % MOD
11        max_score = current_score
12      
13        # Slide the window through the remaining elements
14        for i in range(k, len(nums)):
15            # Get the element leaving the window and the element entering the window
16            leaving_element = nums[i - k]
17            entering_element = nums[i]
18          
19            # Only update if the elements are different
20            if leaving_element != entering_element:
21                # Update score for the entering element
22                # If element already exists: add (value - 1) * value^(old_frequency)
23                # If new element: add value
24                if frequency_map[entering_element]:
25                    current_score += (entering_element - 1) * pow(entering_element, frequency_map[entering_element], MOD)
26                else:
27                    current_score += entering_element
28              
29                # Update score for the leaving element
30                # If frequency > 1: subtract (value - 1) * value^(new_frequency)
31                # If frequency becomes 0: subtract value
32                if frequency_map[leaving_element] > 1:
33                    current_score -= (leaving_element - 1) * pow(leaving_element, frequency_map[leaving_element] - 1, MOD)
34                else:
35                    current_score -= leaving_element
36              
37                # Apply modulo to keep number manageable
38                current_score %= MOD
39              
40                # Update frequency map
41                frequency_map[entering_element] += 1
42                frequency_map[leaving_element] -= 1
43              
44                # Track maximum score
45                max_score = max(max_score, current_score)
46      
47        return max_score
48
1class Solution {
2    // Modulo value for preventing integer overflow
3    private final int MOD = (int) 1e9 + 7;
4
5    /**
6     * Finds the maximum frequency score for any subarray of length k.
7     * The frequency score is calculated as the sum of (value^frequency) for each unique value.
8     * 
9     * @param nums the input array
10     * @param k the length of the subarray window
11     * @return the maximum frequency score modulo 10^9 + 7
12     */
13    public int maxFrequencyScore(int[] nums, int k) {
14        // Map to store frequency count of each number in current window
15        Map<Integer, Integer> frequencyMap = new HashMap<>();
16      
17        // Initialize frequency map with first k elements
18        for (int i = 0; i < k; ++i) {
19            frequencyMap.merge(nums[i], 1, Integer::sum);
20        }
21      
22        // Calculate initial score for first window
23        long currentScore = 0;
24        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
25            int value = entry.getKey();
26            int frequency = entry.getValue();
27            currentScore = (currentScore + modularPower(value, frequency)) % MOD;
28        }
29      
30        // Track maximum score found
31        long maxScore = currentScore;
32      
33        // Slide window through rest of array
34        for (int i = k; i < nums.length; ++i) {
35            int removedElement = nums[i - k];  // Element leaving the window
36            int addedElement = nums[i];        // Element entering the window
37          
38            // Only update if the elements are different
39            if (removedElement != addedElement) {
40                // Update score for added element
41                if (frequencyMap.getOrDefault(addedElement, 0) > 0) {
42                    // Element already exists, update contribution
43                    // New contribution: (value^(freq+1)) - (value^freq) = value * (value^freq - 1)
44                    currentScore += (addedElement - 1) * modularPower(addedElement, frequencyMap.get(addedElement)) % MOD;
45                } else {
46                    // New element, add its contribution (value^1 = value)
47                    currentScore += addedElement;
48                }
49              
50                // Update score for removed element
51                if (frequencyMap.getOrDefault(removedElement, 0) > 1) {
52                    // Element still exists after removal, update contribution
53                    // Removed contribution: (value^freq) - (value^(freq-1)) = value * (value^(freq-1) - 1)
54                    currentScore -= (removedElement - 1) * modularPower(removedElement, frequencyMap.get(removedElement) - 1) % MOD;
55                } else {
56                    // Last occurrence of element, remove its contribution
57                    currentScore -= removedElement;
58                }
59              
60                // Ensure non-negative score after modulo operations
61                currentScore = (currentScore + MOD) % MOD;
62              
63                // Update frequency map
64                frequencyMap.put(addedElement, frequencyMap.getOrDefault(addedElement, 0) + 1);
65                frequencyMap.put(removedElement, frequencyMap.getOrDefault(removedElement, 0) - 1);
66              
67                // Update maximum score
68                maxScore = Math.max(maxScore, currentScore);
69            }
70        }
71      
72        return (int) maxScore;
73    }
74
75    /**
76     * Computes (base^exponent) % MOD using fast exponentiation.
77     * 
78     * @param base the base number
79     * @param exponent the power to raise the base to
80     * @return (base^exponent) % MOD
81     */
82    private long modularPower(long base, long exponent) {
83        long result = 1;
84      
85        // Fast exponentiation using binary representation of exponent
86        while (exponent > 0) {
87            // If current bit is 1, multiply result by current base
88            if ((exponent & 1) == 1) {
89                result = result * base % MOD;
90            }
91            // Square the base for next bit position
92            base = base * base % MOD;
93            // Move to next bit
94            exponent >>= 1;
95        }
96      
97        return result;
98    }
99}
100
1class Solution {
2public:
3    int maxFrequencyScore(vector<int>& nums, int k) {
4        using ll = long long;
5        const int MOD = 1e9 + 7;
6      
7        // Fast modular exponentiation function: calculates (base^exponent) % MOD
8        auto modularPower = [&](ll base, ll exponent) {
9            ll result = 1;
10            while (exponent > 0) {
11                // If exponent is odd, multiply base with result
12                if (exponent & 1) {
13                    result = (result * base) % MOD;
14                }
15                // Square the base and halve the exponent
16                base = (base * base) % MOD;
17                exponent >>= 1;
18            }
19            return result;
20        };
21      
22        // Initialize frequency map for the first window of size k
23        unordered_map<int, int> frequencyMap;
24        for (int i = 0; i < k; ++i) {
25            frequencyMap[nums[i]]++;
26        }
27      
28        // Calculate initial score for the first window
29        // Score = sum of (value^frequency) for each unique value
30        ll currentScore = 0;
31        for (auto& [value, frequency] : frequencyMap) {
32            currentScore = (currentScore + modularPower(value, frequency)) % MOD;
33        }
34      
35        ll maxScore = currentScore;
36      
37        // Slide the window through the rest of the array
38        for (int i = k; i < nums.size(); ++i) {
39            int removedElement = nums[i - k];  // Element leaving the window
40            int addedElement = nums[i];        // Element entering the window
41          
42            // Only update if the elements are different
43            if (removedElement != addedElement) {
44                // Update score for the element being added
45                // If element exists: add difference between new and old contribution
46                // If new element: add its contribution (value^1 = value)
47                if (frequencyMap[addedElement] > 0) {
48                    ll oldContribution = modularPower(addedElement, frequencyMap[addedElement]);
49                    ll newContribution = modularPower(addedElement, frequencyMap[addedElement] + 1);
50                    currentScore = (currentScore - oldContribution + newContribution + MOD) % MOD;
51                } else {
52                    currentScore = (currentScore + addedElement) % MOD;
53                }
54              
55                // Update score for the element being removed
56                // If frequency > 1: subtract difference between old and new contribution
57                // If frequency = 1: subtract its contribution (element is removed completely)
58                if (frequencyMap[removedElement] > 1) {
59                    ll oldContribution = modularPower(removedElement, frequencyMap[removedElement]);
60                    ll newContribution = modularPower(removedElement, frequencyMap[removedElement] - 1);
61                    currentScore = (currentScore - oldContribution + newContribution + MOD) % MOD;
62                } else {
63                    currentScore = (currentScore - removedElement + MOD) % MOD;
64                }
65              
66                // Update frequency map
67                frequencyMap[addedElement]++;
68                frequencyMap[removedElement]--;
69              
70                // Update maximum score
71                maxScore = max(maxScore, currentScore);
72            }
73        }
74      
75        return maxScore;
76    }
77};
78
1function maxFrequencyScore(nums: number[], k: number): number {
2    const MOD = 1e9 + 7;
3  
4    /**
5     * Fast modular exponentiation function
6     * Calculates (base^exponent) % MOD efficiently using binary exponentiation
7     */
8    const modularPower = (base: number, exponent: number): number => {
9        let result = 1;
10        base = base % MOD;
11      
12        while (exponent > 0) {
13            // If exponent is odd, multiply base with result
14            if (exponent & 1) {
15                result = (result * base) % MOD;
16            }
17            // Square the base and halve the exponent
18            base = (base * base) % MOD;
19            exponent >>= 1;
20        }
21        return result;
22    };
23  
24    // Initialize frequency map for the first window of size k
25    const frequencyMap = new Map<number, number>();
26    for (let i = 0; i < k; i++) {
27        frequencyMap.set(nums[i], (frequencyMap.get(nums[i]) || 0) + 1);
28    }
29  
30    // Calculate initial score for the first window
31    // Score = sum of (value^frequency) for each unique value
32    let currentScore = 0;
33    for (const [value, frequency] of frequencyMap.entries()) {
34        currentScore = (currentScore + modularPower(value, frequency)) % MOD;
35    }
36  
37    let maxScore = currentScore;
38  
39    // Slide the window through the rest of the array
40    for (let i = k; i < nums.length; i++) {
41        const removedElement = nums[i - k];  // Element leaving the window
42        const addedElement = nums[i];        // Element entering the window
43      
44        // Only update if the elements are different
45        if (removedElement !== addedElement) {
46            const currentAddedFrequency = frequencyMap.get(addedElement) || 0;
47            const currentRemovedFrequency = frequencyMap.get(removedElement) || 0;
48          
49            // Update score for the element being added
50            // If element exists: add difference between new and old contribution
51            // If new element: add its contribution (value^1 = value)
52            if (currentAddedFrequency > 0) {
53                const oldContribution = modularPower(addedElement, currentAddedFrequency);
54                const newContribution = modularPower(addedElement, currentAddedFrequency + 1);
55                currentScore = (currentScore - oldContribution + newContribution + MOD) % MOD;
56            } else {
57                currentScore = (currentScore + addedElement) % MOD;
58            }
59          
60            // Update score for the element being removed
61            // If frequency > 1: subtract difference between old and new contribution
62            // If frequency = 1: subtract its contribution (element is removed completely)
63            if (currentRemovedFrequency > 1) {
64                const oldContribution = modularPower(removedElement, currentRemovedFrequency);
65                const newContribution = modularPower(removedElement, currentRemovedFrequency - 1);
66                currentScore = (currentScore - oldContribution + newContribution + MOD) % MOD;
67            } else {
68                currentScore = (currentScore - removedElement + MOD) % MOD;
69            }
70          
71            // Update frequency map
72            frequencyMap.set(addedElement, currentAddedFrequency + 1);
73            frequencyMap.set(removedElement, currentRemovedFrequency - 1);
74          
75            // Remove element from map if frequency becomes 0
76            if (frequencyMap.get(removedElement) === 0) {
77                frequencyMap.delete(removedElement);
78            }
79          
80            // Update maximum score
81            maxScore = Math.max(maxScore, currentScore);
82        }
83    }
84  
85    return maxScore;
86}
87

Time and Space Complexity

The time complexity is O(n × k), where n is the length of the array nums and k is the window size. This is because:

  • The initial window setup takes O(k) time to process the first k elements
  • The main while loop runs n - k times
  • In each iteration, the pow(b, cnt[b], mod) and pow(a, cnt[a] - 1, mod) operations take O(log(cnt[b])) and O(log(cnt[a])) time respectively
  • In the worst case, cnt[b] or cnt[a] can be at most k, making each power operation O(log k)
  • Therefore, the overall time complexity is O(k) + O((n - k) × log k) = O(n × log k)

However, upon closer examination, the initial computation sum(pow(k, v, mod) for k, v in cnt.items()) uses variable k incorrectly (it shadows the parameter k). This should be sum(pow(key, v, mod) for key, v in cnt.items()). Each pow(key, v, mod) operation takes O(log v) time, and in the worst case v can be k, so this initial computation takes O(k × log k) time.

Since k ≤ n, the overall time complexity simplifies to O(n × log n) when considering k can be as large as n.

The space complexity is O(n) because:

  • The Counter object cnt can store at most min(k, n) unique elements, which is O(n) in the worst case
  • Other variables use constant space

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Modulo Application During Incremental Updates

One of the most common mistakes is forgetting that subtraction with modulo arithmetic can produce negative results. When we subtract a value from current_score, the result might become negative, and applying % operator in Python on a negative number doesn't give the expected result in modular arithmetic.

Problem Example:

# If current_score = 5 and we subtract 10
current_score = 5
current_score -= 10  # current_score = -5
current_score %= MOD  # This gives 10^9 + 2, not the mathematically correct value

Solution: Always ensure the result is positive before applying modulo, or add MOD before taking modulo:

current_score = (current_score - value + MOD) % MOD

2. Integer Overflow in Power Calculation

When computing (entering_element - 1) * pow(entering_element, frequency_map[entering_element], MOD), the multiplication happens after the power calculation. Even though pow returns a value less than MOD, multiplying it by (entering_element - 1) can cause overflow if the values are large.

Solution: Apply modulo after each multiplication:

contribution = ((entering_element - 1) * pow(entering_element, frequency_map[entering_element], MOD)) % MOD
current_score = (current_score + contribution) % MOD

3. Not Handling Zero Frequencies Properly

The code checks if frequency_map[entering_element] to determine if an element is new. However, after decrementing, elements with zero frequency remain in the Counter, which could lead to incorrect calculations if not handled properly.

Solution: Either remove elements with zero frequency or consistently check for zero values:

if frequency_map[leaving_element] == 1:
    del frequency_map[leaving_element]  # Remove from map entirely
else:
    frequency_map[leaving_element] -= 1

4. Forgetting Edge Cases in Window Updates

A subtle bug can occur if we don't handle the case where the same element is both entering and leaving the window (when leaving_element == entering_element). The current code correctly skips updates in this case, but developers might accidentally process both additions and removals, leading to incorrect scores.

Solution: Always check if the entering and leaving elements are the same before making any updates:

if leaving_element == entering_element:
    continue  # No change needed, skip to next iteration

5. Inefficient Power Recalculation

While the code uses incremental updates, some developers might accidentally recalculate the entire score for each window, which defeats the purpose of the sliding window optimization.

Incorrect approach:

# Don't do this - O(k) per window
for i in range(k, len(nums)):
    frequency_map = Counter(nums[i-k+1:i+1])  # Recounting entire window
    current_score = sum(pow(v, f, MOD) for v, f in frequency_map.items())

Correct approach: Use incremental updates as shown in the original solution to maintain O(1) updates per window movement.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Sliding Window Maximum

https assets algo monster cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in the window The window

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More