Last Updated: 26 Nov, 2020
Find All Sub-Square Of Size K
Moderate
Asked in companies
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’.
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
Approaches
- 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.
- For the two sub-matrix, first starting at index [i, j] and second starting at [i, j+1] the only difference is that the K elements from the (j + K)th column is added and K elements from jth columns are removed. All the other K*(K-1) elements remain the same.
- But we are computing the whole sub-matrix every time, which can be optimized.
- This time lets keep a matrix PREFIX of size NxN, such that PREFIX[i][j] stores the sum of all elements having(1th indexed) rows <= i and columns <= j and a 2D matrix ANS which will store our answer.
- To have an example, PREFIX[N][N] stores the sum of all the elements in the matrix ARR. PREFIX[1][N] stores the sum of all the elements of the 1st row and PREFIX[N][1] stores the sum of all the elements of the 1st column.
- We can see that the sum of the square sub-matrix having top-corner at index [i, j] will be PREFIX[i+K, j+K] - PREFIX[i-1, j+K] - PREFIX[i+K, j] + PREFIX[i-1, j-1].
- The sequence of operations now look like this:
- Traverse every possible top-left corner using 2 nested loops. Let i denote the current row number and j denote the current column number.
- For each i and j insert the value of PREFIX[i+K, j+K] - PREFIX[i-1, j+K] - PREFIX[i+K, j] + PREFIX[i-1, j-1] in ANS[i, j].
- Continue the process.