Maximal Square Problem


Description

LeetCode Problem 221.

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:

1
2
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:

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

Example 3:

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

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int maxSquare = 0;
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        
        int l;
        int maxL = 0;
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (matrix[i-1][j-1] == '1') {
                    l = min(dp[i-1][j], dp[i][j-1]);
                    if (matrix[i-l-1][j-l-1] == '1')
                        dp[i][j] = l + 1;
                    else
                        dp[i][j] = l;
                    maxL = max(maxL, dp[i][j]);
                }
                //cout << dp[i][j] << " ";
            }
            cout << endl;
        }
        return maxL*maxL;
    }
};




Related Posts

Palindromic Substrings Problem

LeetCode 647. Given a string s, return the number of...

Largest Plus Sign Problem

LeetCode 764. You are given an integer n. You have...

K Inverse Pairs Array Problem

LeetCode 629. For an integer array nums, an inverse pair...

Domino And Tromino Tiling Problem

LeetCode 790. You have two types of tiles, a 2...

Decode Ways II Problem

LeetCode 639. A message containing letters from A-Z can be...