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()
            for i in xrange(len(nums)):
                # find the lower bound of the index
                # find max in sum[right]-sum[left]<=k
                if 0<=idx<len(cumset):
                # using insort instead of append since bisect_left reason
            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
            # 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 
                while right<col:
                    # count one row
                    for i in xrange(row):
                    # find the max in this row
            return res

Log in to reply

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