Minimum increment or decrement required to sort the array | Top-down Approach

0 0 9 minutes read

Given an array arr[] of N integers, the task is to sort the array in increasing order by performing a minimum number of operations. In a single operation, an element of the array can either be incremented or decremented by 1. Print the minimum number of operations required.
Examples:

Input: arr[] = {5, 4, 3, 2, 1}
Output: 6
Explanation:
The sorted array of arr[] is {3, 3, 3, 3, 3}
Therefore the minimum increments/decrement are:
At index 0, 5 – 3 = 2 (decrement 2)
At index 1, 4 – 3 = 1 (decrement 1)
At index 3, 2 + 1 = 3 (increment 1)
At index 4, 1 + 2 = 3 (increment 2)
The total increment/decrement is 2 + 1 + 1 + 2 = 6.
Input: arr[] = {1, 2, 3, 4}
Output: 0
Explanation:
The array is already sorted.

Bottom-up Approach: This problem can be solved using Dynamic Programming. A Bottom-up Approach to this problem statement is discussed in this article.
Top-Down Approach: Here we will use Top-down Dynamic Programming to solve this problem.
Let 2D array (say dp[i][j]) used to store the upto index i where last element is at index j.
Below are the steps:

To make the array element in sorted by using the given operations, we know that an element cannot become greater than the maximum value of the array and less than the minimum value of the array(say m) by increment or decrement.
Therefore, Fix an element(say X) at ith position, then (i-1)th position value(say Y) can be in the range [m, X].
Keep placing the smaller element less than or equals to arr[i] at (i-1)th position for every index i of arr[] and calculate the minimum increment or decrement by adding abs(arr[i] – Y).
Therefore the recurrence relation for the above mentioned approach can be written as:

dp[i][j] = min(dp[i][j], abs(arr[i] – Y) + recursive_function(i-1, Y))
where m ? Y ? arr[j].

Below is the implementation of the above approach:

C++

// C++ program of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Dp array to memoized
// the value recursive call
int dp[1000][1000];
 
// Function to find the minimum increment
// or decrement needed to make the array
// sorted
int minimumIncDec(int arr[], int N,
                  int maxE, int minE)
{
    // If only one element is present,
    // then arr[] is sorted
    if (N == 0) {
        return 0;
    }
 
    // If dp[N][maxE] is precalculated,
    // then return the result
    if (dp[N][maxE])
        return dp[N][maxE];
 
    int ans = INT_MAX;
 
    // Iterate from minE to maxE which
    // placed at previous index
    for (int k = minE; k <= maxE; k++) {
 
        // Update the answer according to
        // recurrence relation
        int x = minimumIncDec(arr, N - 1, k, minE);
        ans = min(ans,x + abs(arr[N - 1] - k));
    }
 
    // Memoized the value
    // for dp[N][maxE]
    dp[N][maxE] = ans;
 
    // Return the final result
    return dp[N][maxE];
}
 
// Driver Code
int main()
{
    int arr[] = { 5, 4, 3, 2, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Find the minimum and maximum
    // element from the arr[]
    int minE = *min_element(arr, arr + N);
    int maxE = *max_element(arr, arr + N);
 
    // Function Call
    cout << minimumIncDec(
        arr, N, maxE, minE);
    return 0;
}

Java

// Java program of the above approach
import java.util.*;
 
class GFG{
 
// Dp array to memoized
// the value recursive call
static int [][]dp = new int[1000][1000];
 
// Function to find the minimum increment
// or decrement needed to make the array
// sorted
static int minimumIncDec(int arr[], int N,
                         int maxE, int minE)
{
     
    // If only one element is present,
    // then arr[] is sorted
    if (N == 0)
    {
        return 0;
    }
     
    // If dp[N][maxE] is precalculated,
    // then return the result
    if (dp[N][maxE] != 0)
        return dp[N][maxE];
 
    int ans = Integer.MAX_VALUE;
 
    // Iterate from minE to maxE which
    // placed at previous index
    for(int k = minE; k <= maxE; k++)
    {
 
        // Update the answer according to
        // recurrence relation
        int x = minimumIncDec(arr, N - 1, k, minE);
        ans = Math.min(ans, 
                       x + Math.abs(arr[N - 1] - k));
    }
 
    // Memoized the value
    // for dp[N][maxE]
    dp[N][maxE] = ans;
 
    // Return the final result
    return dp[N][maxE];
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 5, 4, 3, 2, 1 };
    int N = arr.length;
 
    // Find the minimum and maximum
    // element from the arr[]
    int minE = Arrays.stream(arr).min().getAsInt();
    int maxE = Arrays.stream(arr).max().getAsInt();
 
    // Function call
    System.out.print(minimumIncDec(
        arr, N, maxE, minE));
}
}
 
// This code is contributed by amal kumar choubey 

Python3

# Python3 program of the above approach
import sys
 
# Dp array to memoized
# the value recursive call
dp = [[ 0 for x in range(1000)]
          for y in range(1000)]
 
# Function to find the minimum increment
# or decrement needed to make the array
# sorted
def minimumIncDec(arr, N, maxE, minE):
 
    # If only one element is present,
    # then arr[] is sorted
    if (N == 0):
        return 0
 
    # If dp[N][maxE] is precalculated,
    # then return the result
    if (dp[N][maxE]):
        return dp[N][maxE]
 
    ans = sys.maxsize
 
    # Iterate from minE to maxE which
    # placed at previous index
    for k in range(minE, maxE + 1):
 
        # Update the answer according to
        # recurrence relation
        x = minimumIncDec(arr, N - 1, k, minE)
        ans = min(ans, x + abs(arr[N - 1] - k))
 
    # Memoized the value
    # for dp[N][maxE]
    dp[N][maxE] = ans
 
    # Return the final result
    return dp[N][maxE]
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 5, 4, 3, 2, 1 ]
    N = len(arr)
 
    # Find the minimum and maximum
    # element from the arr[]
    minE = min(arr)
    maxE = max(arr)
 
    # Function Call
    print(minimumIncDec(arr, N, maxE, minE))
 
# This code is contributed by chitranayal

C#

// C# program of the above approach
using System;
using System.Linq;
 
class GFG{
 
// Dp array to memoized
// the value recursive call
static int [,]dp = new int[1000, 1000];
 
// Function to find the minimum increment
// or decrement needed to make the array
// sorted
static int minimumIncDec(int []arr, int N,
                         int maxE, int minE)
{
     
    // If only one element is present,
    // then []arr is sorted
    if (N == 0)
    {
        return 0;
    }
     
    // If dp[N,maxE] is precalculated,
    // then return the result
    if (dp[N, maxE] != 0)
        return dp[N, maxE];
 
    int ans = int.MaxValue;
 
    // Iterate from minE to maxE which
    // placed at previous index
    for(int k = minE; k <= maxE; k++)
    {
 
        // Update the answer according to
        // recurrence relation
        int x = minimumIncDec(arr, N - 1, k, minE);
        ans = Math.Min(ans, 
                       x + Math.Abs(arr[N - 1] - k));
    }
 
    // Memoized the value
    // for dp[N,maxE]
    dp[N, maxE] = ans;
 
    // Return the readonly result
    return dp[N,maxE];
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 5, 4, 3, 2, 1 };
    int N = arr.Length;
 
    // Find the minimum and maximum
    // element from the []arr
    int minE = arr.Min();
    int maxE = arr.Max();
 
    // Function call
    Console.Write(minimumIncDec(arr, N, 
                                maxE, minE));
}
}
 
// This code is contributed by Rohit_ranjan

Javascript

<script>
 
// JavaScript program of the above approach
 
// Dp array to memoized
// the value recursive call
let dp = new Array();
 
for(let i = 0; i < 1000; i++){
    let temp = [];
    for(let j = 0; j < 1000; j++){
        temp.push([])
    }
    dp.push(temp)
}
 
// Function to find the minimum increment
// or decrement needed to make the array
// sorted
 
function minimumIncDec(arr, N, maxE, minE)
{
    // If only one element is present,
    // then arr[] is sorted
    if (N == 0) {
        return 0;
    }
    // If dp[N][maxE] is precalculated,
    // then return the result
    if (!dp[N][maxE])
        return dp[N][maxE];
 
    let ans = Number.MAX_SAFE_INTEGER;
 
    // Iterate from minE to maxE which
    // placed at previous index
    for (let k = minE; k <= maxE; k++) {
 
        // Update the answer according to
        // recurrence relation
        let x = minimumIncDec(arr, N - 1, k, minE);
        ans = Math.min(ans,x + Math.abs(arr[N - 1] - k));
    }
 
    // Memoized the value
    // for dp[N][maxE]
    dp[N][maxE] = ans;
 
    // Return the final result
    return dp[N][maxE];
}
 
// Driver Code
 
    let arr = [ 5, 4, 3, 2, 1 ];
    let N = arr.length;
 
    // Find the minimum and maximum
    // element from the arr[]
    let minE = arr.sort((a, b) => a - b)[0];
    let maxE = arr.sort((a, b) => b - a)[0];
 
    // Function Call
    document.write(minimumIncDec(arr, N, maxE, minE));
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Output

Time Complexity: O(N*maxE)
Auxiliary Space: O(N²)

Another approach : Using DP Tabulation method ( Iterative approach )

The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.

Steps to solve this problem :

Create a 2D dynamic array dp of size (N+1) x (maxE+1) and initialize it with zeros.
Use a nested loop to iterate through the remaining rows and columns of dp.
Inside the inner loop, update ans by finding the minimum value between ans and dp[i-1][k] + abs(arr[i-1] – k), where k is the current index in the inner loop.
Store the value of ans in dp[i][j]
After the loops complete, return the value of dp[N][maxE]

Implementation :

C++

// C++ program of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
int minimumIncDec(int arr[], int N,
                int maxE, int minE)
{
    int dp[N+1][maxE+1];
    memset(dp, 0, sizeof(dp));
     
    // If only one element is present,
    // then arr[] is sorted
    for(int j=0;j<=maxE;j++){
        dp[0][j] = 0;
    }
     
    // Iterate from minE to maxE which
    // placed at previous index
    for(int i=1;i<=N;i++){
        for(int j=minE;j<=maxE;j++){
            int ans = INT_MAX;
            for(int k=minE;k<=j;k++){
                // Update the answer according to
                // recurrence relation
                ans = min(ans, dp[i-1][k] + abs(arr[i-1] - k));
            }
             
            // store computation of subproblem
            dp[i][j] = ans;
        }
    }
     
    // Return the final result
    return dp[N][maxE];
}
 
// Driver Code
int main()
{
    int arr[] = {1,2,3,4};
    int N = sizeof(arr) / sizeof(arr[0]);
 
    int minE = *min_element(arr, arr + N);
    int maxE = *max_element(arr, arr + N);
 
    // Function Call
    cout << minimumIncDec(
        arr, N, maxE, minE);
    return 0;
}

Java

// Java program of the above approach
import java.util.Arrays;
 
public class Main {
  public static int minimumIncDec(int[] arr, int N, int maxE, int minE) {
    int[][] dp = new int[N+1][maxE+1];
    for (int[] row : dp) {
      Arrays.fill(row, 0);
    }
 
    // If only one element is present,
    // then arr[] is sorted
    for (int j = 0; j <= maxE; j++) {
      dp[0][j] = 0;
    }
 
    // Iterate from minE to maxE which
    // placed at previous index
    for (int i = 1; i <= N; i++) {
      for (int j = minE; j <= maxE; j++) {
        int ans = Integer.MAX_VALUE;
        for (int k = minE; k <= j; k++) {
 
          // Update the answer according to
          // recurrence relation
          ans = Math.min(ans, dp[i-1][k] + Math.abs(arr[i-1] - k));
        }
        // store computation of subproblem
        dp[i][j] = ans;
      }
    }
    // Return the final result
    return dp[N][maxE];
  }
 
  // Driver Code
  public static void main(String[] args) {
    int[] arr = {1,2,3,4};
    int N = arr.length;
    int minE = Arrays.stream(arr).min().getAsInt();
    int maxE = Arrays.stream(arr).max().getAsInt();
    // Function Call
    System.out.println(minimumIncDec(arr, N, maxE, minE));
  }
}
 
// This code is contributed by shiv1o43g

Python3

import sys
 
def minimum_inc_dec(arr):
    N = len(arr)
    maxE = max(arr)
    minE = min(arr)
     
    dp = [[0] * (maxE + 1) for _ in range(N + 1)]
     
    # If only one element is present, then arr[] is sorted
    for j in range(maxE + 1):
        dp[0][j] = 0
     
    # Iterate from minE to maxE which placed at previous index
    for i in range(1, N + 1):
        for j in range(minE, maxE + 1):
            ans = sys.maxsize
            for k in range(minE, j + 1):
                # Update the answer according to recurrence relation
                ans = min(ans, dp[i - 1][k] + abs(arr[i - 1] - k))
             
            # store computation of subproblem
            dp[i][j] = ans
     
    # Return the final result
    return dp[N][maxE]
 
# Driver Code
arr = [1, 2, 3, 4]
result = minimum_inc_dec(arr)
print(result)

Javascript

function minimumIncDec(arr, N, maxE, minE) {
    let dp = Array.from(Array(N + 1), () => Array(maxE + 1).fill(0));
 
    // If only one element is present,
    // then arr[] is sorted
    for (let j = 0; j <= maxE; j++) {
        dp[0][j] = 0;
    }
 
    // Iterate from minE to maxE which
    // placed at previous index
    for (let i = 1; i <= N; i++) {
        for (let j = minE; j <= maxE; j++) {
            let ans = Infinity;
            for (let k = minE; k <= j; k++) {
                // Update the answer according to
                // recurrence relation
                ans = Math.min(ans, dp[i - 1][k] + Math.abs(arr[i - 1] - k));
            }
 
            // store computation of subproblem
            dp[i][j] = ans;
        }
    }
 
    // Return the final result
    return dp[N][maxE];
}
 
// Driver Code
let arr = [1, 2, 3, 4];
let N = arr.length;
 
let minE = Math.min(...arr);
let maxE = Math.max(...arr);
 
// Function Call
console.log(minimumIncDec(arr, N, maxE, minE));

Output:

Time Complexity: O(N^3)
Auxiliary Space: O(N*maxE)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!