Check if a point having maximum X and Y coordinates exists or not

0 0 10 minutes read

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 infinity
int INF = INT_MAX;
 
// Function to return the point having
// maximum X and Y coordinates
int* 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 point
void 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 Code
int 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 approach
 
import 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 approach
import  sys
 
# Initialize INF as infinity
INF = sys.maxsize;
 
# Function to return the point having
# maximum X and Y coordinates
def 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 point
def 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 Code
if __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 approach
using System;
 
class GFG{
 
// Initialize INF as infinity
static int INF = int.MaxValue;
 
// 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
    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 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) 
    {
        Console.WriteLine(-1);
    }
    else
    {
        Console.WriteLine("(" + 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.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 infinity
let INF = Number.MAX_VALUE;
 
// Function to return the point having
// maximum X and Y coordinates
function 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 point
function 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 points
let arr = [ [ 1, 2 ], [ 2, 1 ],
            [ 3, 4 ], [ 4, 3 ],
            [ 5, 5 ] ];
 
let N = arr.length;
 
// Function Call
findMaxPoints(arr, N);
 
// This code is contributed by splevel62
 
</script>

Output:

(5 5)

Time Complexity: O(N²) 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 coordinates
void 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 Code
int 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 approach
 
import 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 approach
import sys;
 
# Function to find the pohaving
# max X and Y coordinates
def 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 Code
if __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 approach
using System;
 
class GFG{
 
// Function to find the point having
// max X and Y coordinates
static 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 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);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find the pohaving
// max X and Y coordinates
function 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 points
let arr = [[1, 2], [2, 1], [3, 4], [4, 3], [5, 5]];
 
//  Pranswer
findMaxPoint(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 zambiatek!