Easy understand python AC solution with clear comments


  • 1

    The idea comes from the C++ or Java solution posted on discuss, I just rewrite the idea with python.

    • using two pointers to scan the column, Space is O(col)
    • left and right both start from the 0, and move right first when it reaches the end then move left
    • record the sum of the value and find the max sum less than k
    • the following code can also be used to solve Max Sum of Sub-Matrix, only need to replace the maxSubArraylessK with Kadane's algorithm
     def maxSubArraylessK(self,nums,k):
            """
            we need to find the sum[right]-sum[left]<=k
            since the bitsect return the index of the sorted value
            we can't directly pop the nums[idx] 
            we should use insort from the bisect
            """
            # python set() doesn't support indexing, using list instead
            # similar as the c++ or java set()
            
            cumset=[]
            cumset.append(0)
            maxsum=-1<<32
            cursum=0
            for i in xrange(len(nums)):
                cursum+=nums[i]
                # find the lower bound of the index
                idx=bisect.bisect_left(cumset,cursum-k)
                # find max in sum[right]-sum[left]<=k
                if 0<=idx<len(cumset):
                    maxsum=max(maxsum,cursum-cumset[idx])
                # using insort instead of append since bisect_left reason
                bisect.insort(cumset,cursum)
            return maxsum
        
        
        def maxSumSubmatrix(self, matrix, k):
            """
            :type matrix: List[List[int]]
            :type k: int
            :rtype: int
            """
            """
            The python solution hasn't a good time performance,
            since lack some of the datatype to do 
            I am trying to imitate the way solved in c++ or Java
            Ther related quesiton might be:
            1. #53. Maximum Subarray 
            2. Maximum Subarray sum less or equal than K
            3. maximun sum of rectangle 
            """
            if not matrix or not matrix[0]:
                return 0
            row,col=len(matrix),len(matrix[0])
            res=-(1<<32)
            # using two pointer to record the scan position
            for left in xrange(col):
                # reset mem to store the row data
                cursums=[0 for _ in xrange(row)]
                # since the rectange has area>0 
                right=left
                while right<col:
                    # count one row
                    for i in xrange(row):
                        cursums[i]+=matrix[i][right]
                    # find the max in this row
                    curarrmax=self.maxSubArraylessK(cursums,k)
                    res=max(res,curarrmax)
                    right+=1
                    
            return res
    

Log in to reply
 

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