Hi! We are back again with another blog on one of the most frequently asked questions in the interviews. Today we will be looking at the following question: Maximum Sum of Rectangle No Larger Than K.
Let’s Understand The Question
Before we get to the solution part, let’s make sure you understand the question.
Given a non-empty matrix of dimension m X n and an integer k, we have to return the maximum sum of a rectangle in the given matrix such that the sum of the rectangle is no greater than k.
Here’s an example to get a better understanding:
Input matrix : [ [ 3, 0, 2, -5 ], [ 2,-1, 4, 6] ] and the sum ( i.e., k) should be less than or equal to 10.
[ [2, -5], [4, 6] ]
As we can see from the matrix, the output will be 7.
The simplest solution would be to compute the sum for all the sub-matrices and then store them in another array. Now we compare the values stored in this array with the given integer k and get the largest one.
A better solution to the question would be by computing the presum of the array.
- For each number sum[i], we have to find a sum[j], where the sum[j]- sum[i] is less than or equal to the given integer k. Therefore sum [i] >= sum [j] – k.
- Since this is a 2D array, we can choose two rows r1 and r2 or two columns c1 and c2, in which we can implement the above logic.
- Store the prefix sums in a set, and then using binary search, we can find if there exists a sum greater than or equal to the sum [i]-k to update the answer.
Now that you have understood the basic logic of the question, watch this video where Saptarishi Mukherjee explains and solves this in detail.