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

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... ganga4518 debanjan321 ganga4518