Dadas dos arrays arr1[] y arr2[] de N que denotan N coordenadas de la forma (arr1[i], 0) y M enteros positivos que denotan M coordenadas de la forma (arr2[j], 1 ) donde 1 ≤ i ≤ N y 1≤ j ≤ METRO . La tarea es encontrar el área del rectángulo más grande que se puede formar usando estas coordenadas. Imprime 0 si no se puede formar un rectángulo.
Ejemplos:
Entrada: arr1[] = {1, 2, 4}, arr2[] = {1, 3, 4}
Salida: 3
Explicación: El rectángulo más grande posible es {(1, 0), (1, 1), (4 , 0), (4, 1)}.
Por lo tanto, área del rectángulo = largo * ancho = (4 – 1)*(1 – 0) = 3Entrada: arr1[] = {1, 3, 5}, arr2[] = {4, 2, 10}
Salida: 0
Explicación: No se puede formar ningún rectángulo. Por lo tanto, la respuesta es cero.
Enfoque ingenuo: el enfoque más simple es recorrer la array dada arr1[] y, para cada i , recorrer los puntos en arr2[] usando una variable j . Si arr1[i] es igual a arr2[j] , almacene el valor arr1[i] en una array separada, digamos ans[] . Después de encontrar todos esos valores, ordene la array ans[] e imprima el área máxima como ans[L] – ans[0] donde L es el índice del último elemento de ans[] ya que el ancho del rectángulo siempre será 1 .
Complejidad temporal: O(N*M)
Espacio auxiliar: O(M + N)
Enfoque eficiente: la idea es utilizar el algoritmo de clasificación y la técnica de dos puntos . Observa que el ancho del rectángulo siempre será 1 . Por lo tanto, el área máxima se puede encontrar maximizando su longitud. Siga los pasos a continuación para resolver el problema:
- Ordene las arrays dadas arr1[] y arr2[] .
- Inicialice las variables, comience y termine con 0 para almacenar el punto inicial y final de la longitud. Además, inicialice las variables i y j para recorrer la array arr1[] y arr2[] respectivamente.
- Si bien i es más pequeño que N y j más pequeño que M , verifique las siguientes condiciones:
- Si arr1[i] es lo mismo que arr2[j] y start es 0 , actualice start como start = arr1[i] . De lo contrario, actualice end como end = arr1[i] y luego incremente i y j en 1 .
- Si arr1[i] es mayor que arr2[j] , incremente j en 1 . De lo contrario, incremente i en 1 .
- Si inicio o final es 0 , imprima 0 . De lo contrario, imprima (fin – inicio) como el área máxima posible.
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;
// Function to find the maximum possible
// area of a rectangle
int largestArea(int arr1[], int n,
int arr2[], int m)
{
// Initialize variables
int end = 0, start = 0, i = 0, j = 0;
// Sort array arr1[]
sort(arr1, arr1 + n);
// Sort array arr2[]
sort(arr2, arr2 + m);
// Traverse arr1[] and arr2[]
while (i < n and j < m) {
// If arr1[i] is same as arr2[j]
if (arr1[i] == arr2[j]) {
// If no starting point
// is found yet
if (start == 0)
start = arr1[i];
else
// Update maximum end
end = arr1[i];
i++;
j++;
}
// If arr[i] > arr2[j]
else if (arr1[i] > arr2[j])
j++;
else
i++;
}
// If no rectangle is found
if (end == 0 or start == 0)
return 0;
else
// Return the area
return (end - start);
}
// Driver Code
int main()
{
// Given point
int arr1[] = { 1, 2, 4 };
// Given length
int N = sizeof(arr1) / sizeof(arr1[0]);
// Given points
int arr2[] = { 1, 3, 4 };
// Given length
int M = sizeof(arr2) / sizeof(arr2[0]);
// Function Call
cout << largestArea(arr1, N, arr2, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum possible
// area of a rectangle
static int largestArea(int arr1[], int n,
int arr2[], int m)
{
// Initialize variables
int end = 0, start = 0, i = 0, j = 0;
// Sort array arr1[]
Arrays.sort(arr1);
// Sort array arr2[]
Arrays.sort(arr1);
// Traverse arr1[] and arr2[]
while (i < n && j < m)
{
// If arr1[i] is same as arr2[j]
if (arr1[i] == arr2[j])
{
// If no starting point
// is found yet
if (start == 0)
start = arr1[i];
else
// Update maximum end
end = arr1[i];
i++;
j++;
}
// If arr[i] > arr2[j]
else if (arr1[i] > arr2[j])
j++;
else
i++;
}
// If no rectangle is found
if (end == 0 || start == 0)
return 0;
else
// Return the area
return (end - start);
}
// Driver Code
public static void main(String args[])
{
// Given point
int arr1[] = { 1, 2, 4 };
// Given length
int N = arr1.length;
// Given points
int arr2[] = { 1, 3, 4 };
// Given length
int M = arr2.length;
// Function Call
System.out.println(largestArea(arr1, N,
arr2, M));
}
}
// This code is contributed by bolliranadheer
Python3
# Python3 program for the above approach # Function to find the maximum possible # area of a rectangle def largestArea(arr1, n, arr2, m): # Initialize variables end = 0 start = 0 i = 0 j = 0 # Sort array arr1[] arr1.sort(reverse = False) # Sort array arr2[] arr2.sort(reverse = False) # Traverse arr1[] and arr2[] while (i < n and j < m): # If arr1[i] is same as arr2[j] if (arr1[i] == arr2[j]): # If no starting point # is found yet if (start == 0): start = arr1[i] else: # Update maximum end end = arr1[i] i += 1 j += 1 # If arr[i] > arr2[j] elif (arr1[i] > arr2[j]): j += 1 else: i += 1 # If no rectangle is found if (end == 0 or start == 0): return 0 else: # Return the area return (end - start) # Driver Code if __name__ == '__main__': # Given point arr1 = [ 1, 2, 4 ] # Given length N = len(arr1) # Given points arr2 = [ 1, 3, 4 ] # Given length M = len(arr2) # Function Call print(largestArea(arr1, N, arr2, M)) # This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum possible
// area of a rectangle
static int largestArea(int[] arr1, int n,
int[] arr2, int m)
{
// Initialize variables
int end = 0, start = 0, i = 0, j = 0;
// Sort array arr1[]
Array.Sort(arr1);
// Sort array arr2[]
Array.Sort(arr2);
// Traverse arr1[] and arr2[]
while (i < n && j < m)
{
// If arr1[i] is same as arr2[j]
if (arr1[i] == arr2[j])
{
// If no starting point
// is found yet
if (start == 0)
start = arr1[i];
else
// Update maximum end
end = arr1[i];
i++;
j++;
}
// If arr[i] > arr2[j]
else if (arr1[i] > arr2[j])
j++;
else
i++;
}
// If no rectangle is found
if (end == 0 || start == 0)
return 0;
else
// Return the area
return (end - start);
}
// Driver code
static void Main()
{
// Given point
int[] arr1 = { 1, 2, 4 };
// Given length
int N = arr1.Length;
// Given points
int[] arr2 = { 1, 3, 4 };
// Given length
int M = arr2.Length;
// Function Call
Console.WriteLine(largestArea(arr1, N,
arr2, M));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum possible
// area of a rectangle
function largestArea(arr1, n,
arr2, m)
{
// Initialize variables
var end = 0, start = 0, i = 0, j = 0;
// Sort array arr1[]
arr1.sort();
// Sort array arr2[]
arr2.sort();
// Traverse arr1[] and arr2[]
while (i < n && j < m) {
// If arr1[i] is same as arr2[j]
if (arr1[i] == arr2[j]) {
// If no starting point
// is found yet
if (start == 0)
start = arr1[i];
else
// Update maximum end
end = arr1[i];
i++;
j++;
}
// If arr[i] > arr2[j]
else if (arr1[i] > arr2[j])
j++;
else
i++;
}
// If no rectangle is found
if (end == 0 || start == 0)
return 0;
else
// Return the area
return (end - start);
}
// Driver Code
// Given point
var arr1 = [ 1, 2, 4 ];
// Given length
var N = arr1.length;
// Given points
var arr2 = [ 1, 3, 4 ];
// Given length
var M = arr2.length;
// Function Call
document.write(largestArea(arr1, N, arr2, M));
// This code is contributed by noob2000.
</script>
3
Complejidad de tiempo: O(N*log N + M*log M)
Espacio auxiliar: O(M+N)
Publicación traducida automáticamente
Artículo escrito por SaiNikhilKanchukatla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA