Examine if each pair in Array B follows the identical relation as their corresponding values in A

Given two Arrays A[] and B[] every of measurement N, the duty is to verify if the given arrays are legitimate or not, based mostly on the next circumstances:

• Each component in A at index i, shall be mapped with the component in B on the similar index solely, i.e. (A[i] could be mapped with B[i] solely)
• For any pair in A (A[i], A[j]), if A[i] > A[j], then its corresponding worth in B also needs to be higher, i.e. B[i] > B[j] ought to be true.
• For any pair in A (A[i], A[j]), if A[i] = A[j], then its corresponding worth in B also needs to be equal, i.e. B[i] = B[j] ought to be true.

Examples:

Enter: N = 3, A[ ] = {10, 1, 17}, B[ ] = {10, 5, 15}
Output: true
Clarification: Contemplate all pairs in array A:
=> (10 and 1): Since 10>1, and their values in B (10 and 5 respectively) comply with the identical relation, subsequently it is a legitimate pair.
=> (1 and 17): Since 1<17, and their values in B (5 and 15 respectively) comply with the identical relation, subsequently it is a legitimate pair.
=> (10 and 17): Since 10<17, and their values in B (10 and 15 respectively) comply with the identical relation, subsequently it is a legitimate pair.
As all of the pairs are legitimate, subsequently the given arrays are additionally legitimate. Therefore the output is true.

Enter: N = 5, A[ ] = {8, 5, 5, 10, 15}, B[ ] = {50, 10, 10, 15, 5 }
Output: false

Naive Strategy: Essentially the most fundamental method to unravel is downside is to discover every pair in array A, and verify if the relation between that pair is glad for corresponding values in array B. If any such pair exists, the place the values are usually not glad, then return false. Else return true.

Time Complexity: O(N²)
Auxiliary House: O(1)

Environment friendly Strategy: 

Instinct:

The thought for this method is predicated on the statement that if the weather in an Array are sorted in ascending order,  

• Then the primary component shall be all the time smaller than or equal to the second component
• Equally, the primary component will even be smaller than or equal to the final component
• Therefore any component at index i shall be smaller than or equal to component at index j, if (i < j)

Based mostly on the above statement: 

• If we attempt to type the array A by remembering their corresponding values in array B, then as a substitute of checking each pair in A, we are able to merely verify for adjoining pairs in A to comply with the circumstances given in the issue.  
• If all adjoining pairs in sorted A follows the circumstances to be legitimate, then the given Arrays shall be legitimate.

Illustration:

Suppose A[ ] = {10, 1, 17}, and B[ ] = {10, 5, 15}

If we type A, by remembering their corresponding values in B, we get A[] = {1, 10, 17}, B[] = {5, 10, 15}

Now if we verify adjoining pairs in A to comply with the circumstances given in downside, we get:

• Pair (1, 10): Since 1<10 and their values in B (5, 10) additionally comply with similar relation. Subsequently it is a legitimate pair.
• Pair (10, 17): Since 10<17 and their values in B (10, 15) additionally comply with similar relation. Subsequently it is a legitimate pair.

Since all of the values in A has been verified, subsequently the given arrays are additionally legitimate.

Algorithm: Observe the steps beneath to implement the above method:

• Create a brand new vector of pairs to retailer corresponding values in {A[i], B[i]} format.
• Type the vector, based mostly on values of array A.
• For every adjoining pairs within the vector, verify if:
  • if A[i] < A[i+1] and B[i] > B[i+1], then this isn’t a legitimate pair. 
  • if A[i] == A[i+1] and B[i] != B[i+1], then this isn’t a legitimate pair. 
• If not one of the pairs within the above iteration fulfill the invalid pair circumstances

Beneath is the implementation of the above method: 

Time Complexity: O(N * log N)
Auxiliary House: O(N), for making a vector of pairs.