Magic Squares In Matrix

Moderate
0/80
profile
Contributed by
2 upvotes

Problem statement

You are given a matrix ‘MAT’, of size ‘M’ * ‘N’ and has numbers from 1 to 9. Find the number of magic square submatrix present in the matrix. A submatrix is a magic square if that matrix's size is 3 * 3 and consists of distinct numbers from 1 to 9 and having the sum of all the rows, columns, and diagonals equal.

For example: 
Let matrix be : 
8 3 4
1 5 9
6 7 2

The sum of the first row is: 15
The sum of the second row is: 15
The sum of the third row is: 15
The sum of the first column is: 15
The sum of the second column is: 15
The sum of the third column is: 15
The sum of both the diagonals is: 15
The matrix consists of distinct numbers from 1 to 9 and has the sum of all the rows, columns, and diagonals equal. So, it is a magic square.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘M’ and ‘N’, representing the size of the matrices.

The next ‘M’  lines of each test case contain ‘N’ space-separated integers, representing the elements of ‘MAT’.
Output Format : 
For each test case, print the count of magic squares present in the matrix.

Print output of each test case in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= M, N <= 5*10^3
1 <= MAT[i][j] <= 9

Time Limit: 1 sec
Sample Input 1 :
2
3 3
8 3 4
1 5 9
6 7 2
3 3
1 3 5
1 6 3
7 9 2
Sample Output 1 :
1
0
Explanation For Sample Output 1 :
For test case 1: 
The sum of the first row is: 15
The sum of the second row is: 15
The sum of the third row is: 15
The sum of the first column is: 15
The sum of the second column is: 15
The sum of the third column is: 15
The sum of both the diagonals is: 15
The matrix consists of distinct numbers from 1 to 9 and has the sum of all the rows, columns, and diagonals equal. So, the count is 1.

For test case 2:    
The matrix does not consist of any magic squares.
Sample Input 2 :
2
1 2
1 2
6 3
4 3 8
9 5 1
2 7 6
6 7 2
1 5 9
8 3 4
Sample Output 2 :
0
2
Hint

Try to check every submatrix of size 3 * 3.

Approaches (1)
Brute-Force Approach

The basic idea is to check every possible submatrix of size 3 * 3 of the matrix whether it is a good square or not. For every submatrix, we find the sum of all the rows, columns, and diagonals and check whether all are equal or not. We also check whether the elements present in the submatrix are distinct or not.

 

Here is the algorithm :

 

  1. Base case:
    • Check if ‘M’ or ‘N’ is smaller than 3.
      • Return 0.
  2. Create a variable (say, ‘CNT’) to store the number of good squares.
  3. Run a loop from 0 to ‘M’ (say, iterator ‘i’) to traverse the rows.
    • Run a loop from 0 to ‘N’ (say, iterator ‘j’) to traverse the columns.
      • Check if the submatrix starting from the (‘i’, ‘j’) index is valid by calling the function isValid.
        • Increment ‘CNT’ by 1.
  4. Return ‘CNT’.

 

isValid(‘MAT’, ‘M’, ‘N’, ‘i’, ‘j’)   (where ‘MAT’ is given matrix, ‘M’ and ‘N’ are dimensions of the matrix, ‘i’ and ‘j’ are the starting index of the matrix)

 

  1. Base case:
    • Check if ‘M’ - ‘i’ or ‘N’ - ‘j’ is smaller than 3 (a good square cannot exist).
      • Return FALSE.
  2. Create a set (say, ‘VAL’) to store the numbers of the submatrix.
  3. Run a loop from ‘i’ to ‘i’ + 3 (say, iterator ‘r’).
    • Run a loop from ‘j’ to ‘j’ + 3 (say, iterator ‘c’).
      • Insert ‘MAT[r][c]’ in the set.
  4. Check if the size of ‘VAL’ is not equal to 9.
    • Return FALSE.
  5. Create a variable (say, ‘ROW1’) to store the sum of elements of the first row and initialize it with sum of ‘MAT[i][j]’, ‘MAT[i][j + 1]’, and ‘MAT[i][j + 2]’.
  6. Create a variable (say, ‘ROW2’) to store the sum of elements of the second row and initialize it with sum of ‘MAT[i + 1][j]’, ‘MAT[i + 1][j + 1]’, and ‘MAT[i + 1][j + 2]’.
  7. Create a variable (say, ‘ROW3’) to store the sum of elements of the third row and initialize it with sum of ‘MAT[i + 2][j]’, ‘MAT[i + 2][j + 1]’, and ‘MAT[i + 2][j + 2]’.
  8. Check if ‘ROW1’ is not equal to ‘ROW2’ or ‘ROW1’ is not equal to ‘ROW3’.
    • Return FALSE.
  9. Similarly, check if the sum of all the columns is equal and is equal to the sum of the row, otherwise return FALSE.
  10. Similarly, check if the sum of all the diagonals is equal and is equal to the sum of the row, otherwise return FALSE.
  11. Return TRUE.
Time Complexity

O(M*N), where ‘M’ and ‘N’ are the size of the matrix.

 

We traverse all the cells of both the matrices only once. Therefore, the overall time complexity will be O(M*N).

Space Complexity

O(1)

 

We use a set to store the elements of the submatrix, which takes O(3 * 3) space, i.e., O(1). Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Magic Squares In Matrix
Full screen
Console