Question

Formatted question description: https://leetcode.ca/all/221.html

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example 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

Example 2:

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

Example 3:

Input: matrix = [["0"]]
Output: 0

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] is '0' or '1'.

Algorithm

The brute force method, mechanism of this method is to treat each point in the array as the left vertex of a square and scan to the bottom right to find the largest square.

But, there is better solution.

After establishing the cumulative sum array, we start to traverse every position of the two-dimensional array. For any position (i, j), we traverse all squares from that position to (0,0), the number of squares is min(i,j)+1,

Because of the cumulative sum matrix, we can quickly find the sum of any area, so we can quickly get the sum of all sub-squares,

Compare whether the sum of the square is equal to the square of the side length. The equality means that the numbers in the square are all 1. Then update the result.

Code

public class Solution_better_dp {
    public int maximalSquare(char[][] matrix) {

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int cols = rows > 0 ? matrix[0].length : 0;
        int[] dp = new int[cols + 1];

        int maxsqlen = 0;
        int 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;
    }
}

public class Maximal_Square {

    // Time complexity : O(mn). Single pass.
    // Space complexity : O(mn). Another matrix of same size is used for dp.
    public class Solution_dp {
        public int maximalSquare(char[][] matrix) {

            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }

            int rows = matrix.length;
            int cols = rows > 0 ? matrix[0].length : 0;

            // dp(i,j) represents the side length of the maximum square
            // whose bottom right corner is the cell with index (i,j) in the original matrix.
            int[][] dp = new int[rows + 1][cols + 1];

            int maxsqlen = 0;
            for (int i = 1; i <= rows; i++) {
                for (int j = 1; j <= cols; j++) {
                    if (matrix[i - 1][j - 1] == '1') {

                        dp[i][j] = 1 + Math.min(
                            Math.min(dp[i][j - 1], dp[i - 1][j]),
                            dp[i - 1][j - 1]);

                        maxsqlen = Math.max(maxsqlen, dp[i][j]);
                    }
                }
            }

            return maxsqlen * maxsqlen;
        }
    }

    class Solution {
        public int maximalSquare(char[][] matrix) {

            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }

            int result = 0; // worst case, one single pixel

            int row = matrix.length;
            int col = matrix[0].length;

            // largest possible square is fitting the min edge
            int step = Math.min(row, col) - 1; // -1 for index

            // O(): step * (row * col) * (row * col) => (row * col) ^ 2
            while (step >= 0) { // if step==0, then check this very single pixel

                for (int i = 0; i + step < row; i++) {
                    for (int j = 0; j + step < col; j++) {

                        // now check if all 1s for sqaure [i, j] - [i+step, j+step]
                        if (isValidSquare(matrix, i, j, step)) {
                            return (step + 1) * (step + 1); // @note: step is 1 less than actual square edge length
                        }
                    }
                }

                step--;
            }

            return result;
        }

        private boolean isValidSquare(char[][] matrix, int startI, int startJ, int step) {

            for (int i = startI; i <= startI + step; i++) {
                for (int j = startJ; j <= startJ + step; j++) {
                    if (matrix[i][j] != '1') {
                        return false;
                    }
                }
            }

            return true;
        }
    }

}

############

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        int mx = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
                    mx = Math.max(mx, dp[i + 1][j + 1]);
                }
            }
        }
        return mx * mx;
    }
}

// OJ: https://leetcode.com/problems/maximal-square/
// Time: O((MN)^2)
// Space: O(1)
class Solution {
public:
    int maximalSquare(vector<vector<char>>& A) {
        if (A.empty() || A[0].empty()) return 0;
        int M = A.size(), N = A[0].size(), ans = 0;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                int k = 0;
                bool stop = false;
                for (; i + k < M && j + k < N; ++k) {
                    for (int t = 0; t < k + 1 && !stop; ++t) {
                        if (A[i + t][j + k] == '0') stop = true;
                    }
                    for (int t = 0; t < k + 1 && !stop; ++t) {
                        if (A[i + k][j + t] == '0') stop = true;
                    }
                    if (stop) break;
                }
                ans = max(ans, k);
            }
        }
        return ans * ans;
    }
};

'''
eg. a 10*10 sqaure with full of 1s
    this square move 1 line down
    this square move 1 line right

    so there needs an extra single 1 at bottom right, to make it a larger full square
'''
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        mx = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    dp[i + 1][j + 1] = 1 + min(dp[i][j + 1], dp[i + 1][j], dp[i][j]) 
                    mx = max(mx, dp[i + 1][j + 1])
        return mx * mx

############

class Solution(object):
  def maximalSquare(self, matrix):
    """
    :type matrix: List[List[str]]
    :rtype: int
    """
    if len(matrix) == 0:
      return 0
    dp = [[0] * len(matrix[0]) for i in range(0, len(matrix))]
    ans = 0
    for i in range(0, len(matrix)):
      for j in range(0, len(matrix[0])):
        if matrix[i][j] == "1":
          if i == 0:
            dp[i][j] = 1
          elif j == 0:
            dp[i][j] = 1
          else:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
          ans = max(ans, dp[i][j])
    return ans * ans

func maximalSquare(matrix [][]byte) int {
	m, n := len(matrix), len(matrix[0])
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}
	mx := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == '1' {
				dp[i+1][j+1] = min(min(dp[i][j+1], dp[i+1][j]), dp[i][j]) + 1
				mx = max(mx, dp[i+1][j+1])
			}
		}
	}
	return mx * mx
}

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

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

﻿public class Solution {
    public int MaximalSquare(char[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        var dp = new int[m + 1, n + 1];
        int mx = 0;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (matrix[i][j] == '1')
                {
                    dp[i + 1, j + 1] = Math.Min(Math.Min(dp[i, j + 1], dp[i + 1, j]), dp[i, j]) + 1;
                    mx = Math.Max(mx, dp[i + 1, j + 1]);
                }
            }
        }
        return mx * mx;
    }
}

221 - Maximal Square

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions