Longitud del subarreglo más pequeño que se eliminará de modo que se ordene el resto del arreglo

Dada una array arr[] que consta de N enteros, la tarea es imprimir la longitud del subarreglo más pequeño que se eliminará de arr[] de modo que se ordene la array restante.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 10, 4, 2, 3, 5}
Salida: 3
Explicación:
El subarreglo más pequeño que se eliminará es {10, 4, 2} de longitud 3. El arreglo restante es {1, 2, 3, 3, 5} que están ordenados.
Otra solución correcta es eliminar el subarreglo [3, 10, 4].

Entrada: arr[] = {5, 4, 3, 2, 1}
Salida: 4
Explicación:
Dado que la array es estrictamente decreciente, solo es necesario mantener un único elemento en la array.
Por lo tanto, la respuesta requerida es 4.

Enfoque : el problema se puede resolver en función de las siguientes tres formas de eliminar un subarreglo:

1. Retire el subarreglo de la izquierda, es decir, el sufijo izquierdo.
2. Retire el subarreglo de la derecha, es decir, el prefijo.
3. Elimine el subarreglo del medio y combine la parte izquierda y derecha del arreglo.

1. Iterar sobre arr[] de izquierda a derecha, encontrar el primer índice a la izquierda que arr[left] > arr[left + 1] . Entonces, la longitud del subarreglo que se eliminará para ordenar el arreglo es N-izquierda-1.
2. Si se deja == N – 1 , esta array ya está ordenada, por lo que devuelve 0.
3. Iterar sobre el arr[] de derecha a izquierda, encontrar el primer índice a la derecha que arr[right] < arr[right – 1] . Entonces, la longitud del subarreglo que se eliminará para ordenar el arreglo es correcta.
4. Ahora inicialice una variable mincount y tome el mínimo de N-left-1 y right.
5. Ahora calcule la longitud mínima del subarreglo que se eliminará también del medio del arreglo:
   1. Sea i = 0, j = derecho . Y examine si los elementos intermedios, i y j (exclusivo) se pueden eliminar comparando arr[i] y arr[j] .
   2. Si arr[j] >= arr[i] , intente actualizar la respuesta usando j – i – 1 e incremente i para ajustar la ventana.
   3. Si arr[j] < arr[i] , los elementos no se pueden eliminar en el medio, así que incremente j para aflojar la ventana.
   4. Atraviesa el bucle hasta que i > izquierda o j == N . Y actualiza la respuesta.
6. Devuelve el conteo mínimo .

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

// C++ program for the above approach 
#include<bits/stdc++.h>
using namespace std;
  
// Find the length of the shortest subarray 
int findLengthOfShortestSubarray(int arr[], int N)
{
      
    // To store the result 
    int minlength = INT_MAX; 
  
    int left = 0;
    int right = N - 1;
  
    // Calculate the possible length of 
    // the sorted subarray from left 
    while (left < right && 
       arr[left + 1] >= arr[left])
    {
        left++;
    }
  
    // Array is sorted 
    if (left == N - 1) 
        return 0;
  
    // Calculate the possible length of 
    // the sorted subarray from left 
    while (right > left && 
       arr[right - 1] <= arr[right])
    {
        right--;
    }
  
    // Update the result 
    minlength = min(N - left - 1, right); 
  
    // Calculate the possible length 
    // in the middle we can delete 
    // and update the result 
    int j = right; 
    for(int i = 0; i < left + 1; i++)
    {
        if (arr[i] <= arr[j])
        {
              
            // Update the result 
            minlength = min(minlength, j - i - 1); 
        }
        else if (j < N - 1)
        {
            j++;
        }
        else
        {
            break;
        }
    }
  
    // Return the result 
    return minlength; 
}
  
// Driver Code
int main()
{
    int arr[] = { 6, 3, 10, 11, 15,
                  20, 13, 3, 18, 12 };
    int N = sizeof(arr) / sizeof(arr[0]);
      
    // Function call 
    cout << (findLengthOfShortestSubarray(arr, N));
}
  
// This code is contributed by divyeshrabadiya07

// Java program for the 
// above approach
import java.util.*;
class GFG {
  
// Find the length of the shortest subarray
static int findLengthOfShortestSubarray(int arr[],
                                        int N)
{
  // To store the result
  int minlength = Integer.MAX_VALUE;
  
  int left = 0;
  int right = N - 1;
  
  // Calculate the possible length of
  // the sorted subarray from left
  while (left < right && 
         arr[left + 1] >= arr[left]) 
  {
    left++;
  }
  
  // Array is sorted
  if (left == N - 1)
    return 0;
  
  // Calculate the possible length of
  // the sorted subarray from left
  while (right > left && 
         arr[right - 1] <= arr[right]) 
  {
    right--;
  }
  
  // Update the result
  minlength = Math.min(N - left - 1, 
                       right);
  
  // Calculate the possible length
  // in the middle we can delete
  // and update the result
  int j = right;
    
  for (int i = 0; i < left + 1; i++) 
  {
    if (arr[i] <= arr[j]) 
    {
      // Update the result
      minlength = Math.min(minlength,
                           j - i - 1);
    }
    else if (j < N - 1) 
    {
      j++;
    }
    else 
    {
      break;
    }
  }
  
  // Return the result
  return minlength;
}
  
// Driver Code
public static void main(String[] args)
{
  int arr[] = {6, 3, 10, 11, 15, 
               20, 13, 3, 18, 12};
  int N = arr.length;
  
  // Function call
  System.out.print(
         (findLengthOfShortestSubarray(arr, N)));
}
}
  
// This code is contributed by Chitranayal

# Python3 program for the above approach
import sys
  
# Find the length of the shortest subarray
def findLengthOfShortestSubarray(arr):
  
    # To store the result
    minlength = sys.maxsize
  
    left = 0
    right = len(arr) - 1
  
    # Calculate the possible length of
    # the sorted subarray from left
    while left < right and arr[left + 1] >= arr[left]:
        left += 1
  
    # Array is sorted
    if left == len(arr) - 1:
        return 0
  
    # Calculate the possible length of
    # the sorted subarray from left
    while right > left and arr[right-1] <= arr[right]:
        right -= 1
  
    # Update the result
    minlength = min(len(arr) - left - 1, right)
  
    # Calculate the possible length
    # in the middle we can delete
    # and update the result
    j = right
    for i in range(left + 1):
  
        if arr[i] <= arr[j]:
  
            # Update the result
            minlength = min(minlength, j - i - 1)
  
        elif j < len(arr) - 1:
  
            j += 1
  
        else:
  
            break
  
    # Return the result
    return minlength
  
  
# Driver Code
arr = [6, 3, 10, 11, 15, 20, 13, 3, 18, 12]
  
# Function Call
print(findLengthOfShortestSubarray(arr))

// C# program for the 
// above approach
using System;
  
class GFG {
  
// Find the length of the shortest subarray
static int findLengthOfShortestSubarray(int []arr,
                                        int N)
{
    
  // To store the result
  int minlength = int.MaxValue;
  
  int left = 0;
  int right = N - 1;
  
  // Calculate the possible length of
  // the sorted subarray from left
  while (left < right && 
         arr[left + 1] >= arr[left]) 
  {
    left++;
  }
  
  // Array is sorted
  if (left == N - 1)
    return 0;
  
  // Calculate the possible length of
  // the sorted subarray from left
  while (right > left && 
         arr[right - 1] <= arr[right]) 
  {
    right--;
  }
  
  // Update the result
  minlength = Math.Min(N - left - 1, 
                       right);
  
  // Calculate the possible length
  // in the middle we can delete
  // and update the result
  int j = right;
    
  for(int i = 0; i < left + 1; i++) 
  {
    if (arr[i] <= arr[j]) 
    {
        
      // Update the result
      minlength = Math.Min(minlength,
                           j - i - 1);
    }
    else if (j < N - 1) 
    {
      j++;
    }
    else 
    {
      break;
    }
  }
  
  // Return the result
  return minlength;
}
  
// Driver Code
public static void Main(String[] args)
{
  int []arr = { 6, 3, 10, 11, 15, 
                20, 13, 3, 18, 12 };
  int N = arr.Length;
  
  // Function call
  Console.Write(findLengthOfShortestSubarray(
                 arr, N));
}
}
  
// This code is contributed by Amit Katiyar

<script>
  
// Javascript program for the above approach 
  
// Find the length of the shortest subarray
function findLengthOfShortestSubarray(arr, N)
{
      
    // To store the result
    let minlength = Number.MAX_VALUE;
      
    let left = 0;
    let right = N - 1;
      
    // Calculate the possible length of
    // the sorted subarray from left
    while (left < right &&
           arr[left + 1] >= arr[left])
    {
        left++;
    }
      
    // Array is sorted
    if (left == N - 1)
        return 0;
      
    // Calculate the possible length of
    // the sorted subarray from left
    while (right > left &&
           arr[right - 1] <= arr[right])
    {
        right--;
    }
      
    // Update the result
    minlength = Math.min(N - left - 1,
                         right);
      
    // Calculate the possible length
    // in the middle we can delete
    // and update the result
    let j = right;
      
    for(let i = 0; i < left + 1; i++)
    {
        if (arr[i] <= arr[j])
        {
              
            // Update the result
            minlength = Math.min(minlength,
                                 j - i - 1);
        }
        else if (j < N - 1)
        {
            j++;
        }
        else
        {
            break;
        }
    }
      
    // Return the result
    return minlength;
}
  
// Driver Code
let arr = [  6, 3, 10, 11, 15,
            20, 13, 3, 18, 12];
let N = arr.length;
  
// Function call
document.write(
    (findLengthOfShortestSubarray(arr, N)));
      
// This code is contributed by souravghosh0416
  
</script>

8

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

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array