Maximum Frequency After Subarray Operation - Solution & Explanation

Problem Overview: You are given an array and allowed to apply a single operation on a subarray. The operation shifts every element in that subarray by the same value. After the operation, the goal is to maximize the frequency of any number in the array.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

Start by enumerating every possible subarray [l, r]. For each subarray, try all possible shifts that would convert one element in that subarray into a chosen target value. Apply the transformation conceptually and recompute the frequency of all numbers. This involves iterating over the subarray, modifying values, and counting frequencies with a map. The method works for small inputs but becomes impractical because there are O(n^2) subarrays and each evaluation requires another scan.

Approach 2: Target Enumeration with Prefix Counting (O(n^2) time, O(n) space)

Instead of recomputing the whole array each time, fix a target value t. For each index, determine the shift needed to convert nums[i] into t. When the same shift is applied to a subarray, elements that share the same difference align with the target simultaneously. You can track contributions using prefix frequency maps or counters while scanning the array. This reduces redundant work and makes it easier to count how many elements can be converted together.

Approach 3: Greedy Gain Tracking with Kadane's Algorithm (O(n) time, O(n) space)

The optimal strategy treats the operation as a gain/loss problem. Suppose you want the final value to be t. Elements already equal to t contribute to the base frequency. If you apply a shift on a subarray, some elements become t (gain) while existing t values inside the subarray might change (loss). Convert this into a gain array where converting a value gives +1 and breaking an existing match gives -1. The best subarray to operate on is the maximum subarray sum, which can be computed using Kadane's algorithm. Combining the base frequency with the maximum gain yields the final answer.

This approach relies on ideas from array processing, prefix sum style counting, and greedy dynamic programming similar to Kadane’s algorithm. A hash table helps track frequencies efficiently.

Recommended for interviews: The Kadane-style gain tracking approach. Interviewers expect you to recognize that applying the operation on a subarray is equivalent to selecting a segment with maximum net gain. Explaining the brute force first shows understanding of the search space, but converting the problem into a maximum subarray problem demonstrates strong algorithmic intuition.