Given a 2D array arr[] consisting of N coordinates of the form (X, Y), the task is to find a coordinate from the given array such that the X-coordinate of this point is greater than all other X-coordinates and the Y-coordinate of this point is greater than all other Y-coordinates. If no such point exists, print -1.
Examples:
Input: arr[][] = {(1, 2), (2, 1), (3, 4), (4, 3), (5, 5)}
Output: (5, 5)
Explanation:
The maximum X-coordinate is 5 and the maximum Y-coordinate is 5.
Since the point (5, 5) is present in the array, print (5, 5) as the required answer.Input: arr[] = {(5, 3), (3, 5)}
Output: -1
Explanation:
The maximum X-coordinate is 5 and maximum Y-coordinate is 5. Since+ (5, 5) is not present. Therefore, print -1.
Naive Approach: The simplest approach is to traverse the array and for each point, check if it is the maximum X and Y-coordinates or not. If no such point exists, print -1. Otherwise, print the point as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Initialize INF as infinityint INF = INT_MAX;// Function to return the point having// maximum X and Y coordinatesint* findMaxPoint(int arr[][2], int i, int n){ // Base Case if (i == n) { arr[0][0] = INF; arr[0][1] = INF; return arr[0]; } // Stores if valid point exists bool flag = true; // If point arr[i] is valid for(int j = 0; j < n; j++) { // Check for the same point if (j == i) continue; // Check for a valid point if (arr[j][0] >= arr[i][0] || arr[j][1] >= arr[i][1]) { flag = false; break; } } // If current point is the // required point if (flag) return arr[i]; // Otherwise return findMaxPoint(arr, i + 1, n);}// Function to find the required pointvoid findMaxPoints(int arr[][2], int n){ // Stores the point with maximum // X and Y-coordinates int ans[2]; memcpy(ans, findMaxPoint(arr, 0, n), 2 * sizeof(int)); // If no required point exists if (ans[0] == INF) { cout << -1; } else { cout << "(" << ans[0] << " " << ans[1] << ")"; }}// Driver Codeint main(){ // Given array of points int arr[][2] = { { 1, 2 }, { 2, 1 }, { 3, 4 }, { 4, 3 }, { 5, 5 } }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call findMaxPoints(arr, N); return 0;}// This code is contributed by subhammahato348 |
Java
// Java program for the above approachimport java.io.*;class GFG { // Initialize INF as infinity static int INF = Integer.MAX_VALUE; // Function to return the point having // maximum X and Y coordinates static int[] findMaxPoint( int arr[][], int i, int n) { // Base Case if (i == n) return new int[] { INF, INF }; // Stores if valid point exists boolean flag = true; // If point arr[i] is valid for (int j = 0; j < n; j++) { // Check for the same point if (j == i) continue; // Check for a valid point if (arr[j][0] >= arr[i][0] || arr[j][1] >= arr[i][1]) { flag = false; break; } } // If current point is the // required point if (flag) return arr[i]; // Otherwise return findMaxPoint(arr, i + 1, n); } // Function to find the required point static void findMaxPoints(int arr[][], int n) { // Stores the point with maximum // X and Y-coordinates int ans[] = findMaxPoint(arr, 0, n); // If no required point exists if (ans[0] == INF) { System.out.println(-1); } else { System.out.println( "(" + ans[0] + " " + ans[1] + ")"); } } // Driver Code public static void main(String[] args) { // Given array of points int arr[][] = new int[][] {{ 1, 2 }, { 2, 1 }, { 3, 4 }, { 4, 3 }, { 5, 5 }}; int N = arr.length; // Function Call findMaxPoints(arr, N); }} |
Python3
# Python3 program for the above approachimport sys# Initialize INF as infinityINF = sys.maxsize;# Function to return the point having# maximum X and Y coordinatesdef findMaxPoint(arr, i, n): # Base Case if (i == n): return [INF, INF] # Stores if valid point exists flag = True; # If point arr[i] is valid for j in range(n): # Check for the same point if (j == i): continue; # Check for a valid point if (arr[j][0] >= arr[i][0] or arr[j][1] >= arr[i][1]): flag = False; break; # If current point is the # required point if (flag): return arr[i]; # Otherwise return findMaxPoint(arr, i + 1, n);# Function to find the required pointdef findMaxPoints(arr, n): # Stores the point with maximum # X and Y-coordinates ans = findMaxPoint(arr, 0, n); # If no required point exists if (ans[0] == INF): print(-1); else: print("(" , ans[0] , " " , ans[1] , ")");# Driver Codeif __name__ == '__main__': # Given array of points arr = [[1, 2], [2, 1], [3, 4], [4, 3], [5, 5]]; N = len(arr); # Function Call findMaxPoints(arr, N);# This code is contributed by shikhasingrajput |
C#
// C# program for the above approachusing System;class GFG{// Initialize INF as infinitystatic int INF = int.MaxValue;// Function to return the point having// maximum X and Y coordinatesstatic int[] findMaxPoint(int [,]arr, int i, int n){ // Base Case if (i == n) return new int[]{INF, INF}; // Stores if valid point exists bool flag = true; // If point arr[i] is valid for(int j = 0; j < n; j++) { // Check for the same point if (j == i) continue; // Check for a valid point if (arr[j, 0] >= arr[i, 0] || arr[j, 1] >= arr[i, 1]) { flag = false; break; } } // If current point is the // required point int []ans = new int[arr.GetLength(1)]; if (flag) { for(int k = 0; k < ans.GetLength(0); k++) ans[k] = arr[i, k]; return ans; } // Otherwise return findMaxPoint(arr, i + 1, n);}// Function to find the required pointstatic void findMaxPoints(int [,]arr, int n){ // Stores the point with maximum // X and Y-coordinates int []ans = findMaxPoint(arr, 0, n); // If no required point exists if (ans[0] == INF) { Console.WriteLine(-1); } else { Console.WriteLine("(" + ans[0] + " " + ans[1] + ")"); }}// Driver Codepublic static void Main(String[] args){ // Given array of points int [,]arr = new int[,]{ { 1, 2 }, { 2, 1 }, { 3, 4 }, { 4, 3 }, { 5, 5 } }; int N = arr.GetLength(0); // Function Call findMaxPoints(arr, N);}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approach// Initialize INF as infinitylet INF = Number.MAX_VALUE;// Function to return the point having// maximum X and Y coordinatesfunction findMaxPoint(arr, i, n){ // Base Case if (i == n) return [INF, INF]; // Stores if valid point exists let flag = true; // If point arr[i] is valid for(let j = 0; j < n; j++) { // Check for the same point if (j == i) continue; // Check for a valid point if (arr[j][0] >= arr[i][0] || arr[j][1] >= arr[i][1]) { flag = false; break; } } // If current point is the // required point if (flag) return arr[i]; // Otherwise return findMaxPoint(arr, i + 1, n);}// Function to find the required pointfunction findMaxPoints(arr, n){ // Stores the point with maximum // X and Y-coordinates let ans = findMaxPoint(arr, 0, n); // If no required point exists if (ans[0] == INF) { document.write(-1); } else { document.write("(" + ans[0] + " " + ans[1] + ")"); }}// Driver code// Given array of pointslet arr = [ [ 1, 2 ], [ 2, 1 ], [ 3, 4 ], [ 4, 3 ], [ 5, 5 ] ];let N = arr.length;// Function CallfindMaxPoints(arr, N);// This code is contributed by splevel62</script> |
Output:
(5 5)
Time Complexity: O(N2) where N is the length of the given array.
Auxiliary Space: O(N)
Efficient Approach: The idea is to find the maximum X and Y coordinates. Let them be maxX and maxY. Again traverse the given array checking if the point (maxX, maxY) is present. Follow the below steps to solve the problem:
- Traverse the given array arr[] and find the maximum X and Y coordinates. Let them be maxX and maxY.
- Again traverse the array arr[] from i = 0 to N-1 checking if (arr[i].X, arr[i].Y) is equals to (maxX, maxY).
- If the (maxX, maxY) is present in the array arr[], print (maxX, maxY) else print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define N 5#define P 2// Function to find the point having// max X and Y coordinatesvoid findMaxPoint(int arr[N][P]){ // Initialize maxX and maxY int maxX = INT_MIN; int maxY = INT_MIN; // Length of the given array int n = N; // Get maximum X & Y coordinates for(int i = 0; i < n; i++) { maxX = max(maxX, arr[i][0]); maxY = max(maxY, arr[i][1]); } // Check if the required point // i.e., (maxX, maxY) is present for(int i = 0; i < n; i++) { // If point with maximum X and // Y coordinates is present if (maxX == arr[i][0] && maxY == arr[i][1]) { cout << "(" << maxX << ", " << maxY << ")"; return; } } // If no such point exists cout << (-1);}// Driver Codeint main(){ // Given array of points int arr[N][P] = { { 1, 2 }, { 2, 1 }, { 3, 4 }, { 4, 3 }, { 5, 5 } }; // Print answer findMaxPoint(arr);}// This code is contributed by 29AjayKumar |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find the point having // max X and Y coordinates static void findMaxPoint(int arr[][]) { // Initialize maxX and maxY int maxX = Integer.MIN_VALUE; int maxY = Integer.MIN_VALUE; // Length of the given array int n = arr.length; // Get maximum X & Y coordinates for (int i = 0; i < n; i++) { maxX = Math.max(maxX, arr[i][0]); maxY = Math.max(maxY, arr[i][1]); } // Check if the required point // i.e., (maxX, maxY) is present for (int i = 0; i < n; i++) { // If point with maximum X and // Y coordinates is present if (maxX == arr[i][0] && maxY == arr[i][1]) { System.out.println( "(" + maxX + ", " + maxY + ")"); return; } } // If no such point exists System.out.println(-1); } // Driver Code public static void main(String[] args) { // Given array of points int arr[][] = new int[][] {{ 1, 2 }, { 2, 1 }, { 3, 4 }, { 4, 3 }, { 5, 5 }}; // Print answer findMaxPoint(arr); }} |
Python3
# Python3 program for the above approachimport sys;# Function to find the pohaving# max X and Y coordinatesdef findMaxPoint(arr): # Initialize maxX and maxY maxX = -sys.maxsize; maxY = -sys.maxsize; # Length of the given array n = len(arr); # Get maximum X & Y coordinates for i in range(n): maxX = max(maxX, arr[i][0]); maxY = max(maxY, arr[i][1]); # Check if the required point # i.e., (maxX, maxY) is present for i in range(n): # If powith maximum X and # Y coordinates is present if (maxX == arr[i][0] and maxY == arr[i][1]): print("(" , maxX , ", " , maxY , ")"); return; # If no such poexists print(-1);# Driver Codeif __name__ == '__main__': # Given array of points arr = [[1, 2], [2, 1], [3, 4], [4, 3], [5, 5]]; # Print answer findMaxPoint(arr);# This code is contributed by gauravrajput1 |
C#
// C# program for the above approachusing System;class GFG{// Function to find the point having// max X and Y coordinatesstatic void findMaxPoint(int [,]arr){ // Initialize maxX and maxY int maxX = int.MinValue; int maxY = int.MinValue; // Length of the given array int n = arr.GetLength(0); // Get maximum X & Y coordinates for(int i = 0; i < n; i++) { maxX = Math.Max(maxX, arr[i, 0]); maxY = Math.Max(maxY, arr[i, 1]); } // Check if the required point // i.e., (maxX, maxY) is present for(int i = 0; i < n; i++) { // If point with maximum X and // Y coordinates is present if (maxX == arr[i, 0] && maxY == arr[i, 1]) { Console.WriteLine("(" + maxX + ", " + maxY + ")"); return; } } // If no such point exists Console.WriteLine(-1);}// Driver Codepublic static void Main(String[] args){ // Given array of points int [,]arr = new int[,]{ { 1, 2 }, { 2, 1 }, { 3, 4 }, { 4, 3 }, { 5, 5 } }; // Print answer findMaxPoint(arr);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program for the above approach// Function to find the pohaving// max X and Y coordinatesfunction findMaxPoint(arr){ // Initialize maxX and maxY let maxX = Number.MIN_VALUE; let maxY = Number.MIN_VALUE; // Length of the given array let n = arr.length; // Get maximum X & Y coordinates for(let i=0;i<n;i++){ maxX = Math.max(maxX, arr[i][0]); maxY = Math.max(maxY, arr[i][1]); } // Check if the required point // i.e., (maxX, maxY) is present for(let i=0;i<n;i++){ // If powith maximum X and // Y coordinates is present if (maxX == arr[i][0] && maxY == arr[i][1]){ document.write("(" , maxX , ", " , maxY , ")"); return; } } // If no such poexists document.write(-1);}// Driver Code // Given array of pointslet arr = [[1, 2], [2, 1], [3, 4], [4, 3], [5, 5]];// PranswerfindMaxPoint(arr);// This code is contributed by shinjanpatra </script> |
Output:
(5, 5)
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
