Maximum Frequency Score of a Subarray - Practice Coding Problems

Maximum Frequency Score of a Subarray - Problem

Array Hash Table Math Stack Sliding Window Hard

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 10⁹ + 7.

For example, the frequency score of the array [5,4,5,7,4,4] is (4³ + 5² + 7¹) modulo (10⁹ + 7) = 96.

Return the maximum frequency score of a subarray of size k in nums. You should maximize the value under the modulo and not the actual value.

A subarray is a contiguous part of an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,6,4], k = 3

› Output: 72

💡 Note: Window [1,2,6]: score = 1¹ + 2¹ + 6¹ = 9. Window [2,6,4]: score = 2¹ + 6¹ + 4¹ = 12. Maximum is 12. Wait, let me recalculate: actually we need frequency powers. [2,6,4] has frequencies {2:1, 6:1, 4:1}, so score = 2¹ + 6¹ + 4¹ = 12.

Example 2 — Repeated Elements

$ Input: nums = [5,4,5,7,4,4], k = 6

› Output: 96

💡 Note: Only one window of size 6: [5,4,5,7,4,4]. Frequencies: {5:2, 4:3, 7:1}. Score = 5² + 4³ + 7¹ = 25 + 64 + 7 = 96.

Example 3 — Small Window

$ Input: nums = [2,2], k = 1

› Output: 2

💡 Note: Two windows: [2] and [2]. Each has frequency {2:1}, score = 2¹ = 2. Maximum is 2.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ k ≤ nums.length
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with elements and window size k

Calculate Frequencies

Count occurrences in each subarray

Compute Score

Sum of value^frequency for each unique element

Key Takeaway

🎯 Key Insight: Use sliding window to efficiently calculate frequency scores for all k-sized subarrays and track the maximum

Asked in

G Google 25 f Facebook 18 a Amazon 15 M Microsoft 12

The key insight is to use sliding window technique to efficiently examine all subarrays of size k while maintaining frequency counts. Best approach uses sliding window with frequency map updates. Time: O(n×k×log(max_freq)), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subarrays	O(n×k×log(max_freq))	O(k)	Generate every subarray of size k and calculate frequency score for each
Sliding Window with Frequency Map	O(n×k×log(max_freq))	O(k)	Use sliding window technique to efficiently update frequencies as we move the window

Brute Force - Check All Subarrays — Algorithm Steps

Iterate through all valid starting positions (0 to n-k)
For each position, extract subarray of size k
Count frequency of each element in subarray
Calculate frequency score using modular exponentiation
Track maximum score found

Visualization

Tap to expand

Step-by-Step Walkthrough

Position 0

Check first k elements

Position 1

Check next k elements

Calculate

Find maximum score

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_SIZE 1000

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp >> 1;
        base = (base * base) % mod;
    }
    return result;
}

long long calculateScore(int* arr, int size) {
    int freq[2001] = {0};
    int offset = 1000;
    
    for (int i = 0; i < size; i++) {
        freq[arr[i] + offset]++;
    }
    
    long long score = 0;
    for (int i = 0; i < 2001; i++) {
        if (freq[i] > 0) {
            int val = i - offset;
            score = (score + modPow(val, freq[i], MOD)) % MOD;
        }
    }
    return score;
}

long long solution(int* nums, int n, int k) {
    long long maxScore = 0;
    
    for (int i = 0; i <= n - k; i++) {
        long long score = calculateScore(nums + i, k);
        if (score > maxScore) {
            maxScore = score;
        }
    }
    
    return maxScore;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[MAX_SIZE];
    int n = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    long long result = solution(nums, n, k);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×k×log(max_freq))

n-k+1 subarrays, each requires O(k) frequency counting and O(k×log(max_freq)) for power calculations

⚡ Linearithmic

Space Complexity

O(k)

Hash map to store frequencies of at most k elements

✓ Linear Space

28.5K Views

Medium-High Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler