Hard
Find the Minimum Area to Cover All Ones II — Python
Full explanation · Time O(max(n, m)^2) · Space O(max(n, m)^2)
# Time: O(max(n, m)^2)
# Space: O(max(n, m)^2)
# dp
class Solution(object):
def minimumSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def count(dir1, dir2):
dp = [[0]*len(grid[0]) for _ in xrange(len(grid))]
up = [len(grid)]*len(grid[0])
down = [-1]*len(grid[0])
for i in dir1(xrange(len(grid))):
l, r, u, d = len(grid[0]), -1, len(grid), -1
for j in dir2(xrange(len(grid[0]))):
if grid[i][j]:
up[j] = min(up[j], i)
down[j] = max(down[j], i)
u = min(u, up[j])
d = max(d, down[j])
if down[j] >= 0:
l = min(l, j)
r = max(r, j)
dp[i][j] = (r-l+1)*(d-u+1) if r >= 0 else 0
return dp
def count2(is_vertical):
def get_n():
return len(grid) if not is_vertical else len(grid[0])
def get_m():
return len(grid[0]) if not is_vertical else len(grid)
def get(i, j):
return grid[i][j] if not is_vertical else grid[j][i]
left = [get_m() for _ in xrange(get_n())]
right = [-1 for _ in xrange(get_n())]
for i in xrange(get_n()):
for j in xrange(get_m()):
if get(i, j) == 0:
continue
left[i] = min(left[i], j)
right[i] = max(right[i], j)
dp = [[0]*get_n() for _ in xrange(get_n())]
for i in xrange(len(dp)):
l, r, u, d = get_m(), -1, get_n(), -1
for j in xrange(i, len(dp[0])):
if right[j] != -1:
l = min(l, left[j])
r = max(r, right[j])
u = min(u, j)
d = max(d, j)
dp[i][j] = (r-l+1)*(d-u+1) if r >= 0 else 0
return dp
up_left = count(lambda x: x, lambda x: x)
up_right = count(lambda x: x, reversed)
down_left = count(reversed, lambda x: x)
down_right = count(reversed, reversed)
horizon = count2(False)
vertical = count2(True)
result = float("inf")
for i in xrange(len(grid)-1):
for j in xrange(len(grid[0])-1):
result = min(result,
up_left[i][j]+up_right[i][j+1]+horizon[i+1][len(grid)-1],
horizon[0][i]+down_left[i+1][j]+down_right[i+1][j+1],
up_left[i][j]+down_left[i+1][j]+vertical[j+1][len(grid[0])-1],
vertical[0][j]+up_right[i][j+1]+down_right[i+1][j+1])
for i in xrange(len(grid)-2):
for j in xrange(i+1, len(grid)-1):
result = min(result, horizon[0][i]+horizon[i+1][j]+horizon[j+1][len(grid)-1])
for i in xrange(len(grid[0])-2):
for j in xrange(i+1, len(grid[0])-1):
result = min(result, vertical[0][i]+vertical[i+1][j]+vertical[j+1][len(grid[0])-1])
return result
# Time: O(n * m * log(max(n, m)) + max(n, m)^2)
# Space: O(n * m * log(max(n, m)))
# sparse table
class Solution2(object):
def minimumSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# RMQ - Sparse Table
# Template: https://github.com/kamyu104/GoogleCodeJam-Farewell-Rounds/blob/main/Round%20D/genetic_sequences2.py3
# Time: ctor: O(NlogN) * O(fn)
# query: O(fn)
# Space: O(NlogN)
class SparseTable(object):
def __init__(self, arr, fn):
self.fn = fn
self.bit_length = [0]
n = len(arr)
k = n.bit_length()-1 # log2_floor(n)
for i in xrange(k+1):
self.bit_length.extend(i+1 for _ in xrange(min(1<<i, (n+1)-len(self.bit_length))))
self.st = [[0]*n for _ in xrange(k+1)]
self.st[0] = arr[:]
for i in xrange(1, k+1): # Time: O(NlogN) * O(fn)
for j in xrange((n-(1<<i))+1):
self.st[i][j] = fn(self.st[i-1][j], self.st[i-1][j+(1<<(i-1))])
def query(self, L, R): # Time: O(fn)
i = self.bit_length[R-L+1]-1 # log2_floor(R-L+1)
return self.fn(self.st[i][L], self.st[i][R-(1<<i)+1])
def minimumArea(min_i, max_i, min_j, max_j):
min_r = min(st_min_i[min_i].query(min_j, max_j), max_i+1)
max_r = max(st_max_i[max_i].query(min_j, max_j), min_i-1)
min_c = min(st_min_j[min_j].query(min_i, max_i), max_j+1)
max_c = max(st_max_j[max_j].query(min_i, max_i), min_j-1)
return (max_r-min_r+1)*(max_c-min_c+1) if min_r <= max_i else 0
st_min_i = [None]*len(grid)
curr = [len(grid)]*len(grid[0])
for i in reversed(xrange(len(grid))):
for j in xrange(len(grid[0])):
if grid[i][j]:
curr[j] = i
st_min_i[i] = SparseTable(curr, min)
st_max_i = [None]*len(grid)
curr = [-1]*len(grid[0])
for i in xrange(len(grid)):
for j in xrange(len(grid[0])):
if grid[i][j]:
curr[j] = i
st_max_i[i] = SparseTable(curr, max)
st_min_j = [None]*len(grid[0])
curr = [len(grid[0])]*len(grid)
for j in reversed(xrange(len(grid[0]))):
for i in xrange(len(grid)):
if grid[i][j]:
curr[i] = j
st_min_j[j] = SparseTable(curr, min)
st_max_j = [None]*len(grid[0])
curr = [-1]*len(grid)
for j in xrange(len(grid[0])):
for i in xrange(len(grid)):
if grid[i][j]:
curr[i] = j
st_max_j[j] = SparseTable(curr, max)
result = float("inf")
for i in xrange(len(grid)-1):
a = minimumArea(i+1, len(grid)-1, 0, len(grid[0])-1)
for j in xrange(len(grid[0])-1):
b = minimumArea(0, i, 0, j)
c = minimumArea(0, i, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid)-1):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(len(grid[0])-1):
b = minimumArea(i+1, len(grid)-1, 0, j)
c = minimumArea(i+1, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for j in xrange(len(grid[0])-1):
a = minimumArea(0, len(grid)-1, j+1, len(grid[0])-1)
for i in xrange(len(grid)-1):
b = minimumArea(0, i, 0, j)
c = minimumArea(i+1, len(grid)-1, 0, j)
result = min(result, a+b+c)
for j in xrange(len(grid[0])-1):
a = minimumArea(0, len(grid)-1, 0, j)
for i in xrange(len(grid)-1):
b = minimumArea(0, i, j+1, len(grid[0])-1)
c = minimumArea(i+1, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid)-2):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(i+1, len(grid)-1):
b = minimumArea(i+1, j, 0, len(grid[0])-1)
c = minimumArea(j+1, len(grid)-1, 0, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid[0])-2):
a = minimumArea(0, len(grid)-1, 0, i)
for j in xrange(i+1, len(grid[0])-1):
b = minimumArea(0, len(grid)-1, i+1, j)
c = minimumArea(0, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
return result
# Time: O(n * m * log(max(n, m)) + max(n, m)^2)
# Space: O(n * m * log(max(n, m)))
# sparse table
class Solution3(object):
def minimumSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# RMQ - Sparse Table
# Template: https://github.com/kamyu104/GoogleCodeJam-Farewell-Rounds/blob/main/Round%20D/genetic_sequences2.py3
# Time: ctor: O(NlogN) * O(fn)
# query: O(fn)
# Space: O(NlogN)
class SparseTable(object):
def __init__(self, arr, fn):
self.fn = fn
self.bit_length = [0]
n = len(arr)
k = n.bit_length()-1 # log2_floor(n)
for i in xrange(k+1):
self.bit_length.extend(i+1 for _ in xrange(min(1<<i, (n+1)-len(self.bit_length))))
self.st = [[0]*n for _ in xrange(k+1)]
self.st[0] = arr[:]
for i in xrange(1, k+1): # Time: O(NlogN) * O(fn)
for j in xrange((n-(1<<i))+1):
self.st[i][j] = fn(self.st[i-1][j], self.st[i-1][j+(1<<(i-1))])
def query(self, L, R): # Time: O(fn)
i = self.bit_length[R-L+1]-1 # log2_floor(R-L+1)
return self.fn(self.st[i][L], self.st[i][R-(1<<i)+1])
def minimumArea(min_i, max_i, min_j, max_j):
min_r = min(st_min_i[min_i].query(min_j, max_j), max_i+1)
max_r = max(st_max_i[max_i].query(min_j, max_j), min_i-1)
min_c = min(st_min_j[min_j].query(min_i, max_i), max_j+1)
max_c = max(st_max_j[max_j].query(min_i, max_i), min_j-1)
return (max_r-min_r+1)*(max_c-min_c+1) if min_r <= max_i else 0
result = float("inf")
for _ in xrange(4):
st_min_i = [None]*len(grid)
curr = [len(grid)]*len(grid[0])
for i in reversed(xrange(len(grid))):
for j in xrange(len(grid[0])):
if grid[i][j]:
curr[j] = i
st_min_i[i] = SparseTable(curr, min)
st_max_i = [None]*len(grid)
curr = [-1]*len(grid[0])
for i in xrange(len(grid)):
for j in xrange(len(grid[0])):
if grid[i][j]:
curr[j] = i
st_max_i[i] = SparseTable(curr, max)
st_min_j = [None]*len(grid[0])
curr = [len(grid[0])]*len(grid)
for j in reversed(xrange(len(grid[0]))):
for i in xrange(len(grid)):
if grid[i][j]:
curr[i] = j
st_min_j[j] = SparseTable(curr, min)
st_max_j = [None]*len(grid[0])
curr = [-1]*len(grid)
for j in xrange(len(grid[0])):
for i in xrange(len(grid)):
if grid[i][j]:
curr[i] = j
st_max_j[j] = SparseTable(curr, max)
for i in xrange(len(grid)-1):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(len(grid[0])-1):
b = minimumArea(i+1, len(grid)-1, 0, j)
c = minimumArea(i+1, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid)-2):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(i+1, len(grid)-1):
b = minimumArea(i+1, j, 0, len(grid[0])-1)
c = minimumArea(j+1, len(grid)-1, 0, len(grid[0])-1)
result = min(result, a+b+c)
grid = zip(*grid[::-1])
return result
# Time: O(max(n, m)^2 * log(max(n, m)))
# Space: O(1)
# prefix sum, binary search
class Solution4(object):
def minimumSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def binary_search(left, right, check):
while left <= right:
mid = left + (right-left)//2
if check(mid):
right = mid-1
else:
left = mid+1
return left
def binary_search_right(left, right, check):
while left <= right:
mid = left + (right-left)//2
if not check(mid):
right = mid-1
else:
left = mid+1
return right
def minimumArea(min_i, max_i, min_j, max_j):
def count(x1, y1, x2, y2):
cnt = grid[x2][y2]
if x1-1 >= 0:
cnt -= grid[x1-1][y2]
if y1-1 >= 0:
cnt -= grid[x2][y1-1]
if x1-1 >= 0 and y1-1 >= 0:
cnt += grid[x1-1][y1-1]
return cnt
min_r = binary_search(min_i, max_i, lambda i: count(min_i, min_j, i, max_j))
max_r = binary_search_right(min_i, max_i, lambda i: count(i, min_j, max_i, max_j))
min_c = binary_search(min_j, max_j, lambda j: count(min_i, min_j, max_i, j))
max_c = binary_search_right(min_j, max_j, lambda j: count(min_i, j, max_i, max_j))
return (max_r-min_r+1)*(max_c-min_c+1) if min_r <= max_i else 0
for i in xrange(len(grid)):
for j in xrange(len(grid[0])):
if i-1 >= 0:
grid[i][j] += grid[i-1][j]
if j-1 >= 0:
grid[i][j] += grid[i][j-1]
if i-1 >= 0 and j-1 >= 0:
grid[i][j] -= grid[i-1][j-1]
result = float("inf")
result = float("inf")
for i in xrange(len(grid)-1):
a = minimumArea(i+1, len(grid)-1, 0, len(grid[0])-1)
for j in xrange(len(grid[0])-1):
b = minimumArea(0, i, 0, j)
c = minimumArea(0, i, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid)-1):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(len(grid[0])-1):
b = minimumArea(i+1, len(grid)-1, 0, j)
c = minimumArea(i+1, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for j in xrange(len(grid[0])-1):
a = minimumArea(0, len(grid)-1, j+1, len(grid[0])-1)
for i in xrange(len(grid)-1):
b = minimumArea(0, i, 0, j)
c = minimumArea(i+1, len(grid)-1, 0, j)
result = min(result, a+b+c)
for j in xrange(len(grid[0])-1):
a = minimumArea(0, len(grid)-1, 0, j)
for i in xrange(len(grid)-1):
b = minimumArea(0, i, j+1, len(grid[0])-1)
c = minimumArea(i+1, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid)-2):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(i+1, len(grid)-1):
b = minimumArea(i+1, j, 0, len(grid[0])-1)
c = minimumArea(j+1, len(grid)-1, 0, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid[0])-2):
a = minimumArea(0, len(grid)-1, 0, i)
for j in xrange(i+1, len(grid[0])-1):
b = minimumArea(0, len(grid)-1, i+1, j)
c = minimumArea(0, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
return result
# Time: O(max(n, m)^2 * log(max(n, m)))
# Space: O(n * m)
# prefix sum, binary search
class Solution5(object):
def minimumSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def binary_search(left, right, check):
while left <= right:
mid = left + (right-left)//2
if check(mid):
right = mid-1
else:
left = mid+1
return left
def binary_search_right(left, right, check):
while left <= right:
mid = left + (right-left)//2
if not check(mid):
right = mid-1
else:
left = mid+1
return right
def minimumArea(min_i, max_i, min_j, max_j):
def count(x1, y1, x2, y2):
cnt = prefix[x2][y2]
if x1-1 >= 0:
cnt -= prefix[x1-1][y2]
if y1-1 >= 0:
cnt -= prefix[x2][y1-1]
if x1-1 >= 0 and y1-1 >= 0:
cnt += prefix[x1-1][y1-1]
return cnt
min_r = binary_search(min_i, max_i, lambda i: count(min_i, min_j, i, max_j))
max_r = binary_search_right(min_i, max_i, lambda i: count(i, min_j, max_i, max_j))
min_c = binary_search(min_j, max_j, lambda j: count(min_i, min_j, max_i, j))
max_c = binary_search_right(min_j, max_j, lambda j: count(min_i, j, max_i, max_j))
return (max_r-min_r+1)*(max_c-min_c+1) if min_r <= max_i else 0
result = float("inf")
for _ in xrange(4):
prefix = [[0]*len(grid[0]) for _ in xrange(len(grid))]
for i in xrange(len(grid)):
for j in xrange(len(grid[0])):
prefix[i][j] = grid[i][j]
if i-1 >= 0:
prefix[i][j] += prefix[i-1][j]
if j-1 >= 0:
prefix[i][j] += prefix[i][j-1]
if i-1 >= 0 and j-1 >= 0:
prefix[i][j] -= prefix[i-1][j-1]
for i in xrange(len(grid)-1):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(len(grid[0])-1):
b = minimumArea(i+1, len(grid)-1, 0, j)
c = minimumArea(i+1, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid)-2):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(i+1, len(grid)-1):
b = minimumArea(i+1, j, 0, len(grid[0])-1)
c = minimumArea(j+1, len(grid)-1, 0, len(grid[0])-1)
result = min(result, a+b+c)
grid = zip(*grid[::-1])
return result
# Time: O((n^2 + m^2 + 4 * n * m) * n * m) = O(max(n, m)^3 * min(n, m))
# Space: O(1)
# brute force
class Solution6(object):
def minimumSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def minimumArea(min_i, max_i, min_j, max_j):
min_r, max_r, min_c, max_c = max_i+1, min_i-1, max_j+1, min_j-1
for i in xrange(min_i, max_i+1):
for j in xrange(min_j, max_j+1):
if grid[i][j] == 0:
continue
min_r, max_r, min_c, max_c = min(min_r, i), max(max_r, i), min(min_c, j), max(max_c, j)
return (max_r-min_r+1)*(max_c-min_c+1) if min_r <= max_i else 0
result = float("inf")
for i in xrange(len(grid)-1):
a = minimumArea(i+1, len(grid)-1, 0, len(grid[0])-1)
for j in xrange(len(grid[0])-1):
b = minimumArea(0, i, 0, j)
c = minimumArea(0, i, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid)-1):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(len(grid[0])-1):
b = minimumArea(i+1, len(grid)-1, 0, j)
c = minimumArea(i+1, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for j in xrange(len(grid[0])-1):
a = minimumArea(0, len(grid)-1, j+1, len(grid[0])-1)
for i in xrange(len(grid)-1):
b = minimumArea(0, i, 0, j)
c = minimumArea(i+1, len(grid)-1, 0, j)
result = min(result, a+b+c)
for j in xrange(len(grid[0])-1):
a = minimumArea(0, len(grid)-1, 0, j)
for i in xrange(len(grid)-1):
b = minimumArea(0, i, j+1, len(grid[0])-1)
c = minimumArea(i+1, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid)-2):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(i+1, len(grid)-1):
b = minimumArea(i+1, j, 0, len(grid[0])-1)
c = minimumArea(j+1, len(grid)-1, 0, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid[0])-2):
a = minimumArea(0, len(grid)-1, 0, i)
for j in xrange(i+1, len(grid[0])-1):
b = minimumArea(0, len(grid)-1, i+1, j)
c = minimumArea(0, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
return result
# Time: O((n^2 + m^2 + 4 * n * m) * n * m) = O(max(n, m)^3 * min(n, m))
# Space: O(n * m)
# brute force
class Solution7(object):
def minimumSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def minimumArea(min_i, max_i, min_j, max_j):
min_r, max_r, min_c, max_c = max_i+1, min_i-1, max_j+1, min_j-1
for i in xrange(min_i, max_i+1):
for j in xrange(min_j, max_j+1):
if grid[i][j] == 0:
continue
min_r, max_r, min_c, max_c = min(min_r, i), max(max_r, i), min(min_c, j), max(max_c, j)
return (max_r-min_r+1)*(max_c-min_c+1) if min_r <= max_i else 0
result = float("inf")
for _ in xrange(4):
for i in xrange(len(grid)-1):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(len(grid[0])-1):
b = minimumArea(i+1, len(grid)-1, 0, j)
c = minimumArea(i+1, len(grid)-1, j+1, len(grid[0])-1)
result = min(result, a+b+c)
for i in xrange(len(grid)-2):
a = minimumArea(0, i, 0, len(grid[0])-1)
for j in xrange(i+1, len(grid)-1):
b = minimumArea(i+1, j, 0, len(grid[0])-1)
c = minimumArea(j+1, len(grid)-1, 0, len(grid[0])-1)
result = min(result, a+b+c)
grid = zip(*grid[::-1])
return result