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


  • 0
    Y

    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!


  • 0

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


Log in to reply
 

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