Is Make Array Non-decreasing or Non-increasing easy or hard?

LeetCode classifies this problem as Hard because the optimal approach requires recognizing a greedy heap pattern or formulating a dynamic programming state transition. While the concept is simple, deriving the efficient O(n log n) solution is not immediately obvious.

Make Array Non-decreasing or Non-increasing Python/Java solution

In Python, the solution typically uses the heapq module (simulating a max heap with negative values). Java implementations rely on PriorityQueue with a reverse comparator. Both implementations follow the same greedy logic and run in O(n log n) time.

How to solve Make Array Non-decreasing or Non-increasing in O(n)?

A strict O(n) solution is generally not used because maintaining order corrections requires tracking the largest violating element. The practical optimal solution uses a priority queue and runs in O(n log n). This allows efficient detection and correction of order violations while minimizing total modification cost.

What is the best approach for Make Array Non-decreasing or Non-increasing?

The optimal approach uses a greedy strategy with a max heap (priority queue). Iterate through the array and keep previous values in a heap. If a previous value is larger than the current element, reduce the largest previous value and add the difference to the cost. This algorithm runs in O(n log n) time and guarantees the minimum adjustment cost.

Is Make Array Non-decreasing or Non-increasing asked at Google/Amazon/Meta?

Problems involving array transformations, greedy adjustments, and priority queues appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of greedy optimization, heap usage, and dynamic programming tradeoffs.

What data structure is used in Make Array Non-decreasing or Non-increasing?

The optimal solution uses a max heap (priority queue) to track previously processed elements. Dynamic programming solutions may also use arrays for state transitions and prefix minimums when evaluating candidate values.

What is the time complexity of Make Array Non-decreasing or Non-increasing?

The most efficient solution runs in O(n log n) time using a heap-based greedy algorithm. Each element is inserted into a priority queue and may trigger one heap adjustment. The space complexity is O(n) for storing heap elements.

Description Hints 3 Solution Video 1:10:21

2263. Make Array Non-decreasing or Non-increasing

Hard64.7% acceptance2 companiesPremium elsewhere, free here

You are given a 0-indexed integer array nums. In one operation, you can:

Choose an index i in the range 0 <= i < nums.length
Set nums[i] to nums[i] + 1 or nums[i] - 1

Return the minimum number of operations to make nums non-decreasing or non-increasing.

Example 1:

Input: nums = [3,2,4,5,0]
Output: 4
Explanation:
One possible way to turn nums into non-increasing order is to:
- Add 1 to nums[1] once so that it becomes 3.
- Subtract 1 from nums[2] once so it becomes 3.
- Subtract 1 from nums[3] twice so it becomes 3.
After doing the 4 operations, nums becomes [3,3,3,3,0] which is in non-increasing order.
Note that it is also possible to turn nums into [4,4,4,4,0] in 4 operations.
It can be proven that 4 is the minimum number of operations needed.

Example 2:

Input: nums = [2,2,3,4]
Output: 0
Explanation: nums is already in non-decreasing order, so no operations are needed and we return 0.

Example 3:

Input: nums = [0]
Output: 0
Explanation: nums is already in non-decreasing order, so no operations are needed and we return 0.

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

Follow up: Can you solve it in O(n*log(n)) time complexity?

Asked at 2 companies

VMware

Google

Topics

Dynamic Programming Greedy

Hints open one at a time

Hint 1

To find the minimum cost to make nums non-decreasing, use a max heap that contains all of the elements that you have seen so far.

Hint 2

If the largest number in the heap is greater than the current number, calculate the cost to make the two numbers equal. Then, in the heap, replace the largest number with the current number.

Hint 3

Now that we have found the minimum cost to make nums non-decreasing, we can set every nums[i] to -nums[i] and do the same process to find the minimum cost to make nums non-increasing.

1:10:21

Still stuck?Read the written solution, or watch a walkthrough.

Open solution