LeetCode Solutions Blog

Make Array Non-decreasing or Non-increasing

Number: 1419

Difficulty: Hard

Paid? Yes

Problem Description

Given a 0-indexed integer array nums, determine the minimum number of operations required to transform it into either a non-decreasing or non-increasing sequence. In one operation, you can choose any index i and either add 1 or subtract 1 from nums[i].

Key Insights

The problem is equivalent to finding a target sequence (either non-decreasing or non-increasing) that minimizes the total adjustments (absolute differences).
We can use dynamic programming (DP) to compute the minimal cost for adjusting the array.
For the non-decreasing case, each element's chosen value must be at least the value chosen for the previous element.
For non-increasing order, each element's chosen value must be at most the previous one.
By iterating over all possible target values (0 through 1000) for each index and using prefix (or suffix) minimums to speed up state transitions, we can obtain the solution efficiently.
Compute the result for both monotonic orders and return the smaller one.

Space and Time Complexity

Time Complexity: O(n * M), where n is the length of nums and M is 1001 (the range of possible values). Space Complexity: O(M), by using rolling arrays to update the DP state.

Solution

We solve the problem with two DP routines: one for forming a non-decreasing sequence and one for a non-increasing sequence. For each index i and for every possible new value v (0 ≤ v ≤ 1000), the DP state records the minimal cost to adjust nums[0...i] so that the iᵗʰ element becomes v and the monotonic property is satisfied. For the non-decreasing case, we enforce that the previous value is at most v; for non-increasing, the previous value is at least v. By precomputing prefix (or suffix) minima for each state transition, we efficiently update the DP states.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java, with detailed line-by-line comments.

def min_operations(nums):
    # M is the number of possible values (0 to 1000)
    M = 1001
    n = len(nums)
    
    # Function to compute minimum operations for a non-decreasing sequence.
    def non_decreasing():
        # Initialize DP for index 0: cost to set nums[0] to each possible value.
        dp = [abs(val - nums[0]) for val in range(M)]
        for i in range(1, n):
            new_dp = [0] * M
            # Build a prefix minimum array from the previous dp.
            prefix_min = [0] * M
            prefix_min[0] = dp[0]
            for val in range(1, M):
                prefix_min[val] = min(prefix_min[val - 1], dp[val])
            # For each possible value for current element:
            for curr_val in range(M):
                # The cost is the cost to change nums[i] plus the best cost for any previous value <= curr_val.
                new_dp[curr_val] = abs(nums[i] - curr_val) + prefix_min[curr_val]
            dp = new_dp
        return min(dp)
    
    # Function to compute minimum operations for a non-increasing sequence.
    def non_increasing():
        dp = [abs(val - nums[0]) for val in range(M)]
        for i in range(1, n):
            new_dp = [0] * M
            # Build a suffix minimum array since previous value must be >= current value.
            suffix_min = [0] * M
            suffix_min[M - 1] = dp[M - 1]
            for val in range(M - 2, -1, -1):
                suffix_min[val] = min(suffix_min[val + 1], dp[val])
            for curr_val in range(M):
                new_dp[curr_val] = abs(nums[i] - curr_val) + suffix_min[curr_val]
            dp = new_dp
        return min(dp)
    
    # Return the minimum cost from either transformation.
    return min(non_decreasing(), non_increasing())

# Example usage:
print(min_operations([3,2,4,5,0]))  # Expected output: 4

if __name__ == "__main__":
    print(min_operations([2,2,3,4]))  # Expected output: 0
    print(min_operations([0]))        # Expected output: 0