Compruebe si una array se puede organizar en una array posicionada a la izquierda o a la derecha

Dada una array arr[] de tamaño n>4, la tarea es verificar si la array dada se puede organizar en forma de array posicionada a la izquierda o a la derecha. 
Array posicionada a la izquierda o a la derecha significa que cada elemento de la array es igual al número de elementos a su izquierda o al número de elementos a su derecha.

Ejemplos: 

Input  : arr[] = {1, 3, 3, 2}
Output : "YES"  
This array has one such arrangement {3, 1, 2, 3}. 
In this arrangement, first element '3' indicates 
that three numbers are after it, the 2nd element 
'1' indicates that one number is before it, the 
3rd element '2' indicates that two elements are 
before it.

Input : arr[] = {1, 6, 5, 4, 3, 2, 1}
Output: "NO"
// No such arrangement is possible

Input : arr[] = {2, 0, 1, 3}
Output: "YES"
// Possible arrangement is {0, 1, 2, 3}

Input : arr[] = {2, 1, 5, 2, 1, 5}
Output: "YES"
// Possible arrangement is {5, 1, 2, 2, 1, 5}

Una solución simple es generar todos los arreglos posibles (consulte este artículo) y verificar la condición de array posicionada a la izquierda o a la derecha, si cada elemento de la array satisface la condición, entonces «SÍ», de lo contrario, «NO». La complejidad del tiempo para este enfoque es O(n*n! + n), n*n! para generar todos los arreglos y n para verificar la condición usando una array temporal.

Una solución eficiente para este problema necesita un poco de observación y trabajo con lápiz y papel. Para satisfacer la condición de array posicionada a la izquierda o a la derecha, todos los números de la array deben ser iguales a index, i o (n-1-i) y arr[i] < n. Entonces creamos una array visitada [] de tamaño n e inicializamos su elemento con 0. Luego recorremos la array y seguimos los pasos dados:

• Si visitó[arr[i]] = 0, entonces conviértalo en 1, lo que verifica la condición de que el número de elementos en el lado izquierdo de la array arr[0]…arr[i-1] es igual a arr[i].
• De lo contrario, haga visited[n-arr[i]-1] = 1, lo que verifica la condición de que el número de elementos en el lado derecho de la array arr[i+1]…arr[n-1] es igual a arr[i ].
• Ahora recorra la array visitada [] y si todos los elementos de la array visitada [] se convierten en 1, eso significa que la disposición es posible «SÍ» de lo contrario «NO».

Implementación:

// C++ program to check if an array can be arranged
// to left or right positioned array.
#include<bits/stdc++.h>
using namespace std;
 
// Function to check Left or Right Positioned
// Array.
// arr[] is array of n elements
// visited[] is boolean array of size n
bool leftRight(int arr[],int n)
{
    // Initially no element is placed at any position
    int visited[n] = {0};
 
    // Traverse each element of array
    for (int i=0; i<n; i++)
    {
        // Element must be smaller than n.
        if (arr[i] < n)
        {
            // Place "arr[i]" at position "i"
            // or at position n-arr[i]-1
            if (visited[arr[i]] == 0)
                visited[arr[i]] = 1;
            else
                visited[n-arr[i]-1] = 1;
        }
    }
 
    // All positions must be occupied
    for (int i=0; i<n; i++)
        if (visited[i] == 0)
            return false;
 
    return true;
}
 
// Driver program to test the case
int main()
{
    int arr[] = {2, 1, 5, 2, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (leftRight(arr, n) == true)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

// Java program to check if an array
// can be arranged to left or
// right positioned array.
 
class GFG {
     
    // Function to check Left or
    // Right Positioned Array.
    // arr[] is array of n elements
    // visited[] is boolean array of size n
    static boolean leftRight(int arr[], int n) {
     
    // Initially no element is
    // placed at any position
    int visited[] = new int[n];
 
    // Traverse each element of array
    for (int i = 0; i < n; i++) {
         
    // Element must be smaller than n.
    if (arr[i] < n) {
         
        // Place "arr[i]" at position "i"
        // or at position n-arr[i]-1
        if (visited[arr[i]] == 0)
        visited[arr[i]] = 1;
        else
        visited[n - arr[i] - 1] = 1;
    }
    }
 
    // All positions must be occupied
    for (int i = 0; i < n; i++)
    if (visited[i] == 0)
        return false;
 
    return true;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = {2, 1, 5, 2, 1, 5};
    int n = arr.length;
    if (leftRight(arr, n) == true)
    System.out.print("YES");
    else
    System.out.print("NO");
}
}
 
// This code is contributed by Anant Agarwal.

# Python3 program to check
# if an array can be arranged
# to left or right positioned array.
 
# Function to check Left
# or Right Positioned
# Array.
# arr[] is array of n elements
# visited[] is boolean array of size n
def leftRight(arr,n):
 
    # Initially no element
    # is placed at any position
    visited=[]
    for i in range(n+1):
        visited.append(0)
  
    # Traverse each element of array
    for i in range(n):
     
        # Element must be smaller than n.
        if (arr[i] < n):
         
            # Place "arr[i]" at position "i"
            # or at position n-arr[i]-1
            if (visited[arr[i]] == 0):
                visited[arr[i]] = 1
            else:
                visited[n-arr[i]-1] = 1
  
    # All positions must be occupied
    for i in range(n):
        if (visited[i] == 0):
            return False
  
    return True
     
# Driver code
 
arr = [2, 1, 5, 2, 1, 5]
n = len(arr)
 
if (leftRight(arr, n) == True):
    print("YES")
else:
    print("NO")
 
# This code is contributed
# by Anant Agarwal.

     
// C# program to check if an array
// can be arranged to left or
// right positioned array.
using System;
public class GFG {
 
        // Function to check Left or
        // Right Positioned Array.
        // arr[] is array of n elements
        // visited[] is boolean array of size n
        static bool leftRight(int []arr, int n) {
 
        // Initially no element is
        // placed at any position
        int []visited = new int[n];
 
        // Traverse each element of array
        for (int i = 0; i < n; i++) {
 
        // Element must be smaller than n.
        if (arr[i] < n) {
 
            // Place "arr[i]" at position "i"
            // or at position n-arr[i]-1
            if (visited[arr[i]] == 0)
            visited[arr[i]] = 1;
            else
            visited[n - arr[i] - 1] = 1;
        }
        }
 
        // All positions must be occupied
        for (int i = 0; i < n; i++)
        if (visited[i] == 0)
            return false;
 
        return true;
    }
 
    // Driver code
    public static void Main()
    {
        int []arr = {2, 1, 5, 2, 1, 5};
        int n = arr.Length;
        if (leftRight(arr, n) == true)
        Console.WriteLine("YES");
        else
        Console.WriteLine("NO");
    }
}
// This code is contributed by PrinciRaj1992

<?php
// PHP program to check if an
// array can be arranged to
// left or right positioned array.
 
// Function to check Left or
// Right Positioned Array.
// arr[] is array of n elements
// visited[] is boolean array of size n
function leftRight($arr, $n)
{
    // Initially no element is
    // placed at any position
    $visited[$n] = array(0);
 
    // Traverse each element of array
    for ($i = 0; $i < $n; $i++)
    {
        // Element must be smaller than n.
        if ($arr[$i] < $n)
        {
            // Place "arr[i]" at position "i"
            // or at position n-arr[i]-1
                $visited[$arr[$i]] = 1;
                $visited[$n - $arr[$i] - 1] = 1;
        }
    }
 
    // All positions must be occupied
    for ($i = 0; $i < $n; $i++)
        if ($visited[$i] == 0)
            return false;
 
    return true;
}
 
// Driver Code
$arr = array(2, 1, 5, 2, 1, 5);
$n = sizeof($arr);
if (leftRight($arr, $n) == true)
    echo "YES";
else
    echo "NO";
 
// This code is contributed by ajit
?>

<script>
 
    // Javascript program to check if an array
    // can be arranged to left or
    // right positioned array.
     
    // Function to check Left or
    // Right Positioned Array.
    // arr[] is array of n elements
    // visited[] is boolean array of size n
    function leftRight(arr, n) {
   
        // Initially no element is
        // placed at any position
        let visited = new Array(n);
   
        // Traverse each element of array
        for (let i = 0; i < n; i++) {
   
          // Element must be smaller than n.
          if (arr[i] < n) {
 
              // Place "arr[i]" at position "i"
              // or at position n-arr[i]-1
              if (visited[arr[i]] == 0)
                  visited[arr[i]] = 1;
              else
                  visited[n - arr[i] - 1] = 1;
          }
        }
   
        // All positions must be occupied
        for (let i = 0; i < n; i++)
          if (visited[i] == 0)
              return false;
   
        return true;
    }
     
    let arr = [2, 1, 5, 2, 1, 5];
    let n = arr.length;
    if (leftRight(arr, n) == true)
      document.write("YES");
    else
      document.write("NO");
       
</script>

YES

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(n)

Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.