Can someone tell me what is wrong with my solution?


  • 0
    S

    I just re-write this solution: https://leetcode.com/discuss/20240/share-my-dp-solution

    However I got WA on the following example:

    Input:
    ["1111111111111101001111111100111011111111","1111011011111111101101111101111111111111","0111101011111101101101101111111111111111","0101101011111111111101111111010110111111","1111111111110111110110010111111111111111","1111111110110101111111111101011111101111","0110110101110011111111111111110111110101","0111111111111100111111100110011011010101","1111011110111111111011011011110101101011","1111111110111111111101101101110111101111","1110110011111111111100111111111111111111","1011111110111101111001110111111111111111","0110111111111111101111110111011111011111","1111111111111111011111111111110111111011","1111100111111110101100111111111111101111","1111101111111110111111011111111111011111","1111101111111111111111011001111110011111","1111110111111111011111111111110111110111","1011111111111111010111110010111110111111","1111110011111111111110111111111111111011","1111111111111111110111011111011111011011","1100011011111111111111011111011111111111","1111101011111111111101100101110011111111","1110010111111111111011011110111101111101","1111111111111101101111111111101111111111","1111111011111101111011111111111110111111","1110011111111110111011111111110111110111","1111111111111100111111010111111111110111","1111111111111111111111000111111111011101","1111110111111111111111111101100111011011","1111011011111101101101111110111111101111","1111111111011111111111111111111111111111","1111111111111111111111111111111111111111","1100011111111110111111111111101111111011","1111101111111101111010111111111111111111","0111111111110011111111110101011011111111","1011011111101111111111101111111111110011","1010111111111111111111111111111110011111","0111101111011111111111111111110111111111","0111111011111111011101111011101111111111","0111111111110101111011111101011001111011","1111111111111011110111111101111111101110","1111101111111100111111111110111111001111","1101101111110101111101111111100111010100","0110111111100111110010111110111011011101"]
    Output: 96 Expected: 114

    This is the Java solution:

    public int maximalRectangle(char[][] matrix) {
            int res = 0;
            if(matrix.length == 0)
                return 0;
            if(matrix[0].length == 0)
                return 0;
            res = 0;
            int rows = matrix.length;
            int cols = matrix[0].length;
            int[] height = new int[cols];
            int[] left = new int[cols];
            int[] right = new int[cols];
            for(int i = 0; i < cols; i++){
                right[i] = cols;
            }
            for(int i = 0; i < rows; i++){
                int currLeft = 0;
                int currRight = cols;
                //compute height
                for(int j = 0; j< cols; j++){
                    if(matrix[i][j] == '1')
                        height[j]++;
                    else
                        height[j] = 0;
                }
                //compute left vector
                for(int j = 0; j < cols; j++){
                    if(matrix[i][j] == '1')
                        left[j] = Math.max(left[j], currLeft);
                    else
                        currLeft = j+1;
                }
                //compute right vector
                for(int j = cols-1; j >= 0; j--){
                    if(matrix[i][j] == '1')
                        right[j] = Math.min(right[j], currRight);
                    else{
                        currRight = j;
                        right[j] = cols;
                    }    
                }
                //compute area
                for(int j = 0; j < cols; j++){
                    res = Math.max(res, (right[j]-left[j])*height[j]);
                }
            }
             return res;
    }

Log in to reply
 

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