Maximum Frequency After Subarray Operation — Solution
Maximum Frequency After Subarray Operation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Frequency After Subarray Operation is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Dynamic Programming, Greedy, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of length n and an integer k.
You must perform the following operation exactly once: choose a subarray nums[i..j] (with 0 <= i <= j <= n - 1) and an integer x, and add x to every element of that subarray.
Return the maximum possible number of elements equal to k (the frequency of k) after the operation.
Example 1
Input: nums = [1,2,3,4,5,6], k = 1
Output: 2
Explanation: Add -5 to [6] (the last element): the array becomes [1,2,3,4,5,1].
Example 2
Input: nums = [10,2,3,4,5,5,4,3,2,2], k = 10
Output: 4
Explanation: Add 8 to the subarray [2,3,4,5,5,4,3,2,2] — the four 2s become 10, joining the original 10.
Example 3
Input: nums = [7], k = 7
Output: 1
Explanation: Adding x = 0 keeps the single 7.
Constraints
1 <= n == nums.length <= 10^51 <= nums[i] <= 501 <= k <= 50
Hints for Maximum Frequency After Subarray Operation
Hint 1
With a fixed shift
x, the elements that becomekare exactly the copies ofv = k - xinside the subarray — while the originalks inside the subarray stop beingk(unlessx = 0).Hint 2
So for each candidate value
v != k(only 49 of them), the gain of a subarray is (number ofvinside) − (number ofkinside).Hint 3
Maximise that gain with Kadane's algorithm (
+1forv,-1fork,0otherwise), and add the best gain over allvto the original count ofk.
How to solve Maximum Frequency After Subarray Operation
Choosing x means choosing which value v = k - x will turn into k. Inside the subarray every v becomes a k and every original k is lost; outside nothing changes. That is a maximum-subarray-sum problem per value v, and the values are bounded by 50.
Approach
- Let
basebe the number of elements equal tok. - For each
vin1..50withv != k, run Kadane's algorithm overnumswith weight+1forv,-1forkand0otherwise, keeping the best non-negative prefix sum ending at each position. - Let
gainbe the largest sum seen over allv(at least 0, which corresponds tox = 0). - Return
base + gain.
Why it works
For a fixed x != 0 the final frequency of k is base - (k inside) + (v inside), so maximising over subarrays is exactly the maximum subarray sum of the ±1 weights. x = 0 leaves the array unchanged, which the floor of 0 covers, and every other x leads to a v outside 1..50 that never occurs and gains nothing.
Complexity
- Time —
O(50 · n) - Space —
O(1)
Pitfalls
- Elements equal to
kinside the chosen subarray are lost whenx != 0— they must count as-1. - The operation is mandatory, but
x = 0is allowed, so the answer is never belowbase.
Reference solution
Python
from typing import List
def maxFrequency(nums: List[int], k: int) -> int:
base = nums.count(k)
gain = 0
for v in set(nums):
if v == k:
continue
cur = 0
for x in nums:
if x == v:
cur += 1
elif x == k:
cur -= 1
if cur < 0:
cur = 0
elif cur > gain:
gain = cur
return base + gainJava
public static int maxFrequency(int[] nums, int k) {
int base = 0;
for (int x : nums) if (x == k) base++;
int gain = 0;
for (int v = 1; v <= 50; v++) {
if (v == k) continue;
int cur = 0;
for (int x : nums) {
if (x == v) cur++;
else if (x == k) cur--;
if (cur < 0) cur = 0;
else if (cur > gain) gain = cur;
}
}
return base + gain;
}C++
int maxFrequency(vector<int>& nums, int k) {
int base = 0;
for (int x : nums) if (x == k) base++;
int gain = 0;
for (int v = 1; v <= 50; v++) {
if (v == k) continue;
int cur = 0;
for (int x : nums) {
if (x == v) cur++;
else if (x == k) cur--;
if (cur < 0) cur = 0;
else if (cur > gain) gain = cur;
}
}
return base + gain;
}JavaScript
var maxFrequency = function(nums, k) {
var base = 0;
for (var i = 0; i < nums.length; i++) if (nums[i] === k) base++;
var gain = 0;
for (var v = 1; v <= 50; v++) {
if (v === k) continue;
var cur = 0;
for (var j = 0; j < nums.length; j++) {
if (nums[j] === v) cur++;
else if (nums[j] === k) cur--;
if (cur < 0) cur = 0;
else if (cur > gain) gain = cur;
}
}
return base + gain;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets