Recuento de subarreglos de tamaño K, que es una permutación de números del 1 al K

Dada una array arr de enteros distintos, la tarea es encontrar el recuento de sub-arrays de tamaño i que tienen todos los elementos de 1 a i , en otras palabras, la sub-array es cualquier permutación de elementos de 1 a i , con 1 < = yo <= norte .

Ejemplos:

Entrada: arr[] = {2, 3, 1, 5, 4} 
Salida: 3 
Explicación: 
tenemos {1}, {2, 3, 1} y {2, 3, 1, 5, 4} subarreglo para i =1, i=3, i=5 respectivamente. 
La permutación de tamaño 4 y tamaño 2 no se puede realizar porque 5 y 3 están en el camino respectivamente.

Entrada: arr[] = {1, 3, 5, 4, 2} 
Salida: 2 
Explicación: 
tenemos {1} y {1, 3, 5, 4, 2} subarreglo para i=1 e i=5 respectivamente.

Un enfoque Naive es comenzar desde cada índice e intentar encontrar el subarreglo de cada tamaño (i) y verificar si todos los elementos del 1 al i están presentes. 
Complejidad temporal: O(N ² )

Se puede dar un enfoque eficiente comprobando si es posible crear un subarreglo de tamaño i para cada valor de i de 1 a N .
Como sabemos, cada subarreglo de tamaño K debe ser una permutación de todos los elementos de 1 a K , sabiendo que podemos mirar el índice de los números de 1 a N en orden y calcular el índice de los valores mínimo y máximo en cada paso.

• Si ind_máximo – ind_mínimo + 1 = K , entonces tenemos una permutación de tamaño K, de lo contrario no.
• Actualice el valor de minimo_ind y maximo_ind en cada paso.

Complejidad temporal: O(n)
Ilustración:

Dado Arr = {2, 3, 1, 5, 4} , comencemos con min_ind = INF y max_ind = -1

1. índice de 1 es 2, entonces min_ind = min(min_ind, 2) = 2 y max_ind = max(max_ind, 2) = 2, 
   2-2+1 = 1 entonces tenemos una permutación de tamaño 1
2. índice de 2 es 0, por lo que min_ind = min(min_ind, 0) = 0 y max_ind = max(max_ind, 0) = 2, 
   2-0+1 = 3 por lo que no tenemos una permutación de tamaño 2
3. índice de 3 es 1, entonces min_ind = min(min_ind, 1) = 0 y max_ind = max(max_ind, 1) = 2, 
   2-0+1 = 3 entonces tenemos una permutación de tamaño 3
4. índice de 4 es 4, entonces min_ind = min(min_ind, 4) = 0 y max_ind = max(max_ind, 4) = 4, 
   4-0+1 = 5 así que no tenemos una permutación de tamaño 4
5. índice de 5 es 3, entonces min_ind = min(min_ind, 3) = 0 y max_ind = max(max_ind, 4) = 4, 
   4-0+1 = 5 entonces tenemos una permutación de tamaño 5

entonces la respuesta es 3

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

// C++ program to implement
// the above approach
 
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
int find_permutations(vector<int>& arr)
{
    int cnt = 0;
    int max_ind = -1, min_ind = 10000000;
    int n = arr.size();
    unordered_map<int, int> index_of;
 
    // Save index of numbers of the array
    for (int i = 0; i < n; i++) {
        index_of[arr[i]] = i + 1;
    }
 
    for (int i = 1; i <= n; i++) {
 
        // Update min and max index
        // with the current index
        // and check if it's a valid permutation
        max_ind = max(max_ind, index_of[i]);
        min_ind = min(min_ind, index_of[i]);
        if (max_ind - min_ind + 1 == i)
            cnt++;
    }
 
    return cnt;
}
 
// Driver code
int main()
{
    vector<int> nums;
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(1);
    nums.push_back(5);
    nums.push_back(4);
 
    cout << find_permutations(nums);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
public static int find_permutations(
    Vector<Integer> arr)
{
    int cnt = 0;
    int max_ind = -1, min_ind = 10000000;
    int n = arr.size();
     
    HashMap<Integer,
            Integer> index_of = new HashMap<>();
             
    // Save index of numbers of the array
    for(int i = 0; i < n; i++)
    {
        index_of.put(arr.get(i), i + 1);
    }
 
    for(int i = 1; i <= n; i++)
    {
         
        // Update min and max index with
        // the current index and check
        // if it's a valid permutation
        max_ind = Math.max(max_ind, index_of.get(i));
        min_ind = Math.min(min_ind, index_of.get(i));
         
        if (max_ind - min_ind + 1 == i)
            cnt++;
    }
    return cnt;
}
 
// Driver Code
public static void main(String[] args)
{
    Vector<Integer> nums = new Vector<Integer>();
    nums.add(2);
    nums.add(3);
    nums.add(1);
    nums.add(5);
    nums.add(4);
     
    System.out.print(find_permutations(nums));
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to implement
# the above approach
def find_permutations(arr):
     
    cnt = 0
    max_ind = -1
    min_ind = 10000000;
     
    n = len(arr)
    index_of = {}
 
    # Save index of numbers of the array
    for i in range(n):
        index_of[arr[i]] = i + 1
 
    for i in range(1, n + 1):
 
        # Update min and max index with the
        # current index and check if it's a
        # valid permutation
        max_ind = max(max_ind, index_of[i])
        min_ind = min(min_ind, index_of[i])
         
        if (max_ind - min_ind + 1 == i):
            cnt += 1
             
    return cnt
 
# Driver code
if __name__ == "__main__":
 
    nums = []
    nums.append(2)
    nums.append(3)
    nums.append(1)
    nums.append(5)
    nums.append(4)
 
    print(find_permutations(nums))
 
# This code is contributed by chitranayal

// C# program to implement
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
     
static int find_permutations(ArrayList arr)
{
    int cnt = 0;
    int max_ind = -1, min_ind = 10000000;
    int n = arr.Count;
     
    Dictionary<int,
               int> index_of = new Dictionary<int,
                                              int>();
             
    // Save index of numbers of the array
    for(int i = 0; i < n; i++)
    {
        index_of[(int)arr[i]] = i + 1;
    }
 
    for(int i = 1; i <= n; i++)
    {
         
        // Update min and max index with
        // the current index and check
        // if it's a valid permutation
        max_ind = Math.Max(max_ind, index_of[i]);
        min_ind = Math.Min(min_ind, index_of[i]);
         
        if (max_ind - min_ind + 1 == i)
            cnt++;
    }
    return cnt;
}
 
// Driver Code
public static void Main(string[] args)
{
    ArrayList nums = new ArrayList();
 
    nums.Add(2);
    nums.Add(3);
    nums.Add(1);
    nums.Add(5);
    nums.Add(4);
 
    Console.Write(find_permutations(nums));
}
}
 
// This code is contributed by rutvik_56

<script>
// Javascript implementation
function find_permutations(arr)
{
    var cnt = 0;
    var max_ind = -1, min_ind = 10000000;
    var n = arr.length;
    var index_of = new Map();
   
    // Save index of numbers of the array
    for (var i = 0; i < n; i++) {
        index_of.set(arr[i], i + 1);
    }
   
    for (var i = 1; i <= n; i++) {
   
        // Update min and max index
        // with the current index
        // and check if it's a valid permutation
        max_ind = Math.max(max_ind, index_of.get(i));
        min_ind = Math.min(min_ind, index_of.get(i));
        if (max_ind - min_ind + 1 == i)
            cnt++;
    }
   
    return cnt;
}
  
var nums = [];
nums.push(2);
nums.push(3);
nums.push(1);
nums.push(5);
nums.push(4);
 
document.write(find_permutations(nums));
// This code contributed by shubhamsingh10
</script>

3