Make Array Non-decreasing or Non-increasing - Problem

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.

Input & Output

Example 1 — Mixed Array
$ Input: nums = [3,1,4,2]
Output: 4
💡 Note: Transform to non-decreasing [1,1,3,3]: |3-1| + |1-1| + |4-3| + |2-3| = 2 + 0 + 1 + 1 = 4 operations
Example 2 — Already Sorted
$ Input: nums = [1,2,3,4]
Output: 0
💡 Note: Array is already non-decreasing, so no operations needed
Example 3 — Reverse Order
$ Input: nums = [5,4,3,2,1]
Output: 0
💡 Note: Array is already non-increasing, so no operations needed

Constraints

  • 1 ≤ nums.length ≤ 300
  • 1 ≤ nums[i] ≤ 100

Visualization

Tap to expand
Make Array Monotonic: [3,1,4,2]3142Original ArrayTry Non-decreasing: [1,1,3,3]11332 ops0 ops1 op1 opCost: |3-1| + |1-1| + |4-3| + |2-3| = 2 + 0 + 1 + 1 = 4Minimum Operations: 4
Understanding the Visualization
1
Input
Array [3,1,4,2] - neither sorted order
2
Try Both
Consider non-decreasing and non-increasing options
3
Output
Minimum operations needed: 4
Key Takeaway
🎯 Key Insight: Try both monotonic directions and use DP with original array values as targets
Asked in
Google 25 Amazon 18 Microsoft 15
15.4K Views
Medium Frequency
~35 min Avg. Time
680 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen