Python O(n^4) solution


  • 1

    Convert the problem to 1-D and them find max subarray no larger than K.

    class Solution(object):
        def maxSumSubmatrix(self, matrix, k):
            maxSum = -9999999
            horizontalSum = [[0 for j in xrange(0, len(matrix[0]) + 1)] for i in xrange(0, len(matrix))]
            for i in xrange(0, len(matrix)):
                for j in xrange(0, len(matrix[0])):
                    horizontalSum[i][j] = horizontalSum[i][j - 1] + matrix[i][j]
            for cola in xrange(0, len(matrix[0])):
                for colb in xrange(cola, len(matrix[0])):
                    bilist, vsum = [0], 0
                    for i in xrange(0, len(matrix)):
                        vsumj = horizontalSum[i][colb] - horizontalSum[i][cola - 1]
                        vsum += vsumj
                        i = bisect.bisect_left(bilist, vsum - k)
                        if i < len(bilist):
                            maxSum = max(maxSum, vsum - bilist[i])
                        bisect.insort(bilist, vsum)
            return maxSum

  • 0

    (Edit: This was about the title, which has now been fixed)

    That's not O(logn*n^3) but only O(n^4). I guess you think insort is O(log n)?


  • 0

    yes. Insort takes o(n). Did you solve this by pyrhon? I am really excited to ser your implementation.


  • 1

    No, I didn't try it in Python, because of the lack of an appropriate data structure and because I had previously noticed that my O(n^4) C++ solution was faster than O(n^3 logn) C++ solutions. The latter apparently have a much larger hidden constant due to the advanced data structure being more complicated. So I suspect that if I implement an O(log n) data structure in Python, it would be much slower. I'd love to see an accepted O(n^3 logn) Python solution, though, which is why I was excited to see your post but then disappointed when I opened it :-P


  • 0

    My previous O(n^4) Python solution cannot pass which just calls the interface implemented in Range Sum 2D.


  • 0

    Ok, I did write my own implementation now.


  • 0

    Yeah, I just implemented a "Range Sum 2D"-style solution in Python as well, and it's a lot slower. Like 160 times slower for the largest matrix. Not surprising, of course, as we're getting a factor O(n) from our own non-simple Python code instead of the O(n) from bisect.insort, which uses list.insert for it, which is probably dead-simple efficient C.


  • 0
    S

    thank you to discuss this. looking forward another real O(n^3*log n) python solution.


  • 0
    S

    Why are these O(n^4), aka O(n^2m^2) (I guess), python solution accepted when the naive O(n^2m^2) solution using a 2-D prefix sum matrix fail? Is it just a matter of making that matrix taking extra time?


  • 0

    @samk522 Probably because all four factors in your prefix sum complexity come from Python code while one of the four factors in the above solution comes from super basic C code.


Log in to reply
 

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