Skip to content

3434. Maximum Frequency After Subarray Operation 👍

  • Time: $O(50n) = O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int maxFrequency(vector<int>& nums, int k) {
    constexpr int kMax = 50;
    int maxFreq = 0;
    for (int target = 1; target <= kMax; ++target)
      if (target != k)
        maxFreq = max(maxFreq, kadane(nums, target, k));
    return ranges::count(nums, k) + maxFreq;
  }

 private:
  // Returns the maximum achievable frequency of `k` by Kakane's algorithm,
  // where each `target` in subarrays is transformed to `k`.
  int kadane(const vector<int>& nums, int target, int k) {
    int maxSum = 0;
    int sum = 0;
    for (const int num : nums) {
      if (num == target)
        ++sum;
      else if (num == k)
        --sum;
      if (sum < 0)  // Reset if sum becomes negative (Kadane's spirit).
        sum = 0;
      maxSum = max(maxSum, sum);
    }
    return maxSum;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int maxFrequency(int[] nums, int k) {
    final int MAX = 50;
    int maxFreq = 0;
    for (int target = 1; target <= MAX; ++target)
      if (target != k)
        maxFreq = Math.max(maxFreq, kadane(nums, target, k));
    return (int) Arrays.stream(nums).filter(num -> num == k).count() + maxFreq;
  }

  // Returns the maximum achievable frequency of `k` using Kakane's algorithm,
  // where each `target` in subarrays is transformed to `k`.
  private int kadane(int[] nums, int target, int k) {
    int maxSum = 0;
    int sum = 0;
    for (final int num : nums) {
      if (num == target)
        ++sum;
      else if (num == k)
        --sum;
      if (sum < 0) // Reset if sum becomes negative (Kadane's spirit).
        sum = 0;
      maxSum = Math.max(maxSum, sum);
    }

    return maxSum;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def maxFrequency(self, nums: list[int], k: int) -> int:
    return nums.count(k) + max(self._kadane(nums, target, k)
                               for target in range(1, 51)
                               if target != k)

  def _kadane(self, nums: list[int], target: int, k: int) -> int:
    """
    Returns the maximum achievable frequency of `k` by Kakane's algorithm,
    where each `target` in subarrays is transformed to `k`.
    """
    maxSum = 0
    sum = 0
    for num in nums:
      if num == target:
        sum += 1
      elif num == k:
        sum -= 1
      if sum < 0:  # Reset sum if it becomes negative (Kadane's spirit).
        sum = 0
      maxSum = max(maxSum, sum)
    return maxSum