Given two Arrays A[] and B[] each of size N, the task is to check if the given arrays are valid or not, based on the following conditions:
- Every element in A at index i, will be mapped with the element in B at the same index only, i.e. (A[i] can be mapped with B[i] only)
- For any pair in A (A[i], A[j]), if A[i] > A[j], then its corresponding value in B should also be greater, i.e. B[i] > B[j] should be true.
- For any pair in A (A[i], A[j]), if A[i] = A[j], then its corresponding value in B should also be equal, i.e. B[i] = B[j] should be true.
Examples:
Input: N = 3, A[ ] = {10, 1, 17}, B[ ] = {10, 5, 15}
Output: true
Explanation: Consider all pairs in array A:
=> (10 and 1): Since 10>1, and their values in B (10 and 5 respectively) follow the same relation, therefore this is a valid pair.
=> (1 and 17): Since 1<17, and their values in B (5 and 15 respectively) follow the same relation, therefore this is a valid pair.
=> (10 and 17): Since 10<17, and their values in B (10 and 15 respectively) follow the same relation, therefore this is a valid pair.
As all the pairs are valid, therefore the given arrays are also valid. Hence the output is true.Input: N = 5, A[ ] = {8, 5, 5, 10, 15}, B[ ] = {50, 10, 10, 15, 5 }
Output: false
Naive Approach: The most basic approach to solve is problem is to find each pair in array A, and check if the relation between that pair is satisfied for corresponding values in array B. If any such pair exists, where the values are not satisfied, then return false. Else return true.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach:
Intuition:
The idea for this approach is based on the observation that if the elements in an Array are sorted in ascending order,
- Then the first element will be always smaller than or equal to the second element
- Similarly, the first element will also be smaller than or equal to the last element
- Hence any element at index i will be smaller than or equal to element at index j, if (i < j)
Based on the above observation:
- If we try to sort the array A by remembering their corresponding values in array B, then instead of checking every pair in A, we can simply check for adjacent pairs in A to follow the conditions given in the problem.
- If all adjacent pairs in sorted A follows the conditions to be valid, then the given Arrays will be valid.
Illustration:
Suppose A[ ] = {10, 1, 17}, and B[ ] = {10, 5, 15}
If we sort A, by remembering their corresponding values in B, we get A[] = {1, 10, 17}, B[] = {5, 10, 15}
Now if we check adjacent pairs in A to follow the conditions given in problem, we get:
- Pair (1, 10): Since 1<10 and their values in B (5, 10) also follow same relation. Therefore this is a valid pair.
- Pair (10, 17): Since 10<17 and their values in B (10, 15) also follow same relation. Therefore this is a valid pair.
Since all the values in A has been verified, therefore the given arrays are also valid.
Algorithm: Follow the steps below to implement the above approach:
- Create a new vector of pairs to store corresponding values in {A[i], B[i]} format.
- Sort the vector, based on values of array A.
- For each adjacent pairs in the vector, check if:
- if A[i] < A[i+1] and B[i] > B[i+1], then this is not a valid pair.
- Hence return false.
- if A[i] == A[i+1] and B[i] != B[i+1], then this is not a valid pair.
- Hence return false.
- if A[i] < A[i+1] and B[i] > B[i+1], then this is not a valid pair.
- If none of the pairs in the above iteration satisfy the invalid pair conditions
- Return true.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check the given array relations are valid or notbool 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 Codeint 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
// Java program for the above approachimport 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
# Python3 code for the above approach# Function to check the given array relations are valid or notdef 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 CodeA = [10, 1, 17]B = [10, 5, 15]N = len(A)print(isValidArrays(A, B, N)) # This code is contributed by phasing17 |
C#
// C# program for the above approachusing 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 |
Javascript
<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
Time Complexity: O(N * log N)
Auxiliary Space: O(N), for creating a vector of pairs.
