Publicado el 18 de enero
5
3
3
3
2
Guía para Principiantes ‘Cuadrado Mágico Más Grande’ – LeetCode 1895 (C++, Python, JavaScript)
#programming#cpp#javascript#python
Buscar patrones en una cuadrícula es un desafío clásico en el pensamiento algorítmico. En este problema, se nos pide encontrar la subcuadrícula más grande posible donde cada fila, columna y ambas diagonales principales sumen exactamente el mismo valor.
Te dan:
- Una cuadrícula de números enteros.
- Una definición de Cuadrado Mágico: una subcuadrícula donde la suma de cada fila, cada columna y ambas diagonales son iguales.
Tu objetivo:
- Encontrar y devolver la longitud máxima del lado de cualquier cuadrado mágico oculto en la cuadrícula.
Ejemplo 1:
Entrada: grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
Salida: 3
Explicación: El cuadrado mágico más grande tiene un tamaño de 3.
La suma de cada fila, columna y diagonal de este cuadrado mágico es igual a 12.
- Sumas de filas: 5+1+6 = 5+4+3 = 2+7+3 = 12
- Sumas de columnas: 5+5+2 = 1+4+7 = 6+3+3 = 12
- Sumas de diagonales: 5+4+3 = 6+4+2 = 12
Ejemplo 2:
Entrada: grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
Salida: 2
Restricciones:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 50
- 1 <= grid[i][j] <= 10^6
Intuición
El enfoque de fuerza bruta sería verificar cada cuadrado posible de cada tamaño y sumar manualmente sus filas, columnas y diagonales. Sin embargo, eso implica mucho trabajo repetido. Para hacer esto eficiente, utilizamos una técnica llamada Sumas de Prefijos.
Piensa en una suma de prefijo como un “total acumulado”. Si conoces la suma total de una fila desde el inicio hasta el índice 10, y la suma total hasta el índice 5, puedes encontrar la suma de los elementos entre 5 y 10 instantáneamente restando los dos totales.
En esta solución, precalculamos cuatro tipos de totales acumulados para cada celda:
- Horizontal: Suma de elementos en esa fila.
- Vertical: Suma de elementos en esa columna.
- Diagonal Principal: Suma de elementos moviéndose de arriba a la izquierda a abajo a la derecha.
- Antidiagonal: Suma de elementos moviéndose de arriba a la derecha a abajo a la izquierda.
Una vez que tenemos estas tablas, verificar si un cuadrado es “mágico” se convierte en una cuestión de resta simple en lugar de iterar a través de cada celda. Comenzamos buscando desde la longitud de lado más grande posible (el mínimo de m y n) y trabajamos hacia abajo. El primero que satisface la condición de cuadrado mágico es nuestra respuesta.
Bloques de Código
C++
class Solution {
public:
bool isMagic(vector<vector<arra```cpp
bool isMagic(vector<vector<array<int,4>>> const & prefixSum, int r, int c, int sz) {
// Calcular la suma de la diagonal principal
int targetSum = prefixSum[r+sz][c+sz][2] - prefixSum[r][c][2];
// Verificar la suma de la anti-diagonal
if (targetSum != prefixSum[r+sz][c+1][3] - prefixSum[r][c+sz+1][3]) {
return false;
}
// Verificar todas las sumas de filas dentro del cuadrado
for (int j = r; j < r + sz; j++) {
if (targetSum != prefixSum[j+1][c+sz][0] - prefixSum[j+1][c][0]) {
return false;
}
}
// Verificar todas las sumas de columnas dentro del cuadrado
for (int j = c; j < c + sz; j++) {
if (targetSum != prefixSum[r+sz][j+1][1] - prefixSum[r][j+1][1]) {
return false;
}
}
return true;
}
int largestMagicSquare(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
// prefixSum almacena: sumas de [fila, columna, diagonal, anti-diagonal]
vector<vector<array<int,4>>> prefixSum(m + 1, vector<array<int,4>>(n + 2));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int val = grid[i-1][j-1];
prefixSum[i][j][0] = prefixSum[i][j-1][0] + val; // Fila
prefixSum[i][j][1] = prefixSum[i-1][j][1] + val; // Columna
prefixSum[i][j][2] = prefixSum[i-1][j-1][2] + val; // Diagonal
prefixSum[i][j][3] = prefixSum[i-1][j+1][3] + val; // Anti-Diagonal
}
}
for (int k = min(m, n); k >= 2; k--) {
for (int i = 0; i <= m - k; i++) {
for (int j = 0; j <= n - k; j++) {
if (isMagic(prefixSum, i, j, k)) return k;
}
}
}
return 1;
}
Python
class Solution:
def largestMagicSquare(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
# prefixSum[i][j] almacena [fila, columna, diagonal, anti_diagonal]
# Agregamos relleno para manejar condiciones de límite fácilmente
pref = [[[0] * 4 for _ in range(n + 2)] for _ in range(m + 1)]
for r in range(1, m + 1):
for c in range(1, n + 1):
val = grid[r-1][c-1]
pref[r][c][0] = pref[r][c-1][0] + val
pref[r][c][1] = pref[r-1][c][1] + val
pref[r][c][2] = pref[r-1][c-1][2] + val
pref[r][c][3] = pref[r-1][c+1][3] + val
def is_magic(r, c, k):
# Suma objetivo de la diagonal principal
target = pref[r+k][c+k][2] - pref[r][c][2]
# Verificar anti-diagonal
if target != pref[r+k][c+1][3] - pref[r][c+k+1][3]:
return False
# Verificar todas las filas
for i in range(r, r + k):
if pref[i+1][c+k][0] - pref[i+1][c][0] != target:
return False
# Verificar todas las columnas
for j in range(c, c + k):
if pref[r+k][j+1][1] - pref[r][j+1][1] != target:
return False
return True
# Verificar desde la longitud de lado más grande hacia abajo
for k in range(min(m, n), 1, -1):
for i in range(m - k + 1):
for j in range(n - k + 1):
if is_magic(i, j, k):
return k
return 1
JavaScript
/**
* @param {number[][]} grid
* @return {number}
*/
var largestMagicSquare = function(grid) {
const m = grid.length;
const n = grid[0].length;
// Crear matriz de suma de prefijos 3D: [m+1][n+2][4]
const pref = Array.from({ length: m + 1 }, () =>
Array.from({ length: n + 2 }, () => new Int32Array(4))
);
for (let r = 1; r <= m; r++) {
for (let c = 1; c <= n; c++) {
const val = grid[r-1][c-1];
pref[r][c][0] = pref[r][c-1][0] + val; // Fila
pref[r][c][1] = pref[r-1][c][1] + val; // Columna
pref[r][c][2] = pref[r-1][c-1][2] + val; // Diagonal
pref[r][c][3] = pref[r-1][c+1][3] + val; // Anti-Diagonal
}
}
const isMagic = (r, c, k) => {
const target = pref[r+k][c+k][2] - pref[r][c][2];
if (target !== pref[r+k][c+1][3] - pref[r][c+k+1][3]) return false;
for (let i = r; i < r + k; i++) {
if (pref[i+1][c+k][0] - pref[i+1][c][0] !== target) return false;
}
for (let j = c; j < c + k; j++) {
if (pref[r+k][j+1][1] - pref[r][j+1][1] !== target) return false;
}
return true;
};
for (let k = Math.min(m, n); k >= 2; k--) {
for (let i = 0; i <= m - k; i++) {
for (let j = 0; j <= n - k; j++) {
if (isMagic(i, j, k)) return k;
}
}
}
return 1;
};
Puntos Clave
- Sumas de Prefijos en 2D: Esta técnica es muy poderosa para consultas de suma de rangos en cuadrículas, reduciendo la complejidad de tiempo de verificar un subcuadrado a O(1) para cada fila o columna.
- Intercambio Espacio-Tiempo: Al usar memoria adicional para almacenar nuestras tablas de
prefixSum, aceleramos significativamente el proceso de validación para cada cuadrado potencial. - Optimización Codiciosa: Buscar desde el tamaño más grande posible hasta 2 nos permite devolver la respuesta inmediatamente al encontrar una coincidencia, ahorrando cálculos innecesarios.
Reflexiones Finales
Como mentor, a menudo veo que los estudiantes luchan con problemas de cuadrículas porque intentan “contar” todo manualmente. Aprender a usar sumas de prefijos es como mejorar tu visión en desarrollo de juegos o procesamiento de datos: dejas de ver píxeles individuales y comienzas a ver regiones. Este problema es una excelente práctica para entrevistas en empresas como Google o Amazon, donde la manipulación de matrices multidimensionales y la optimización se prueban frecuentemente. En el mundo real, estos conceptos son la base para filtros de procesamiento de imágenes y análisis de datos espaciales.
Publicado originalmente en dev.to