Subarray cuadrada más grande con fila, columna y suma diagonal iguales

Dada una array mat[][] de dimensiones N*M , la tarea es encontrar el tamaño de la subarray cuadrada más grande tal que la suma de todas las filas, columnas y diagonales en esa subarray sean iguales.

Ejemplos:

Entrada: N = 3, M = 4, mat[][] = [[5, 1, 3, 1], [9, 3, 3, 1], [1, 3, 3, 8]]
Salida: 2
Explicación:
La subarray que satisface todas las condiciones dadas se muestra en negrita
5 1 3 1
9 3 3 1
1 3 3 8
Por lo tanto, el tamaño de la subarray es 2.

Entrada: N = 4, M = 5, mat[][] = [[7, 1, 4, 5, 6], [2, 5, 1, 6, 4], [1, 5, 4, 3, 2], [1, 2, 7, 3, 4]]
Salida: 3
Explicación:
La subarray que satisface todas las condiciones dadas se muestra en negrita
7 1 4 5 6
2 5 1 6 4
1 5 4 3 2
1 2 7 3 4
Por lo tanto, el tamaño de la subarray es 3.

Enfoque: el problema dado se puede resolver encontrando la suma de prefijos de todas las filas y columnas y luego iterando para todos los tamaños posibles de la subarray cuadrada de cada celda de la array y si existe tal array cuadrada que satisfaga los criterios dados luego imprima ese tamaño de una array cuadrada. Siga los pasos a continuación para resolver el problema:

• Mantenga dos arrays de suma de prefijos prefixSumRow[] y prefixSumColumn[] y almacene la suma de prefijos de filas y columnas de la array dada, respectivamente.
• Realice los siguientes pasos para verificar si alguna array cuadrada a partir de la celda (i, j) de tamaño K cumple o no con los criterios dados:
  1. Encuentra la suma de los elementos de la diagonal primaria de la subarray mat[i][j] a mat[i + K][j + K] y guárdala en la variable, digamos sum .
  2. Si el valor de la suma es el mismo que el valor mencionado a continuación, devuelva true . De lo contrario, devuelve falso .
     • La suma del prefijo de todas las filas, es decir, el valor de prefixSumRow[k][j + K] – prefixSumRow[k][j] para todos los valores de k sobre el rango [i, i + K] .
     • La suma del prefijo de todas las columnas, es decir, el valor de prefixSumColumn[i + K][j] – prefixSumColumn[i][k] para todos los valores de k sobre el rango [j, j + K] .
     • La suma de prefijos de elementos antidiagonales.
• Ahora, itere para todos los tamaños posibles de la array cuadrada que se puede formar en el rango [min(N, M), 1] y si existe alguna posibilidad que satisfaga los criterios dados usando los pasos de arriba, luego imprima ese tamaño de una array cuadrada.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Define the prefix sum arrays globally
int prefix_sum_row[50][51];
int prefix_sum_col[51][50];
 
bool is_valid(int r, int c, int size,
              vector<vector<int> >& grid)
{
    int r_end = r + size, c_end = c + size;
 
    // Diagonal sum
    int sum = 0;
    for (int i = r, j = c; i < r_end; i++, j++) {
        sum += grid[i][j];
    }
 
    // Check each row
    for (int i = r; i < r_end; i++) {
        if (prefix_sum_row[i][c_end]
                - prefix_sum_row[i]
            != sum) {
            return false;
        }
    }
 
    // Check each column
    for (int i = c; i < c_end; i++) {
        if (prefix_sum_col[r_end][i]
                - prefix_sum_col[r][i]
            != sum) {
            return false;
        }
    }
 
    // Check anti-diagonal
    int ad_sum = 0;
    for (int i = r, j = c_end - 1; i < r_end;
         i++, j--) {
        ad_sum += grid[i][j];
    }
 
    return ad_sum == sum;
}
 
int largestSquareValidMatrix(
    vector<vector<int> >& grid)
{
    // Store the size of the given grid
    int m = grid.size(), n = grid[0].size();
 
    // Compute the prefix sum for the rows
    for (int i = 0; i < m; i++) {
        for (int j = 1; j <= n; j++) {
            prefix_sum_row[i][j]
                = prefix_sum_row[i][j - 1]
                  + grid[i][j - 1];
        }
    }
 
    // Compute the prefix sum for the columns
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < n; j++) {
            prefix_sum_col[i][j]
                = prefix_sum_col[i - 1][j]
                  + grid[i - 1][j];
        }
    }
 
    // Check for all possible square submatrix
    for (int size = min(m, n); size > 1; size--) {
        for (int i = 0; i <= m - size; i++) {
            for (int j = 0; j <= n - size; j++) {
                if (is_valid(i, j, size, grid)) {
                    return size;
                }
            }
        }
    }
 
    return 1;
}
 
// Driver Code
int main()
{
    vector<vector<int> > grid = { { 7, 1, 4, 5, 6 },
                                  { 2, 5, 1, 6, 4 },
                                  { 1, 5, 4, 3, 2 },
                                  { 1, 2, 7, 3, 4 } };
    cout << largestSquareValidMatrix(grid);
 
    return 0;
}

// Java program for the above approach
class GFG
{
   
    // Define the prefix sum arrays globally
    public static int[][] prefix_sum_row = new int[50][51];
    public static int[][] prefix_sum_col = new int[51][50];
 
    public static boolean is_valid(int r, int c, int size, int[][] grid) {
        int r_end = r + size, c_end = c + size;
 
        // Diagonal sum
        int sum = 0;
        for (int i = r, j = c; i < r_end; i++, j++) {
            sum += grid[i][j];
        }
 
        // Check each row
        for (int i = r; i < r_end; i++) {
            if (prefix_sum_row[i][c_end] - prefix_sum_row[i] != sum) {
                return false;
            }
        }
 
        // Check each column
        for (int i = c; i < c_end; i++) {
            if (prefix_sum_col[r_end][i] - prefix_sum_col[r][i] != sum) {
                return false;
            }
        }
 
        // Check anti-diagonal
        int ad_sum = 0;
        for (int i = r, j = c_end - 1; i < r_end; i++, j--) {
            ad_sum += grid[i][j];
        }
 
        return ad_sum == sum;
    }
 
    public static int largestSquareValidMatrix(int[][] grid) {
        // Store the size of the given grid
        int m = grid.length, n = grid[0].length;
 
        // Compute the prefix sum for the rows
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix_sum_row[i][j] = prefix_sum_row[i][j - 1] + grid[i][j - 1];
            }
        }
 
        // Compute the prefix sum for the columns
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                prefix_sum_col[i][j] = prefix_sum_col[i - 1][j] + grid[i - 1][j];
            }
        }
 
        // Check for all possible square submatrix
        for (int size = Math.min(m, n); size > 1; size--) {
            for (int i = 0; i <= m - size; i++) {
                for (int j = 0; j <= n - size; j++) {
                    if (is_valid(i, j, size, grid)) {
                        return size;
                    }
                }
            }
        }
 
        return 1;
    }
 
    // Driver Code
    public static void main(String args[]) {
        int[][] grid = { { 7, 1, 4, 5, 6 }, { 2, 5, 1, 6, 4 }, { 1, 5, 4, 3, 2 }, { 1, 2, 7, 3, 4 } };
        System.out.println(largestSquareValidMatrix(grid));
 
    }
 
}
 
// This code is contributed by saurabh_jaiswal.

## Python program for the above approach:
 
## Define the prefix sum arrays globally
prefix_sum_row = [[0]*51 for _ in range(50)]
prefix_sum_col = [[0]*50 for _ in range(51)]
 
def is_valid(r, c, size, grid):
     
    r_end = r + size
    c_end = c + size
 
    ## Diagonal sum
    sum = 0;
    j = c
    for i in range(r, r_end):
        sum += grid[i][j];
        j+=1
 
    ## Check each row
    for i in range(r, r_end):
        if ((prefix_sum_row[i][c_end] - prefix_sum_row[i]) != sum):
            return False
 
    ## Check each column
    for i in range(c, c_end):
        if ((prefix_sum_col[r_end][i] - prefix_sum_col[r][i]) != sum):
            return False
 
    ## Check anti-diagonal
    ad_sum = 0;
    j = c_end - 1
    for i in range(r, r_end):
        ad_sum += grid[i][j]
        j-=1
 
    return (ad_sum == sum)
 
def largestSquareValidMatrix(grid):
 
    ## Store the size of the given grid
    m = len(grid)
    n = len(grid[0])
 
    ## Compute the prefix sum for the rows
    for i in range(0, m):
        for j in range(1, n+1):
            prefix_sum_row[i][j] = prefix_sum_row[i][j - 1] + grid[i][j - 1];
     
    ## Compute the prefix sum for the columns
    for i in range(1, m+1):
        for j in range(0, n):
            prefix_sum_col[i][j] = prefix_sum_col[i - 1][j] + grid[i - 1][j]
 
 
    ## Check for all possible square submatrix
    for size in range(min(m, n), 1, -1):
        for i in range(0, m-size+1):
            for j in range(0, n-size+1):
                if (is_valid(i, j, size, grid)):
                    return size
 
    return 1
 
## Driver code
if __name__=='__main__':
 
    grid =  [   [ 7, 1, 4, 5, 6 ],
                [ 2, 5, 1, 6, 4 ],
                [ 1, 5, 4, 3, 2 ],
                [ 1, 2, 7, 3, 4 ]
            ]
             
    print(largestSquareValidMatrix(grid))
 
    # This code is contributed by subhamgoyal2014.

// C# program for the above approach
using System;
class GFG
{
   
    // Define the prefix sum arrays globally
    public static int[,] prefix_sum_row = new int[50,51];
    public static int[,] prefix_sum_col = new int[51,50];
 
    public static bool is_valid(int r, int c, int size, int[,] grid) {
        int r_end = r + size, c_end = c + size;
 
        // Diagonal sum
        int sum = 0;
        for (int i = r, j = c; i < r_end; i++, j++) {
            sum += grid[i,j];
        }
 
        // Check each row
        for (int i = r; i < r_end; i++) {
            if (prefix_sum_row[i,c_end] - prefix_sum_row[i,c] != sum) {
                return false;
            }
        }
 
        // Check each column
        for (int i = c; i < c_end; i++) {
            if (prefix_sum_col[r_end,i] - prefix_sum_col[r,i] != sum) {
                return false;
            }
        }
 
        // Check anti-diagonal
        int ad_sum = 0;
        for (int i = r, j = c_end - 1; i < r_end; i++, j--) {
            ad_sum += grid[i,j];
        }
 
        return ad_sum == sum;
    }
 
    public static int largestSquareValidMatrix(int[,] grid) {
        // Store the size of the given grid
        int m = grid.GetLength(0), n = grid.GetLength(1);
 
        // Compute the prefix sum for the rows
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix_sum_row[i,j] = prefix_sum_row[i,j - 1] + grid[i,j - 1];
            }
        }
 
        // Compute the prefix sum for the columns
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                prefix_sum_col[i,j] = prefix_sum_col[i - 1,j] + grid[i - 1,j];
            }
        }
 
        // Check for all possible square submatrix
        for (int size = Math.Min(m, n); size > 1; size--) {
            for (int i = 0; i <= m - size; i++) {
                for (int j = 0; j <= n - size; j++) {
                    if (is_valid(i, j, size, grid)) {
                        return size;
                    }
                }
            }
        }
 
        return 1;
    }
 
    // Driver Code
    public static void Main() {
        int[,] grid = { { 7, 1, 4, 5, 6 }, { 2, 5, 1, 6, 4 },
                       { 1, 5, 4, 3, 2 }, { 1, 2, 7, 3, 4 } };
        Console.WriteLine(largestSquareValidMatrix(grid));
 
    }
 
}
 
// This code is contributed by ukasp.

<script>
       // JavaScript Program to implement
       // the above approach
 
       // Define the prefix sum arrays globally
       let prefix_sum_row = new Array(50);
       for (let i = 0; i < prefix_sum_row.length; i++) {
           prefix_sum_row[i] = new Array(51).fill(0);
       }
       let prefix_sum_col = new Array(50);
       for (let i = 0; i < prefix_sum_col.length; i++) {
           prefix_sum_col[i] = new Array(51).fill(0);
       }
       function is_valid(r, c, size, grid) {
           let r_end = r + size, c_end = c + size;
 
           // Diagonal sum
           let sum = 0;
           for (let i = r, j = c; i < r_end; i++, j++) {
               sum += grid[i][j];
           }
           // Check each row
           for (let i = r; i < r_end; i++) {
               if (prefix_sum_row[i][c_end]
                   - prefix_sum_row[i]
                   != sum) {
                   return false;
               }
           }
 
           // Check each column
           for (let i = c; i < c_end; i++) {
               if (prefix_sum_col[r_end][i]
                   - prefix_sum_col[r][i]
                   != sum) {
                   return false;
               }
           }
 
           // Check anti-diagonal
           let ad_sum = 0;
           for (let i = r, j = c_end - 1; i < r_end;
               i++, j--) {
               ad_sum += grid[i][j];
           }
 
           return ad_sum == sum;
       }
 
       function largestSquareValidMatrix(grid) {
           // Store the size of the given grid
           let m = grid.length, n = grid[0].length;
 
           // Compute the prefix sum for the rows
           for (let i = 0; i < m; i++) {
               for (let j = 1; j <= n; j++) {
                   prefix_sum_row[i][j]
                       = prefix_sum_row[i][j - 1]
                       + grid[i][j - 1];
               }
           }
 
           // Compute the prefix sum for the columns
           for (let i = 1; i <= m; i++) {
               for (let j = 0; j < n; j++) {
                   prefix_sum_col[i][j]
                       = prefix_sum_col[i - 1][j]
                       + grid[i - 1][j];
               }
           }
 
           // Check for all possible square submatrix
           for (let size = Math.min(m, n); size > 1; size--) {
               for (let i = 0; i <= m - size; i++) {
                   for (let j = 0; j <= n - size; j++) {
                       if (is_valid(i, j, size, grid)) {
                           return size;
                       }
                   }
               }
           }
 
           return 1;
       }
 
       // Driver Code
 
       let grid = [[7, 1, 4, 5, 6],
       [2, 5, 1, 6, 4],
       [1, 5, 4, 3, 2],
       [1, 2, 7, 3, 4]];
       document.write(largestSquareValidMatrix(grid));
 
    // This code is contributed by Potta Lokesh
 
   </script>

3

Complejidad de tiempo: O(N*M*min(N, M) ² )
Espacio auxiliar: O(N*M)