Tuesday, July 7, 2015

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
Have you met this question in a real interview? 
Yes

Example
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

public class Solution {
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
    public int maxSquare(int[][] matrix) {
        // write your code here
        int m = matrix.length, n = matrix[0].length;
        int res = 0;
        int[][] t = new int[m][n];
        for(int i = 0; i < m; i++){
            if(matrix[i][0] == 1){
                 t[i][0] = 1;
                 res = 1;
            }
        }
        
         for(int i = 0; i < n; i++){
            if(matrix[0][i] == 1){
                 t[0][i] = 1;
                 res = 1;
            }
        }
        
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == 1){
                    t[i][j] = Math.min(t[i-1][j], Math.min(t[i][j-1], t[i-1][j-1])) + 1;
                    res = Math.max(t[i][j], res);
                }
            }
        }
        return res * res;
    }
}

No comments:

Post a Comment