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) + 1)] for i in xrange(0, len(matrix))] for i in xrange(0, len(matrix)): for j in xrange(0, len(matrix)): horizontalSum[i][j] = horizontalSum[i][j - 1] + matrix[i][j] for cola in xrange(0, len(matrix)): for colb in xrange(cola, len(matrix)): bilist, vsum = , 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.