221. Maximal Square

https://leetcode.com/problems/maximal-square/

Problem

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Solution

class Solution {
public:
    int maximalSquare(vector<vector<char>> &matrix) {
        if (matrix.empty()) return 0;
        int area = 0;
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                area = max(area, search(matrix, i, j));
            }
        }
        return area;
    }
    inline int search(vector<vector<char>> &matrix, const int row, const int col) {
        int len = 0;
        while (row + len < matrix.size() && col + len < matrix[0].size()) {
            for (int i = 0; i <= len; ++i) {
                if (matrix[row + len][col + i] == '0' || matrix[row + i][col + len] == '0') return len * len;
            }
            ++len;
        }
        return len * len;
    }
};