# Python O(n^4) solution

• 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``````

• (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)?

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

• 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

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

• Ok, I did write my own implementation now.

• 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.

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

• 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?

• @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.

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