Make Array Non-decreasing or Non-increasing

Make Array Non-decreasing or Non-increasing

What is this problem about?

The Make Array Non-decreasing or Non-increasing problem asks you to take an array of integers and apply operations to it. In one operation, you can either increment or decrement an element by 1. Your goal is to find the minimum total number of operations (cost) required to make the array sorted, either perfectly non-decreasing (ascending) or perfectly non-increasing (descending).

Why is this asked in interviews?

This is a famously difficult problem (often associated with competitive programming) that occasionally appears in very high-level tech interviews. It rigorously tests a candidate's knowledge of advanced Greedy Algorithms and Priority Queues (Heaps). It assesses your ability to map out a "cost function" and use a heap to dynamically flatten peaks and valleys in an array.

Algorithmic pattern used

The most efficient approach uses a Max Heap (Priority Queue) to track the optimal sequence dynamically. We solve the problem twice: once to find the cost for non-decreasing, and once for non-increasing (by simply reversing the array and running the exact same non-decreasing logic). To make an array non-decreasing, we iterate through it. If the current number is smaller than the maximum number we've seen so far (stored in the max heap), it creates a violation. We add the difference to our total cost, and "replace" the peak in our heap with the current number, flattening the curve.

Example explanation

Let's find the cost to make [3, 2, 4, 1] non-decreasing. Heap: [], Cost = 0.

• 3: Push 3 to Heap. Heap [3].
• 2: 2 < max(Heap) (which is 3). Violation!
  • Cost += 3 - 2 = 1.
  • Pop 3. Push 2. Push 2 again (to maintain state). Heap [2, 2].
  • Array effectively becomes [2, 2, 4, 1].
• 4: 4 >= 2. No violation. Push 4. Heap [4, 2, 2].
• 1: 1 < max(Heap) (4). Violation!
  • Cost += 4 - 1 = 3. Total cost = 4.
  • Pop 4. Push 1, Push 1. Heap [2, 2, 1, 1]. The cost to make it non-decreasing is 4. (We would also check non-increasing by reversing the array and comparing costs).

Common mistakes candidates make

A common trap is trying to use standard 2D Dynamic Programming. While a DP approach like dp[index][value] works conceptually, the values in the array can be very large, making the DP matrix impossibly huge and causing Memory and Time Limit Exceeded errors. Another mistake is forgetting to push the current element into the heap twice when a violation occurs, which is mathematically necessary to represent the "slope" adjustment.

Interview preparation tip

If you encounter the Make Array Non-decreasing or Non-increasing coding problem, the "Slope Trick" using Priority Queues is the golden key. It is an advanced competitive programming pattern. Focus on understanding why popping the maximum and pushing the smaller element twice correctly offsets the cost of flattening the array.