Ordene la permutación de 1 a N eliminando cualquier elemento e insertándolo al frente o al reverso

Dada una array arr[] de tamaño N que tiene enteros distintos del 1 al N, la tarea es contar el número mínimo de pasos necesarios para clasificar la array en orden creciente eliminando cualquier elemento e insertándolo en la parte delantera o trasera de la array . .

Ejemplos:

Entrada: arr[ ] = {4, 1, 3, 2}
Salida: 2
Explicación:
La array dada se puede ordenar en orden creciente siguiendo dos operaciones:
Operación 1: Eliminar 3 y agregarlo al final de la array. {4, 1, 3 , 2} -> {4, 1, 2, 3 }
Operación 2: elimine 4 y agréguelo al final de la array. { 4 , 1, 2, 3} -> {1, 2, 3, 4 }

Entrada: arr[ ] = {4, 1, 2, 5, 3}
Salida: 2

Enfoque: el problema se puede resolver utilizando el hecho de que para ordenar la array en un número mínimo de pasos, se debe mover el número mínimo de elementos hacia adelante o hacia atrás . Además, los elementos cuya posición se debe cambiar no estarán inicialmente en orden creciente . Entonces, el problema se reduce a encontrar el subarreglo creciente más largo , ya que solo esos elementos del arreglo no se moverán. 

A continuación se muestra la implementación del enfoque anterior:

// CPP program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the minimum steps
// to sort the array
void 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 Code
int main(){
 
  int N = 5;
  int arr[] = {4, 1, 2, 5, 3};
 
  findMinStepstoSort(arr, N);
 
}
 
// This code is contributed by SURENDRA_GANGWAR.

// JAVA program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the minimum steps
// to sort the array
static 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 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 gauravrajput1

# Python program for the above approach
 
# Function to find the minimum steps
# to sort the array
def 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 Code
if __name__ == '__main__':
  N = 5
  arr = [4, 1, 2, 5, 3]
 
  findMinStepstoSort(arr, N)

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
// Function to find the minimum steps
// to sort the array
static 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.

<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

Complejidad temporal: O(N)
Espacio auxiliar: O(N)