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

Question

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)

Answer 1

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.