<221> Maximal Square

Posted on Edited on In Views:

Description

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

Leetcode link: 221. Maximal Square

Quick Sum-up:

  • Input: a 2D array
  • Output: a number indicating the number of 1 in the largest square

Idea

For each cell in the matrix, if its value is 1, try expanding a square from top left to down right until a 0 is encountered. A 2D array is used for recording the maximal length of the expanded square at each cell. The speed of expanding square can be increased by using the 2D array record, since the initial length used for expanding a square is the maximum of records of top cell and left cell minus 1. => Pass, 3ms

Test cases

Input Expected Output
board=[] 0
board=[[]] 0
board=[["1"]] 1
board=[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]		 4
board=[
["0","1","1","0","0"],
["1","1","1","1","1"],
["1","1","1","1","1"],
["1","0","1","1","1"]
]		 9

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// Java
class Solution {
    private int height;
    private int width;
    private int[][] record;
    private int maxLen = 0;
    private char[][] mat;
    
    private int expandRegion(int x, int y, int size) {
        int endX = x + size;
        int endY = y + size;
        
        while (true) {
            if (endX >= width || endY >= height)
                break;
            
            for (int j = y; j <= endY; j++)
                if (mat[j][endX] == '0')
                    return size;
            
            for (int i = x; i <= endX; i++)
                if (mat[endY][i] == '0')
                    return size;
                
            size++;
            endX++;
            endY++;
        }
        
        return size;
    }
    
    private int findSquare(int x, int y) {
        int lastLen = 1;
        if (x == 0 && y == 0) {
            lastLen = 1;
        } else if (x == 0) {
            lastLen = record[y-1][x];
        } else if (y == 0) {
            lastLen = record[y][x-1];
        } else {
            lastLen = record[y-1][x] > record[y][x-1] ? record[y-1][x] : record[y][x-1];
        }

        lastLen = lastLen > 1 ? lastLen - 1 : 1;
        record[y][x] = expandRegion(x, y, lastLen);
        
        return record[y][x];
    }
    
    public int maximalSquare(char[][] matrix) {
        height = matrix.length;
        if (height == 0)
            return 0;
        
        width = matrix[0].length;
        if (width == 0)
            return 0;
        
        mat = matrix;
        
        // initialize record
        record = new int[height][width];
        for (int j = 0; j < height; j++)
            for (int i = 0; i < width; i++)
                record[j][i] = 0;
        
        for (int j = 0; j < height; j++) {
            for (int i = 0; i < width; i++) {
                if (matrix[j][i] == '1') {
                    int squareLen = findSquare(i, j);
                    if (squareLen > maxLen)
                        maxLen = squareLen;
                }
            }
        }
        
        return maxLen * maxLen;
    }
}