Make Array Non-decreasing or Non-increasing - Solution & Explanation

Problem Overview: You are given an integer array and can change any element to any value with a cost equal to the absolute difference. The goal is to make the array either non-decreasing or non-increasing while minimizing the total modification cost.

Approach 1: Dynamic Programming with Value Compression (O(n * m) time, O(m) space)

This approach treats the problem as a dynamic programming optimization. First collect all possible candidate values (usually the sorted version of the array). For each position i and candidate value v, compute the minimum cost to make the prefix valid if nums[i] becomes v. To maintain the non-decreasing constraint, transitions only come from candidate values ≤ v. Maintain prefix minimums to speed up the transition. Each state adds abs(nums[i] - v) to the previous minimum cost. Repeat the same process for the reversed array to simulate the non-increasing case.

This method is conceptually straightforward and useful when explaining the structure of the problem. However, the number of candidate values m can be up to n, giving O(n * m) time, which becomes slower for large inputs.

Approach 2: Greedy with Priority Queue (Optimal) (O(n log n) time, O(n) space)

A more efficient solution uses a greedy strategy with a max heap from greedy algorithms and a priority queue. Iterate through the array while maintaining a max heap of previously chosen values. Push each number into the heap. If the maximum element in the heap becomes larger than the current number, the non-decreasing constraint is violated. Fix it by lowering that previous value to the current number. The cost added is heap_top - current. Pop the top element and insert the corrected value.

The intuition is that when a previous element is too large, decreasing the largest one produces the smallest possible cost increase. The heap efficiently tracks which earlier element causes the biggest violation. This greedy correction guarantees minimal total adjustment cost.

To handle the non-increasing case, apply the same algorithm after reversing the array or by negating values. Compute both costs and return the minimum.

Recommended for interviews: Start by describing the dynamic programming formulation because it clearly models the constraint. Then present the greedy heap optimization. Interviewers typically expect the O(n log n) heap solution since it demonstrates pattern recognition and efficient constraint handling.