Given an array arr[] of size N having distinct integers from 1 to N, the task is to count the minimum number of steps required to sort the array in increasing order by removing any element and inserting it to the front or back of the array.
Examples:
Input: arr[ ] = {4, 1, 3, 2}
Output: 2
Explanation:
The given array can be sorted in increasing order by following two operations:
Operation 1: Remove 3 and add it to the back of the array. {4, 1, 3, 2} -> {4, 1, 2, 3}
Operation 2: Remove 4 and add it to the back of the array. {4, 1, 2, 3} -> {1, 2, 3, 4}Input: arr[ ] = {4, 1, 2, 5, 3}
Output: 2
Approach: The problem can be solved by using the fact that to make the array sorted in a minimum number of steps, the minimum number of elements must be moved to the front or back. Also, the elements whose position must be changed will not lie in the increasing order initially. So the problem reduces to finding the longest increasing subarray as only those elements of the array will not be moved.
Below is the implementation of the above approach:
C++
// CPP program for the above approach#include<bits/stdc++.h>using namespace std;// Function to find the minimum steps// to sort the arrayvoid findMinStepstoSort(int arr[], int N){ // Storing the positions of elements map<int,int> pos; for(int i = 0; i < N; i++) pos[arr[i]] = i; // Initialize answer int ans = N-1; int prev = -1; int count = 0; // Traversing the array for(int i = 1; i < N + 1; i++){ // If current is greater than // previous if(pos[i] > prev) count += 1; // else if current is less than // previous else count = 1; // Updating previous prev = pos[i]; // Updating ans ans = min(ans, N - count); } cout<<ans;}// Driver Codeint main(){ int N = 5; int arr[] = {4, 1, 2, 5, 3}; findMinStepstoSort(arr, N);}// This code is contributed by SURENDRA_GANGWAR. |
Java
// JAVA program for the above approachimport java.util.*;class GFG{// Function to find the minimum steps// to sort the arraystatic void findMinStepstoSort(int arr[], int N){ // Storing the positions of elements HashMap<Integer,Integer> pos = new HashMap<>(); for(int i = 0; i < N; i++) pos.put(arr[i], i); // Initialize answer int ans = N - 1; int prev = -1; int count = 0; // Traversing the array for(int i = 1; i < N + 1; i++){ // If current is greater than // previous if(pos.get(i) > prev) count += 1; // else if current is less than // previous else count = 1; // Updating previous prev = pos.get(i); // Updating ans ans = Math.min(ans, N - count); } System.out.print(ans);}// Driver Codepublic static void main(String[] args){ int N = 5; int arr[] = {4, 1, 2, 5, 3}; findMinStepstoSort(arr, N);}}// This code is contributed by gauravrajput1 |
Python3
# Python program for the above approach# Function to find the minimum steps# to sort the arraydef findMinStepstoSort(arr, N): # Storing the positions of elements pos = {arr[i]:i for i in range(N)} # Initialize answer ans = N-1 prev = -1;count = 0 # Traversing the array for i in range(1, N + 1): # If current is greater than # previous if pos[i] > prev: count += 1 # else if current is less than # previous else: count = 1 # Updating previous prev = pos[i] # Updating ans ans = min(ans, N - count) print(ans)# Driver Codeif __name__ == '__main__': N = 5 arr = [4, 1, 2, 5, 3] findMinStepstoSort(arr, N) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{// Function to find the minimum steps// to sort the arraystatic void findMinStepstoSort(int[] arr, int N){ // Storing the positions of elements Dictionary<int, int> pos = new Dictionary<int, int>(); for(int i = 0; i < N; i++) pos[arr[i]] = i; // Initialize answer int ans = N - 1; int prev = -1; int count = 0; // Traversing the array for(int i = 1; i < N + 1; i++){ // If current is greater than // previous if(pos[i] > prev) count += 1; // else if current is less than // previous else count = 1; // Updating previous prev = pos[i]; // Updating ans ans = Math.Min(ans, N - count); } Console.WriteLine(ans);} // Driver Code public static void Main (string[] args) { int N = 5; int[] arr = {4, 1, 2, 5, 3}; findMinStepstoSort(arr, N); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the minimum steps // to sort the array function findMinStepstoSort(arr, N) { // Storing the positions of elements let pos = new Array(N); for (let i = 0; i < N; i++) { pos[i] = arr[i]; } // Initialize answer ans = N - 1 prev = -1; count = 0 // Traversing the array for (let i = 1; i < N + 1; i++) { // If current is greater than // previous if (pos[i] > prev) count += 1 // else if current is less than // previous else count = 1 // Updating previous prev = pos[i] // Updating ans ans = Math.min(ans, N - count) } document.write(ans) } let N = 5 let arr = [4, 1, 2, 5, 3] findMinStepstoSort(arr, N) // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
