Skip to content

3914. Minimum Operations to Make Array Non Decreasing

Description

You are given an integer array nums of length n.

In one operation, you may choose any subarray nums[l..r] and increase each element in that subarray by x, where x is any positive integer.

Return the minimum possible sum of the values of x across all operations required to make the array non-decreasing.

An array is non-decreasing if nums[i] <= nums[i + 1] for all 0 <= i < n - 1.

Β 

Example 1:

Input: nums = [3,3,2,1]

Output: 2

Explanation:

One optimal set of operations:

  • Choose subarray [2..3] and add x = 1 resulting in [3, 3, 3, 2]
  • Choose subarray [3..3] and add x = 1 resulting in [3, 3, 3, 3]

The array becomes non-decreasing, and the total sum of chosen x values is 1 + 1 = 2.

Example 2:

Input: nums = [5,1,2,3]

Output: 4

Explanation:

One optimal set of operations:

  • Choose subarray [1..3] and add x = 4 resulting in [5, 5, 6, 7]

The array becomes non-decreasing, and the total sum of chosen x values is 4.

Β 

Constraints:

  • 1 <= n == nums.length <= 105
  • 1 <= nums[i] <= 109

Solutions

Solution 1: Greedy

We can traverse the array from left to right and calculate the difference between each pair of adjacent elements. If the current element is smaller than the previous one, we need to increase the current element so that it is at least equal to the previous element. The amount to increase is the difference between the previous element and the current element.

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

1
2
3
class Solution:
    def minOperations(self, nums: list[int]) -> int:
        return sum(max(a - b, 0) for a, b in pairwise(nums))

1
2
3
4
5
6
7
8
9
class Solution {
    public long minOperations(int[] nums) {
        long ans = 0;
        for (int i = 1; i < nums.length; ++i) {
            ans += Math.max(nums[i - 1] - nums[i], 0);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    long long minOperations(vector<int>& nums) {
        long long ans = 0;
        for (int i = 1; i < nums.size(); ++i) {
            ans += max(nums[i - 1] - nums[i], 0);
        }
        return ans;
    }
};

1
2
3
4
5
6
func minOperations(nums []int) (ans int64) {
    for i := 1; i < len(nums); i++ {
        ans += max(int64(nums[i-1]-nums[i]), 0)
    }
    return
}

1
2
3
4
5
6
7
function minOperations(nums: number[]): number {
    let ans = 0;
    for (let i = 1; i < nums.length; ++i) {
        ans += Math.max(nums[i - 1] - nums[i], 0);
    }
    return ans;
}

Comments