Leetcode Problem 2263. Make Array Non-decreasing or Non-increasing

2263. Make Array Non-decreasing or Non-increasing

Leetcode Solutions

DP with Rolling Minimum

  1. Initialize a 2D DP array dp with size n x (maxValue + 1) where n is the length of nums and maxValue is the maximum value in nums.
  2. Fill the first row of dp with the cost to change nums[0] to each possible value j.
  3. For each element i from 1 to n-1, iterate over all possible values j from 0 to maxValue.
  4. Maintain a rolling minimum curmin which represents the minimum cost to make the subarray nums[0...i-1] non-decreasing with nums[i-1] set to any value from 0 to j.
  5. Set dp[i][j] to curmin + abs(nums[i] - j).
  6. After filling the DP table, find the minimum value in the last row of dp for the non-decreasing case.
  7. Repeat steps 2-6 for the non-increasing case by reversing nums and iterating from n-1 to 0.
  8. Return the minimum of the two values obtained from the non-decreasing and non-increasing cases.
UML Thumbnail

Greedy with Max Heap

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...