Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
For example, given the following matrix:
1 2 3 4
| 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
|
Return 4.
O(mn) time O(n) space DP solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| public class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; } int[] up = new int[matrix[0].length + 1]; int[] cur = new int[matrix[0].length + 1]; int size = 0; for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { if (matrix[i][j] == '1') { cur[j + 1] = Math.min(Math.min(cur[j], up[j]), up[j + 1]) + 1; size = Math.max(size, cur[j + 1]); } } up = cur; cur = new int[matrix[0].length + 1]; } return size * size; } }
|