# Find all sub matrices of type N*M in it which are palindromic

Today I had an interview, where I was asked to solve this question.

A $N*M$ matrix is called a palindromic matrix, if for all of its rows and columns, elements read from left to right in a row are same as elements read from right to left, and similarly, elements read from top to bottom in a column are same as elements read from bottom to top in the column.

Example: below matrices are palindromic

3*5 Matrix

1 2 2 2 1
2 1 1 1 2
1 2 2 2 1


Given a matrix, find all submatrices of type $N*M$ in it which are palindromic. If the original matrix is a palindrome, print it as well. Constraints: $2 <= N, 2 <= M$

I wrote this code, How do I improve its complexity?

def check_palindrome(mat):
if mat:
m = len(mat)
n = len(mat[0])
for i in xrange(m/2 + 1):
for j in xrange(n/2 + 1):
if mat[i][j] != mat[m-1-i][j] or mat[i][j] != mat[i][n-1-j] or mat[i][j] != mat[m-1-i][n-1-j]:
return False

return True

def check_submatrix_palindome(mat):
m = len(mat)
n = len(mat[0])

for i in xrange(m-1):
for j in xrange(n-1):
for k in xrange(i+2,m):
for l in xrange(j+2,n):
sub_mat = [mat[x][j:l+1] for x in xrange(i,k+1)]
if check_palindrome(sub_mat):
print "palindrome =", sub_mat

return

m = int(raw_input())
mat = []
for i in xrange(m):
row = []
row = map(int, raw_input().strip().split(' '))
mat.append(row)

check_submatrix_palindome(mat)


Checking if a matrix is a palindrom can be simplified using the fact that you store your matrices as a list of rows.

If the matrix is a palindrom, then:

1. each line is a palindrom by itself;
2. each line is equal to its symetic (first with last, second with the one before last, etc).

Which can be written like:

def check_palindrome(mat):
for i, row in enumerate(mat, 1):
if row != row[::-1]:
# The current row is not a palindrome
return False
if row != mat[-i]:
# One of the columns is not a palindrome
return False
return True


Here I use the second argument of enumerate to get the correct index when accessing the matrix backwards.

This writing can be simplified using the all builtin:

def check_palindrome(mat):
return all(
row == mat[-i] and row == row[::-1]
for i, row in enumerate(mat, 1)
)


You can also shave half the tests by using enumerate(mat[:(len(mat)+1)//2], 1) but it won't change the overall complexity.