Minimize Operation to Make Array Non-decreasing or Non-increasing
Given an integer array arr[]. In one operation, you can choose an index i and either increment or decrement arr[i] by 1. The task is to find the minimum number of operations needed to make arr either non-decreasing or non-increasing.
Example:
Input: arr = [3, 2, 4, 5, 0]
Output: 4
Explanation: One possible way to turn arr into non-increasing order is to:
- Add 1 to arr[1] once so that it becomes 3.
- Subtract 1 from arr[2] once so it becomes 3.
- Subtract 1 from arr[3] twice so it becomes 3. After doing the 4 operations, arr becomes [3, 3, 3, 3, 0] which is in non-increasing order.
Input: arr = [2, 2, 3, 4]
Output: 0
Explanation: arr is already in non-decreasing order, so no operations are needed and we return 0.
Approach:
There is no need to go below the minimum value or go above the maximum value. Check increasing and decreasing separately.
- For increasing, define dp[i][j] as the minimum operations to make arr[0,i] increasing and <= j, where dp[i][j] = min(dp[i][j-1], dp[i-1][j] + abs(arr[i] – j)).
- For decreasing, define dp[i][j] as the minimum operations to make arr[0,i] decreasing and >= j, where dp[i][j] = min(dp[i][j+1], dp[i-1][j] + abs(arr[i] – j)).
Step-by-step approach:
- Implement the inc() function:
- Create a 2D dynamic programming (DP) array dp of size (n+1) x (max_val-min_val+1), where n is the length of the arr array.
- Initialize the first row of the dp array with the absolute difference between each element and the minimum value min_val.
- Iterate through the arr array and fill the dp array. For each element, calculate the minimum number of operations needed to either increment or keep the element the same.
- Return the value stored in dp[n][max_val-min_val], which represents the minimum number of operations needed to make the array non-decreasing.
- Implement the dec() function:
- Similar to the inc() function, create a 2D dp array and initialize the first row.
- Iterate through the arr array and fill the dp array.
- For each element, calculate the minimum number of operations needed to either decrement or keep the element the same.
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
// Helper function to convert the array by increasing all
// elements
int inc(const vector<int>& nums, int n, int min_val,
int max_val)
{
vector<vector<int> > dp(
n + 1, vector<int>(max_val - min_val + 1));
// Iterate through the array and fill the dp table
for (int i = 1; i <= n; ++i) {
dp[i][0]
= dp[i - 1][0] + abs(nums[i - 1] - min_val);
for (int j = 1; j <= max_val - min_val; ++j) {
dp[i][j] = dp[i - 1][j]
+ abs(nums[i - 1] - min_val - j);
dp[i][j] = min(dp[i][j], dp[i][j - 1]);
}
}
return dp[n][max_val - min_val];
}
// Helper function to convert the array by decreasing all
// elements
int dec(const vector<int>& nums, int n, int min_val,
int max_val)
{
vector<vector<int> > dp(
n + 1, vector<int>(max_val - min_val + 1));
// Iterate through the array and fill the dp table
for (int i = 1; i <= n; ++i) {
dp[i][max_val - min_val]
= dp[i - 1][max_val - min_val]
+ abs(nums[i - 1] - max_val);
for (int j = max_val - min_val - 1; j >= 0; --j) {
dp[i][j] = dp[i - 1][j]
+ abs(nums[i - 1] - min_val - j);
dp[i][j] = min(dp[i][j], dp[i][j + 1]);
}
}
return dp[n][0];
}
// Function to convert the given array to a new array with
// minimum sum of absolute differences
int convertArray(vector<int>& nums)
{
int n = nums.size();
int min_val = INT_MAX;
int max_val = INT_MIN;
// Find the minimum and maximum value in the input array
for (int num : nums) {
min_val = min(min_val, num);
max_val = max(max_val, num);
}
// Return the minimum of the results from the inc() and
// dec() functions
return min(inc(nums, n, min_val, max_val),
dec(nums, n, min_val, max_val));
}
int main()
{
vector<int> nums = { 3, 2, 4, 5, 0 };
int result = convertArray(nums);
cout << "Minimum cost: " << result << endl;
return 0;
}
import java.util.Arrays;
public class Main {
// Helper function to convert the array by increasing
// all elements
static int inc(int[] nums, int n, int minVal,
int maxVal)
{
int[][] dp = new int[n + 1][maxVal - minVal + 1];
// Iterate through the array and fill the dp table
for (int i = 1; i <= n; ++i) {
dp[i][0] = dp[i - 1][0]
+ Math.abs(nums[i - 1] - minVal);
for (int j = 1; j <= maxVal - minVal; ++j) {
dp[i][j]
= dp[i - 1][j]
+ Math.abs(nums[i - 1] - minVal - j);
dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]);
}
}
return dp[n][maxVal - minVal];
}
// Helper function to convert the array by decreasing
// all elements
static int dec(int[] nums, int n, int minVal,
int maxVal)
{
int[][] dp = new int[n + 1][maxVal - minVal + 1];
// Iterate through the array and fill the dp table
for (int i = 1; i <= n; ++i) {
dp[i][maxVal - minVal]
= dp[i - 1][maxVal - minVal]
+ Math.abs(nums[i - 1] - maxVal);
for (int j = maxVal - minVal - 1; j >= 0; --j) {
dp[i][j]
= dp[i - 1][j]
+ Math.abs(nums[i - 1] - minVal - j);
dp[i][j] = Math.min(dp[i][j], dp[i][j + 1]);
}
}
return dp[n][0];
}
// Function to convert the given array to a new array
// with minimum sum of absolute differences
static int convertArray(int[] nums)
{
int n = nums.length;
int minVal = Integer.MAX_VALUE;
int maxVal = Integer.MIN_VALUE;
// Find the minimum and maximum value in the input
// array
for (int num : nums) {
minVal = Math.min(minVal, num);
maxVal = Math.max(maxVal, num);
}
// Return the minimum of the results from the inc()
// and dec() functions
return Math.min(inc(nums, n, minVal, maxVal),
dec(nums, n, minVal, maxVal));
}
public static void main(String[] args)
{
int[] nums = { 3, 2, 4, 5, 0 };
int result = convertArray(nums);
System.out.println("Minimum cost: " + result);
}
}
import sys
from typing import List
# Helper function to convert the array by increasing all elements
def inc(nums: List[int], n: int, min_val: int, max_val: int) -> int:
dp = [[0 for _ in range(max_val - min_val + 1)] for _ in range(n + 1)]
# Iterate through the array and fill the dp table
for i in range(1, n + 1):
dp[i][0] = dp[i - 1][0] + abs(nums[i - 1] - min_val)
for j in range(1, max_val - min_val + 1):
dp[i][j] = dp[i - 1][j] + abs(nums[i - 1] - min_val - j)
dp[i][j] = min(dp[i][j], dp[i][j - 1])
return dp[n][max_val - min_val]
# Helper function to convert the array by decreasing all elements
def dec(nums: List[int], n: int, min_val: int, max_val: int) -> int:
dp = [[0 for _ in range(max_val - min_val + 1)] for _ in range(n + 1)]
# Iterate through the array and fill the dp table
for i in range(1, n + 1):
dp[i][max_val - min_val] = dp[i - 1][max_val -
min_val] + abs(nums[i - 1] - max_val)
for j in range(max_val - min_val - 1, -1, -1):
dp[i][j] = dp[i - 1][j] + abs(nums[i - 1] - min_val - j)
dp[i][j] = min(dp[i][j], dp[i][j + 1])
return dp[n][0]
# Function to convert the given array to a new array with minimum sum of absolute differences
def convertArray(nums: List[int]) -> int:
n = len(nums)
min_val = min(nums)
max_val = max(nums)
# Return the minimum of the results from the inc() and dec() functions
return min(inc(nums, n, min_val, max_val), dec(nums, n, min_val, max_val))
def main():
nums = [3, 2, 4, 5, 0]
result = convertArray(nums)
print("Minimum cost:", result)
if __name__ == "__main__":
main()
// Helper function to convert the array by increasing all elements
function inc(nums, n, min_val, max_val) {
const dp = Array.from({ length: n + 1 }, () => Array(max_val - min_val + 1).fill(0));
// Iterate through the array and fill the dp table
for (let i = 1; i <= n; ++i) {
dp[i][0] = dp[i - 1][0] + Math.abs(nums[i - 1] - min_val);
for (let j = 1; j <= max_val - min_val; ++j) {
dp[i][j] = dp[i - 1][j] + Math.abs(nums[i - 1] - min_val - j);
dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]);
}
}
return dp[n][max_val - min_val];
}
// Helper function to convert the array by decreasing all elements
function dec(nums, n, min_val, max_val) {
const dp = Array.from({ length: n + 1 }, () => Array(max_val - min_val + 1).fill(0));
// Iterate through the array and fill the dp table
for (let i = 1; i <= n; ++i) {
dp[i][max_val - min_val] = dp[i - 1][max_val - min_val] + Math.abs(nums[i - 1] - max_val);
for (let j = max_val - min_val - 1; j >= 0; --j) {
dp[i][j] = dp[i - 1][j] + Math.abs(nums[i - 1] - min_val - j);
dp[i][j] = Math.min(dp[i][j], dp[i][j + 1]);
}
}
return dp[n][0];
}
// Function to convert the given array to a new array with minimum sum of absolute differences
function convertArray(nums) {
const n = nums.length;
let min_val = Infinity;
let max_val = -Infinity;
// Find the minimum and maximum value in the input array
for (const num of nums) {
min_val = Math.min(min_val, num);
max_val = Math.max(max_val, num);
}
// Return the minimum of the results from the inc() and dec() functions
return Math.min(inc(nums, n, min_val, max_val), dec(nums, n, min_val, max_val));
}
const nums = [3, 2, 4, 5, 0];
const result = convertArray(nums);
console.log(`Minimum cost: ${result}`);
// This code is contributed by Ayush Mishra
Output
Minimum cost: 4
Time Complexity: O(n*(max-min))
Auxiliary Space: O(n*(max-min))
Contact Us