221. Maximal Square

leetcode medium

#array#csharp#dynamic-programming#leetcode#math#matrix#medium#string

Task

Дана бинарная матрица размером m x n, заполненная 0 и 1. Найдите наибольший квадрат, содержащий только 1, и верните его площадь.

Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output: 4

C# solution

matched/original

public class Solution {
    public int MaximalSquare(char[][] matrix) {
        int rows = matrix.Length, cols = rows > 0 ? matrix[0].Length : 0;
        int[] dp = new int[cols + 1];
        int maxsqlen = 0, prev = 0;
        
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = Math.Min(Math.Min(dp[j - 1], prev), dp[j]) + 1;
                    maxsqlen = Math.Max(maxsqlen, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        
        return maxsqlen * maxsqlen;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaximalSquare(char[][] matrix) {
        int rows = matrix.size(), cols = rows > 0 ? matrix[0].size() : 0;
        vector<int>& dp = new int[cols + 1];
        int maxsqlen = 0, prev = 0;
        
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = min(min(dp[j - 1], prev), dp[j]) + 1;
                    maxsqlen = max(maxsqlen, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        
        return maxsqlen * maxsqlen;
    }
}

Java solution

matched/original

public class Solution {

    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
        int[] dp = new int[cols + 1];
        int maxsqlen = 0, prev = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;
                    maxsqlen = Math.max(maxsqlen, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return maxsqlen * maxsqlen;
    }
}

JavaScript solution

matched/original

var maximalSquare = function(matrix) {
    let rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
    let dp = new Array(cols + 1).fill(0);
    let maxsqlen = 0, prev = 0;
    
    for (let i = 1; i <= rows; i++) {
        for (let j = 1; j <= cols; j++) {
            let temp = dp[j];
            if (matrix[i - 1][j - 1] == '1') {
                dp[j] = Math.min(dp[j - 1], Math.min(prev, dp[j])) + 1;
                maxsqlen = Math.max(maxsqlen, dp[j]);
            } else {
                dp[j] = 0;
            }
            prev = temp;
        }
    }
    
    return maxsqlen * maxsqlen;
};

Python solution

matched/original

class Solution:
    def maximalSquare(self, matrix):
        rows = len(matrix)
        cols = len(matrix[0]) if rows > 0 else 0
        dp = [0] * (cols + 1)
        maxsqlen = 0
        prev = 0
        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                temp = dp[j]
                if matrix[i - 1][j - 1] == "1":
                    dp[j] = min(min(dp[j - 1], prev), dp[j]) + 1
                    maxsqlen = max(maxsqlen, dp[j])
                else:
                    dp[j] = 0
                prev = temp
        return maxsqlen * maxsqlen

Go solution

matched/original

func maximalSquare(matrix [][]byte) int {
    rows := len(matrix)
    cols := 0
    if rows > 0 {
        cols = len(matrix[0])
    }
    dp := make([]int, cols+1)
    maxsqlen := 0
    prev := 0
    
    for i := 1; i <= rows; i++ {
        for j := 1; j <= cols; j++ {
            temp := dp[j]
            if matrix[i-1][j-1] == '1' {
                dp[j] = min(dp[j-1], min(prev, dp[j])) + 1
                maxsqlen = max(maxsqlen, dp[j])
            } else {
                dp[j] = 0
            }
            prev = temp
        }
    }
    
    return maxsqlen * maxsqlen
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Инициализировать 1D массив dp с нулями, чтобы хранить промежуточные результаты для каждого столбца, а также переменные maxsqlen для максимальной длины квадрата и prev для предыдущего значения.

Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением.

По завершении пройти по всем строкам и столбцам, вернуть квадрат maxsqlen как площадь наибольшего квадрата.

😎