Verifique si la permutación dada de 1 a N es factible usando operaciones dadas

Dada una array arr[] de tamaño N , la tarea de verificar si esta array está construida bajo las siguientes restricciones:

1. La array solo puede contener números del 1 al N.
2. Tenemos que construir la array secuencialmente. Significa que primero colocamos 1, luego 2 y así sucesivamente hasta N.
3. Si la array está vacía, podemos colocar un número en cualquier posición.
4. Si no está vacío, podemos colocar el siguiente elemento en la siguiente posición del elemento anterior. En caso de que la siguiente posición esté fuera del tamaño de la array o ya esté llena, podemos elegir cualquier posición que esté desocupada y colocar el número. 
    

Ejemplos:

Entrada: arr[] = {2, 3, 4, 5, 1} 
Salida: SÍ 
Explicación: 
Inicialmente, la array está vacía. Entonces podemos colocar 1 en cualquier posición. 
Nos ubicamos en la posición 5 (indexación basada en 1). 
Como la siguiente posición está fuera del tamaño de la array. 
entonces podemos colocar 2 en cualquier posición. Lo colocamos en 1ª posición. 
Luego colocamos 3 en la 2ª posición, 4 en la 3ª posición y 5 en la 4ª posición. 
Entonces podemos construir tal array.

Entrada: arr[] = {1, 5, 2, 4, 3} 
Salida: NO 
Explicación: 
Al principio podemos colocar 1 en la primera posición. Luego, tenemos que colocar 2 en el segundo lugar 
, ya que la segunda posición está vacía, pero 2 se coloca en la posición 3 en esa array dada. 
Entonces, tal array no es posible de construir. 

Acercarse:  

1. Primero, almacene los índices de cada elemento de array en un mapa .
2. Almacene la posición del siguiente elemento en ‘next’ . Inicialmente, como la array está vacía, next contiene la posición de 1 .
3. Iterar sobre [1, N] y verificar si el elemento actual está presente en el siguiente índice. Si no, devuelve -1.
4. En cada iteración, marque la posición actual como visitada y actualice el siguiente índice posible para el siguiente valor. Si no se visita el siguiente índice (i + 1) del índice actual, actualice junto a (i + 1). De lo contrario, si el siguiente índice posible excede el rango de índices de la array, almacene la posición del siguiente elemento del mapa, ya que puede colocarse en cualquier índice antes del índice actual en el mapa.
5. En el recorrido completo de la array, devuelve verdadero, ya que todos los índices se han colocado en sus respectivos índices siguientes .

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

// C++ program to Check If we
// can build the given array
// under given constraints.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function return true if we
// can build the array
bool CheckArray(int a[], int n)
{
    int i, f = 0, next;
 
    // First one is to keep position
    // of each element
    // Second one is for marking
    // the current position
    map<int, int> pos, vis;
 
    for (i = 0; i < n; i++) {
        pos[a[i]] = i;
    }
 
    // Initially next contains
    // the position of 1.
    next = pos[1];
 
    for (i = 1; i <= n; i++) {
        // Mark the current
        // position.
        vis[next] = 1;
 
        // If the element is not
        // present at that position
        // then it is impossible
        // to build
        if (i != a[next]) {
            return false;
        }
 
        // Updating the next
        if (next + 1 == n
            || vis[next + 1]) {
 
            // If the next position is
            // out of array size or next
            // position is not empty then
            // we use the map to find the
            // position of the next element
            next = pos[i + 1];
        }
        else
            // Else just increment it
            next++;
    }
 
    return true;
}
 
// Driver code
int main()
{
 
    int arr[] = { 2, 3, 4, 5, 1 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    if (CheckArray(arr, N)) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
 
    return 0;
}

// Java program to check If we
// can build the given array
// under given constraints.
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function return true if we
// can build the array
static boolean CheckArray(int[] a, int n)
{
    int i, f = 0, next;
 
    // First one is to keep position
    // of each element
    // Second one is for marking
    // the current position
    HashMap<Integer,
            Integer> pos = new HashMap<Integer,
                                       Integer>();
    HashMap<Integer,
            Integer> vis = new HashMap<Integer,
                                       Integer>();
    vis.put(0, 0);
 
    for(i = 0; i < n; i++)
    {
        pos.put(a[i], i);
    }
 
    // Initially next contains
    // the position of 1.
    next = pos.getOrDefault(1, 0);
 
    for(i = 1; i <= n; i++)
    {
         
        // Mark the current
        // position.
        vis.put(next, 1);
 
        // If the element is not
        // present at that position
        // then it is impossible
        // to build
        if (i != a[next])
        {
            return false;
        }
 
        // Updating the next
        if (next + 1 == n ||
            vis.getOrDefault(next + 1, 0) != 0)
        {
             
            // If the next position is
            // out of array size or next
            // position is not empty then
            // we use the map to find the
            // position of the next element
            next = pos.getOrDefault(i + 1, 0);
        }
        else
         
            // Else just increment it
            next++;
    }
    return true;
}
 
// Driver code
public static void main(String[] args)
{
    int[] arr = { 2, 3, 4, 5, 1 };
    int N = arr.length;
 
    if (CheckArray(arr, N) == true)
    {
        System.out.println("YES");
    }
    else
    {
        System.out.println("NO");
    }
}
}
 
// This code is contributed by akhilsaini

# Python3 program to check if we
# can build the given array
# under given constraints.
 
# Function return true if we
# can build the array
def CheckArray(a, n):
     
    f = 0
 
    # First one is to keep position
    # of each element
    # Second one is for marking
    # the current position
    pos = {}
    vis = {}
     
    for i in range(n):
        pos[a[i]] = i
 
    # Initially next contains
    # the position of 1.
    next = pos[1]
     
    for i in range(1, n + 1):
         
        # Mark the current
        # position.
        vis[next] = 1
 
        # If the element is not
        # present at that position
        # then it is impossible
        # to build
        if (i != a[next]):
            return False
 
        # Updating the next
        if (next + 1 == n or
           (next + 1 in vis and
                        vis[next + 1])):
             
            # If the next position is
            # out of array size or next
            # position is not empty then
            # we use the map to find the
            # position of the next element
            if(i + 1 in pos):
                next = pos[i + 1]
        else:
             
            # Else just increment it
            next += 1
 
    return True
 
# Driver code
arr = [ 2, 3, 4, 5, 1 ]
N = len(arr)
 
if (CheckArray(arr, N)):
    print('YES')
else:
    print('NO')
 
# This code is contributed by yatinagg

// C# program to check If we
// can build the given array
// under given constraints.
using System;
using System.Collections;
 
class GFG{
 
// Function return true if we
// can build the array
static bool CheckArray(int[] a, int n)
{
    int i, next;
 
    // First one is to keep position
    // of each element
    // Second one is for marking
    // the current position
    Hashtable pos = new Hashtable();
      Hashtable vis = new Hashtable();
 
    for(i = 0; i < n; i++)
    {
        pos.Add(a[i], i);
    }
 
    // Initially next contains
    // the position of 1.
      if (pos.Contains(1))
        next = (int)pos[1];
      else
        next = 0; 
 
    for(i = 1; i <= n; i++)
    {
         
        // Mark the current
        // position.
        vis.Add(next, 1);
 
        // If the element is not
        // present at that position
        // then it is impossible
        // to build
        if (i != a[next])
        {
            return false;
        }
 
        // Updating the next
        if (next + 1 == n ||
           (vis.Contains(next + 1) &&
                (int)vis[next + 1] != 0))
        {
             
            // If the next position is
            // out of array size or next
            // position is not empty then
            // we use the map to find the
            // position of the next element
              if (pos.Contains(i + 1))
                next = (int)pos[i + 1];
              else
                next = 0; 
        }
        else
         
            // Else just increment it
            next++;
    }
    return true;
}
 
// Driver code
static public void Main()
{
    int[] arr = { 2, 3, 4, 5, 1 };
    int N = arr.Length;
 
    if (CheckArray(arr, N) == true)
    {
        Console.WriteLine("YES");
    }
    else
    {
        Console.WriteLine("NO");
    }
}
}
 
// This code is contributed by akhilsaini

<script>
 
// JavaScript program to Check If we
// can build the given array
// under given constraints.
 
// Function return true if we
// can build the array
function CheckArray(a, n)
{
    var i, f = 0, next;
 
    // First one is to keep position
    // of each element
    // Second one is for marking
    // the current position
    var pos = new Map(), vis = new Map();
 
    for (i = 0; i < n; i++) {
        pos.set(a[i], i);
    }
 
    // Initially next contains
    // the position of 1.
    next = pos.get(1);
 
    for (i = 1; i <= n; i++) {
        // Mark the current
        // position.
        vis.set(next, 1);
 
        // If the element is not
        // present at that position
        // then it is impossible
        // to build
        if (i != a[next]) {
            return false;
        }
 
        // Updating the next
        if (next + 1 == n
            || vis.get(next + 1)) {
 
            // If the next position is
            // out of array size or next
            // position is not empty then
            // we use the map to find the
            // position of the next element
            next = pos.get(i + 1);
        }
        else
            // Else just increment it
            next++;
    }
 
    return true;
}
 
// Driver code
var arr = [2, 3, 4, 5, 1];
var N = arr.length;
if (CheckArray(arr, N)) {
    document.write( "YES" );
}
else {
    document.write( "NO" );
}
 
</script>

YES