# Simple Dynamic Programming Solution in O(NM)

• ``````class Matrix
{
private:

const vector<vector<char>> &mat;
const int _rows;
const int _cols;

public:

Matrix(const vector<vector<char>> &m)
: mat(m)
, _rows(m.size())
, _cols(m[0].size())
{
}

int rows() const { return _rows; }
int cols() const { return _cols; }

char get(int x, int y) const { return mat[y][x]; }

int maximal_square() const
{
int max_square = 0;

// dp[y][x] = maximal square's side length whose bottom-right corner is on (x,y)
vector<vector<int>> dp( rows(),
vector<int>(cols(), 0) );

// the base cases: for each cell on the topmost row and leftmost column,
// they can only be the bottom-right corner of a 1-sided square, if at all
for (int c = 0; c < cols(); ++c)
{
dp[0][c] = get(c, 0) == '1' ? 1 : 0;
max_square = max(max_square, dp[0][c]);
}
for (int r = 0; r < rows(); ++r)
{
dp[r][0] = get(0, r) == '1' ? 1 : 0;
max_square = max(max_square, dp[r][0]);
}

// for the rest, a cell can be the bottom-right corner of a k+1 sided square, IFF
// (a) it contains a '1',
// (b) its top, left, and top-left neighbors all contain '1's, AND
// (c) k is the minimum dp value of those neighbors
// otherwise, this cell is at best the bottom-right corner of its own 1-sided square

for (int y = 1; y < rows(); ++y)
{
for (int x = 1; x < cols(); ++x)
{
if (get(x, y) != '1')
{
dp[y][x] = 0;
}
else
{
dp[y][x] = 1;
if (get(x-1, y-1) == '1' &&
get(x-1, y)   == '1' &&
get(x, y-1)   == '1')
{
dp[y][x] += min( dp[y-1][x-1], min(
dp[y][x-1],
dp[y-1][x] ));
}

max_square = max(max_square, dp[y][x]);
}
}
}

return max_square * max_square;
}

};

class Solution {
public:

int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.size() == 0) return 0;

Matrix mat(matrix);
return mat.maximal_square();
}

};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.