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

• 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``````

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

``````1101
1101
1111``````

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

• I just added some more test cases. Try again?

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