Anything wrong with my algorithm? stucked at test case 56/58


  • 0
    P

    Basic idea: scan each row top-down and store in buf the consecutive 1s at colunm j (the height). Then scan buf again to find consecutive 1s in each row (store in region), and calculate the currentMax based on min of buf value within that region. Update currentMax by scanning likewise for each row.

    Test is passed for most cases but ouput 110 at 56th test case (100*100 matrix), however the result is 114. Anybody can see any fault of my code?? Thanks!

    class Solution:
        # @param matrix, a list of lists of 1 length string
        # @return an integer
        def maximalRectangle(self, matrix):
            nRows = len(matrix)
            if not nRows:
                return 0
            nCols = len(matrix[0])
            currentMax = 0
            if not nCols:
                return 0
            buf = [0] * nCols   # build as buf
            for i in range(nRows):
                for j in range(nCols):
                    if matrix[i][j] != '0':
                        buf[j] += 1
                    else:
                        buf[j] = 0
                currentMax = self.calcMax(buf, currentMax)
            return currentMax
    
        def calcMax(self, buf, currentMax):
            region = []
            for x in buf:
                if x != 0:
                    region.append(x)
                else:
                    region, currentMax = self.calRegionMax(region, currentMax)
            # do not forget the last row case
            # print region
            region, currentMax = self.calRegionMax(region,currentMax)
            return currentMax
    
        def calRegionMax(self, region, currentMax):
            while region:
                currentMax = max(len(region)*min(region), currentMax)
                if region[0] < region[-1]:
                    region = region[1:]
                elif region[0] > region[-1]:
                    region.pop()
                else:
                    # compare nearest element thru middle point
                    i = 0
                    j = len(region)-1
                    while i<=j:
                        if region[i] > region[j]:
                            region = region[:-1]
                            break
                        elif region[i] < region[j]:
                            region = region[1:]
                            break
                        else:
                            i += 1
                            j -= 1
                    if i>j :region = region[1:] # break tie
            return region, currentMax

  • 0

    Please try resubmit your code again, I have added new test cases to help you debug.

    For the following test case, the answer is 6, but your code returns 4.

    1101
    1101
    1111

  • 0
    P

    thank you very much! I modified my code solving above problem, but still cannot pass it. I have updated my code as above


  • 0

    I just added some more test cases. Try again?


Log in to reply
 

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