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)