Skip to main content
Talentd

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

HardPremiumFree on FleetCodeDynamic ProgrammingGreedy5 min readAsked at: Google, VMware
Practice this problem

Problem Statement

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?

Approach Overview

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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Value CompressionO(n * m)O(m)When explaining the full DP formulation or when candidate values are small
Greedy with Max Heap (Priority Queue)O(n log n)O(n)Best general solution; handles large arrays efficiently
Greedy Heap on Reversed ArrayO(n log n)O(n)Used to compute the non-increasing transformation cost

Video Solution

2263. Make Array Non-decreasing or Non-increasing (Leetcode Hard) • Programming Live with Larry • 659 views views

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Make Array Non-decreasing or Non-increasing with our built-in code editor and test cases.

Practice on FleetCode
Previous

Make Array Strictly Increasing

Next

Minimum Operations to Make the Array Increasing