[Java] Toeplitz matrix

A matrix is called toeplitz matrix if all element along the left to right diagonals are same.

Given a matrix, test whether it is a toeplitz matrix.

We can verify the given condition with two consecutive loops. The first will check all diagonals for the first row starting with the previous to last element until the first of the row.

The last element of the row is on a diagonal with itself, therefore there is nothing to check.

We repeat the process for all diagonals for the first column starting with the second element until the previous to last. The first element was already checked as first element of the row at the previous step, and the last element again is on a diagonal with itself.

We can do this in O(NM) time and constant space.

You can check my implementation of isToeplitz on my Gist along with some tests in ToeplitzMatrixJTests.