Assuming your budget is N, you need to buy a rectangular land. Give a matrix of land prices and ask what is the largest area available for buying land. Land prices must be non-negative. (Source:https://www.careercup.com/question?id=5519438609645568)
The solution provided uses a O(n^4) solution,but can this problem be solved with BFS?If we apply BFS from every point in the matrix,can we get the correct answer?
Please provide some suggestions on how to solve this question more efficiently? Thank you for your time.
Well this can be improved to O(n3logn) time complexity. Suppose you need to solve this problem in an array instead of a matrix. You need to find the longest subarray whose sum is at most N. This can be solved with preffix sum and binary search in O(n log n).
Now, in a matrix you can iterate over all possible rank of columns. Suppose you have the submatrix composed by the columns between l and r. You can iterate over all these ranks in O(n2), get its preffix sum by overlapping all the rows, and then apply the same algorithm to solve the easier version.
It can be improved to O(n3) too, because the simpler version can be solved using two pointers in O(n)