Apply Operations to Maximize Frequency Score solution and explanation
Google
4 more videos on this problem
Apply Operations to Maximize Frequency Score | Weekly Contest 376 | Leetcode 2968codestorywithMIK · 1:06:03 · 6K views
2968. Apply Operations to Maximize Frequency Score | Weekly Leetcode 376codingMohan · 40:27 · 1K views
2968 || Apply Operations to Maximize Frequency Score || Leetcode Hard || Weekly Contest 376Harsit Sinha · 27:49 · 222 views
2968. Apply Operations to Maximize Frequency Score (Leetcode Hard)Programming Live with Larry · 56:37 · 182 views
Apply Operations to Maximize Frequency Score - LeetCode 2968 - PythonAlpha-Code · 37:01 · 144 views
The problem
You are given a 0-indexed integer array nums and an integer k.
You can perform the following operation on the array at most k times:
- Choose any index
ifrom the array and increase or decreasenums[i]by1.
The score of the final array is the frequency of the most frequent element in the array.
Return the maximum score you can achieve.
The frequency of an element is the number of occurences of that element in the array.
Example 1:
Input: nums = [1,2,6,4], k = 3 Output: 3 Explanation: We can do the following operations on the array: - Choose i = 0, and increase the value of nums[0] by 1. The resulting array is [2,2,6,4]. - Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,3]. - Choose i = 3, and decrease the value of nums[3] by 1. The resulting array is [2,2,6,2]. The element 2 is the most frequent in the final array so our score is 3. It can be shown that we cannot achieve a better score.
Example 2:
Input: nums = [1,4,4,2,4], k = 0 Output: 3 Explanation: We cannot apply any operations so our score will be the frequency of the most frequent element in the original array, which is 3.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1090 <= k <= 1014
Approach overview
Problem Overview: You are given an array and a limit on operations. Each operation increases an element, and the goal is to maximize the frequency score of equal values after performing at most k operations. The challenge is determining the largest group of numbers that can be adjusted to the same value without exceeding the operation budget.
Approach 1: Sliding Window (Sorting + Cost Tracking) (Time: O(n log n), Space: O(1))
Sort the array so values grow monotonically. Then use a classic two‑pointer sliding window. The right pointer expands the window while the left pointer shrinks it when the cost exceeds k. The key idea: if you want all numbers in the window to match nums[right], the cost equals nums[right] * window_size - window_sum. Maintain the running sum of the window to compute this efficiently. This approach avoids recomputation and finds the maximum valid window length in linear time after sorting.
Approach 2: Binary Search + Prefix Sum (Time: O(n log n), Space: O(n))
Another way is to binary search the answer (the maximum achievable frequency). After sorting, precompute a prefix sum array to query sums quickly. For a candidate frequency f, check every window of size f. The target value becomes the largest element in the window, and the cost to raise all other values is computed using the prefix sums. If the required operations stay within k, that frequency is feasible. Binary search narrows down the maximum valid frequency.
Approach 3: Custom Frequency Analysis with Priority Handling (Time: O(n log n), Space: O(n))
This strategy maintains candidate values and dynamically tracks the cost of aligning nearby elements. A priority or ordered structure helps determine which elements require the least incremental operations. The algorithm gradually grows candidate groups while maintaining the operation budget. While more complex, this method can be useful when experimenting with dynamic grouping or extending the logic to streaming scenarios.
Recommended for interviews: The Sliding Window solution is usually what interviewers expect. Sorting combined with a two‑pointer window shows strong understanding of cost aggregation and greedy expansion. The Binary Search + Prefix Sum approach demonstrates deeper algorithmic thinking and is useful when the feasibility of a window size must be checked repeatedly. Relevant techniques include array processing, sliding window, binary search, and prefix sum.
Approach 1: Sliding Window and Two-pointer Technique
This approach uses a sliding window technique combined with sorting and a two-pointer mechanism to maximize frequency within the constraints of given operations. By setting a window, we gradually calculate the cost to equalize the elements to a candidate element. We carefully track the cost and adjust the window size to keep it within allowed operations (k).
def maxFrequency(nums, k):
nums.sort()
left = 0
total_sum = 0
max_freq = 0
for right in range(len(nums)):
total_sum += nums[right]
# Calculate the total cost to convert all current window elements to nums[right]
while (right - left + 1) * nums[right] - total_sum > k:
total_sum -= nums[left]
left += 1
max_freq = max(max_freq, right - left + 1)
return max_freq
# Example Usage
print(maxFrequency([1,2,6,4], 3)) # Output: 3The solution starts by sorting the array. We then use two pointers (left and right) to track the elements under consideration for increasing their frequency. The total_sum helps compute the total difference from the minimal cost to make all elements in the window equal to nums[right]. Whenever the cost exceeds k, the left pointer moves to reduce the window size.
Time Complexity: O(n log n), dominated by the sorting step.
Space Complexity: O(1), using constant extra space.
Approach 2: Custom Frequency Analysis with Priority Handling
This solution involves calculating how many moves are needed to make every number in an array segment equal to a target value, continually adjusting this target to examine possible solutions. Unique numbers are processed by frequency and incremented/decremented based on cost, leveraging efficient priority management to keep track of operations required to balance the array.
#include <algorithm>
#include <vector>
using namespace std;
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int left = 0;
long total_sum = 0;
int max_freq = 0;
for (int right = 0; right < nums.size(); ++right) {
total_sum += nums[right];
while ((long)(right - left + 1) * nums[right] - total_sum > k) {
total_sum -= nums[left];
++left;
}
max_freq = max(max_freq, right - left + 1);
}
return max_freq;
}
// Example usage:
// vector<int> nums = {1, 2, 6, 4};
// int result = maxFrequency(nums, 3);By sorting and using two pointers, the code maintains a window of feasible size. The goal is to track the required sum increment to form that window into equal elements with a maximum count. Adjustments are made when necessary, rolled back by moving the left pointer, representing the boundary of the feasible range.
Time Complexity: O(n log n) for sorting and O(n) for the two-pointer traversal.
Space Complexity: O(1), additional space is not used beyond constants.
Approach 3: Approach 1: Sliding Window
This approach utilizes a sliding window technique to find the maximum frequency possible by converting a contiguous segment of the array into the most frequent number possible under the constraints of given k operations.
def maxFrequency(nums, k):
nums.sort()
total = 0
left = 0
result = 0
for right in range(len(nums)):
total += nums[right]
while nums[right] * (right - left + 1) > total + k:
total -= nums[left]
left += 1
result = max(result, right - left + 1)
return result
# Example usage
nums = [1, 2, 6, 4]
k = 3
print(maxFrequency(nums, k))import java.util.Arrays;
public class MaxFrequency {
public static int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
long total = 0;
int result = 0, left = 0;
for (int right = 0; right < nums.length; ++right) {
total += nums[right];
while (nums[right] * (right - left + 1) > total + k) {
total -= nums[left++];
}
result = Math.max(result, right - left + 1);
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 6, 4};
int k = 3;
System.out.println(maxFrequency(nums, k));
}
}#include <vector>
#include <algorithm>
#include <iostream>
int maxFrequency(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
long total = 0;
int result = 0, left = 0;
for (int right = 0; right < nums.size(); ++right) {
total += nums[right];
while (nums[right] * (right - left + 1) > total + k) {
total -= nums[left++];
}
result = std::max(result, right - left + 1);
}
return result;
}
int main() {
std::vector<int> nums = {1, 2, 6, 4};
int k = 3;
std::cout << maxFrequency(nums, k) << std::endl;
return 0;
}function maxFrequency(nums, k) {
nums.sort((a, b) => a - b);
let total = 0, left = 0, result = 0;
for (let right = 0; right < nums.length; right++) {
total += nums[right];
while (nums[right] * (right - left + 1) > total + k) {
total -= nums[left++];
}
result = Math.max(result, right - left + 1);
}
return result;
}
// Example usage:
let nums = [1, 2, 6, 4];
let k = 3;
console.log(maxFrequency(nums, k));#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int maxFrequency(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), compare);
long total = 0;
int left = 0, result = 0;
for (int right = 0; right < numsSize; ++right) {
total += nums[right];
while ((long)nums[right] * (right - left + 1) > total + k) {
total -= nums[left++];
}
result = (right - left + 1) > result ? (right - left + 1) : result;
}
return result;
}
int main() {
int nums[] = {1, 2, 6, 4};
int k = 3;
printf("%d\n", maxFrequency(nums, 4, k));
return 0;
}using System;
class Program {
public static int MaxFrequency(int[] nums, int k) {
Array.Sort(nums);
long total = 0;
int result = 0, left = 0;
for (int right = 0; right < nums.Length; ++right) {
total += nums[right];
while (nums[right] * (right - left + 1) > total + k) {
total -= nums[left++];
}
result = Math.Max(result, right - left + 1);
}
return result;
}
static void Main() {
int[] nums = {1, 2, 6, 4};
int k = 3;
Console.WriteLine(MaxFrequency(nums, k));
}
}This Python solution sorts the input array and then uses a sliding window approach to calculate and return the maximum possible frequency of any number after using at most k operations.
Time Complexity: O(n log n) because of the sorting process. Space Complexity: O(1) additional space.
Approach 4: Approach 2: Binary Search + Prefix Sum
This approach combines binary search with prefix sums to efficiently compute potential frequency scores and compare them to k operations to find the feasible maximum frequency achievable.
def is_possible(nums, k, mid):
total = 0
for i in range(mid):
total += nums[mid - 1] - nums[i]
if total <= k:
return True
for j in range(mid, len(nums)):
total += (nums[j] - nums[j - 1]) * (mid - 1)
total -= nums[j] - nums[j - mid]
if total <= k:
return True
return False
def maxFrequency(nums, k):
nums.sort()
low, high = 1, len(nums)
result = 1
while low <= high:
mid = low + (high - low) // 2
if is_possible(nums, k, mid):
result = mid
low = mid + 1
else:
high = mid - 1
return result
# Example usage
nums = [1, 2, 6, 4]
k = 3
print(maxFrequency(nums, k))import java.util.Arrays;
public class MaxFrequency {
private static boolean isPossible(int[] nums, int k, int mid) {
long total = 0;
for (int i = 0; i < mid; i++) total += nums[mid - 1] - nums[i];
if (total <= k) return true;
for (int j = mid; j < nums.length; j++) {
total += (nums[j] - nums[j - 1]) * (mid - 1);
total -= nums[j] - nums[j - mid];
if (total <= k) return true;
}
return false;
}
public static int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int low = 1, high = nums.length, result = 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isPossible(nums, k, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 6, 4};
int k = 3;
System.out.println(maxFrequency(nums, k));
}
}#include <iostream>
#include <vector>
#include <algorithm>
bool isPossible(const std::vector<int>& nums, int k, int mid) {
long long total = 0;
for (int i = 0; i < mid; ++i) total += nums[mid - 1] - nums[i];
if (total <= k) return true;
for (size_t j = mid; j < nums.size(); ++j) {
total += (nums[j] - nums[j - 1]) * (mid - 1);
total -= nums[j] - nums[j - mid];
if (total <= k) return true;
}
return false;
}
int maxFrequency(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
int low = 1, high = nums.size(), result = 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isPossible(nums, k, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
int main() {
std::vector<int> nums = {1, 2, 6, 4};
int k = 3;
std::cout << maxFrequency(nums, k) << std::endl;
return 0;
}function isPossible(nums, k, mid) {
let total = 0;
for (let i = 0; i < mid; i++) {
total += nums[mid - 1] - nums[i];
}
if (total <= k) return true;
for (let j = mid; j < nums.length; j++) {
total += (nums[j] - nums[j - 1]) * (mid - 1);
total -= nums[j] - nums[j - mid];
if (total <= k) return true;
}
return false;
}
function maxFrequency(nums, k) {
nums.sort((a, b) => a - b);
let low = 1, high = nums.length;
let result = 1;
while (low <= high) {
const mid = Math.floor(low + (high - low) / 2);
if (isPossible(nums, k, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
// Example usage:
let nums = [1, 2, 6, 4];
let k = 3;
console.log(maxFrequency(nums, k));#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int isPossible(int *nums, int numsSize, int mid, int k) {
long total = 0;
for (int i = 0; i < mid; i++) total += nums[mid - 1] - nums[i];
if (total <= k) return 1;
for (int j = mid; j < numsSize; ++j) {
total += (nums[j] - nums[j - 1]) * (mid - 1);
total -= nums[j] - nums[j - mid];
if (total <= k) return 1;
}
return 0;
}
int maxFrequency(int *nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), cmp);
int low = 1, high = numsSize, result = 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isPossible(nums, numsSize, mid, k)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
int main() {
int nums[] = {1, 2, 6, 4};
int k = 3;
printf("%d\n", maxFrequency(nums, 4, k));
return 0;
}using System;
class Program {
static bool IsPossible(int[] nums, int k, int mid) {
long total = 0;
for (int i = 0; i < mid; i++) total += nums[mid - 1] - nums[i];
if (total <= k) return true;
for (int j = mid; j < nums.Length; j++) {
total += (nums[j] - nums[j - 1]) * (mid - 1);
total -= nums[j] - nums[j - mid];
if (total <= k) return true;
}
return false;
}
public static int MaxFrequency(int[] nums, int k) {
Array.Sort(nums);
int low = 1, high = nums.Length, result = 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (IsPossible(nums, k, mid)) {
result = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
static void Main() {
int[] nums = {1, 2, 6, 4};
int k = 3;
Console.WriteLine(MaxFrequency(nums, k));
}
}This Python solution employs binary search to determine the highest feasible frequency, leveraging prefix sums to assess operational expenses.
Time Complexity: O(n log n), due to sorting and binary search operations. Space Complexity: O(1), employing minimal additional space.
Approach 5: Sorting + Prefix Sum + Binary Search
The problem asks for the maximum frequency of the mode we can get after performing at most k operations. If we sort the array nums in ascending order, it would be best to turn a continuous segment of numbers into the same number, which can reduce the number of operations and increase the frequency of the mode.
Therefore, we might as well sort the array nums first.
Next, we analyze that if a frequency x is feasible, then for any y \le x, the frequency y is also feasible, which shows monotonicity. Therefore, we can use binary search to find the maximum feasible frequency.
We binary search the frequency, define the left boundary of the binary search as l = 0, and the right boundary as r = n, where n is the length of the array. In each binary search process, we take the middle value mid = \lfloor \frac{l + r + 1}{2} \rfloor, and then determine whether there exists a continuous subarray of length mid in nums, such that all elements in this subarray become the median of this subarray, and the number of operations does not exceed k. If it exists, then we update the left boundary l to mid, otherwise we update the right boundary r to mid - 1.
To determine whether such a subarray exists, we can use prefix sum. We first define two pointers i and j, initially i = 0, j = i + mid. Then all elements from nums[i] to nums[j - 1] are changed to nums[(i + j) / 2], and the number of operations required is left + right, where:
$
\begin{aligned}
left &= sum_{k = i}^{(i + j) / 2 - 1} (nums[(i + j) / 2] - nums[k]) \
&= ((i + j) / 2 - i) times nums[(i + j) / 2] - sum_{k = i}^{(i + j) / 2 - 1} nums[k]
\end{aligned}
\begin{aligned}
right &= sum_{k = (i + j) / 2 + 1}^{j} (nums[k] - nums[(i + j) / 2]) \
&= sum_{k = (i + j) / 2 + 1}^{j} nums[k] - (j - (i + j) / 2) times nums[(i + j) / 2]
\end{aligned}
We can use the prefix sum array s to calculate sum_{k = i}^{j} nums[k], so as to calculate left and right in O(1) time.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n$ is the length of the array.
function maxFrequencyScore(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
const s: number[] = Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
s[i] = s[i - 1] + nums[i - 1];
}
let l: number = 0;
let r: number = n;
while (l < r) {
const mid: number = (l + r + 1) >> 1;
let ok: boolean = false;
for (let i = 0; i <= n - mid; i++) {
const j = i + mid;
const x = nums[Math.floor((i + j) / 2)];
const left = (Math.floor((i + j) / 2) - i) * x - (s[Math.floor((i + j) / 2)] - s[i]);
const right = s[j] - s[Math.floor((i + j) / 2)] - (j - Math.floor((i + j) / 2)) * x;
if (left + right <= k) {
ok = true;
break;
}
}
if (ok) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}func maxFrequencyScore(nums []int, k int64) int {
sort.Ints(nums)
n := len(nums)
s := make([]int64, n+1)
for i := 1; i <= n; i++ {
s[i] = s[i-1] + int64(nums[i-1])
}
l, r := 0, n
for l < r {
mid := (l + r + 1) >> 1
ok := false
for i := 0; i <= n-mid; i++ {
j := i + mid
x := int64(nums[(i+j)/2])
left := (int64((i+j)/2-i) * x) - (s[(i+j)/2] - s[i])
right := (s[j] - s[(i+j)/2]) - (int64(j-(i+j)/2) * x)
if left+right <= k {
ok = true
break
}
}
if ok {
l = mid
} else {
r = mid - 1
}
}
return l
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window and Two-pointer Technique | Time Complexity: O(n log n), dominated by the sorting step. |
| Custom Frequency Analysis with Priority Handling | Time Complexity: O(n log n) for sorting and O(n) for the two-pointer traversal. |
| Approach 1: Sliding Window | Time Complexity: O(n log n) because of the sorting process. Space Complexity: O(1) additional space. |
| Approach 2: Binary Search + Prefix Sum | Time Complexity: O(n log n), due to sorting and binary search operations. Space Complexity: O(1), employing minimal additional space. |
| Sorting + Prefix Sum + Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window (Sorting + Two Pointers) | O(n log n) | O(1) | Best practical solution after sorting; efficient for large arrays |
| Binary Search + Prefix Sum | O(n log n) | O(n) | Useful when validating candidate frequency sizes or practicing feasibility checks |
| Custom Frequency Analysis with Priority Handling | O(n log n) | O(n) | Exploring dynamic grouping strategies or more flexible frequency tracking |
Frequently asked questions
Is Apply Operations to Maximize Frequency Score easy or hard?
Apply Operations to Maximize Frequency Score is classified as a Hard problem. The challenge lies in recognizing that sorting plus a sliding window can track the cost of aligning elements efficiently. Without this insight, brute force approaches quickly become too slow for large inputs.
Apply Operations to Maximize Frequency Score Python/Java solution
Python and Java implementations typically sort the array and maintain a sliding window while tracking the running sum of elements. The window expands with the right pointer and shrinks when the operation cost exceeds k. This pattern produces a clean O(n log n) solution used in most editorial explanations.
How to solve Apply Operations to Maximize Frequency Score in O(n)?
A pure O(n) solution is not possible because the array must be sorted to reason about increasing elements efficiently. After sorting, a sliding window keeps track of the sum of the current window and calculates the cost needed to match the largest value. This reduces the main computation to O(n) after the O(n log n) sorting step.
What is the best approach for Apply Operations to Maximize Frequency Score?
The most efficient and commonly used solution combines sorting with a sliding window. After sorting the array, expand a two‑pointer window and track the cost required to raise all elements to the rightmost value. If the cost exceeds k, move the left pointer to shrink the window. This approach runs in O(n log n) time due to sorting and O(1) extra space.
Is Apply Operations to Maximize Frequency Score asked at Google/Amazon/Meta?
Problems combining sliding window, prefix sums, and greedy cost calculations frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test the ability to manage window costs and optimize frequency using limited operations.
What data structure is used in Apply Operations to Maximize Frequency Score?
The main data structures are arrays along with prefix sums for fast range calculations. The optimal approach relies on sorting and a sliding window with two pointers. Some alternative implementations may use priority queues or ordered structures for frequency management.
What is the time complexity of Apply Operations to Maximize Frequency Score?
The optimal solution runs in O(n log n) time. Sorting the array takes O(n log n), and the sliding window traversal is O(n). Alternative solutions using binary search and prefix sums also result in O(n log n) complexity because each feasibility check scans the array.