Problem

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 _theminimum number of operations to make _nums non-decreasing or non-increasing.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: nums = [3,2,4,5,0]
Output: 4
Explanation:
One possible way to turn nums into non-increasing order is to:
- Add 1 to nums[1] once so that it becomes 3.
- Subtract 1 from nums[2] once so it becomes 3.
- Subtract 1 from nums[3] twice so it becomes 3.
After doing the 4 operations, nums becomes [3,3,3,3,0] which is in non-increasing order.
Note that it is also possible to turn nums into [4,4,4,4,0] in 4 operations.
It can be proven that 4 is the minimum number of operations needed.

Example 2:

1
2
3

Input: nums = [2,2,3,4]
Output: 0
Explanation: nums is already in non-decreasing order, so no operations are needed and we return 0.

Example 3:

1
2
3

Input: nums = [0]
Output: 0
Explanation: nums is already in non-decreasing order, so no operations are needed and we return 0.

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Follow up: Can you solve it in O(n*log(n)) time complexity?

Solution

Method 1 – Dynamic Programming (DP) with Value Compression

Intuition

To minimize the number of operations to make the array non-decreasing or non-increasing, we can use DP. For each position, we try to set the value to any possible value and compute the minimum cost. Value compression helps reduce the DP state space.

Approach

  1. Collect all unique values in nums and sort them for compression.
  2. For non-decreasing:
    • Let dp[i][j] be the minimum operations to make the first i+1 elements non-decreasing, with nums[i] set to the j-th value.
    • For each i, for each possible value, try all previous values <= current and update the cost.
  3. For non-increasing:
    • Similar, but for each possible value, try all previous values >= current.
  4. The answer is the minimum of the two DP results.

Code

 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

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        vector<int> vals = nums;
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        int n = nums.size(), m = vals.size();
        vector<vector<int>> dp1(n, vector<int>(m, 1e9)), dp2(n, vector<int>(m, 1e9));
        for (int j = 0; j < m; ++j) dp1[0][j] = abs(nums[0] - vals[j]), dp2[0][j] = abs(nums[0] - vals[j]);
        for (int i = 1; i < n; ++i) {
            int mn1 = 1e9, mn2 = 1e9;
            for (int j = 0; j < m; ++j) {
                mn1 = min(mn1, dp1[i-1][j]);
                dp1[i][j] = mn1 + abs(nums[i] - vals[j]);
            }
            for (int j = m-1; j >= 0; --j) {
                mn2 = min(mn2, dp2[i-1][j]);
                dp2[i][j] = mn2 + abs(nums[i] - vals[j]);
            }
        }
        int ans = 1e9;
        for (int j = 0; j < m; ++j) ans = min({ans, dp1[n-1][j], dp2[n-1][j]});
        return ans;
    }
};
 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

func minimumOperations(nums []int) int {
    vals := append([]int{}, nums...)
    sort.Ints(vals)
    vals = unique(vals)
    n, m := len(nums), len(vals)
    dp1 := make([][]int, n)
    dp2 := make([][]int, n)
    for i := range dp1 {
        dp1[i] = make([]int, m)
        dp2[i] = make([]int, m)
    }
    for j := 0; j < m; j++ {
        dp1[0][j] = abs(nums[0]-vals[j])
        dp2[0][j] = abs(nums[0]-vals[j])
    }
    for i := 1; i < n; i++ {
        mn1, mn2 := 1<<30, 1<<30
        for j := 0; j < m; j++ {
            if dp1[i-1][j] < mn1 {
                mn1 = dp1[i-1][j]
            }
            dp1[i][j] = mn1 + abs(nums[i]-vals[j])
        }
        for j := m-1; j >= 0; j-- {
            if dp2[i-1][j] < mn2 {
                mn2 = dp2[i-1][j]
            }
            dp2[i][j] = mn2 + abs(nums[i]-vals[j])
        }
    }
    ans := 1<<30
    for j := 0; j < m; j++ {
        if dp1[n-1][j] < ans {
            ans = dp1[n-1][j]
        }
        if dp2[n-1][j] < ans {
            ans = dp2[n-1][j]
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
func unique(a []int) []int {
    if len(a) == 0 { return a }
    res := []int{a[0]}
    for i := 1; i < len(a); i++ {
        if a[i] != a[i-1] {
            res = append(res, a[i])
        }
    }
    return res
}
 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

import java.util.*;
class Solution {
    public int minimumOperations(int[] nums) {
        int[] vals = Arrays.copyOf(nums, nums.length);
        Arrays.sort(vals);
        int m = 1;
        for (int i = 1; i < vals.length; i++) if (vals[i] != vals[i-1]) vals[m++] = vals[i];
        int n = nums.length;
        int[][] dp1 = new int[n][m], dp2 = new int[n][m];
        for (int j = 0; j < m; ++j) dp1[0][j] = Math.abs(nums[0]-vals[j]);
        for (int j = 0; j < m; ++j) dp2[0][j] = Math.abs(nums[0]-vals[j]);
        for (int i = 1; i < n; ++i) {
            int mn1 = Integer.MAX_VALUE, mn2 = Integer.MAX_VALUE;
            for (int j = 0; j < m; ++j) {
                mn1 = Math.min(mn1, dp1[i-1][j]);
                dp1[i][j] = mn1 + Math.abs(nums[i]-vals[j]);
            }
            for (int j = m-1; j >= 0; --j) {
                mn2 = Math.min(mn2, dp2[i-1][j]);
                dp2[i][j] = mn2 + Math.abs(nums[i]-vals[j]);
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < m; ++j) ans = Math.min(ans, Math.min(dp1[n-1][j], dp2[n-1][j]));
        return ans;
    }
}
 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 {
    fun minimumOperations(nums: IntArray): Int {
        val vals = nums.sorted().distinct()
        val n = nums.size
        val m = vals.size
        val dp1 = Array(n) { IntArray(m) }
        val dp2 = Array(n) { IntArray(m) }
        for (j in 0 until m) {
            dp1[0][j] = kotlin.math.abs(nums[0] - vals[j])
            dp2[0][j] = kotlin.math.abs(nums[0] - vals[j])
        }
        for (i in 1 until n) {
            var mn1 = Int.MAX_VALUE
            var mn2 = Int.MAX_VALUE
            for (j in 0 until m) {
                mn1 = minOf(mn1, dp1[i-1][j])
                dp1[i][j] = mn1 + kotlin.math.abs(nums[i] - vals[j])
            }
            for (j in m-1 downTo 0) {
                mn2 = minOf(mn2, dp2[i-1][j])
                dp2[i][j] = mn2 + kotlin.math.abs(nums[i] - vals[j])
            }
        }
        var ans = Int.MAX_VALUE
        for (j in 0 until m) ans = minOf(ans, dp1[n-1][j], dp2[n-1][j])
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def minimumOperations(self, nums: list[int]) -> int:
        vals = sorted(set(nums))
        n, m = len(nums), len(vals)
        dp1 = [ [0]*m for _ in range(n) ]
        dp2 = [ [0]*m for _ in range(n) ]
        for j in range(m):
            dp1[0][j] = abs(nums[0] - vals[j])
            dp2[0][j] = abs(nums[0] - vals[j])
        for i in range(1, n):
            mn1 = mn2 = float('inf')
            for j in range(m):
                mn1 = min(mn1, dp1[i-1][j])
                dp1[i][j] = mn1 + abs(nums[i] - vals[j])
            for j in range(m-1, -1, -1):
                mn2 = min(mn2, dp2[i-1][j])
                dp2[i][j] = mn2 + abs(nums[i] - vals[j])
        ans = float('inf')
        for j in range(m):
            ans = min(ans, dp1[n-1][j], dp2[n-1][j])
        return ans
 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
30
31
32

impl Solution {
    pub fn minimum_operations(nums: Vec<i32>) -> i32 {
        let mut vals = nums.clone();
        vals.sort();
        vals.dedup();
        let n = nums.len();
        let m = vals.len();
        let mut dp1 = vec![vec![1_000_000_000; m]; n];
        let mut dp2 = vec![vec![1_000_000_000; m]; n];
        for j in 0..m {
            dp1[0][j] = (nums[0] - vals[j]).abs();
            dp2[0][j] = (nums[0] - vals[j]).abs();
        }
        for i in 1..n {
            let mut mn1 = 1_000_000_000;
            let mut mn2 = 1_000_000_000;
            for j in 0..m {
                mn1 = mn1.min(dp1[i-1][j]);
                dp1[i][j] = mn1 + (nums[i] - vals[j]).abs();
            }
            for j in (0..m).rev() {
                mn2 = mn2.min(dp2[i-1][j]);
                dp2[i][j] = mn2 + (nums[i] - vals[j]).abs();
            }
        }
        let mut ans = 1_000_000_000;
        for j in 0..m {
            ans = ans.min(dp1[n-1][j].min(dp2[n-1][j]));
        }
        ans
    }
}
 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

class Solution {
    minimumOperations(nums: number[]): number {
        const vals = Array.from(new Set(nums)).sort((a, b) => a - b);
        const n = nums.length, m = vals.length;
        const dp1 = Array.from({length: n}, () => Array(m).fill(0));
        const dp2 = Array.from({length: n}, () => Array(m).fill(0));
        for (let j = 0; j < m; ++j) {
            dp1[0][j] = Math.abs(nums[0] - vals[j]);
            dp2[0][j] = Math.abs(nums[0] - vals[j]);
        }
        for (let i = 1; i < n; ++i) {
            let mn1 = Infinity, mn2 = Infinity;
            for (let j = 0; j < m; ++j) {
                mn1 = Math.min(mn1, dp1[i-1][j]);
                dp1[i][j] = mn1 + Math.abs(nums[i] - vals[j]);
            }
            for (let j = m-1; j >= 0; --j) {
                mn2 = Math.min(mn2, dp2[i-1][j]);
                dp2[i][j] = mn2 + Math.abs(nums[i] - vals[j]);
            }
        }
        let ans = Infinity;
        for (let j = 0; j < m; ++j) ans = Math.min(ans, dp1[n-1][j], dp2[n-1][j]);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(nk), where n is the length of nums and k is the number of unique values in nums.
  • 🧺 Space complexity: O(nk), for the DP tables.