FilesExpand file tree

 master

/

MaximalRectangle.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

42 lines (41 loc) · 1.05 KB

 master

/

MaximalRectangle.java

Top

File metadata and controls

• Code
• Blame

42 lines (41 loc) · 1.05 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle

* containing all ones and return its area.

*/

public class MaximalRectangle {

public int maximalRectangle(char[][] matrix) {

int rows = matrix.length;

if (rows == 0)

return 0;

int maxArea = 0;

int cols = matrix[0].length;

int[][] map = new int[rows][cols];

for (int j = 0; j < cols; j++) {

map[0][j] = matrix[0][j] == '0' ? 0 : 1;

}

for (int i = 1; i < rows; i++) {

for (int j = 0; j < cols; j++) {

map[i][j] = matrix[i][j] == '0' ? map[i - 1][j]

: map[i - 1][j] + 1;

}

}

int[] row = new int[cols];

for (int i = 0; i < rows; i++) {

for (int j = i; j < rows; j++) {

for (int k = 0; k < cols; k++) {

row[k] = map[j][k] - (i == 0 ? 0 : map[i - 1][k]);

}

int count = 0;

for (int k = 0; k < cols; k++) {

if (row[k] == j - i + 1) {

maxArea = Math.max(maxArea, ++count * (j - i + 1));

} else {

maxArea = Math.max(maxArea, count * (j - i + 1));

count = 0;

}

}

}

}

return maxArea;

}

}