4
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.