Hard problems

221. Maximal Square

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 maxsize
area = check(i,j,size)
if area==0:
break
maxsize = max(maxsize, check(i,j,size))
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
for array sum(j,i)= sum(0,i)-sum(0,j). So that make a sum matrix, from (0,0) to current point sum[i][j]. . the sum from the left up to the bottom right position sum[i][j]-sum[i][y-1]-sum[x-1][j]+sum[x-1][y-1]
find the dp function to compute the sums
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 0
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
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
use different dp, dp[i][j] means the max size can achieve at (x,y) as bottom right location, if it is 0, then 0, if it is y, min(case1,case2,case3)+1
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

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 maxsize
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 0
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+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
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

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 maxsize
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 maxsize

188. Best Time to Buy and Sell Stock IV

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)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store