Last Updated: 21 Sep, 2021

Max Sum Matrix

Moderate

Asked in companies

Solve now

Problem statement

You are given a matrix “mat” of size ‘m’ * ‘n’ and an integer “val”. You need to find the maximum length of the side of a square having sum not greater than “val”.

If there is no such square, return 0.

For Example :

m = 4, n = 3, mat = {{1, 1, 1}, {2, 1, 2}, {1, 2, 1}, {1, 1, 1}}, val = 5.

In this example, the maximum value of length of side which can be obtained is 2, Having the starting index: {0, 0} or {0, 1} or {2, 0} or {2, 1}.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains two integers ‘n’ and ‘m’ denoting the dimensions of the matrix.

The next ‘n’ lines contain ‘m’ integer where the jth integer of the ith line denotes the value at “mat[i][j]”.

The next line contains a single integer “val” denoting the maximum sum needed.

Output Format :

For each test case, print a single integer “ans” denoting the maximum side of the square.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10    
1 <= N, M <= 300
1 <= mat[i][j] <= 5000
1 <= val <= 50000

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will iterate through all the square matrices and check whether the sum of the matrix is less than “val” and return the value of the side of the matrix having the maximum length.

The steps are as follows:

Take a 2D array “PrefixSum” in which we will store the sum of all the values of all the elements in the matrix from 0, 0 to i, j.
Iterate through the loop from 0 to n-1(say iterator be i):
- Take a vector “curr” to store the prefix sum of all the elements in the current row.
- Iterate through the loop from 0 to m-1(say iterator be j):
  - Update the value of “curr[j]” = “curr[j - 1]” + “mat[i][j]”.
  - Update “prefixSum[i][j]” = “curr[j]” + “prefixSum[i-1][j]”.
Now take an integer “answer” to store the final result.
Iterate through the loop from 0 to n-1(say iterator be i):
- Iterate through the loop from 0 to m-1(say iterator be j):
  - Iterate through the loop from 1 to min(i, j) + 1(say iterator be k):
    - if the sum of elements in the square matrix (i - k, j), (i, j) is less than “val”, i.e., “prefixSum[i][j]” - “prefixSum[i - k][j]” - “prefixSum[i][j - k]” + “prefixSum[i - k][j - k]” <= “val”
      - Update “answer” = max(“answer”, ‘k’).
Return “answer”.

Solve now

02 Approach

The steps are as follows:

Take a 2D array “PrefixSum” in which we will store the sum of all the values of all the elements in the matrix from 0, 0 to i, j.
Iterate through the loop from 0 to n-1(say iterator be i):
- Take a vector “curr” to store the prefix sum of all the elements in the current row.
- Iterate through the loop from 0 to m-1(say iterator be j):
  - Update the value of “curr[j]” = “curr[j - 1]” + “mat[i][j]”.
  - Update “prefixSum[i][j]” = “curr[j]” + “prefixSum[i-1][j]”.
Now take an integer “answer” to store the final result.
Iterate through the loop from 0 to n-1(say iterator be i):
- Iterate through the loop from 0 to m-1(say iterator be j):
  - Binary search in all the square matrices of size 1 to min(i, j) +1:
    - Take an integer ‘k’ = (“left” + “right”) / 2.
    - if the sum of elements in the square matrix (i - k, j), (i, j) is less than “val”, i.e., “prefixSum[i][j]” - “prefixSum[i - k][j]” - “prefixSum[i][j - k]” + “prefixSum[i - k][j - k]” <= “val”
      - Update “answer” = max(“answer”, ‘k’).
      - Update the value of “left” = ‘k’ + 1, to search in the bigger sizes of the matrix.
    - Else Update “right” = ‘k’ + 1, to search in the smaller sizes of the matrix.
Return “answer”.

Solve now