Dada una array N*M Mat[][] que contiene todos los enteros distintos, la tarea es encontrar el área mínima de la array ( r*c , donde 1 ≤ r ≤ N y 1 ≤ c ≤ M ) para cada subarray de tamaño r*c el valor máximo sigue siendo el mismo.
Ejemplos :
Entrada : N = 4, M = 4, Mat[][] = {{9, 12, 6, 11}, {3, 15, 19, 4}, {1, 13, 8, 11}, {14, 7, 9, 15}}
Salida : 3, 3
Explicación : el tamaño mínimo de la subarray es 3*3.
Todas las subarray por debajo de ese tamaño no contienen el máximo de 19.Entrada : N = 1, M = 1, Mat[][] = {{25}}
Salida : 1, 1
Enfoque : para resolver el problema, siga la siguiente idea:
Solo puede haber un elemento máximo en la array ya que todos los elementos son únicos.
Entonces todas las subarrays deben contener ese elemento.
Digamos que la posición del máximo es (i, j) .
- Si el tamaño de fila de la array es menor que (i+1) , puede haber una subarray que comience en la fila 0 que no contenga el máximo.
- Además, si tiene menos de (N – i) filas, la subarray que comienza en la última fila no contendrá el máximo.
- Entonces, el tamaño de la fila será el máximo entre (i + 1) y (N – i) .
- Del mismo modo, el tamaño de la columna será el máximo entre (j + 1) y (M – j) .
Siga los pasos mencionados a continuación para implementar la idea:
- Ejecute un bucle anidado y recorra toda la array para encontrar el elemento máximo de la array.
- Almacene la ubicación del elemento máximo.
- Usa la observación anterior para encontrar el tamaño de la subarray.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
// Find M and N for which in every N*M
// area the max element remains same
pair<int, int> findMinArea(int Mat[][MAX],
int N, int M)
{
// Initialize the variable
int r, c;
int Max = INT_MIN;
// Find position of maximum element
// from the grid
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (Mat[i][j] > Max) {
Max = Mat[i][j];
r = i;
c = j;
}
}
}
// Return minimum value of submatrix
return make_pair(max(r + 1, N - r),
max(c + 1, M - c));
}
// Driver Code
int main()
{
int N = 4, M = 4;
int Mat[][MAX] = { { 9, 12, 6, 11 },
{ 3, 15, 19, 4 },
{ 1, 13, 8, 11 },
{ 14, 7, 9, 15 } };
// Function call
pair<int, int> X = findMinArea(Mat, N, M);
cout << X.first << " " << X.second << endl;
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
class GFG {
static int MAX = 1000;
// Find M and N for which in every N*M
// area the max element remains same
public static int[] findMinArea(int Mat[][], int N,
int M)
{
// Initialize the variable
int r = 0, c = 0;
int Max = Integer.MIN_VALUE;
// Find position of maximum element
// from the grid
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (Mat[i][j] > Max) {
Max = Mat[i][j];
r = i;
c = j;
}
}
}
int ans[] = new int[2];
// Return minimum value of submatrix
ans[0] = Math.max(r + 1, N - r);
ans[1] = Math.max(c + 1, M - c);
return ans;
}
// Driver Code
public static void main(String[] args)
{
int N = 4, M = 4;
int Mat[][] = { { 9, 12, 6, 11 },
{ 3, 15, 19, 4 },
{ 1, 13, 8, 11 },
{ 14, 7, 9, 15 } };
// Function call
int X[] = findMinArea(Mat, N, M);
System.out.println(X[0] + " " + X[1]);
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python code to implement the above approach import sys MAX = 1000; # Find M and N for which in every N*M # area the max element remains same def findMinArea(Mat, N, M): # Initialize the variable r = 0; c = 0; Max = -sys.maxsize -1; # Find position of maximum element # from the grid for i in range(0,N): for j in range(0,M): if (Mat[i][j] > Max): Max = Mat[i][j]; r = i; c = j; ans = [0 for i in range(2)]; # Return minimum value of submatrix ans[0] = max(r + 1, N - r); ans[1] = max(c + 1, M - c); return ans; # Driver Code if __name__ == '__main__': N = 4; M = 4; Mat = [[ 9, 12, 6, 11 ], [ 3, 15, 19, 4 ], [ 1, 13, 8, 11 ], [ 14, 7, 9, 15 ]]; # Function call X = findMinArea(Mat, N, M); print(X[0] , " " , X[1]); # This code is contributed by shikhasingrajput
C#
// Java code to implement the above approach
using System;
public class GFG {
// Find M and N for which in every N*M
// area the max element remains same
public static int[] findMinArea(int[, ] Mat, int N,
int M)
{
// Initialize the variable
int r = 0, c = 0;
int Max = Int32.MinValue;
// Find position of maximum element
// from the grid
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (Mat[i, j] > Max) {
Max = Mat[i, j];
r = i;
c = j;
}
}
}
int[] ans = new int[2];
// Return minimum value of submatrix
ans[0] = Math.Max(r + 1, N - r);
ans[1] = Math.Max(c + 1, M - c);
return ans;
}
// Driver Code
static public void Main()
{
int N = 4, M = 4;
int[, ] Mat = new int[, ] { { 9, 12, 6, 11 },
{ 3, 15, 19, 4 },
{ 1, 13, 8, 11 },
{ 14, 7, 9, 15 } };
// Function call
int[] X = findMinArea(Mat, N, M);
Console.WriteLine(X[0] + " " + X[1]);
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
const MAX = 1000;
// Find M and N for which in every N*M
// area the max element remains same
function findMinArea(Mat, N, M)
{
// Initialize the variable
let r = 0, c = 0;
let Max = Number.MIN_VALUE;
// Find position of maximum element
// from the grid
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (Mat[i][j] > Max) {
Max = Mat[i][j];
r = i;
c = j;
}
}
}
let ans = new Array(2);
// Return minimum value of submatrix
ans[0] = Math.max(r + 1, N - r);
ans[1] = Math.max(c + 1, M - c);
return ans;
}
// Driver Code
let N = 4, M = 4;
let Mat = [ [ 9, 12, 6, 11 ],
[ 3, 15, 19, 4 ],
[ 1, 13, 8, 11 ],
[ 14, 7, 9, 15 ] ];
// Function call
let X = findMinArea(Mat, N, M);
document.write(X[0] + " " + X[1]);
// This code is contributed by shinjanpatra
</script>
Producción
3 3
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA