Compruebe si cada par en la array B sigue la misma relación que sus valores correspondientes en A

Dados dos arreglos A[] y B[] , cada uno de tamaño N , la tarea es verificar si los arreglos dados son válidos o no, en función de las siguientes condiciones:

• Cada elemento en A en el índice i , será mapeado con el elemento en B en el mismo índice solamente, es decir ( A[i] puede ser mapeado con B[i] solamente )
• Para cualquier par en A (A[i], A[j]), si A[i] > A[j] , entonces su valor correspondiente en B también debería ser mayor, es decir, B[i] > B[j] debería ser verdad
• Para cualquier par en A (A[i], A[j]), si A[i] = A[j] , entonces su valor correspondiente en B también debería ser igual, es decir, B[i] = B[j] debería ser verdad

Ejemplos:

Entrada: N = 3, A[ ] = {10, 1, 17}, B[ ] = {10, 5, 15}
Salida: verdadero
Explicación: Considere todos los pares en el arreglo A:
=> (10 y 1): Dado que 10>1, y sus valores en B (10 y 5 respectivamente) siguen la misma relación, por lo tanto este es un par válido.
=> (1 y 17): Dado que 1<17, y sus valores en B (5 y 15 respectivamente) siguen la misma relación, entonces este es un par válido.
=> (10 y 17): Dado que 10<17, y sus valores en B (10 y 15 respectivamente) siguen la misma relación, entonces este es un par válido.
Como todos los pares son válidos, las arrays dadas también son válidas. Por lo tanto, la salida es verdadera.

Entrada: N = 5, A[ ] = {8, 5, 5, 10, 15}, B[ ] = {50, 10, 10, 15, 5 } Salida
: falso

Enfoque ingenuo: el enfoque más básico para resolver el problema es encontrar cada par en la array A y verificar si la relación entre ese par se cumple para los valores correspondientes en la array B. Si existe tal par, donde los valores no se cumplen, luego devuelve falso. De lo contrario, devuelve verdadero.

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

Enfoque eficiente: 

Intuición:

La idea de este enfoque se basa en la observación de que si los elementos de un Array se ordenan en orden ascendente,  

• Entonces el primer elemento siempre será menor o igual que el segundo elemento
• De manera similar, el primer elemento también será menor o igual que el último elemento.
• Por lo tanto, cualquier elemento en el índice i será menor o igual que el elemento en el índice j, si (i < j)

Con base en la observación anterior: 

• Si tratamos de ordenar el arreglo A recordando sus valores correspondientes en el arreglo B, entonces en lugar de verificar cada par en A, podemos simplemente verificar los pares adyacentes en A para seguir las condiciones dadas en el problema.  
• Si todos los pares adyacentes en el orden A siguen las condiciones para ser válidos, entonces las arrays dadas serán válidas.

Ilustración:

Supongamos que A[ ] = {10, 1, 17} y B[ ] = {10, 5, 15}

Si ordenamos A, recordando sus valores correspondientes en B, obtenemos A[] = {1, 10, 17}, B[] = {5, 10, 15}

Ahora, si verificamos que los pares adyacentes en A sigan las condiciones dadas en el problema, obtenemos:

• Par (1, 10): Dado que 1<10 y sus valores en B (5, 10) también siguen la misma relación. Por lo tanto, este es un par válido.
• Par (10, 17): Dado que 10<17 y sus valores en B (10, 15) también siguen la misma relación. Por lo tanto, este es un par válido.

Dado que todos los valores en A han sido verificados, las arrays dadas también son válidas.

Algoritmo: siga los pasos a continuación para implementar el enfoque anterior:

• Cree un nuevo vector de pares para almacenar los valores correspondientes en formato {A[i], B[i]}.
• Ordene el vector, según los valores de la array A.
• Para cada par adyacente en el vector, verifique si:
  • si A[i] < A[i+1] y B[i] > B[i+1] , entonces este no es un par válido. 
    • Por lo tanto, devuelve falso.
  • si A[i] == A[i+1] y B[i] != B[i+1] , entonces este no es un par válido. 
    • Por lo tanto, devuelve falso.
• Si ninguno de los pares en la iteración anterior satisface las condiciones de par no válido
  • Devolver verdadero.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check the given array relations are valid or not
bool isValidArrays(int A[], int B[], int n)
{
    // creating new vector of pair to store the array
    // relations.
    vector<pair<int, int> > v1;
 
    // push elements of A with its corresponding
    // value in B;
    for (int i = 0; i < n; i++) {
        v1.push_back(make_pair(A[i], B[i]));
    }
 
    // sort vector by first value
    sort(v1.begin(), v1.end());
 
    // check the given relations.
    for (int i = 0; i < v1.size() - 1; i++) {
        if (v1[i].first == v1[i + 1].first) {
            // if relation is not valid return false
            if (v1[i].second != v1[i + 1].second) {
                return false;
            }
        }
        else {
            // if relation is not valid return false
            if (v1[i].second >= v1[i + 1].second) {
                return false;
            }
        }
    }
 
    return true;
}
 
// Driver Code
int main()
{
    int A[] = { 10, 1, 17 };
    int B[] = { 10, 5, 15 };
    int N = sizeof(A) / sizeof(A[0]);
 
    cout << boolalpha << isValidArrays(A, B, N);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
 
  // Function to check the given array relations are valid
  // or not
  public static boolean isValidArrays(int A[], int B[],
                                      int n)
  {
 
    // creating new array of pair to store the array
    // relations.
    int v1[][] = new int[n][2];
 
    // push elements of A with its corresponding
    // value in B.
    for (int i = 0; i < n; i++) {
      v1[i][0] = A[i];
      v1[i][1] = B[i];
    }
 
    // sort array by first value
    Arrays.sort(v1,
                (a, b) -> Integer.compare(a[0], b[0]));
 
    // check the given relations.
    for (int i = 0; i < n - 1; i++) {
      if (v1[i][0] == v1[i + 1][0]) {
        // if relation is not valid return false
        if (v1[i][1] != v1[i + 1][1]) {
          return false;
        }
      }
      else {
        // if relation is not valid return false
        if (v1[i][1] >= v1[i + 1][1]) {
          return false;
        }
      }
    }
 
    return true;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int A[] = { 10, 1, 17 };
    int B[] = { 10, 5, 15 };
    int N = 3;
 
    System.out.print(isValidArrays(A, B, N));
  }
}
 
// This code is contributed by Rohit Pradhan

# Python3 code for the above approach
 
# Function to check the given array relations are valid or not
def isValidArrays(A, B, n):
     
    # creating new 2d list to store the array
    # relations
    v1 = []
     
    # push elements of A with its corresponding
    # value in B
    for i in range(n):
        v1.append([A[i], B[i]])
     
    # sort v1 by first value
    v1.sort()
     
    # check the given relations
    for i in range(len(v1) - 1):
        if v1[i][0] == v1[i + 1][0]:
            # if relation is not valid
            # return false
            if v1[i][1] != v1[i + 1][1]:
                return False
        else:
            # if relation is not valid
            # return false
            if v1[i][1] >= v1[i + 1][1]:
                return False
     
    return True
     
# Driver Code
A = [10, 1, 17]
B = [10, 5, 15]
N = len(A)
 
print(isValidArrays(A, B, N))
                  
# This code is contributed by phasing17

// C# program for the above approach
using System;
 
public class GFG
{
 
  // Function to check the given array relations are valid
  // or not
  public static bool isValidArrays(int[] A, int[] B,
                                   int n)
  {
 
    // creating two arrays to store the array
    // relations.
    int[] v1 = new int[n];
    int[] v2 = new int[n];
 
    // push elements of A with its corresponding
    // value in B.
    for (int i = 0; i < n; i++) {
      v1[i] = A[i];
      v2[i] = B[i];
    }
 
    // sort both the arrays by v1 values
    Array.Sort(v1, v2);
 
    // check the given relations.
    for (int i = 0; i < n - 1; i++) {
      if (v1[i] == v1[i + 1]) {
        // if relation is not valid return false
        if (v2[i] != v2[i + 1]) {
          return false;
        }
      }
      else {
        // if relation is not valid return false
        if (v2[i] >= v2[i + 1]) {
          return false;
        }
      }
    }
 
    return true;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int[] A = { 10, 1, 17 };
    int[] B = { 10, 5, 15 };
    int N = 3;
 
    // Function Call
    Console.WriteLine(isValidArrays(A, B, N));
  }
}
 
// This code is contributed by phasing17

<script>
       // JavaScript code for the above approach
 
       // Function to check the given array relations are valid or not
       function isValidArrays(A, B, n)
       {
        
           // creating new vector of pair to store the array
           // relations.
           let v1 = [];
 
           // push elements of A with its corresponding
           // value in B;
           for (let i = 0; i < n; i++) {
               v1.push({ first: A[i], second: B[i] });
           }
 
           // sort vector by first value
           v1.sort(function (a, b) { return a.first - b.first })
 
           // check the given relations.
           for (let i = 0; i < v1.length - 1; i++)
           {
               if (v1[i].first == v1[i + 1].first)
               {
                
                   // if relation is not valid return false
                   if (v1[i].second != v1[i + 1].second) {
                       return false;
                   }
               }
               else
               {
                
                   // if relation is not valid return false
                   if (v1[i].second >= v1[i + 1].second) {
                       return false;
                   }
               }
           }
 
           return true;
       }
 
       // Driver Code
       let A = [10, 1, 17];
       let B = [10, 5, 15];
       let N = A.length;
 
       document.write(isValidArrays(A, B, N));
 
   // This code is contributed by Potta Lokesh
   </script>

true

Complejidad Temporal: O(N * log N)
Espacio Auxiliar: O(N), para la creación de un vector de pares.