Dada una array N x M donde N es el número de filas y M es el número de columnas en la array dada y un número entero K . La tarea es encontrar la longitud máxima de una subarray cuadrada que tiene la suma de elementos menor o igual a K o imprimir 0 si no existe tal cuadrado.
Ejemplos:
Input: r = 4, c = 4 , k = 6
matrix[][] = { {1, 1, 1, 1},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0},
}
Output: 3
Explanation:
Square from (0,0) to (2,2) with
sum 5 is one of the valid answer.
Input: r = 4, c = 4 , k = 1
matrix[][] = { {2, 2, 2},
{2, 2, 2},
{2, 2, 2},
{2, 2, 2},
}
Output: 0
Explanation:
There is no valid answer.
Enfoque:
La idea es calcular la array de suma de prefijos. Una vez que se calcula la array de la suma del prefijo, la suma de la subarray requerida se puede calcular en una complejidad de tiempo O(1). Utilice la técnica de ventana deslizante para calcular la subarray cuadrada de longitud máxima. Para cada cuadrado de longitud cur_max+1 , donde cur_max es la longitud máxima encontrada actualmente de una subarray cuadrada, verificamos si la suma de elementos en la subarray actual, que tiene la longitud de cur_max+1 , es menor o igual a K o no. En caso afirmativo, aumente el resultado en 1; de lo contrario, continuamos verificando.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <iostream>
using namespace std;
// Function to return maximum
// length of square submatrix
// having sum of elements at-most K
int maxLengthSquare(int row, int column,
int arr[][4], int k)
{
// Matrix to store prefix sum
int sum[row + 1][column + 1] ;
for(int i = 1; i <= row; i++)
for(int j = 0; j <= column; j++)
sum[i][j] = 0;
// Current maximum length
int cur_max = 1;
// Variable for storing
// maximum length of square
int max = 0;
for (int i = 1; i <= row; i++)
{
for (int j = 1; j <= column; j++)
{
// Calculating prefix sum
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] +
arr[i - 1][j - 1] - sum[i - 1][j - 1];
// Checking whether there
// exits square with length
// cur_max+1 or not
if(i >= cur_max && j >= cur_max &&
sum[i][j] - sum[i - cur_max][j]
- sum[i][j - cur_max] +
sum[i - cur_max][j - cur_max] <= k)
{
max = cur_max++;
}
}
}
// Returning the
// maximum length
return max;
}
// Driver code
int main()
{
int row = 4, column = 4;
int matrix[4][4] = { {1, 1, 1, 1},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0}
};
int k = 6;
int ans = maxLengthSquare(row, column, matrix, k);
cout << ans;
return 0;
}
// This code is contributed by AnkitRai01
Java
// Java implementation of
// the above approach
import java.util.*;
class GFG
{
// Function to return maximum
// length of square submatrix
// having sum of elements at-most K
public static int maxLengthSquare(int row,int column,
int[][] arr, int k)
{
// Matrix to store prefix sum
int sum[][] = new int[row + 1][column + 1];
// Current maximum length
int cur_max = 1;
// Variable for storing
// maximum length of square
int max = 0;
for (int i = 1; i <= row; i++)
{
for (int j = 1; j <= column; j++)
{
// Calculating prefix sum
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] +
arr[i - 1][j - 1] - sum[i - 1][j - 1];
// Checking whether there
// exits square with length
// cur_max+1 or not
if(i >=cur_max&&j>=cur_max&&sum[i][j]-sum[i - cur_max][j]
- sum[i][j - cur_max]
+ sum[i - cur_max][j - cur_max] <= k){
max = cur_max++;
}
}
}
// Returning the
// maximum length
return max;
}
// Driver code
public static void main(String args[])
{
int row = 4 , column = 4;
int matrix[][] = { {1, 1, 1, 1},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0}
};
int k = 6;
int ans = maxLengthSquare(row,column,matrix, k);
System.out.println(ans);
}
}
Python3
# Python3 implementation of the above approach import numpy as np # Function to return maximum # length of square submatrix # having sum of elements at-most K def maxLengthSquare(row, column, arr, k) : # Matrix to store prefix sum sum = np.zeros((row + 1, column + 1)); # Current maximum length cur_max = 1; # Variable for storing # maximum length of square max = 0; for i in range(1, row + 1) : for j in range(1, column + 1) : # Calculating prefix sum sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + \ arr[i - 1][j - 1] - \ sum[i - 1][j - 1]; # Checking whether there # exits square with length # cur_max+1 or not if(i >= cur_max and j >= cur_max and sum[i][j] - sum[i - cur_max][j] - sum[i][j - cur_max] + sum[i - cur_max][j - cur_max] <= k) : max = cur_max; cur_max += 1; # Returning the maximum length return max; # Driver code if __name__ == "__main__" : row = 4 ; column = 4; matrix = [[1, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]; k = 6; ans = maxLengthSquare(row, column, matrix, k); print(ans); # This code is contributed by AnkitRai01
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to return maximum
// length of square submatrix
// having sum of elements at-most K
public static int maxLengthSquare(int row,int column,
int[,] arr, int k)
{
// Matrix to store prefix sum
int [,]sum = new int[row + 1,column + 1];
// Current maximum length
int cur_max = 1;
// Variable for storing
// maximum length of square
int max = 0;
for (int i = 1; i <= row; i++)
{
for (int j = 1; j <= column; j++)
{
// Calculating prefix sum
sum[i, j] = sum[i - 1, j] + sum[i, j - 1] +
arr[i - 1, j - 1] - sum[i - 1, j - 1];
// Checking whether there
// exits square with length
// cur_max+1 or not
if(i >=cur_max && j>=cur_max && sum[i, j]-sum[i - cur_max, j]
- sum[i, j - cur_max]
+ sum[i - cur_max, j - cur_max] <= k)
{
max = cur_max++;
}
}
}
// Returning the
// maximum length
return max;
}
// Driver code
public static void Main()
{
int row = 4 , column = 4;
int [,]matrix = { {1, 1, 1, 1},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0}
};
int k = 6;
int ans = maxLengthSquare(row, column, matrix, k);
Console.WriteLine(ans);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the above approach
// Function to return maximum
// length of square submatrix
// having sum of elements at-most K
function maxLengthSquare(row, column, arr, k) {
// Matrix to store prefix sum
let sum = new Array();[row + 1][column + 1];
for (let i = 0; i < row + 1; i++) {
let temp = new Array();
for (let j = 0; j < column + 1; j++) {
temp.push([])
}
sum.push(temp)
}
for (let i = 1; i <= row; i++)
for (let j = 0; j <= column; j++)
sum[i][j] = 0;
// Current maximum length
let cur_max = 1;
// Variable for storing
// maximum length of square
let max = 0;
for (let i = 1; i <= row; i++) {
for (let j = 1; j <= column; j++) {
// Calculating prefix sum
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] +
arr[i - 1][j - 1] - sum[i - 1][j - 1];
// Checking whether there
// exits square with length
// cur_max+1 or not
if (i >= cur_max && j >= cur_max &&
sum[i][j] - sum[i - cur_max][j]
- sum[i][j - cur_max] +
sum[i - cur_max][j - cur_max] <= k) {
max = cur_max++;
}
}
}
// Returning the
// maximum length
return max;
}
// Driver code
let row = 4, column = 4;
let matrix = [[1, 1, 1, 1],
[1, 0, 0, 0],
[1, 0, 0, 0],
[1, 0, 0, 0]
];
let k = 6;
let ans = maxLengthSquare(row, column, matrix, k);
document.write(ans);
// This code is contributed by gfgking
</script>
Producción:
3
Complejidad temporal: O(N x M)
Publicación traducida automáticamente
Artículo escrito por ishan_trivedi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA