Apr 11, 2018
Hard problems
221. Maximal Square
Solution: brute force
class Solution:
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
if len(matrix[0])==0:
return 0
row,col = len(matrix),len(matrix[0])
def check(x,y,size):
for i in range(x, x+size):
for j in range(y, y+size):
if matrix[i][j]=='0':
return 0
return size**2
maxsize = 0
for i in range(row):
for j in range(col): #start point i,j
if matrix[i][j]=='0':
continue
for size in range(1, min(row-i,col-j)+1): #decide the size of the window
maxsize = max(maxsize, check(i,j,size))
return maxsizeNow, optimize it, if size 2 not satisfied, then no need to check size 3, now the code is accepted. 868ms
area = check(i,j,size)
if area==0:
break
maxsize = max(maxsize, check(i,j,size))More optimization: use because when we check size 3, we recheck size 2 area, that is repeation. So we can only check the last col and the last row. 564ms
def check(x,y,size):
#check the last col
for i in range(x, x+size):
if matrix[i][y+size-1]=='0':
return 0
#check the last row
for j in range(y, y+size):
if matrix[x+size-1][j]=='0':
return 0
return size**2
Now to compute the sum
The time complexity of the following is O(n³)
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
if len(matrix[0])==0:
return 0
row,col = len(matrix),len(matrix[0])sums = [[0 for _ in range(col+1)] for _ in range(row+1)]
#no need to initialize row 0 and col 0, because we just need it to be 0
for i in range(1, row+1):
for j in range(1, col+1):
sums[i][j]=sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1]+[0,1][matrix[i-1][j-1]=='1']def check(x,y,size):
count = sums[x+size-1][y+size-1]-sums[x+size-1][y-1]-sums[x-1][y+size-1]+sums[x-1][y-1]
return count if count==size**2 else 0maxsize = 0
for i in range(row):
for j in range(col): #start point i,j
if matrix[i][j]=='0':
continue
for size in range(1, min(row-i,col-j)+1): #decide the size of the window
area = check(i+1,j+1,size) #the index in sums need to increase 1
if area==0:
break
maxsize = max(maxsize, area)
return maxsize
For the upper case: if we use row+1 and col+1 then we dont need to think about col 0 and row 0. This will solve the problem in O(n²)
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
if len(matrix[0])==0:
return 0
row,col = len(matrix),len(matrix[0])dp = [[0 for _ in range(col+1)] for _ in range(row+1)]
#no need to initialize row 0 and col 0, because we just need it to be 0
maxsize = 0
for i in range(1, row+1):
for j in range(1, col+1):
if matrix[i-1][j-1]=='0':
dp[i][j]=0
else:
dp[i][j]=min(dp[i-1][j],dp[i][j-1], dp[i-1][j-1])+1
maxsize=max(maxsize, dp[i][j])
return maxsize**2
85. Maximal Rectangle
64/66 with LTE
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
if len(matrix[0])==0:
return 0
row,col = len(matrix),len(matrix[0])
def check(x,y,w,h):
#check the last col
for i in range(x, x+h): #change row
if matrix[i][y+w-1]=='0':
return 0
for j in range(y, y+w): #change col
if matrix[x+h-1][j]=='0':
return 0
return w*h
maxsize = 0
for i in range(row):
for j in range(col): #start point i,j
if matrix[i][j]=='0':
continue
for h in range(1, row-i+1): #decide the size of the window
for w in range(1,col-j+1):
rslt = check(i,j,w,h)
if rslt==0: #we definitely need to break it. or else we get wrong result
break
maxsize = max(maxsize, check(i,j,w,h))
return maxsizeNow, the same as before, use the sums
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
if len(matrix[0])==0:
return 0
row,col = len(matrix),len(matrix[0])
sums = [[0 for _ in range(col+1)] for _ in range(row+1)]
#no need to initialize row 0 and col 0, because we just need it to be 0
for i in range(1, row+1):
for j in range(1, col+1):
sums[i][j]=sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1]+[0,1][matrix[i-1][j-1]=='1']
def check(x,y,w,h):
count = sums[x+h-1][y+w-1]-sums[x+h-1][y-1]-sums[x-1][y+w-1]+sums[x-1][y-1]
return count if count==w*h else 0maxsize = 0
for i in range(row):
for j in range(col): #start point i,j
if matrix[i][j]=='0':
continue
for h in range(1, row-i+1): #decide the size of the window
for w in range(1,col-j+1):
rslt = check(i+1,j+1,w,h)
if rslt==0: #we definitely need to break it. or else we get wrong result
break
maxsize = max(maxsize, rslt)
return maxsize
Still can not be AC. So we need another solution. Now use the largest rectangle in histogram.
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
if len(matrix[0])==0:
return 0
def getMaxAreaHist(heights):
if not heights:
return 0
maxsize = max(heights)stack = [-1]#the stack will only grow
for i, h in enumerate(heights):
if stack[-1]!=-1:
if h>heights[stack[-1]]:
stack.append(i)
else:
#start to kick to pop and compute the area
while stack[-1]!=-1 and h<=heights[stack[-1]]: #same or equal needs to be pop out
idx = stack.pop()
v = heights[idx]
maxsize=max(maxsize, (i-stack[-1]-1)*v)
stack.append(i)else:
stack.append(i)
#handle the left stack
while stack[-1]!=-1:
idx = stack.pop()
v = heights[idx]
maxsize=max(maxsize, (len(heights)-stack[-1]-1)*v)
return maxsize
row,col = len(matrix),len(matrix[0])
heights =[0]*col #save the maximum heights till here
maxsize = 0
for r in range(row):
for c in range(col):
if matrix[r][c]=='1':
heights[c]+=1
else:
heights[c]=0
#print(heights)
maxsize = max(maxsize, getMaxAreaHist(heights))
return maxsize
84. Largest Rectangle in Histogram
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given heights = [2,1,5,6,2,3],
return 10.
Solution: brute force. O(n²) to track the min height and width.
class Solution:
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
if not heights:
return 0
maxsize = max(heights)
for i in range(len(heights)):
minheight = heights[i]
width = 1
for j in range(i+1, len(heights)):
width+=1
minheight = min(minheight, heights[j])
maxsize = max(maxsize,minheight*width)
return maxsizeNow, try the BCR. the thought is find the maximum area that use each height as rectangle height.
[6, 7, 5, 2, 4, 5, 9, 3]
idx value stack [-1]
0 ``6 [-1, 0] #becuase the area that use 6 as height is growing
1 ``7 [-1, 0,1] #the area that use 6 and 7 as height is growing
2``5 because 5<7, the growing of 7 ends here, pop(7), the width is current-index- index of 0 -1 = 1, the area is 7*width = 7
because 5<6, the growing of 6 ends here, the width is current_index-(-1)-1=2, and the area = 2*6=12
how to deal if current number equals to previous, 6,6,6,6,6, we need to pop previous, and append current. The structure we use here is called Monotonic Stack, which will only allow the increasing elements to get in the stack, and once smaller or equal ones get in, it kicks out the previous smaller elements.
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
if not heights:
return 0
maxsize = max(heights)
stack = [-1]
#the stack will only grow
for i, h in enumerate(heights):
if stack[-1]!=-1:
if h>heights[stack[-1]]:
stack.append(i)
else:
#start to kick to pop and compute the area
while stack[-1]!=-1 and h<=heights[stack[-1]]: #same or equal needs to be pop out
idx = stack.pop()
v = heights[idx]
maxsize=max(maxsize, (i-stack[-1]-1)*v)
stack.append(i)
else:
stack.append(i)
#handle the left stack
while stack[-1]!=-1:
idx = stack.pop()
v = heights[idx]
maxsize=max(maxsize, (len(heights)-stack[-1]-1)*v)
return maxsize188. Best Time to Buy and Sell Stock IV
Solution: for this problem, at first, I try to find the difference of all the peaks and bottoms, get the different, sort them and return the first k. passed 200/211. This case gave me the wrong answers: [1,2,4,2,5,7,2,4,9,0]. k=2, my answer is 12, the right is 13
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
if not prices or len(prices)==1:
return 0
#we track the peak or bottom of the line
i,j = 0,1
diffs = []
while j<len(prices):
if prices[j]>=prices[j-1]:
j+=1
else:
#record the last peak
diffs.append(prices[j-1]-prices[i])
i=j
j=j+1
diffs.append(prices[-1]-prices[i])
diffs.sort(reverse=True)
print(diffs)
return sum(diffs[:k]) if k<=len(diffs) else sum(diffs)A different approach, save the bottoms and peaks [1,4,2,7,2,9]. Find at most k pairs that has the maximum accumulated differences.
(0,0) to build a tree, (1,4) (1,7),(1,9) another level (2,7) (2,9) …. The subproblems. However this subproblems are still pretty hard to resolve.
