sourcecode

Wednesday, December 5, 2012

Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
class Solution {
    vector<vector<char> >* v;
    int getArea(int const cornerRow, int const cornerCol){
        int maxArea = 0;
        int maxX = (*v)[0].size();
        for(int row = cornerRow; row < v->size(); ++row){
            if ((*v)[row][cornerCol] == '0') break;
            for(int x = cornerCol; x < maxX; ++x){
                if ((*v)[row][x] == '0'){
                    maxX = x;
                    break;
                }
            }
            int area = (maxX-cornerCol) * (row-cornerRow+1);
            if (maxArea <area) maxArea = area;
        }
        return maxArea;        
    }
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (matrix.empty() || matrix[0].empty()) return 0;
        v = &matrix;
        int max = 0;
        for(int row = 0; row < matrix.size(); ++row)
            for(int col = 0; col < matrix[0].size(); ++col){
                int area = getArea(row,col);
                if (max < area) max = area;
            }
        return max;
    }
};

No comments: