Scale Engineer

Maximum Frequency After Subarray Operation

Med
#3052Time: 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.
Patterns
Dynamic ProgrammingGreedyEnumerationPrefix Sum
Data structures
ArrayHash Table

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem