Maximum Frequency Score of a Subarray

Problem

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 109 + 7.

For example, the frequency score of the array [5,4,5,7,4,4] is (43 + 52 + 71) modulo (109 + 7) = 96.

Return _themaximum frequency score of a subarray of size _k innums. You should maximize the value under the modulo and not the actual value.

A subarray is a contiguous part of an array.

Examples

Example 1:

1
2
3


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:

1
2
3


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^5
1 <= nums[i] <= 10^6

Solution

Method 1 – Sliding Window with Hash Map

Intuition

We want to efficiently compute the frequency score for every subarray of size k. By using a sliding window and a hash map to track frequencies, we can update the score incrementally as the window moves.

Approach

Use a hash map to count the frequency of each number in the current window.
For each new element added to the window, update its frequency and the running score.
For each element removed from the window, update its frequency and the running score.
For each window of size k, compute the frequency score as the sum of val^freq for all distinct values, modulo 10^9 + 7.
Track and return the maximum frequency score found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    int maxFrequencyScore(vector<int>& nums, int k) {
        const int MOD = 1e9+7;
        unordered_map<int, int> freq;
        int n = nums.size();
        long long score = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            freq[nums[i]]++;
            if (i >= k) {
                freq[nums[i-k]]--;
                if (freq[nums[i-k]] == 0) freq.erase(nums[i-k]);
            }
            if (i >= k-1) {
                long long cur = 0;
                for (auto& [v, f] : freq) {
                    long long t = 1;
                    for (int j = 0; j < f; ++j) t = t * v % MOD;
                    cur = (cur + t) % MOD;
                }
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


func maxFrequencyScore(nums []int, k int) int {
    mod := int(1e9+7)
    freq := map[int]int{}
    ans := 0
    for i, v := range nums {
        freq[v]++
        if i >= k {
            freq[nums[i-k]]--
            if freq[nums[i-k]] == 0 {
                delete(freq, nums[i-k])
            }
        }
        if i >= k-1 {
            cur := 0
            for val, f := range freq {
                t := 1
                for j := 0; j < f; j++ {
                    t = t * val % mod
                }
                cur = (cur + t) % mod
            }
            if cur > ans {
                ans = cur
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
    public int maxFrequencyScore(int[] nums, int k) {
        int mod = 1000000007, n = nums.length, ans = 0;
        Map<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i < n; i++) {
            freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
            if (i >= k) {
                freq.put(nums[i-k], freq.get(nums[i-k]) - 1);
                if (freq.get(nums[i-k]) == 0) freq.remove(nums[i-k]);
            }
            if (i >= k-1) {
                int cur = 0;
                for (var e : freq.entrySet()) {
                    long t = 1;
                    for (int j = 0; j < e.getValue(); j++) t = t * e.getKey() % mod;
                    cur = (int)((cur + t) % mod);
                }
                ans = Math.max(ans, cur);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    fun maxFrequencyScore(nums: IntArray, k: Int): Int {
        val mod = 1_000_000_007
        val freq = mutableMapOf<Int, Int>()
        var ans = 0
        for (i in nums.indices) {
            freq[nums[i]] = freq.getOrDefault(nums[i], 0) + 1
            if (i >= k) {
                freq[nums[i-k]] = freq.getOrDefault(nums[i-k], 0) - 1
                if (freq[nums[i-k]] == 0) freq.remove(nums[i-k])
            }
            if (i >= k-1) {
                var cur = 0L
                for ((v, f) in freq) {
                    var t = 1L
                    repeat(f) { t = t * v % mod }
                    cur = (cur + t) % mod
                }
                ans = maxOf(ans, cur.toInt())
            }
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def maxFrequencyScore(self, nums: list[int], k: int) -> int:
        from collections import defaultdict
        mod = 10**9+7
        freq = defaultdict(int)
        ans = 0
        for i, v in enumerate(nums):
            freq[v] += 1
            if i >= k:
                freq[nums[i-k]] -= 1
                if freq[nums[i-k]] == 0:
                    del freq[nums[i-k]]
            if i >= k-1:
                cur = 0
                for val, f in freq.items():
                    t = pow(val, f, mod)
                    cur = (cur + t) % mod
                ans = max(ans, cur)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


impl Solution {
    pub fn max_frequency_score(nums: Vec<i32>, k: i32) -> i32 {
        use std::collections::HashMap;
        let modn = 1_000_000_007;
        let mut freq = HashMap::new();
        let mut ans = 0;
        for (i, &v) in nums.iter().enumerate() {
            *freq.entry(v).or_insert(0) += 1;
            if i as i32 >= k {
                let e = freq.get_mut(&nums[i - k as usize]).unwrap();
                *e -= 1;
                if *e == 0 { freq.remove(&nums[i - k as usize]); }
            }
            if i as i32 >= k - 1 {
                let mut cur = 0;
                for (&val, &f) in &freq {
                    let mut t = 1i64;
                    for _ in 0..f {
                        t = t * val as i64 % modn;
                    }
                    cur = (cur + t) % modn;
                }
                ans = ans.max(cur as i32);
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
    maxFrequencyScore(nums: number[], k: number): number {
        const mod = 1e9+7;
        const freq = new Map<number, number>();
        let ans = 0;
        for (let i = 0; i < nums.length; i++) {
            freq.set(nums[i], (freq.get(nums[i]) ?? 0) + 1);
            if (i >= k) {
                freq.set(nums[i-k], freq.get(nums[i-k])! - 1);
                if (freq.get(nums[i-k]) === 0) freq.delete(nums[i-k]);
            }
            if (i >= k-1) {
                let cur = 0;
                for (const [val, f] of freq.entries()) {
                    let t = 1;
                    for (let j = 0; j < f; j++) t = t * val % mod;
                    cur = (cur + t) % mod;
                }
                ans = Math.max(ans, cur);
            }
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n * m), where n is the length of nums and m is the number of distinct values in a window (worst case up to k).
🧺 Space complexity: O(m), for the frequency map.

Problem#

Examples#

Solution#

Method 1 – Sliding Window with Hash Map#

Intuition#

Approach#

Code#

Complexity#