HardNo. 2263LeetCode Premium
Make Array Non-decreasing or Non-increasing — LeetCode 2263 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Example
- Input
- nums = [3,2,4,5,0]
- Output
- 4
- Explanation
- One possible way to turn nums into non-increasing order is to:
Python solution
class Solution:
def convertArray(self, nums: List[int]) -> int:
def solve(nums):
n = len(nums)
f = [[0] * 1001 for _ in range(n + 1)]
for i, x in enumerate(nums, 1):
mi = inf
for j in range(1001):
if mi > f[i - 1][j]:
mi = f[i - 1][j]
f[i][j] = mi + abs(x - j)
return min(f[n])
return min(solve(nums), solve(nums[::-1]))Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 2263. Make Array Non-decreasing or Non-increasing is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0044 | Wildcard Matching | Hard |
| 0045 | Jump Game II | Medium |
| 0055 | Jump Game | Medium |
| 0122 | Best Time to Buy and Sell Stock II | Medium |
| 0376 | Wiggle Subsequence | Medium |
| 0397 | Integer Replacement | Medium |
Frequently asked questions
- How hard is LeetCode 2263. Make Array Non-decreasing or Non-increasing?
LeetCode 2263. Make Array Non-decreasing or Non-increasing is rated Hard on LeetCode.
- What topics does LeetCode 2263. Make Array Non-decreasing or Non-increasing cover?
LeetCode 2263. Make Array Non-decreasing or Non-increasing is tagged Greedy and Dynamic Programming on LeetCode.
- Is LeetCode 2263. Make Array Non-decreasing or Non-increasing a premium problem?
Yes. LeetCode 2263. Make Array Non-decreasing or Non-increasing is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.