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) 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) 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)