Make array non decreasing or non increasing

Array Dynamic Programming Greedy Heap (Priority Queue)

65.6% acceptance

Mar 31, 2026

You are given a 0-indexed integer array nums. In one operation, you can: Choose an index i in the range 0 <= i < nums.length Set nums[i] to nums[i] + 1 or nums[i] - 1 Return the minimum number of operations to make nums non-decreasing or non-increasing.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn convert_array(nums: Vec<i32>) -> i32 {
    fn min_cost_non_decreasing(nums: &[i32]) -> i32 {
      let max_val = 1000;
      let n = nums.len();
      if n == 0 { return 0; }
      let mut dp = vec![0i32; max_val + 1];
      for j in 0..=max_val {
        dp[j] = (nums[0] - j as i32).abs();
      }
      for i in 1..n {
        let mut new_dp = vec![0i32; max_val + 1];
        let mut min_prev = dp[0];
        for j in 0..=max_val {
          min_prev = min_prev.min(dp[j]);
          new_dp[j] = (nums[i] - j as i32).abs() + min_prev;
        }
        dp = new_dp;
      }
      *dp.iter().min().unwrap()
    }
    let cost1 = min_cost_non_decreasing(&nums);
    let rev: Vec<i32> = nums.iter().rev().copied().collect();
    let cost2 = min_cost_non_decreasing(&rev);
    cost1.min(cost2)
  }
}