Problem

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

Example

Input ::
[
 [1,1,0,1],
 [1,1,0,1],
 [1,1,1,1]
]
Output :: 4.

JavaScript Code

function maximalSquare(matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
        return 0;
    
    var m = matrix.length;
    var n = matrix[0].length;
 
    var t = [];
    
    for (var i = 0; i < m; i++) {
        var temp = [];
        for (var j = 0; j < n; j++) {
            temp.push(0);
        }
        t.push(temp);
    }
    
    //left column
    for (var i = 0; i < m; i++) {
        t[i][0] = matrix[i][0];
    }
 
    //top row
    for (var j = 0; j < n; j++) {
        t[0][j] = matrix[0][j];
    }
 
    //cells inside
    for(var i = 1; i < m; i++) {
        for (var j = 1; j < n; j++) {
            if (matrix[i][j] == '1') {
                var min = Math.min(t[i - 1][j], t[i - 1][j - 1]);
                min = Math.min(min,t[i][j - 1]);
                t[i][j] = min + 1;
            } else {
                t[i][j] = 0;
            }
        }
    }
 
    var max = 0;
    //get maximal length
    for (var i = 0; i < m; i++) {
        for (var j = 0; j < n; j++) {
            if (t[i][j] > max) {
                max = t[i][j];
            }
        }
    }
    return max * max;
}

0 comments:

Blogroll

Follow this blog by Email

Popular Posts