Frequently Asked Interview Problem – Maximum Sum of Rectangle No Larger Than K

1 min read

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.  

Solution Logic 

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. 

  1. 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.
  2. 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. 
  3. 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.

What Skills Do You Need To Work At Elon…

Heyya there! SpaceX has been generating quite a buzz, and you would have surely heard of this company. But have you ever thought of...
2 min read

The Second September Starters Didn’t Disappoint!

Starters 12 put up quite a show last night, and here’s us bringing you the whole lowdown. From a stunning ranklist to an equally skillfully...
1 min read

Rising Stars | September Long Challenge

We kick-started September with the lengthy Long Challenge, and there are so many more contests coming up for you soon. The Chef kept a...
1 min read

Leave a Reply