Find All Sub-Square Of Size K

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
21 upvotes
Asked in companies
AmdocsQ2

Problem statement

You are given two integers ‘N’ and ‘K’, also provided with a ‘N x N’ square matrix ‘ARR’.

Your task is to print the sum of all sub-squares of size ‘K x K’ where ‘K’ is smaller than or equal to ‘N’.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.

The first line of each test case contains two positive integers, ‘N’ and ‘K’ denoting the number of rows in the square matrix ‘ARR’ and the number of rows in the square sub-matrix respectively.

For each test case, the next ‘N’ lines contain N numbers each denoting the elements of the matrix ‘ARR’.
Output Format: 
For each test case return a 2D array that stores ‘N - K’ arrays each containing ‘N - K’ elements, where the number in the ith array at the jth position denotes the sum of the sub-matrix whose left corner is at index [i, j].

The output of each test case will be printed in a separate line.
Constraints: 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 500
1 <= ‘K’ <= ‘N’
1 <= ‘ARR[i][j]’ <= 1000

Where ‘ARR[i][j]’ denotes the matrix element at the jth column in the ith row


Time Limit: 1 sec
Sample Input 1:
1
3 2
8 1 3
2 9 3
0 3 5
Sample Output 1:
20 16
14 20
Explanation for sample input 1:
There can be a total of 4 sub-matrix of size 2x2:
First, starting at index [0,0]:
8 1
2 9
So the sum of this matrix will be (8+1+2+9) = 20.
Second, starting at index [0,1]:
1 3
9 3
So the sum of this matrix will be (1+3+9+3) =16.
Third, starting at index [1,0]:
2 9
0 3
So the sum of this matrix will be (2+9+0+3) = 14
Fourth, starting at index [1,1]:
9 3
3 5
So the sum of this matrix will be (9+3+3+5) = 20.
So we will return 2D array of size 2*2 with values as calculated above.
Sample Input 2:
1
2 2
5 7
8 1
Sample Output 2:
21
Explanation for sample input 2:
Only 1 sub-matrix is possible starting from index [0, 0] sum of which is 21.
Hint

Try to find a brute force approach.

Approaches (2)
Brute Force Approach
  • We need to traverse the matrix, look for every KxK submatrix, find its sum and print it in the appropriate position.
  • Keep a 2D vector ANS which will store our answer such that the value at [0, 0] will be the sum of the sub-matrix with top-left corner at [0, 0].
  • Suppose we have a matrix with infinite rows and columns. If we are standing at index [i, j] then one of the sub-matrix has top-left corner at [i, j] and bottom-right corner at [i+k, j+k] index. Similarly the next sub-matrix has top-left corner at [i, j+1] and bottom-right corner at [i+k, j+k+1] index. Therefore we can go to every top-left possible corner starting from [0, 0] to [N-K, N-K] and find the sum for each sub-matrix.
  • The operations look like this:
    • Traverse the matrix, suppose we are at the ith row and jth column.
    • A sub-matrix is possible with this index as top-left corner only if i+K < N and j+K < N. If it is a possible sub-matrix, then run 2 nested loops to find the sum of elements from row i, i+K and column j, j+K.
    • Store this sum in ANS[i][j].
    • Continue this process.
  • Return ANS.
Time Complexity

O(N^2*K^2), where N and K is the number of rows in the square matrix ARR and the number of rows in the required square sub-matrix respectively.


We are traversing all the possible top-left corners in the initial matrix. There are (N-K)*(N-K) such corners and for each corner, we again run 2 nested loops to find the sum of this specific sub-matrix the time complexity of which is K*K. Therefore the net time Complexity is O((N-K)*(N-K)*K*K) = O(N^2*K^2).

Space Complexity

O(1)

 

As we use constant extra space.

Code Solution
(100% EXP penalty)
Find All Sub-Square Of Size K
Full screen
Console