Count operations to sort the Array by incrementing each element of increasing subsegment by 1
Given an array arr[] of size N, the task is to make array arr[] sorted in non-decreasing order in the minimum number of operations where in one operation, you can choose any non-decreasing sub-segment and increment each element of sub-segment by 1.
Examples:
Input: arr[] = {5, 3, 2, 5}
Output: 3
Explanation: First operation: [5, 3, 2, 5]?[5, 3, 3, 5]
Second operation: [5, 3, 3, 5]?[5, 4, 4, 5]
Third operation: [5, 4, 4, 5]?[5, 5, 5, 5]
Hence, the minimum operations required will be 3Input: arr[] = {1, 2, 3, 5, 3}
Output: 2
Explanation: First operation: [1, 2, 3, 5, 3] -> [1, 2, 3, 5, 4]
Second operation: [1, 2, 3, 5, 4] -> [1, 2, 3, 5, 5]
Hence, the minimum operations required will be 2
Approach: To solve the problem follow the below idea:
This problem can be solved using a greedy approach. We know that an array is sorted in non-decreasing order if arr[i] <= arr[i+1] for all i. So we can start iterating from back and if any element is found to be greater than the minimum of all its right elements, We must set all the right elements to arr[i] in order to make it increase. The number of operations taken will be the absolute difference between the minimum and the arr[i].
Follow the below steps to implement the idea:
- Start iterating from the back and find the index where arr[i] > minimum on right.
- Increment count by the absolute difference of minimum and arr[i] as in one operation element can only be increased by 1.
- Keep track of the minimum in each step.
- If arr[i] is not greater than the minimum of all its right, update minimum to nums[i].
- Return count.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function for finding out the minimum // number of operations. int minimumOperations(vector< int >& nums, int n) { // Keeping track of minimum from right int mini = nums[n - 1]; // Count the total number of operations int cnt = 0; for ( int i = n - 2; i >= 0; i--) { // If any element is greater than // the minimum of its right, // increment count if (nums[i] > mini) { cnt += abs (mini - nums[i]); mini = nums[i]; } else { // Updating minimum mini = nums[i]; } } // Returning count return cnt; } // Driver code int main() { vector< int > arr = { 5, 3, 2, 5 }; int n = arr.size(); // Function call cout << minimumOperations(arr, n); return 0; } |
Java
// Java code for the above approach: import java.util.*; class GFG { // Function for finding out the minimum // number of operations. public static int minimumOperations(List<Integer> nums, int n) { // Keeping track of minimum from right int mini = nums.get(n - 1 ); // Count the total number of operations int cnt = 0 ; for ( int i = n - 2 ; i >= 0 ; i--) { // If any element is greater than // the minimum of its right, // increment count if (nums.get(i) > mini) { cnt += Math.abs(mini - nums.get(i)); mini = nums.get(i); } else { // Updating minimum mini = nums.get(i); } } // Returning count return cnt; } // Driver code public static void main(String[] args) { List<Integer> arr = Arrays.asList( 5 , 3 , 2 , 5 ); int n = arr.size(); // Function call System.out.println(minimumOperations(arr, n)); } } // This Code is Contributed by Prasad Kandekar(prasad264) |
Python3
# Python code for the above approach: # Function for finding out the minimum # number of operations. def minimumOperations(nums, n): # Keeping track of minimum from right mini = nums[n - 1 ] # Count the total number of operations cnt = 0 for i in range (n - 2 , - 1 , - 1 ): # If any element is greater than # the minimum of its right, # increment count if nums[i] > mini: cnt + = abs (mini - nums[i]) mini = nums[i] else : # Updating minimum mini = nums[i] # Returning count return cnt # Driver code arr = [ 5 , 3 , 2 , 5 ] n = len (arr) # Function call print (minimumOperations(arr, n)) # This code is contributed by Prasad Kandekar(prasad264) |
C#
using System; using System.Collections.Generic; public class GFG { // Function for finding out the minimum // number of operations. public static int MinimumOperations(List< int > nums, int n) { // Keeping track of minimum from right int mini = nums[n - 1]; // Count the total number of operations int cnt = 0; for ( int i = n - 2; i >= 0; i--) { // If any element is greater than // the minimum of its right, // increment count if (nums[i] > mini) { cnt += Math.Abs(mini - nums[i]); mini = nums[i]; } else { // Updating minimum mini = nums[i]; } } // Returning count return cnt; } // Driver code public static void Main( string [] args) { List< int > arr = new List< int >() { 5, 3, 2, 5 }; int n = arr.Count; // Function call Console.WriteLine(MinimumOperations(arr, n)); } } |
Javascript
// Function for finding out the minimum number of operations. function minimumOperations(nums, n) { // Keeping track of minimum from right let mini = nums[n - 1]; // Count the total number of operations let cnt = 0; for (let i = n - 2; i >= 0; i--) { // If any element is greater than // the minimum of its right, increment count if (nums[i] > mini) { cnt += Math.abs(mini - nums[i]); mini = nums[i]; } else { // Updating minimum mini = nums[i]; } } // Returning count return cnt; } // Driver code const arr = [5, 3, 2, 5]; const n = arr.length; // Function call console.log(minimumOperations(arr, n)); |
3
Time Complexity: O(N)
Auxiliary Space: O(1)