naive solution in c++ but 6ms


  • 0
    X
    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
    		int h = matrix.size(), w = matrix[0].size();
    		
    		//vector<vector<bool>> visited(h, vector<bool>(w, false));
    		int result = 0;
    		for(int i = 0; i < h; i++){
    			for(int j = 0; j < w; j++){
    				int curr = 0;
    				if(matrix[i][j] == '1'){ //treat it as potential upper left of i
    				    curr++;
    					int row = i, col = j;
    					while(helper(matrix, row, col, i, j, h, w)){
    						row++;
    						col++;
    						curr++;
    					}
    				}
    				result = max(result, curr * curr);
    			}
    		}
    		return result;
        }
    	bool helper(vector<vector<char>>& matrix, int row, int col, int i, int j, int h, int w){
    		if((row+1 < h) && (col+1 < w) && (matrix[row+1][col+1] == '1')){
    				for(int r = i; r < row+1; r++){
    					if(matrix[r][col+1] != '1') return false;
    				}
    				for(int c = j; c < col+1; c++){
    					if(matrix[row+1][c] != '1') return false;
    				}
    				return true;
    		}
    		else return false;
    	}
    };
    

  • 0
    X

    use integral image method, should be O(n^2) but 9ms

    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
    		int h = matrix.size(), w = matrix[0].size();
    		
    		//calculate the accumulative sum 
    		vector<vector<int>> sum(h, vector<int>(w, 0));
    		for(int i = 0; i < h; i++){
    			for(int j = 0; j < w; j++){
    				int n1 = ((i>=1) && (j>=1))? sum[i-1][j-1] : 0;
    				int n2 = (i>=1)? sum[i-1][j] : 0;
    				int n3 = (j>=1)? sum[i][j-1] : 0;
    				sum[i][j] = n2 + n3 - n1 + (int)(matrix[i][j] == '1');
    			}
    		}
    		int result = 0;
    		for(int i = 0; i < h; i++){
    			for(int j = 0; j < w; j++){
    				if(matrix[i][j] == '1'){ //treat it as potential upper left of i
    					result = max(result, 1);
    					if((i+result-1 < h) && (j + result-1 < w)){
    						int n1 = ((i>=1) && (j>=1))? sum[i-1][j-1] : 0;
    						int n2 = (i>=1)? sum[i-1][j+result-1] : 0;
    						int n3 = (j>=1)? sum[i+result-1][j-1] : 0;
    						int range = sum[i+result-1][j+result-1] + n1 - n2 - n3;
    						if(range == result * result){
    							int row = i+result-1, col = j+result-1;
    							while(helper(matrix, row, col, i, j, h, w)){
    								row++;
    								col++;
    								result++;
    							}
    						}
    					}
    				}
    			}
    		}
    		return result*result;
        }
    	bool helper(vector<vector<char>>& matrix, int row, int col, int i, int j, int h, int w){
    		if((row+1 < h) && (col+1 < w) && (matrix[row+1][col+1] == '1')){
    				for(int r = i; r < row+1; r++){
    					if(matrix[r][col+1] != '1') return false;
    				}
    				for(int c = j; c < col+1; c++){
    					if(matrix[row+1][c] != '1') return false;
    				}
    				return true;
    		}
    		else return false;
    	}
    };
    

Log in to reply
 

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