# Merge sort, beat 100% python submissions

• class Solution(object):
def findMaxArea(self, a, l, r, k):
if l >= r: return -2**31

``````    m = (l+r)/2
res = max(self.findMaxArea(a, l, m, k), self.findMaxArea(a, m+1, r, k))

i = l
for j in range(m+1, r+1):
while i <= m and a[j] - a[i] > k: i += 1
if i > m: break
if res < a[j] - a[i]: res = a[j] - a[i]

tmp = [0]*(r-l+1)
i = l
j = m+1
t = 0

while i <= m and j <= r:
if a[i] <= a[j]:
tmp[t] = a[i]
i += 1
t += 1
else:
tmp[t] = a[j]
t += 1
j += 1

while i <= m:
tmp[t] = a[i]
t += 1
i += 1

while j <= r:
tmp[t] = a[j]
t += 1
j += 1

for i in range(len(tmp)): a[l+i] = tmp[i]

return res

def maxSumSubmatrix(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
if len(matrix) == 0 or len(matrix[0]) == 0: return 0
m = len(matrix)
n = len(matrix[0])
if m > n:
m, n = n, m
a = [[0]*n for i in range(m)]

for i in range(m):
for j in range(n):
a[i][j] = matrix[j][i]

else:
a = [[0]*n for i in range(m)]
for i in range(m):
for j in range(n):
a[i][j] = matrix[i][j]

res = -2**31
for i in range(m):
h = [0] * n
for j in range(i, m):
sum = [0] * (n+1)

low = 0
maxArea = -2**31

for t in range(n):
h[t] += a[j][t]
sum[t+1] = sum[t] + h[t]

maxArea = max(maxArea, sum[t+1]-low)
low = min(low, sum[t+1])

if maxArea <= res: continue

if maxArea == k: return k
if maxArea > k: maxArea = self.findMaxArea(sum, 0, n, k)

res = max(res, maxArea)

return res``````

• Nice answer. Still O(min^2 * max * log(max)) complexity but the constant is smaller (about a half).

I rewrote your Python code as a more concise version:

``````class Solution(object):
def maxSumSubmatrix(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
m, n = len(matrix), len(matrix[0])
M, N = min(m,n), max(m,n)
ans = None
def findMaxArea(sums, beg, end):
if beg + 1 >= end: return None
mid = beg + ((end - beg)>>1)
res = max(findMaxArea(sums, beg, mid), findMaxArea(sums, mid, end))
i = mid
for l in sums[beg:mid]:
while i < len(sums) and sums[i] - l <= k:
res = max(res, sums[i] - l)
i += 1
sums[beg:end] = sorted(sums[beg:end])
return res

for i1 in xrange(M):
tmp = [0]*N
for i2 in xrange(i1, M):
sums, low, maxArea = [0], 0, None
for j in xrange(N):
tmp[j] += matrix[i2][j] if m <= n else matrix[j][i2]
sums.append(sums[-1] + tmp[j])
maxArea = max(maxArea, sums[-1] - low)
low = min(low, sums[-1])
if maxArea <= ans: continue
if maxArea == k: return k
if maxArea > k: maxArea = findMaxArea(sums, 0, N+1)
ans = max(ans, maxArea)
return ans or 0
``````

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