Maximum Frequency After Subarray Operation

Medium
1674.

Maximum Frequency After Subarray Operation

Maximum Frequency After Subarray Operation is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.

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^5
  • 1 <= nums[i] <= 50
  • 1 <= k <= 50
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxFrequency = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= nums[i] <= 50
  • 1 <= k <= 50

Hints for Maximum Frequency After Subarray Operation

  1. Hint 1

    With a fixed shift x, the elements that become k are exactly the copies of v = k - x inside the subarray — while the original ks inside the subarray stop being k (unless x = 0).

  2. Hint 2

    So for each candidate value v != k (only 49 of them), the gain of a subarray is (number of v inside) − (number of k inside).

  3. Hint 3

    Maximise that gain with Kadane's algorithm (+1 for v, -1 for k, 0 otherwise), and add the best gain over all v to the original count of k.

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

  1. Let base be the number of elements equal to k.
  2. For each v in 1..50 with v != k, run Kadane's algorithm over nums with weight +1 for v, -1 for k and 0 otherwise, keeping the best non-negative prefix sum ending at each position.
  3. Let gain be the largest sum seen over all v (at least 0, which corresponds to x = 0).
  4. 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 k inside the chosen subarray are lost when x != 0 — they must count as -1.
  • The operation is mandatory, but x = 0 is allowed, so the answer is never below base.

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 + gain

Java

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