Merge sort, beat 100% python submissions


  • 1
    Q

    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

  • 0
    T

    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
    

Log in to reply
 

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