Maximum frequency after subarray operation

Array Hash Table Dynamic Programming Greedy Enumeration Prefix Sum

30.9% acceptance

Feb 25, 2026

264

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_frequency(nums: Vec<i32>, k: i32) -> i32 {
    let _n = nums.len();
    let count_k: i32 = nums.iter().filter(|&&x| x == k).count() as i32;
    let mut best_gain = 0i32;
    // For each value v != k, find max subarray sum of f(i) where f(i) = +1 if nums[i]==v, -1 if nums[i]==k, 0 otherwise
    let mut freq = std::collections::HashMap::new();
    for &x in &nums { *freq.entry(x).or_insert(0) += 1; }
    for (&v, _) in &freq {
      if v == k { continue; }
      // Kadane's on f
      let mut cur = 0i32;
      let mut max_s = 0i32;
      for &x in &nums {
        let delta = if x == v { 1 } else if x == k { -1 } else { 0 };
        cur += delta;
        if cur < 0 { cur = 0; }
        if cur > max_s { max_s = cur; }
      }
      if max_s > best_gain { best_gain = max_s; }
    }
    count_k + best_gain
  }
}