Max Sum Matrix

Moderate
0/80
profile
Contributed by
3 upvotes
Asked in companies
UberD.E.Shaw

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}.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 2
1 1
1 1
1 1
1 1
25
3 3
3 3 3
3 1 3
3 3 3
2
Sample Output 1 :
2
1
Explanation For Sample Input 1 :
In the first test case, val is high enough, so we can take a square of the maximum side, which is 2.
Hence the answer is 2.

In the second test case, val is 2, hence the only square matrix having the sum of value less than 2 is {{1}}, having side equal to 1.
Hence the answer is 1.
Sample Input 2 :
2
1 5
1 4 2 3 4
100
6 4
1 8 7 3
4 2 9 7
1 2 7 1
88 5 4 11
4 2 6 2
8 45 66 5
11
Sample Output 2 :
1
2
Hint

Create a 2D prefix sum array, and check for every square matrix whether the sum is less than “val” or not.

Approaches (2)
Prefix Sum

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”.
Time Complexity

O( M * N * min(M*N) ), where M, N are the dimensions of the matrix.

 

As we are checking all the square matrices.

Hence the time complexity is O( M * N * min(M*N) ).

Space Complexity

O( M * N ), where M, N are the dimensions of the matrix.

 

As we are using a 2D array to store the prefix sum

Hence the space complexity is O( M * N ).

Code Solution
(100% EXP penalty)
Max Sum Matrix
Full screen
Console