# Maximum Frequency After Subarray Operation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-frequency-after-subarray-operation)
Canonical: https://scaleengineer.com/dsa/problems/maximum-frequency-after-subarray-operation
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
---
## Problem
You are given an array `nums` of length `n`. You are also given an integer `k`.

You perform the following operation on `nums` **once**:

* Select a subarray `nums[i..j]` where `0 <= i <= j <= n - 1`.
* Select an integer `x` and add `x` to **all** the elements in `nums[i..j]`.

Find the **maximum** frequency of the value `k` after the operation.

**Example 1:**

**Input:** nums = \[1,2,3,4,5,6\], k = 1

**Output:** 2

**Explanation:**

After adding -5 to `nums[2..5]`, 1 has a frequency of 2 in `[1, 2, -2, -1, 0, 1]`.

**Example 2:**

**Input:** nums = \[10,2,3,4,5,5,4,3,2,2\], k = 10

**Output:** 4

**Explanation:**

After adding 8 to `nums[1..9]`, 10 has a frequency of 4 in `[10, 10, 11, 12, 13, 13, 12, 11, 10, 10]`.

**Constraints:**

* `1 <= n == nums.length <= 105`
* `1 <= nums[i] <= 50`
* `1 <= k <= 50`

# Approaches
## Brute Force Iteration over Subarrays
This approach exhaustively checks every possible subarray and, for each one, determines the best possible value `v` to convert into `k`. It calculates the potential gain in frequency for every single subarray and keeps track of the maximum gain found across all possibilities. This method is straightforward but computationally very expensive.
**Time:** O(n^3). There are two nested loops to iterate through all `O(n^2)` subarrays. For each subarray of length `L`, building the frequency map takes `O(L)` time, which is `O(n)` in the worst case. This results in a total time complexity of `O(n^2 * n) = O(n^3)`. · **Space:** O(C), where C is the number of unique values in the input array (at most 50). This space is used for the frequency map in each iteration.
**Pros:** Simple to understand and implement.; Correctly explores the entire search space.
**Cons:** Extremely inefficient due to three nested loops.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The fundamental idea is to simulate the process for every single choice we can make. A choice consists of a subarray `nums[i..j]` and a value `x` to add. The optimal `x` for a given subarray is one that converts an existing number `v` into `k`, i.e., `x = k - v`. This operation converts all occurrences of `v` in the subarray to `k` but also changes any original `k`'s within the subarray. The net change in the frequency of `k` is `count(v, nums[i..j]) - count(k, nums[i..j])`. To find the best outcome for a subarray `nums[i..j]`, we must find the value `v` that maximizes this gain. The brute-force algorithm iterates through all `O(n^2)` subarrays, and for each, it takes `O(n)` time to build a frequency map and find the best `v`, leading to an overall cubic time complexity.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxFrequency(int[] nums, int k) {
        int n = nums.length;
        int initialKCount = 0;
        for (int num : nums) {
            if (num == k) {
                initialKCount++;
            }
        }

        int maxGain = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Subarray nums[i..j]
                Map<Integer, Integer> freqMap = new HashMap<>();
                for (int l = i; l <= j; l++) {
                    freqMap.put(nums[l], freqMap.getOrDefault(nums[l], 0) + 1);
                }

                int kInSubarray = freqMap.getOrDefault(k, 0);
                int maxVInSubarray = 0;
                for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
                    if (entry.getKey() != k) {
                        maxVInSubarray = Math.max(maxVInSubarray, entry.getValue());
                    }
                }
                
                int gain = maxVInSubarray - kInSubarray;
                maxGain = Math.max(maxGain, gain);
            }
        }

        return initialKCount + maxGain;
    }
}
```
### Algorithm
- Calculate `initial_k_count`, the total number of `k`'s in the original `nums` array.
- Initialize `max_gain = 0`. This will store the maximum possible net increase in the frequency of `k`.
- Iterate through all possible start indices `i` from `0` to `n-1`.
- For each `i`, iterate through all possible end indices `j` from `i` to `n-1`. This defines the subarray `nums[i..j]`.
- For each subarray, create a frequency map to count the occurrences of each number within `nums[i..j]`.
- From the frequency map, determine `k_in_subarray`, the count of `k`.
- Also, find `max_v_in_subarray`, which is the highest frequency of any number `v` (where `v != k`) in the subarray.
- The gain for this specific subarray and the best choice of `v` is `max_v_in_subarray - k_in_subarray`.
- Update the global `max_gain` with this gain if it's larger.
- After checking all subarrays, the final result is `initial_k_count + max_gain`.

## Optimized Brute Force with Sliding Frequency Map
This approach is an optimization of the naive brute-force method. Instead of re-calculating counts for each subarray from scratch, it maintains a running frequency map. For a fixed starting point `i`, it expands the subarray to the right by incrementing `j` and updates the frequency map in constant time. This reduces the work done for each subarray.
**Time:** O(n^2 * C). The two nested loops for `i` and `j` give `O(n^2)`. Inside the inner loop, we iterate up to `C` (50) values to find the max frequency. This results in a total time complexity of `O(n^2 * C)`. · **Space:** O(C), where C is at most 50. This space is for the frequency map.
**Pros:** More efficient than the naive O(n^3) approach.; Reduces redundant computations.
**Cons:** Still too slow for the given constraints due to the `O(n^2)` structure.; The constant factor `C` (for finding the max frequency in the map) can be significant.
### Explanation
The core logic of maximizing the gain `count(v, nums[i..j]) - count(k, nums[i..j])` remains the same. The improvement lies in the computation. We fix the left boundary `i` of the subarray and iterate the right boundary `j` from `i` to `n-1`. As we expand the subarray, we don't need to re-scan it. We can maintain a frequency map for `nums[i..j]` and just add `nums[j]` to it at each step. After updating the map, we find the best `v` to convert by scanning the map's values. Since the range of values is small (1-50), scanning the map or a fixed range of potential values takes `O(C)` time. This optimization reduces the complexity from cubic to quadratic.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxFrequency(int[] nums, int k) {
        int n = nums.length;
        int initialKCount = 0;
        for (int num : nums) {
            if (num == k) {
                initialKCount++;
            }
        }

        int maxGain = 0;
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> freqMap = new HashMap<>();
            for (int j = i; j < n; j++) {
                // Update frequency map for subarray nums[i..j]
                freqMap.put(nums[j], freqMap.getOrDefault(nums[j], 0) + 1);

                int kInSubarray = freqMap.getOrDefault(k, 0);
                int maxVInSubarray = 0;
                // Since values are 1-50, we can iterate 1-50 instead of map keys
                for (int val = 1; val <= 50; val++) {
                    if (val != k) {
                        maxVInSubarray = Math.max(maxVInSubarray, freqMap.getOrDefault(val, 0));
                    }
                }
                
                int gain = maxVInSubarray - kInSubarray;
                maxGain = Math.max(maxGain, gain);
            }
        }

        return initialKCount + maxGain;
    }
}
```
### Algorithm
- Calculate `initial_k_count`.
- Initialize `max_gain = 0`.
- Iterate through all possible start indices `i` from `0` to `n-1`.
- For each `i`, initialize an empty frequency map.
- Start a second loop for the end index `j` from `i` to `n-1`.
- In the `j` loop, update the frequency map by adding `nums[j]`. This incrementally builds the map for the subarray `nums[i..j]`.
- With the updated map, find `k_in_subarray` and `max_v_in_subarray` (the max frequency of any element `v != k`).
- Calculate the gain and update the global `max_gain`.
- The final result is `initial_k_count + max_gain`.

## Maximum Subarray Sum (Kadane's Algorithm)
This highly efficient approach reframes the problem. Instead of iterating through subarrays, it iterates through all possible values `v` that could be converted to `k`. For each `v`, it calculates the maximum possible 'gain' using a single pass over the array. This is achieved by transforming the problem into a classic Maximum Subarray Sum problem, which can be solved optimally with Kadane's algorithm.
**Time:** O(C * n), where `C` is the range of values (50) and `n` is the length of the array. The outer loop runs `C` times, and the inner loop (Kadane's algorithm) runs in `O(n)` time. Since `C` is a small constant, the complexity is effectively linear in `n`. · **Space:** O(1). The algorithm only requires a few variables to store the initial count and the running gains, regardless of the input size.
**Pros:** Highly efficient, passing for the given constraints.; Optimal time complexity of O(C*n).; Minimal space complexity.
**Cons:** The logic can be less intuitive to derive compared to brute-force methods.
### Explanation
The key insight is that the final frequency of `k` is `initial_k_count + gain`, where `gain = count(v, nums[i..j]) - count(k, nums[i..j])`. We need to maximize this gain over all choices of `i, j, v`.

We can iterate through all possible values for `v` (from 1 to 50, as per constraints) and for each `v`, find the maximum possible gain. For a fixed `v`, the problem is to find `max_{i,j} (count(v, nums[i..j]) - count(k, nums[i..j]))`.

This is equivalent to finding the maximum subarray sum on a transformed array where `nums[p] == v` maps to `+1`, `nums[p] == k` maps to `-1`, and all other numbers map to `0`. The sum of a subarray in this transformed array represents the gain. Kadane's algorithm finds the maximum subarray sum in linear time.

By applying Kadane's algorithm for each potential value `v`, we can find the overall maximum gain efficiently.

```java
class Solution {
    public int maxFrequency(int[] nums, int k) {
        int n = nums.length;
        int initialKCount = 0;
        for (int num : nums) {
            if (num == k) {
                initialKCount++;
            }
        }

        int maxGain = 0;
        // Iterate through all possible values 'v' to be converted to 'k'
        for (int v = 1; v <= 50; v++) {
            if (v == k) {
                continue;
            }

            // Use Kadane's algorithm to find the max gain for this 'v'
            int currentGain = 0;
            int maxGainForV = 0;
            for (int num : nums) {
                int score = 0;
                if (num == v) {
                    score = 1; // We gain an element that becomes k
                } else if (num == k) {
                    score = -1; // We lose an original k
                }
                
                currentGain += score;
                
                if (currentGain < 0) {
                    currentGain = 0; // Start a new potential subarray
                }
                maxGainForV = Math.max(maxGainForV, currentGain);
            }
            maxGain = Math.max(maxGain, maxGainForV);
        }

        return initialKCount + maxGain;
    }
}
```
### Algorithm
- First, calculate `initial_k_count`, the frequency of `k` in the entire array.
- Initialize `max_gain = 0`.
- Iterate through each possible value `v` from 1 to 50. This `v` is the candidate number we will transform into `k`.
- If `v == k`, skip it, as this operation results in no change (gain is 0).
- For each `v`, we want to find the subarray that maximizes `count(v, subarray) - count(k, subarray)`. This is a maximum subarray sum problem.
- We can solve this using Kadane's algorithm. Iterate through `nums`, maintaining a `current_gain`.
- For each element `nums[i]`: if it's `v`, add 1 to `current_gain`; if it's `k`, subtract 1. Otherwise, add 0.
- If `current_gain` becomes negative, reset it to 0 (as we can always start a new subarray).
- Keep track of the maximum `current_gain` seen for this `v` (`max_gain_for_v`).
- After iterating through `nums`, update the overall `max_gain = max(max_gain, max_gain_for_v)`.
- The final answer is `initial_k_count + max_gain`.