Minimum operations to achieve at least k peaks

Array Dynamic Programming

30.2% acceptance

May 13, 2026

You are given a circular integer array nums of length n. An index i is a peak if its value is strictly greater than its neighbors: The previous neighbor of i is nums[i - 1] if i > 0, otherwise nums[n - 1]. The next neighbor of i is nums[i + 1] if i < n - 1, otherwise nums[0]. You are allowed to perform the following operation any number of times: Choose any index i and increase nums[i] by 1. Return an integer denoting the minimum number of operations required to make the array contain at least k peaks. If it is impossible, return -1.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as usize;
    if k == 0 { return 0; }
    if k > n / 2 { return -1; }
    let cost: Vec<i64> = (0..n).map(|i| {
      let prev = nums[(i + n - 1) % n] as i64;
      let next = nums[(i + 1) % n] as i64;
      (prev.max(next) + 1 - nums[i] as i64).max(0)
    }).collect();
    const INF: i64 = 1 << 60;
    fn dp(cost: &[i64], positions: &[usize], kk: usize) -> i64 {
      if kk == 0 { return 0; }
      let m = positions.len();
      if kk > (m + 1) / 2 { return INF; }
      let mut pp = vec![INF; kk + 1];
      let mut p = vec![INF; kk + 1];
      pp[0] = 0;
      p[0] = 0;
      p[1] = cost[positions[0]];
      for i in 1..m {
        let mut c = vec![INF; kk + 1];
        c[0] = 0;
        let ci = cost[positions[i]];
        for j in 1..=kk {
          let skip = p[j];
          let take = if pp[j - 1] < INF { pp[j - 1] + ci } else { INF };
          c[j] = skip.min(take);
        }
        pp = p;
        p = c;
      }
      p[kk]
    }
    let pos_a: Vec<usize> = (1..n).collect();
    let ans_a = dp(&cost, &pos_a, k);
    let pos_b: Vec<usize> = if n >= 3 { (2..n - 1).collect() } else { vec![] };
    let sub = dp(&cost, &pos_b, k - 1);
    let ans_b = if sub >= INF { INF } else { cost[0] + sub };
    let ans = ans_a.min(ans_b);
    if ans >= INF { -1 } else { ans as i32 }
  }
}