Dada una array 2D arr[] que consta de N coordenadas de la forma (X, Y) , la tarea es encontrar una coordenada de la array dada tal que la coordenada X de este punto sea mayor que todas las demás coordenadas X y la La coordenada Y de este punto es mayor que todas las demás coordenadas Y. Si no existe tal punto, imprima -1 .
Ejemplos:
Entrada: arr[][] = {(1, 2), (2, 1), (3, 4), (4, 3), (5, 5)}
Salida: (5, 5)
Explicación:
El máximo La coordenada X es 5 y la coordenada Y máxima es 5.
Dado que el punto (5, 5) está presente en la array, imprima (5, 5) como la respuesta requerida.Entrada: arr[] = {(5, 3), (3, 5)}
Salida: -1
Explicación:
La coordenada X máxima es 5 y la coordenada Y máxima es 5. Dado que + (5, 5) no está presente. Por lo tanto, imprima -1.
Enfoque ingenuo: el enfoque más simple es atravesar la array y, para cada punto, verificar si son las coordenadas X e Y máximas o no. Si no existe tal punto, imprima -1 . De lo contrario, imprima el punto como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
(5 5)
Complejidad de tiempo: O(N 2 ) donde N es la longitud de la array dada.
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea es encontrar las coordenadas X e Y máximas. Sean maxX y maxY . Nuevamente recorra la array dada verificando si el punto ( maxX , maxY ) está presente. Siga los pasos a continuación para resolver el problema:
- Recorra la array dada arr[] y encuentre las coordenadas X e Y máximas . Sean maxX y maxY .
- De nuevo, recorra la array arr[] de i = 0 a N-1 comprobando si (arr[i].X, arr[i].Y) es igual a (maxX, maxY) .
- Si (maxX, maxY) está presente en la array arr[] , imprime (maxX, maxY) sino imprime -1 .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
(5, 5)
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por BIRANCHINARAYANPADHI y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA