Given a vector of pairs arr[] and Q queries in the form of pairs in an array Queries[], the task for each query is to check if there exists any pair with both the values smaller than those in the pair of the current query. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[][] = {{3, 5}, {2, 7}, {2, 3}, {4, 9}}, Queries[][] = {{3, 4}, {3, 2}, {4, 1}, {3, 7}}
Output:
Yes
No
No
Yes
Explanation:
Query 1: Pair {2, 3} exists in arr[] which has both the values smaller than {3, 4}.
Query 2: No valid pair found in arr[] for {3, 2}.
Query 3: No valid pair found in arr[] for {4, 1}.
Query 4: Pair {2, 7} exists in arr[] for {3, 7}.Input: arr[][] = {{2, 1}, {4, 2}, {4, 4}, {7, 2}}, Queries[][] = {{2, 1}, {1, 1}}
Output:
Yes
No
Naive Approach: The simplest approach is to traverse the array Queries[][] and for each pair, traverse the given array of pairs and check if there exists any such pair whose corresponding values is greater than or equal to the pair {p1, p2} then print “Yes”. Otherwise, print “No”.
Time Complexity: O(N*K)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Binary Search. Follow the steps below to solve this problem:
- Sort the array of pairs with respect to first element in the pairs in increasing order. If there exist 2 pairs whose first values are the same, then pairs are arranged on the basis of the second element of the pair.
- After sorting, traverse the array of pairs, and for all pairs having the same first value, replace the second value with the minimum of all the pairs having the same first value.
- Now, traverse the given Queries[] arrays and perform binary search on the array arr[] for each pair in it.
- If the pairs obtained from the above steps is smaller than the current pair in the Query[], then print “Yes” else print “No”.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that performs binary search// to find value less than or equal to// first value of the pairint binary_search(vector<pair<int, int> > vec, int n, int a){ int low, high, mid; low = 0; high = n - 1; // Perform binary search while (low < high) { // Find the mid mid = low + (high - low + 1) / 2; // Update the high if (vec[mid].first > a) { high = mid - 1; } // Else update low else if (vec[mid].first <= a) { low = mid; } } // Return the low index return low;}// Function to modify the second// value of each pairvoid modify_vec( vector<pair<int, int> >& v, int n){ // start from index 1 for (int i = 1; i < n; i++) { v[i].second = min(v[i].second, v[i - 1].second); }}// Function to evaluate each queryint evaluate_query(vector<pair<int, int> > v, int n, int m1, int m2){ // Find value less than or equal to // the first value of pair int temp = binary_search(v, n, m1); // check if we got the required // pair or not if ((v[temp].first <= m1) && (v[temp].second <= m2)) { return 1; } return 0;}// Function to find a pair whose values is// less than the given pairs in queryvoid checkPairs(vector<pair<int, int> >& v, vector<pair<int, int> >& queries){ // Find the size of the vector int n = v.size(); // sort the vector based on // the first value sort(v.begin(), v.end()); // Function Call to modify the // second value of each pair modify_vec(v, n); int k = queries.size(); // Traverse each queries for (int i = 0; i < k; i++) { int m1 = queries[i].first; int m2 = queries[i].second; // Evaluate each query int result = evaluate_query(v, n, m1, m2); // Print the result if (result > 0) cout << "Yes\n"; else cout << "No\n"; }}// Driver Codeint main(){ vector<pair<int, int> > arr = { { 3, 5 }, { 2, 7 }, { 2, 3 }, { 4, 9 } }; vector<pair<int, int> > queries = { { 3, 4 }, { 3, 2 }, { 4, 1 }, { 3, 7 } }; // Function Call checkPairs(arr, queries); return 0;} |
Java
// Java program for above approachimport java.util.*;import java.lang.*;class GFG{ // Function that performs binary search // to find value less than or equal to // first value of the pair static int binary_search(int[][] vec, int n, int a) { int low, high, mid; low = 0; high = n - 1; // Perform binary search while (low < high) { // Find the mid mid = low + (high - low + 1) / 2; // Update the high if (vec[mid][0] > a) { high = mid - 1; } // Else update low else if (vec[mid][1] <= a) { low = mid; } } // Return the low index return low; } // Function to modify the second // value of each pair static void modify_vec( int[][] v, int n) { // start from index 1 for (int i = 1; i < n; i++) { v[i][1] = Math.min(v[i][1], v[i - 1][1]); } } // Function to evaluate each query static int evaluate_query(int[][] v, int n, int m1, int m2) { // Find value less than or equal to // the first value of pair int temp = binary_search(v, n, m1); // check if we got the required // pair or not if ((v[temp][0] <= m1) && (v[temp][1] <= m2)) { return 1; } return 0; } // Function to find a pair whose values is // less than the given pairs in query static void checkPairs(int[][] v, int[][] queries) { // Find the size of the vector int n = v.length; // sort the vector based on // the first value Arrays.sort(v, (a, b)->a[0]-b[0]); // Function Call to modify the // second value of each pair modify_vec(v, n); int k = queries.length; // Traverse each queries for (int i = 0; i < k; i++) { int m1 = queries[i][0]; int m2 = queries[i][1]; // Evaluate each query int result = evaluate_query(v, n, m1, m2); // Print the result if (result > 0) System.out.println("Yes"); else System.out.println("No"); } } // Driver function public static void main (String[] args) { int[][] arr = { { 3, 5 }, { 2, 7 }, { 2, 3 }, { 4, 9 } }; int[][] queries = { { 3, 4 }, { 3, 2 }, { 4, 1 }, { 3, 7 } }; // Function Call checkPairs(arr, queries); }}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach# Function that performs binary search# to find value less than or equal to# first value of the pairdef binary_search(vec, n, a): low, high, mid = 0, 0, 0 low = 0 high = n - 1 # Perform binary search while (low < high): # Find the mid mid = low + (high - low + 1) // 2 # Update the high if (vec[mid][0] > a): high = mid - 1 # Else update low elif vec[mid][0] <= a: low = mid # Return the low index return low# Function to modify the second# value of each pairdef modify_vec(v, n): # start from index 1 for i in range(n): v[i][1] = min(v[i][1], v[i - 1][1]) return v# Function to evaluate each querydef evaluate_query(v, n, m1, m2): # Find value less than or equal to # the first value of pair temp = binary_search(v, n, m1) # check if we got the required # pair or not if ((v[temp][0] <= m1) and (v[temp][1] <= m2)): return 1 return 0# Function to find a pair whose values is# less than the given pairs in querydef checkPairs(v, queries): # Find the size of the vector n = len(v) # sort the vector based on # the first value v = sorted(v) # Function Call to modify the # second value of each pair v = modify_vec(v, n) k = len(queries) # Traverse each queries for i in range(k): m1 = queries[i][0] m2 = queries[i][1] # Evaluate each query result = evaluate_query(v, n, m1, m2) # Print the result if (result > 0): print("Yes") else: print("No")# Driver Codeif __name__ == '__main__': arr= [ [ 3, 5 ], [ 2, 7 ], [ 2, 3 ], [ 4, 9 ] ] queries = [ [ 3, 4 ], [ 3, 2 ], [ 4, 1 ], [ 3, 7 ] ] # Function Call checkPairs(arr, queries)# This code is contributed by mohit kumar 29 |
C#
// C# program for above approachusing System;using System.Collections.Generic;class GFG{ // Function that performs binary search // to find value less than or equal to // first value of the pair static int binary_search(int[][] vec, int n, int a) { int low, high, mid; low = 0; high = n - 1; // Perform binary search while (low < high) { // Find the mid mid = low + (high - low + 1) / 2; // Update the high if (vec[mid][0] > a) { high = mid - 1; } // Else update low else if (vec[mid][1] <= a) { low = mid; } } // Return the low index return low; } // Function to modify the second // value of each pair static void modify_vec( int[][] v, int n) { // start from index 1 for (int i = 1; i < n; i++) { v[i][1] = Math.Min(v[i][1], v[i - 1][1]); } } // Function to evaluate each query static int evaluate_query(int[][] v, int n, int m1, int m2) { // Find value less than or equal to // the first value of pair int temp = binary_search(v, n, m1); // check if we got the required // pair or not if ((v[temp][0] <= m1) && (v[temp][1] <= m2)) { return 1; } return 0; } static int compare(int[] a, int[] b) { if (a[0] < b[0]) return -1; if (a[0] == b[0]) return 0; return 1; } // Function to find a pair whose values is // less than the given pairs in query static void checkPairs(int[][] v, int[][] queries) { // Find the size of the vector int n = v.Length; // sort the vector based on // the first value Array.Sort(v, compare); // Function Call to modify the // second value of each pair modify_vec(v, n); int k = queries.Length; // Traverse each queries for (int i = 0; i < k; i++) { int m1 = queries[i][0]; int m2 = queries[i][1]; // Evaluate each query int result = evaluate_query(v, n, m1, m2); // Print the result if (result > 0) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // Driver function public static void Main (string[] args) { int[][] arr = { new int[] { 3, 5 }, new int[] { 2, 7 }, new int[] { 2, 3 }, new int[] { 4, 9 } }; int[][] queries = { new int[] { 3, 4 }, new int[] { 3, 2 }, new int[] { 4, 1 }, new int[] { 3, 7 } }; // Function Call checkPairs(arr, queries); }}// This code is contributed by phasing17 |
Javascript
<script>// Javascript program for above approach// Function that performs binary search // to find value less than or equal to // first value of the pairfunction binary_search(vec,a,n){ let low, high, mid; low = 0; high = n - 1; // Perform binary search while (low < high) { // Find the mid mid = low + Math.floor((high - low + 1) / 2); // Update the high if (vec[mid][0] > a) { high = mid - 1; } // Else update low else if (vec[mid][1] <= a) { low = mid; } } // Return the low index return low;} // Function to modify the second // value of each pairfunction modify_vec(v,n){ // start from index 1 for (let i = 1; i < n; i++) { v[i][1] = Math.min(v[i][1], v[i - 1][1]); }}// Function to evaluate each queryfunction evaluate_query(v,n,m1,m2){ // Find value less than or equal to // the first value of pair let temp = binary_search(v, n, m1); // check if we got the required // pair or not if ((v[temp][0] <= m1) && (v[temp][1] <= m2)) { return 1; } return 0; } // Function to find a pair whose values is // less than the given pairs in queryfunction checkPairs(v, queries){ // Find the size of the vector let n = v.length; // sort the vector based on // the first value v.sort(function(a, b){return a[0]-b[0]}); // Function Call to modify the // second value of each pair modify_vec(v, n); let k = queries.length; // Traverse each queries for (let i = 0; i < k; i++) { let m1 = queries[i][0]; let m2 = queries[i][1]; // Evaluate each query let result = evaluate_query(v, n, m1, m2); // Print the result if (result > 0) document.write("Yes<br>"); else document.write("No<br>"); }}// Driver functionlet arr=[[ 3, 5 ], [ 2, 7 ], [ 2, 3 ], [ 4, 9 ]];let queries=[[ 3, 4 ], [ 3, 2 ], [ 4, 1 ], [ 3, 7 ]];// Function CallcheckPairs(arr, queries);// This code is contributed by unknown2108</script> |
Output:
Yes No No Yes
Time Complexity: O(Q*log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
