Given an array arr[], the task is to find the minimum steps required to make an array decreasing, where in each step remove all elements which are greater than elements on its left element.
Examples:
Input: arr[] = {3, 2, 1, 7, 5}
Output: 2
Explanation:
In the above array there are two steps required to make array decreasing –
Step 1: In step 1 there is one element which is greater than its left, that is 7 > 1.
Step 2: In step 2 there is one element which is greater than its left, that is 5 > 1.
Input: arr[] = {6, 5, 8, 4, 7, 10, 9}
Output: 2
In the above array there are two steps required to make array decreasing –
Step 1: In step 1 there are three elements which is greater than its left, which is 8 > 5, 7 > 4 and 10 > 7.
Step 2: In step 2 there are three is only one element which is greater than its left which is 9 > 4.
Naive Approach: Iterate over the array and count the elements which are greater than its left, if the element is not greater than its left then push the element into another array/vector (say arr1) and after the complete iteration of the array copy all the elements of arr1 to the initial array and repeat the same procedure until the count of elements removed in a step is 0. This approach takes O(N2) time in the worst case and O(N) space.
Code-
C++
// C++ implementation to make an// array decreasing#include <bits/stdc++.h>using namespace std;// Function to find the// minimum steps requiredvoid minSteps(int arr[], int N){ vector<int> arr1; int size = N; // For count of greater element int count; // For storing answer int ans = 0; while (true) { count = 0; arr1.push_back(arr[0]); for (int i = 1; i < size; i++) { // If elements is not greater than element on // its left then add that element into arr1 if (arr[i] <= arr[i - 1]) { arr1.push_back(arr[i]); } // else increment the count because we got a // greater element else { count++; } } // If there is no greater element then out from the // outer loop if (count == 0) { break; } // Copy all the elements of arr1 to the initial // array size = arr1.size(); for (int i = 0; i < size; i++) { arr[i] = arr1[i]; } arr1.clear(); ans++; } cout << ans << endl;}// Driver Codeint main(){ int arr[] = { 3, 2, 1, 7, 5 }; int size = sizeof(arr) / sizeof(arr[0]); minSteps(arr, size); return 0;} |
Java
import java.util.ArrayList;public class GFG { // Function to find the minimum steps required to make the array decreasing public static void minSteps(int[] arr) { ArrayList<Integer> arr1 = new ArrayList<>(); int size = arr.length; // For count of greater element int count; // For storing answer int ans = 0; while (true) { count = 0; arr1.add(arr[0]); for (int i = 1; i < size; i++) { // If elements is not greater than the element on // its left, // then add that element into arr1 if (arr[i] <= arr[i - 1]) { arr1.add(arr[i]); } // else increment the count because we got a // greater element else { count++; } } // If there is no greater element, then break out from // the outer loop if (count == 0) { break; } // Copy all the elements of arr1 to the initial array size = arr1.size(); for (int i = 0; i < size; i++) { arr[i] = arr1.get(i); } arr1.clear(); ans++; } System.out.println(ans); } // Driver code public static void main(String[] args) { int[] arr = { 3, 2, 1, 7, 5 }; minSteps(arr); }} |
Python3
import sys# Function to find minimum steps requireddef minSteps(arr, N): arr1 = [] size = N # For count of greater element count = 0 # For storing answer ans = 0 while True: count = 0 arr1.append(arr[0]) for i in range(1, size): # If elements is not greater than # element on its left then add # that element into arr1 if arr[i] <= arr[i-1]: arr1.append(arr[i]) # else increment the count # because we got a greater element else: count += 1 # If there is no greater element # then out from the outer loop if count == 0: break # Copy all the elements of arr1 # to the initial array size = len(arr1) for i in range(size): arr[i] = arr1[i] arr1.clear() ans += 1 print(ans)# Driver Codeif __name__ == '__main__': arr = [3, 2, 1, 7, 5] size = len(arr) minSteps(arr, size) |
C#
using System;public class GFG{ // Function to find the minimum steps required public static void MinSteps(int[] arr, int N) { var arr1 = new System.Collections.Generic.List<int>(); int size = N; // For count of greater element int count; // For storing answer int ans = 0; while (true) { count = 0; arr1.Add(arr[0]); for (int i = 1; i < size; i++) { // If elements is not greater than element on its // left then add that element into arr1 if (arr[i] <= arr[i - 1]) { arr1.Add(arr[i]); } // else increment the count because we got a greater element else { count++; } } // If there is no greater element then break out from the // outer loop if (count == 0) { break; } // Copy all the elements of arr1 to the initial array size = arr1.Count; for (int i = 0; i < size; i++) { arr[i] = arr1[i]; } arr1.Clear(); ans++; } Console.WriteLine(ans); } // Driver Code public static void Main(string[] args) { int[] arr = { 3, 2, 1, 7, 5 }; int size = arr.Length; MinSteps(arr, size); }} |
Javascript
// Function to find the// minimum steps requiredfunction minSteps(arr, N){ let arr1 = []; let size = N; // For count of greater element let count; // For storing answer let ans = 0; while (true) { count = 0; arr1.push(arr[0]); for (let i = 1; i < size; i++) { // If elements is not greater than element on // its left then add that element into arr1 if (arr[i] <= arr[i - 1]) { arr1.push(arr[i]); } // else increment the count because we got a // greater element else { count++; } } // If there is no greater element then out from the // outer loop if (count == 0) { break; } // Copy all the elements of arr1 to the initial // array size = arr1.length; for (let i = 0; i < size; i++) { arr[i] = arr1[i]; } arr1 = []; ans++; } console.log(ans);}// Driver Codelet arr = [ 3, 2, 1, 7, 5 ];let size = arr.length;minSteps(arr, size); |
Output
2
Time Complexity-O(N2)
Auxiliary Space-O(N)
Efficient Approach: The idea is to use a stack and push the element into the stack only if the element is greater than its previous element, else count the number of scans and pop.
We only care about the elements which is smaller.
C++
// C++ implementation to make an// array decreasing#include <bits/stdc++.h>using namespace std;// Structure to store elementsstruct Node { int elementID; int stepsToeliminate;};// Function to find the// minimum steps requiredvoid minSteps(int arr[], int N){ stack<Node> s; s.push({ 0, -1 }); // Minimum steps int maxStepsToeliminate = -1; // Loop to iterate // over the array for (int i = 1; i < N; i++) { int stepsToeliminate = 1; // Traversing the stack until // it is not empty while (!s.empty()) { // Condition if the top of the // stack is greater than the // current element if (arr[s.top().elementID] >= arr[i]) { stepsToeliminate = max(stepsToeliminate, s.top().stepsToeliminate + 1); s.pop(); } else { break; } } // Condition if no previous // elements value less than // this element then steps is -1 if (s.empty()) { stepsToeliminate = -1; } maxStepsToeliminate = max(maxStepsToeliminate, stepsToeliminate); s.push({ i, stepsToeliminate }); } cout << (maxStepsToeliminate < 0 ? 0 : maxStepsToeliminate) << endl;}// Driver Codeint main(){ int arr[] = { 3, 2, 1, 7, 5 }; int size = sizeof(arr) / sizeof(arr[0]); minSteps(arr, size); return 0;} |
Java
// Java implementation to make an// array decreasingimport java.util.*;class GFG { // Structure to store elements static class Node { int elementID; int stepsToeliminate; public Node(int elementID, int stepsToeliminate) { super(); this.elementID = elementID; this.stepsToeliminate = stepsToeliminate; } }; // Function to find the // minimum steps required static void minSteps(int arr[], int N) { Stack<Node> s = new Stack<Node>(); s.add(new Node(0, -1)); // Minimum steps int maxStepsToeliminate = -1; // Loop to iterate // over the array for (int i = 1; i < N; i++) { int stepsToeliminate = 1; // Traversing the stack until // it is not empty while (!s.isEmpty()) { // Condition if the top of the // stack is greater than the // current element if (arr[s.peek().elementID] >= arr[i]) { stepsToeliminate = Math.max( stepsToeliminate, s.peek().stepsToeliminate + 1); s.pop(); } else { break; } } // Condition if no previous // elements value less than // this element then steps is -1 if (s.isEmpty()) { stepsToeliminate = -1; } maxStepsToeliminate = Math.max( maxStepsToeliminate, stepsToeliminate); s.add(new Node(i, stepsToeliminate)); } System.out.print((maxStepsToeliminate < 0 ? 0 : maxStepsToeliminate) + "\n"); } // Driver Code public static void main(String[] args) { int arr[] = { 3, 2, 1, 7, 5 }; int size = arr.length; minSteps(arr, size); }}// This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation to make an# array decreasing# Function to find the# minimum steps requireddef minSteps(arr, N): s = [] s.append((0, -1)) # Minimum steps maxStepsToeliminate = -1 # Loop to iterate # over the array for i in range(1, N): stepsToeliminate = 1 # Traversing the stack until # it is not empty while (len(s) != 0): # Condition if the top of the # stack is greater than the # current element if (arr[s[-1][0]] >= arr[i]): stepsToeliminate = max(stepsToeliminate, s[-1][1] + 1) s.pop() else: break # Condition if no previous # elements value less than # this element then steps is -1 if (len(s) == 0): stepsToeliminate = -1 maxStepsToeliminate = max(maxStepsToeliminate, stepsToeliminate) s.append((i, stepsToeliminate)) print(0 if (maxStepsToeliminate < 0) else maxStepsToeliminate)# Driver Codeif __name__ == "__main__": arr = [3, 2, 1, 7, 5] size = len(arr) minSteps(arr, size)# This code is contributed by AnkitRai01 |
C#
// C# implementation to make an// array decreasingusing System;using System.Collections.Generic;class GFG { // Structure to store elements class Node { public int elementID; public int stepsToeliminate; public Node(int elementID, int stepsToeliminate) { this.elementID = elementID; this.stepsToeliminate = stepsToeliminate; } }; // Function to find the // minimum steps required static void minSteps(int[] arr, int N) { Stack<Node> s = new Stack<Node>(); s.Push(new Node(0, -1)); // Minimum steps int maxStepsToeliminate = -1; // Loop to iterate // over the array for (int i = 1; i < N; i++) { int stepsToeliminate = 1; // Traversing the stack until // it is not empty while (s.Count != 0) { // Condition if the top of the // stack is greater than the // current element if (arr[s.Peek().elementID] >= arr[i]) { stepsToeliminate = Math.Max( stepsToeliminate, s.Peek().stepsToeliminate + 1); s.Pop(); } else { break; } } // Condition if no previous // elements value less than // this element then steps is -1 if (s.Count != 0) { stepsToeliminate = -1; } maxStepsToeliminate = Math.Max( maxStepsToeliminate, stepsToeliminate); s.Push(new Node(i, stepsToeliminate)); } Console.Write((maxStepsToeliminate < 0 ? 0 : maxStepsToeliminate) + "\n"); } // Driver Code public static void Main(String[] args) { int[] arr = { 3, 2, 1, 7, 5 }; int size = arr.Length; minSteps(arr, size); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation to make an array decreasing // Structure to store elements class Node { constructor(elementID, stepsToeliminate) { this.elementID = elementID; this.stepsToeliminate = stepsToeliminate; } } // Function to find the // minimum steps required function minSteps(arr, N) { let s = []; s.push(new Node( 0, -1 )); // Minimum steps let maxStepsToeliminate = -1; // Loop to iterate // over the array for (let i = 1; i < N; i++) { let stepsToeliminate = 1; // Traversing the stack until // it is not empty while (s.length!=0) { // Condition if the top of the // stack is greater than the // current element if (arr[s[s.length - 1].elementID] >= arr[i]) { stepsToeliminate = Math.max(stepsToeliminate, s[s.length - 1].stepsToeliminate + 1); s.pop(); } else { break; } } // Condition if no previous // elements value less than // this element then steps is -1 if (s.length!=0) { stepsToeliminate = -1; } maxStepsToeliminate = Math.max(maxStepsToeliminate, stepsToeliminate); s.push(new Node(i, stepsToeliminate )); } document.write((maxStepsToeliminate < 0 ? 0 : maxStepsToeliminate) +"</br>"); } let arr = [3, 2, 1, 7, 5]; let size = arr.length; minSteps(arr, size); // This code is contributed by rameshtravel07.</script> |
Output
2
Performance Analysis:
- Time Complexity: As in the above approach, there is one loop which takes O(N) time, Hence the Time Complexity will be O(N).
- Space Complexity: As in the above approach, there is stack used to store the previous elements, Hence the space complexity will be O(N).
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
