# There's a bug in my code but it passed the OJ.

• My code in Java uses a flawed algorithm where every cell [i][j] uses the max rect information of [i+1][j] and [i][j+1] to calculate the max area. This code passed the OJ but failed to give the correct answer in the test case. The correct answer is 21 by my code gives 20.

``````11111111
11111110
11111110
11111000
01111000
``````

And here's my code,

``````public class Solution{
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int h = matrix.length, w = matrix[0].length;
int overallMax = 0;
CellInfo[][] info = new CellInfo[h + 1][w + 1];
for (int i = 0; i < h + 1; i++) {
info[i][w] = new CellInfo(0, 0, 0, 0);
}
for (int j = 0; j < w + 1; j++) {
info[h][j] = new CellInfo(0, 0, 0, 0);
}
for (int i = h - 1; i >= 0; i--) {
for (int j = w - 1; j >= 0; j--) {
if (matrix[i][j] == '0') {
info[i][j] = new CellInfo(0, 0, 0, 0);
continue;
}
int maxX = info[i][j + 1].maxX + 1;
int maxY = info[i + 1][j].maxY + 1;
int maxArea = maxX > maxY ? maxX : maxY;
int candidateX = maxX > maxY ? maxX : 1;
int candidateY = maxX > maxY ? 1 : maxY;
if (maxX < info[i + 1][j].recX) {
if (maxX * (info[i + 1][j].recY + 1) > maxArea) {
maxArea = maxX * (info[i + 1][j].recY + 1);
candidateX = maxX;
candidateY = info[i + 1][j].recY + 1;
}
} else {
if (info[i + 1][j].recX * (info[i + 1][j].recY + 1) > maxArea) {
maxArea = info[i + 1][j].recX * (info[i + 1][j].recY + 1);
candidateX = info[i + 1][j].recX;
candidateY = info[i + 1][j].recY + 1;
}
}
if (maxY < info[i][j + 1].recY) {
if (maxY * (info[i][j + 1].recX + 1) > maxArea) {
maxArea = maxY * (info[i][j + 1].recX + 1);
candidateX = info[i][j + 1].recX + 1;
candidateY = maxY;
}
} else {
if (info[i][j + 1].recY * (info[i][j + 1].recX + 1) > maxArea) {
maxArea = info[i][j + 1].recY * (info[i][j + 1].recX + 1);
candidateX = info[i][j + 1].recX + 1;
candidateY = info[i][j + 1].recY;
}
}
info[i][j] = new CellInfo(maxX, maxY, candidateX, candidateY);
overallMax = Math.max(overallMax, candidateX * candidateY);
}
}
return overallMax;
}
class CellInfo {
int maxX, maxY;
int recX, recY;
CellInfo(int a, int b, int c, int d) {
maxX = a;
maxY = b;
recX = c;
recY = d;
}
}
}
``````

It'd be great if my test case can be added to the OJ. Thanks!

• Thanks @yaitsrick. I have added the test case suggested by you and now your code should get Wrong Answer.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.