2524. Maximum Frequency Score of a Subarray


Problem Description

In this problem, you are provided with an integer array nums and a positive integer k. Your task is to find the maximum frequency score of any subarray of size k.

A frequency score is calculated by taking unique values in the array, raising each to the power of how frequently they appear in the subarray (their frequency), then summing these values up. The final score is computed using the modulo operator with 10^9 + 7.

Consider an array [5,4,5,7,4,4]. The frequency score is calculated by:

  • The number 4 appears 3 times, so 4^3 = 64.
  • The number 5 appears 2 times, so 5^2 = 25.
  • The number 7 appears 1 time, so 7^1 = 7.

The frequency score is (64 + 25 + 7) % (10^9 + 7) = 96.

What you need to find is the subarray of exactly k elements which has the highest frequency score. A subarray is simply a contiguous segment of the array.

Intuition

To arrive at the solution for this problem, the intuition follows the idea of a sliding window combined with efficient calculation of powers and modulo operations.

Since you need to find the maximum frequency score of any subarray with size k, you'll want to look at each possible subarray of that size. This is a classic case for using a sliding window technique, that allows you to iterate over subarrays of size k efficiently without re-calculating everything from scratch for each subarray.

The code must maintain and update a count of the occurrences of each distinct element in the current window. The Counter from Python's collections library is handy for this task. When the window slides, you update the count for the element that leaves the window (decreasing its frequency) and for the one that enters (increasing its frequency).

Another key part of the intuition behind the solution is handling the modulo operation efficiently. To avoid large intermediate values, the modulo operator should be used smartly during the calculations. The solution involves incrementally updating the total score of the window and applying modulo 10^9 + 7 to keep numbers within a manageable range.

There's a neat little optimization to avoid re-computing powers from scratch. The code updates the contribution to the score of a number using (b - 1) * pow(b, cnt[b], mod) for a number entering the window and (a - 1) * pow(a, cnt[a] - 1, mod) for a number exiting the window. This takes advantage of the existing counts to update the score, which limits the need for recalculating exponents.

The mod variable is used to apply the modulo operator to all intermediate sums so that the final result is under the modulo of 10^9 + 7.

The solution keeps track of the current score (cur) and continuously updates it while sliding the window through the array. The maximum score encountered (ans) is the value returned at the end.

Solution Approach

The solution makes use of a few important programming and algorithmic concepts: sliding window technique, hashing (via the Counter from Python's collections library), and modular arithmetic. Here's a step-by-step explanation of the approach:

  1. Initialize a variable mod to 10**9 + 7 to store the modulus value for later operations.

  2. Use the Counter to count the frequency of each distinct element within the first subarray of size k in nums. This establishes the initial state of the window.

  3. Calculate the initial frequency score using a sum of powers of each unique element multiplied by its respective frequency, with each intermediate result taken modulo mod.

  4. Store both the current frequency score (cur) and the maximum score (ans) observed so far. Initially, cur is the frequency score of the first window and ans is set to the same value.

  5. Iterate through the elements of nums starting from index k to the end, effectively sliding the window across the array. For each iteration:

    • Compute the new frequency score when a new element enters the subarray from the right, and an old element leaves from the left.
    • If the incoming and outgoing elements are different, update the current frequency score (cur) as follows:
      • For the element entering the window (let's call it b), increment its count and update cur by adding (b - 1) * pow(b, cnt[b], mod). If b wasn't previously in the counter (i.e., cnt[b] is 0), just add b.
      • For the element leaving the window (let's call it a), decrement its count and update cur by subtracting (a - 1) * pow(a, cnt[a] - 1, mod). If a's new frequency is now below or equal to 1, just subtract a.
    • Apply the modulo operation to the current frequency score to ensure the result stays within the allowed range.
    • Update the maximum score ans if the new cur is larger.
  6. After finishing the iteration over the array, return the highest frequency score (ans) found during the sliding window process.

This approach ensures that only relevant elements are considered for the score calculation and that the calculation is as efficient as possible. The solution effectively handles each subarray of size k without recalculating the entire frequency score from scratch and uses modular arithmetic to manage large numbers.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's walk through a small example using the solution approach described above.

Given the integer array nums = [3, 2, 2, 3, 3] and k = 3, we want to find the maximum frequency score of any subarray of size k.

  1. We initialize our modulus mod to 10**9 + 7 for the modulo operations.

  2. Starting with the first subarray [3, 2, 2], we use a Counter to count the frequency of each number. We get:

    • 3: 1 occurrence
    • 2: 2 occurrences
  3. We calculate the initial frequency score:

    • For 3, the score component is 3^1 = 3.
    • For 2, the score component is 2^2 = 4.
    • Summing them up, we get an initial score cur of 3 + 4 = 7.
  4. We set ans = cur, so ans = 7 as the maximum score observed so far.

  5. We slide the window to the next subarray [2, 2, 3] by removing the first element (3) and adding the next element (3) after the initial subarray.

    • Before doing that, our current frequency score is cur = 7.
    • The element leaving the window is 3 (frequency was 1).
    • The element entering the window is another 3 (frequency will be 2).
    • For the exiting 3, we subtract 3^1 = 3 from cur which becomes 7 - 3 = 4.
    • For the incoming 3, we add 3^2 = 9 since the count of 3 is increasing from 1 to 2.
    • Our new cur is 4 + 9 = 13, so we apply modulo to cur: cur = 13 % (10^9 + 7) = 13.
    • We compare cur with ans and cur is greater, so we update ans to 13.
  6. Next, we continue sliding the window to get to the subarray [2, 3, 3] and perform similar calculations. The element leaving is 2 (its frequency will be 1), and the incoming element is 3 (its frequency will be 3).

    • Our current frequency score cur is 13.
    • For the exiting 2, we subtract 2^1 = 2 from cur, which becomes 13 - 2 = 11.
    • For the incoming 3, we add 3^3 = 27 and our new cur is 11 + 27 = 38.
    • After applying the modulo operation, cur = 38 % (10^9 + 7) = 38.
    • We compare cur with ans, and cur is greater, so we update ans to 38.
  7. Having finished sliding the window through the array, we find that the maximum frequency score (ans) is 38. This is the final answer.

In conclusion, sliding across the subarray [2, 3, 3], we reach the highest frequency score of 38 for the array nums = [3, 2, 2, 3, 3] with k = 3.

Python Solution

1from collections import Counter
2
3class Solution:
4    def max_frequency_score(self, nums, k):
5        # Define the modulus for the calculations as per the problem statement, which is 10^9 + 7
6        mod = 10**9 + 7
7      
8        # Create a Counter for the first 'k' elements in the list
9        counter = Counter(nums[:k])
10      
11        # Calculate the initial score by raising 'k' to the power of the frequency count, modulo 'mod'
12        current_score = sum(pow(num, frequency, mod) for num, frequency in counter.items()) % mod
13      
14        # Set the 'answer' to the initial score, it will keep track of the highest score
15        answer = current_score
16      
17        # Start iterating from the 'k'th element in 'nums'
18        i = k
19        while i < len(nums):
20            # 'previous_num' is the number which will be excluded from the current window
21            # 'new_num' is the number which will be included in the current window
22            previous_num, new_num = nums[i - k], nums[i]
23          
24            # Only process if we're examining a new number; otherwise, skip re-calculation
25            if previous_num != new_num:
26                # Increase the score by the power of the count of the new number, if it already exists
27                current_score += (new_num - 1) * pow(new_num, counter[new_num], mod) if counter[new_num] else new_num
28              
29                # Decrease the score by the power of the count of the previous number, if necessary
30                current_score -= (previous_num - 1) * pow(previous_num, counter[previous_num] - 1, mod) if counter[previous_num] > 1 else previous_num
31              
32                # Ensure the current score does not exceed 'mod'
33                current_score %= mod
34              
35                # Update the counter for the new window
36                counter[new_num] += 1
37                counter[previous_num] -= 1
38              
39                # Update the answer if the current score is higher
40                answer = max(answer, current_score)
41          
42            # Move to the next element
43            i += 1
44      
45        # Return the highest score found
46        return answer
47

Java Solution

1import java.util.Map;
2import java.util.HashMap;
3
4class Solution {
5    private final int MOD = (int) 1e9 + 7;
6
7    // Method to find the maximum frequency score of a sequence
8    public int maxFrequencyScore(int[] nums, int k) {
9        // Map to store the frequency of each number
10        Map<Integer, Integer> frequencyMap = new HashMap<>();
11      
12        // Populate the map with the frequency of first k numbers
13        for (int i = 0; i < k; ++i) {
14            frequencyMap.merge(nums[i], 1, Integer::sum);
15        }
16      
17        long currentScore = 0;
18        // Calculate the initial score based on the first k elements
19        for (var entry : frequencyMap.entrySet()) {
20            currentScore = (currentScore + quickPower(entry.getKey(), entry.getValue())) % MOD;
21        }
22      
23        long maxScore = currentScore;
24      
25        // Iterate through the rest of the array, updating the score
26        for (int i = k; i < nums.length; ++i) {
27            int removedNum = nums[i - k];
28            int addedNum = nums[i];
29
30            // Update score only if the incoming and outgoing elements are different
31            if (removedNum != addedNum) {
32                // Decrease score for the removed number
33                if (frequencyMap.getOrDefault(addedNum, 0) > 0) {
34                    currentScore += (addedNum - 1) * quickPower(addedNum, frequencyMap.get(addedNum)) % MOD;
35                } else {
36                    currentScore += addedNum;
37                }
38
39                // Increase score for the added number
40                if (frequencyMap.getOrDefault(removedNum, 0) > 1) {
41                    currentScore -= (removedNum - 1) * quickPower(removedNum, frequencyMap.get(removedNum) - 1) % MOD;
42                } else {
43                    currentScore -= removedNum;
44                }
45              
46                // Normalize the current score to be within the range of MOD
47                currentScore = (currentScore + MOD) % MOD;
48
49                // Update the frequencies of the added and removed numbers
50                frequencyMap.put(addedNum, frequencyMap.getOrDefault(addedNum, 0) + 1);
51                frequencyMap.put(removedNum, frequencyMap.getOrDefault(removedNum, 0) - 1);
52
53                // Check if the current score is the maximum score so far
54                maxScore = Math.max(maxScore, currentScore);
55            }
56        }
57      
58        // Cast the max score to int before returning as per the method signature
59        return (int) maxScore;
60    }
61
62    // Helper method to perform quick power (exponentiation by squaring)
63    private long quickPower(long base, long exponent) {
64        long result = 1;
65        while (exponent > 0) {
66            if ((exponent & 1) == 1) {
67                result = result * base % MOD;
68            }
69            base = base * base % MOD;
70            exponent >>= 1;
71        }
72        return result;
73    }
74}
75

C++ Solution

1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5class Solution {
6public:
7    // Method to calculate the max frequency score
8    int maxFrequencyScore(vector<int>& nums, int k) {
9        using ll = long long; // Define type alias for long long
10        const int mod = 1e9 + 7; // Define the modulus for calculations
11
12        // Quick power function for calculating a^n % mod efficiently
13        auto quickPower = [&](ll base, ll exponent) {
14            ll result = 1;
15            while (exponent > 0) {
16                if (exponent & 1) { // If the current bit is 1
17                    result = result * base % mod; // Multiply the base
18                }
19                base = base * base % mod; // Square the base for next bit
20                exponent >>= 1; // Right-shift exponent for next bit
21            }
22            return result;
23        };
24
25        // Count the frequency of each number in the first k elements
26        unordered_map<int, int> frequencyCounter;
27        for (int i = 0; i < k; ++i) {
28            frequencyCounter[nums[i]]++;
29        }
30
31        // Calculate initial score based on frequency
32        ll currentScore = 0;
33        for (auto& [number, count] : frequencyCounter) {
34            currentScore = (currentScore + quickPower(number, count)) % mod;
35        }
36
37        // Initial answer is the current score
38        ll maxScore = currentScore;
39
40        // Slide the window and update the score
41        for (int i = k; i < nums.size(); ++i) {
42            // Old and new numbers at the ends of the current window
43            int oldNumber = nums[i - k], newNumber = nums[i];
44
45            if (oldNumber != newNumber) {
46                // Update current score based on the new and old number counts
47                currentScore += frequencyCounter[newNumber] ? (newNumber - 1) * quickPower(newNumber, frequencyCounter[newNumber]) % mod : newNumber;
48                currentScore -= frequencyCounter[oldNumber] > 1 ? (oldNumber - 1) * quickPower(oldNumber, frequencyCounter[oldNumber] - 1) % mod : oldNumber;
49                // Modulo operation to keep the score within valid range
50                currentScore = (currentScore + mod) % mod;
51                maxScore = std::max(maxScore, currentScore);
52
53                // Update counts for the new and old numbers
54                frequencyCounter[newNumber]++;
55                frequencyCounter[oldNumber]--;
56            }
57        }
58
59        // Return the maximum score obtained
60        return maxScore;
61    }
62};
63

Typescript Solution

1function maxFrequencyScore(nums: number[], k: number): number {
2    type ll = number; // Using 'number' type to represent long long in this context
3
4    const mod: ll = 1e9 + 7; // Define the modulus for calculations
5
6    // Quick power function for calculating a^n % mod efficiently
7    const quickPower = (base: ll, exponent: ll): ll => {
8        let result: ll = 1;
9        while (exponent > 0) {
10            if (exponent & 1) { // If the current bit is 1
11                result = (result * base) % mod; // Multiply the base
12            }
13            base = (base * base) % mod; // Square the base for next bit
14            exponent >>= 1; // Right-shift exponent for next bit
15        }
16        return result;
17    };
18
19    // Count the frequency of each number in the first k elements
20    const frequencyCounter: Record<number, number> = {};
21    for (let i = 0; i < k; ++i) {
22        frequencyCounter[nums[i]] = (frequencyCounter[nums[i]] || 0) + 1;
23    }
24
25    // Calculate initial score based on frequency
26    let currentScore: ll = 0;
27    for (const number in frequencyCounter) {
28        currentScore = (currentScore + quickPower(+number, frequencyCounter[number])) % mod;
29    }
30
31    // Initial maxScore is the current score
32    let maxScore: ll = currentScore;
33
34    // Slide the window and update the score
35    for (let i = k; i < nums.length; ++i) {
36        // Old and new numbers at the ends of the current window
37        const oldNumber: number = nums[i - k], newNumber: number = nums[i];
38
39        if (oldNumber !== newNumber) {
40            // Update current score based on the new and old number counts
41            currentScore += (frequencyCounter[newNumber] ? ((newNumber - 1) * quickPower(newNumber, frequencyCounter[newNumber])) % mod : newNumber);
42            currentScore -= (frequencyCounter[oldNumber] > 1 ? ((oldNumber - 1) * quickPower(oldNumber, frequencyCounter[oldNumber] - 1)) % mod : oldNumber);
43            // Modulo operation to keep the score within a valid range
44            currentScore = (currentScore % mod + mod) % mod;
45            maxScore = Math.max(maxScore, currentScore);
46
47            // Update counts for the new and old numbers
48            frequencyCounter[newNumber] = (frequencyCounter[newNumber] || 0) + 1;
49            if (frequencyCounter[oldNumber] > 1) {
50                frequencyCounter[oldNumber]--;
51            } else {
52                delete frequencyCounter[oldNumber];
53            }
54        }
55    }
56
57    // Return the maximum score obtained
58    return maxScore;
59}
60

Time and Space Complexity

Time Complexity

The time complexity of the code can be analyzed as follows:

  1. Sorting the nums[:k] list (implicitly done by Counter initializer): O(k * log(k))
  2. Iterating over the items in the Counter object to calculate the initial ans: O(u), where u is the number of unique elements in nums[:k].
  3. The main loop runs from i = k to len(nums), which gives us O(n - k) iterations, where n is the total number of elements in nums. Inside this loop:
    • Updating cur involves a constant number of arithmetic operations and power calculations: the power calculations can be considered constant time since the exponents are bounded by k (which is the maximum frequency a number can have in nums[:k]), and modulo is O(1).
    • The cnt dictionary update takes O(1) per iteration because dictionaries in Python offer constant time complexity for setting and getting elements. Therefore, this part of the loop contributes O(n - k) to the time complexity.

Combining all parts, the total time complexity is dominated by the largest term, resulting in O(n) for the overall complexity, assuming that k << n and disregarding the less significant terms.

Space Complexity

The space complexity can be analyzed as follows:

  1. The cnt dictionary space usage is O(u), where u is the number of unique elements in nums[:k].
  2. Other variables such as ans, cur, i, a, and b use constant space O(1).

Therefore, the overall space complexity of the program is O(u), which is the space needed to store the count of unique elements in the initial segment of nums.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫