LeetCode 2263 - Make Array Non-decreasing or Non-increasing

The problem asks us to transform a given integer array nums into either a non-decreasing or a non-increasing array with the minimum number of operations. Each operation allows increasing or decreasing an element by exactly 1.

leetcodehardarraydynamic-programminggreedyheap-(priority-queue)

LeetCode Problem 2263

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks us to transform a given integer array nums into either a non-decreasing or a non-increasing array with the minimum number of operations. Each operation allows increasing or decreasing an element by exactly 1.

A non-decreasing array is one in which every element is greater than or equal to the previous element, i.e., nums[i] <= nums[i+1]. A non-increasing array is one in which every element is less than or equal to the previous element, i.e., nums[i] >= nums[i+1].

The input is a list of integers between 0 and 1000, and its length can go up to 1000. The output is a single integer representing the minimum total number of increment/decrement operations needed to satisfy either of the two monotone conditions.

Important edge cases to consider include:

  • Arrays of length 1 (already monotone, 0 operations needed).
  • Arrays that are already non-decreasing or non-increasing (0 operations needed).
  • Arrays where all elements are equal (already monotone).
  • Arrays with alternating high/low patterns, which might need multiple adjustments.

The key challenge is that each element can be adjusted individually, but we must consider the global order constraint when choosing the target values.

Approaches

Brute Force

A brute-force approach would attempt to check every possible final array configuration that is non-decreasing or non-increasing. For each element, we could try all possible values from 0 to 1000 and calculate the number of operations required. We would then select the configuration with the minimum total operations. This approach is correct but extremely inefficient, with a time complexity of O(n * 1000^n), which is infeasible for n up to 1000.

Optimal Approach

The key observation is that we can model this as a Dynamic Programming (DP) problem where the state represents the minimum number of operations needed to make the first i elements monotone if the i-th element is set to a specific value. Since the values of nums[i] are bounded (0 to 1000), we can limit our DP table to these values.

  1. For non-decreasing arrays, we can iterate from left to right and, for each possible value of nums[i], choose the minimum operation cost considering all smaller or equal previous values.
  2. For non-increasing arrays, we can do the same but reverse the direction (or negate the array to reuse the same logic).

This is equivalent to solving a monotone DP problem with value compression from 0 to 1000. The DP table size is manageable (n * 1001) for the given constraints, making this approach feasible.

Approach Time Complexity Space Complexity Notes
Brute Force O(1000^n) O(1) Try all possible final values for each element
Optimal (DP) O(n * maxVal) O(maxVal) Use DP to track min operations for each possible element value (maxVal = 1001)

Algorithm Walkthrough

  1. Initialize a DP array of size maxVal = 1001, where dp[v] represents the minimum operations needed to make the array non-decreasing up to the current index with the last element being v.
  2. Iterate through each element num in nums.
  3. For each possible target value v from 0 to 1000:
  • Update dp[v] as the sum of abs(num - v) plus the minimum dp[u] for all u <= v.
  • This ensures the array remains non-decreasing.
  1. After processing all elements, the answer for non-decreasing transformation is min(dp).
  2. To handle non-increasing arrays, either reverse the array or negate values and reuse the same DP logic.
  3. Return the minimum of non-decreasing and non-increasing results.

Why it works: The DP array maintains the invariant that at each step, dp[v] is the minimal total operations for a valid monotone array ending with value v. By considering all possible last values and combining with previous minima, we guarantee the global minimum for the array.

Python Solution

from typing import List
import sys

class Solution:
    def convertArray(self, nums: List[int]) -> int:
        def min_operations(arr: List[int]) -> int:
            max_val = 1001
            dp = [0] * max_val
            for i, num in enumerate(arr):
                new_dp = [0] * max_val
                min_so_far = sys.maxsize
                for v in range(max_val):
                    min_so_far = min(min_so_far, dp[v])
                    new_dp[v] = min_so_far + abs(num - v)
                dp = new_dp
            return min(dp)
        
        inc_ops = min_operations(nums)
        dec_ops = min_operations(nums[::-1])
        return min(inc_ops, dec_ops)

Explanation: We define a helper min_operations that calculates the minimum operations to make an array non-decreasing. For each element, we iterate over all possible values and use a running minimum (min_so_far) to efficiently track the best previous cost that keeps the array monotone. We compute this for both the original array (non-decreasing) and the reversed array (non-increasing) and return the smaller result.

Go Solution

import (
    "math"
)

func convertArray(nums []int) int {
    maxVal := 1001

    minOperations := func(arr []int) int {
        dp := make([]int, maxVal)
        for i := range arr {
            newDp := make([]int, maxVal)
            minSoFar := math.MaxInt32
            for v := 0; v < maxVal; v++ {
                if dp[v] < minSoFar {
                    minSoFar = dp[v]
                }
                newDp[v] = minSoFar + abs(arr[i]-v)
            }
            dp = newDp
        }
        minOps := math.MaxInt32
        for _, val := range dp {
            if val < minOps {
                minOps = val
            }
        }
        return minOps
    }

    incOps := minOperations(nums)
    decOps := minOperations(reverse(nums))
    if incOps < decOps {
        return incOps
    }
    return decOps
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func reverse(arr []int) []int {
    n := len(arr)
    res := make([]int, n)
    for i := 0; i < n; i++ {
        res[i] = arr[n-1-i]
    }
    return res
}

Go-specific notes: Go requires manual handling of abs and array reversal. We also handle math.MaxInt32 for initialization of running minima.

Worked Examples

Example 1: nums = [3,2,4,5,0]

Step-by-step for non-decreasing DP:

i num dp[0..5] sample min_so_far new_dp[0..5] sample
0 3 0 0 3
1 2 prev dp 3 2+3=5
2 4 ... ... ...

After DP, min(dp) = 4 for non-increasing.

Result: 4 operations.

Example 2: nums = [2,2,3,4]

Already non-decreasing, min(dp) = 0

Example 3: nums = [0]

Single element, min(dp) = 0

Complexity Analysis

Measure Complexity Explanation
Time O(n * 1001) For each of n elements, we iterate over max value range 0-1000
Space O(1001) We only keep current DP array of size 1001

The algorithm efficiently reduces the problem to DP over bounded value range rather than trying all permutations.

Test Cases

# Basic examples
assert Solution().convertArray([3,2,4,5,0]) == 4  # Example 1
assert Solution().convertArray([2,2,3,4]) == 0    # Example 2
assert Solution().convertArray([0]) == 0          # Example 3

# Edge cases
assert Solution().convertArray([1,1,1,1]) == 0    # Already monotone
assert Solution().convertArray([5,4,3,2,1]) == 0  # Already non-increasing
assert Solution().convertArray([1,1000,1,1000]) == 1998  # Alternating extremes
assert Solution().convertArray([0,500,1000]) == 500       # Need small adjustments
Test Why
[3,2,4,5,0] Typical case requiring adjustments
[2,2,3,4] Already non-decreasing
[0] Single element
[1,1,1,1] All elements equal
[5,4,