Given a 2D array arr[][] consisting of N pairs of integers, the task is to find the pair which covers all other pairs of the given array. If it is impossible to find such a pair, then print -1.
A pair {a, ?b} will cover another pair {c, ?d}, if the condition (a???c???d???b) holds true.
Examples:
Input: arr[][2] = {{2, 2}, {3, 3}, {3, 5}, {4, 5}, {1, 1}, {1, 5}}
Output: 6
Explanation:
There exist a pair (1, 5) which cover all other pair because all other pair lies in the pair {1, 5}.
Therefore, the position of the pair {1, 5} is 6. So, the output is 6.Input: arr[][] = {{1, 20}, {2, 22}, {3, 18}}
Output: -1
Explanation:
No such pair exists which covers all the remaining pairs.
Therefore, the output is -1
Naive Approach: The simplest approach is to compare each pair with all other pairs and check if any pair covers all the pairs or not. Below are the steps:
- Initialize a variable count = 0 which stores the number of pairs that lie between the current pair.
- Traverse the array of pairs and for each pair, check if the count is equal to the total number of pairs or not.
- If found to be true, it means that the pair can cover all other pairs. Print the pair.
- Otherwise, set count = 0 and repeat the above steps for the next pair.
- If no such pair exists, then print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the position of // the pair that covers every pair // in the array arr[][] void position( int arr[][2], int N) { // Stores the index of the // resultant pair int pos = -1; // To count the occurrences int count; // Iterate to check every pair for ( int i = 0; i < N; i++) { // Set count to 0 count = 0; for ( int j = 0; j < N; j++) { // Condition to checked for // overlapping of pairs if (arr[i][0] <= arr[j][0] && arr[i][1] >= arr[j][1]) { count++; } } // If that pair can cover all other // pairs then store its position if (count == N) { pos = i; } } // If position not found if (pos == -1) { cout << pos; } // Otherwise else { cout << pos + 1; } } // Driver Code int main() { // Given array of pairs int arr[][2] = {{ 3, 3 }, { 1, 3 }, { 2, 2 }, { 2, 3 }, { 1, 2 }}; int N = sizeof (arr) / sizeof (arr[0]); // Function Call position(arr, N); } |
Java
// Java program for // the above approach import java.util.*; class GFG{ // Function to find the position of // the pair that covers every pair // in the array arr[][] static void position( int arr[][], int N) { // Stores the index of the // resultant pair int pos = - 1 ; // To count the occurrences int count; // Iterate to check every pair for ( int i = 0 ; i < N; i++) { // Set count to 0 count = 0 ; for ( int j = 0 ; j < N; j++) { // Condition to checked for // overlapping of pairs if (arr[i][ 0 ] <= arr[j][ 0 ] && arr[i][ 1 ] >= arr[j][ 1 ]) { count++; } } // If that pair can cover all other // pairs then store its position if (count == N) { pos = i; } } // If position not found if (pos == - 1 ) { System.out.print(pos); } // Otherwise else { System.out.print(pos + 1 ); } } // Driver Code public static void main(String[] args) { // Given array of pairs int arr[][] = {{ 3 , 3 }, { 1 , 3 }, { 2 , 2 }, { 2 , 3 }, { 1 , 2 }}; int N = arr.length; // Function Call position(arr, N); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for # the above approach # Function to find the position of # the pair that covers every pair # in the array arr def position(arr, N): # Stores the index of the # resultant pair pos = - 1 ; # To count the occurrences count = 0 ; # Iterate to check every pair for i in range (N): # Set count to 0 count = 0 ; for j in range (N): # Condition to checked for # overlapping of pairs if (arr[i][ 0 ] < = arr[j][ 0 ] and arr[i][ 1 ] > = arr[j][ 1 ]): count + = 1 ; # If that pair can cover # all other pairs then # store its position if (count = = N): pos = i; # If position not found if (pos = = - 1 ): print (pos); # Otherwise else : print (pos + 1 ); # Driver Code if __name__ = = '__main__' : # Given array of pairs arr = [[ 3 , 3 ], [ 1 , 3 ], [ 2 , 2 ], [ 2 , 3 ], [ 1 , 2 ]]; N = len (arr); # Function Call position(arr, N); # This code is contributed by shikhasingrajput |
C#
// C# program for // the above approach using System; class GFG{ // Function to find the position of // the pair that covers every pair // in the array arr[][] static void position( int [,] arr, int N) { // Stores the index of the // resultant pair int pos = -1; // To count the occurrences int count; // Iterate to check every pair for ( int i = 0; i < N; i++) { // Set count to 0 count = 0; for ( int j = 0; j < N; j++) { // Condition to checked for // overlapping of pairs if (arr[i, 0] <= arr[j, 0] && arr[i, 1] >= arr[j, 1]) { count++; } } // If that pair can cover // all other pairs then // store its position if (count == N) { pos = i; } } // If position not found if (pos == -1) { Console.Write(pos); } // Otherwise else { Console.Write(pos + 1); } } // Driver Code public static void Main() { // Give array of pairs int [,] arr = {{3, 3}, {1, 3}, {2, 2}, {2, 3}, {1, 2}}; int N = arr.GetLength(0); // Function Call position(arr, N); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program for // the above approach // Function to find the position of // the pair that covers every pair // in the array arr[][] function position(arr, N) { // Stores the index of the // resultant pair let pos = -1; // To count the occurrences let count; // Iterate to check every pair for (let i = 0; i < N; i++) { // Set count to 0 count = 0; for (let j = 0; j < N; j++) { // Condition to checked for // overlapping of pairs if (arr[i][0] <= arr[j][0] && arr[i][1] >= arr[j][1]) { count++; } } // If that pair can cover all other // pairs then store its position if (count == N) { pos = i; } } // If position not found if (pos == -1) { document.write(pos); } // Otherwise else { document.write(pos + 1); } } // Driver Code // Given array of pairs let arr = [[3, 3], [1, 3], [2, 2], [2, 3], [1, 2]]; let N = arr.length; // Function Call position(arr, N); </script> |
2
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to observe that the answer is always unique because there is always a unique pair that contains both minimum and maximum value. Below are the steps:
- Iterate over the given array of pairs and find the minimum first pair and maximum second pair from all the pairs in arr[][].
- After finding the maximum and minimum in the above step, there must exist any pair with arr[i][0] = minimum and arr[i][1] = maximum.
- Iterate through every array of pairs and check if there exists a pair whose arr[i][0] is equal to the minimum and arr[i][1] is equal to the maximum.
- If there exists any position in the above step, then print that position.
- Otherwise, print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the position of // the pair that covers every pair // in the array arr[][] void position( int arr[][2], int N) { // Position to store the index int pos = -1; // Stores the maximum second value int right = INT_MIN; // Stores the minimum first value int left = INT_MAX; // Iterate over the array of pairs for ( int i = 0; i < N; i++) { // Update right maximum if (arr[i][1] > right) { right = arr[i][1]; } // Update left minimum if (arr[i][0] < left) { left = arr[i][0]; } } // Iterate over the array of pairs for ( int i = 0; i < N; i++) { // If any pair exists with value // {left, right} then store it if (arr[i][0] == left && arr[i][1] == right) { pos = i + 1; } } // Print the answer cout << pos << endl; } // Driver Code int main() { // Given array of pairs int arr[][2] = {{ 3, 3 }, { 1, 3 }, { 2, 2 }, { 2, 3 }, { 1, 2 }}; int N = sizeof (arr) / sizeof (arr[0]); // Function Call position(arr, N); } |
Java
// Java program for the // above approach import java.util.*; class GFG{ // Function to find the position // of the pair that covers // every pair in the array arr[][] static void position( int arr[][], int N) { // Position to store // the index int pos = - 1 ; // Stores the maximum // second value int right = Integer.MIN_VALUE; // Stores the minimum // first value int left = Integer.MAX_VALUE; // Iterate over the array // of pairs for ( int i = 0 ; i < N; i++) { // Update right maximum if (arr[i][ 1 ] > right) { right = arr[i][ 1 ]; } // Update left minimum if (arr[i][ 0 ] < left) { left = arr[i][ 0 ]; } } // Iterate over the array // of pairs for ( int i = 0 ; i < N; i++) { // If any pair exists // with value {left, // right} then store it if (arr[i][ 0 ] == left && arr[i][ 1 ] == right) { pos = i + 1 ; } } // Print the answer System.out.print(pos + "\n" ); } // Driver Code public static void main(String[] args) { // Given array of pairs int arr[][] = {{ 3 , 3 }, { 1 , 3 }, { 2 , 2 }, { 2 , 3 }, { 1 , 2 }}; int N = arr.length; // Function Call position(arr, N); } } // This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach import sys # Function to find the position of # the pair that covers every pair # in the array arr[][] def position(arr, N): # Position to store the index pos = - 1 # Stores the minimum second value right = - sys.maxsize - 1 # Stores the maximum first value left = sys.maxsize # Iterate over the array of pairs for i in range (N): # Update right maximum if (arr[i][ 1 ] > right): right = arr[i][ 1 ] # Update left minimum if (arr[i][ 0 ] < left): left = arr[i][ 0 ] # Iterate over the array of pairs for i in range (N): # If any pair exists with value # {left, right then store it if (arr[i][ 0 ] = = left and arr[i][ 1 ] = = right): pos = i + 1 # Print the answer print (pos) # Driver Code if __name__ = = '__main__' : # Given array of pairs arr = [ [ 3 , 3 ], [ 1 , 3 ], [ 2 , 2 ], [ 2 , 3 ], [ 1 , 2 ] ] N = len (arr) # Function call position(arr, N) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approach using System; class GFG{ // Function to find the position // of the pair that covers // every pair in the array [,]arr static void position( int [,]arr, int N) { // Position to store // the index int pos = -1; // Stores the maximum // second value int right = int .MinValue; // Stores the minimum // first value int left = int .MaxValue; // Iterate over the array // of pairs for ( int i = 0; i < N; i++) { // Update right maximum if (arr[i, 1] > right) { right = arr[i, 1]; } // Update left minimum if (arr[i, 0] < left) { left = arr[i, 0]; } } // Iterate over the array // of pairs for ( int i = 0; i < N; i++) { // If any pair exists // with value {left, // right} then store it if (arr[i, 0] == left && arr[i, 1] == right) { pos = i + 1; } } // Print the answer Console.Write(pos + "\n" ); } // Driver Code public static void Main(String[] args) { // Given array of pairs int [,]arr = {{3, 3}, {1, 3}, {2, 2}, {2, 3}, {1, 2}}; int N = arr.GetLength(0); // Function Call position(arr, N); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program for the above approach // Function to find the position of // the pair that covers every pair // in the array arr[][] function position(arr, N){ // Position to store the index let pos = -1 // Stores the minimum second value let right = Number.MIN_VALUE // Stores the maximum first value let left = Number.MAX_VALUE // Iterate over the array of pairs for (let i=0;i<N;i++){ // Update right maximum if (arr[i][1] > right) right = arr[i][1] // Update left minimum if (arr[i][0] < left) left = arr[i][0] } // Iterate over the array of pairs for (let i=0;i<N;i++){ // If any pair exists with value // {left, right then store it if (arr[i][0] == left && arr[i][1] == right) pos = i + 1 } // Print the answer document.write(pos, "</br>" ) } // Driver Code // Given array of pairs let arr = [ [ 3, 3 ], [ 1, 3 ], [ 2, 2 ], [ 2, 3 ], [ 1, 2 ] ] let N = arr.length // Function call position(arr, N) // This code is contributed by shinjanpatra </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!