El prefijo más pequeño que se eliminará de modo que la array restante se pueda reorganizar para formar una array ordenada

Dada una array arr[] que consta de N enteros, la tarea es encontrar la longitud mínima del prefijo necesario para eliminar de modo que los elementos restantes de la array se puedan reorganizar repetidamente seleccionando el primero o el último elemento uno por uno para formar un array ordenada .

Ejemplos:

Entrada: arr[] = {6, 5, 4, 3, 4}
Salida: 3
Explicación:
Para ordenar una array según la condición dada, elimine los primeros 3 elementos.
Después de la eliminación, la array arr[] se modifica a {3, 4}.
De la array arr[], seleccionando los primeros elementos uno por uno, es decir, arr[0] -> arr[1], forma una array ordenada {3, 4}.

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

Enfoque ingenuo: el enfoque más simple es eliminar todas las longitudes posibles del prefijo de la array dada y, para cada prefijo, verificar si se puede formar una array ordenada a partir de los elementos restantes de la array mediante la eliminación de esos prefijos. Si es cierto, imprima la longitud mínima del prefijo eliminado. 

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar observando que el sufijo resultante debe tener la forma arr[1] ≤ arr[2] ≤ … ≥ arr[N – 2] ≥ arr[N – 1] donde N es la longitud de la array restante y el sufijo es de la longitud máxima. Siga los pasos a continuación:

• Inicialice un índice de variable en N – 1 .
• Atraviese la array desde el final y deténgase en el punto donde arr[index – 1] ≤ arr[index] .
• A medida que avanza la iteración, seguimos disminuyendo la respuesta .
• Después de completar todos los pasos anteriores, imprima el valor del índice que es la longitud mínima del prefijo que debe eliminarse.

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

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum length
// of prefix required to be deleted
int findMinLength(vector<int>& arr)
{
    // Stores index to be returned
    int index = (int)arr.size() - 1;
 
    // Iterate until previous element
    // is <= current index
    while (index > 0
           && arr[index] >= arr[index - 1]) {
 
        // Decrementing index
        index--;
    }
 
    // Return index
    return index;
}
 
// Driver Code
int main()
{
 
    // Given arr[]
    vector<int> arr = { 7, 8, 5, 0, -1,
                        -1, 0, 1, 2, 3, 4 };
 
    // Function Call
    cout << findMinLength(arr);
 
    return 0;
}

// Java program for above approach
import java.util.*;
import java.io.*;
 
class GFG{
      
// Function to find the minimum length
// of prefix required to be deleted
static int findMinLength(int[] arr)
{
     
    // Stores index to be returned
    int index = (int)arr.length - 1;
   
    // Iterate until previous element
    // is <= current index
    while (index > 0 && arr[index] >=
                        arr[index - 1])
    {
         
        // Decrementing index
        index--;
    }
   
    // Return index
    return index;
}
 
// Driver code
public static void main(String args[])
{
     
    // Given arr[]
    int arr[]=  { 7, 8, 5, 0, -1,
                 -1, 0, 1, 2, 3, 4 };
    int n = arr.length;
     
    // Function call
    System.out.println(findMinLength(arr));
}
}
 
// This code is contributed by bikram2001jha

# Python3 program for above approach
 
# Function to find the minimum length
# of prefix required to be deleted
def findMinLength(arr):
   
    # Stores index to be returned
    index = len(arr) - 1;
 
    # Iterate until previous element
    # is <= current index
    while (index > 0 and arr[index] >= arr[index - 1]):
       
        # Decrementing index
        index -= 1;
 
    # Return index
    return index;
 
# Driver code
if __name__ == '__main__':
   
    # Given arr
    arr = [7, 8, 5, 0, -1,
           -1, 0, 1, 2, 3, 4];
    n = len(arr);
 
    # Function call
    print(findMinLength(arr));
 
# This code is contributed by Princi Singh

// C# program for above approach
using System;
 
class GFG{
      
// Function to find the minimum length
// of prefix required to be deleted
static int findMinLength(int[] arr)
{
     
    // Stores index to be returned
    int index = (int)arr.Length - 1;
   
    // Iterate until previous element
    // is <= current index
    while (index > 0 && arr[index] >=
                        arr[index - 1])
    {
         
        // Decrementing index
        index--;
    }
     
    // Return index
    return index;
}
 
// Driver code
public static void Main(String []args)
{
     
    // Given []arr
    int []arr =  { 7, 8, 5, 0, -1,
                  -1, 0, 1, 2, 3, 4 };
                  
    int n = arr.Length;
     
    // Function call
    Console.WriteLine(findMinLength(arr));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Java Script program for above approach
      
// Function to find the minimum length
// of prefix required to be deleted
function findMinLength( arr)
{
     
    // Stores index to be returned
    let index = parseInt(arr.length) - 1;
   
    // Iterate until previous element
    // is <= current index
    while (index > 0 && arr[index] >=
                        arr[index - 1])
    {
         
        // Decrementing index
        index--;
    }
   
    // Return index
    return index;
}
 
// Driver code
 
     
    // Given arr[]
    let arr=  [ 7, 8, 5, 0, -1,
                 -1, 0, 1, 2, 3, 4 ];
    let n = arr.length;
     
    // Function call
    document.write(findMinLength(arr));
//contributed by sravan kumar
</script>

4

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