toeplitz matrix

#pramp #cs #matrix #interview

A Toeplitz matrix is a matrix where every left-to-right-descending diagonal has the same element. Given a non-empty matrix arr, write a function that returns true if and only if it is a Toeplitz matrix. The matrix can be any dimensions, not necessarily square.

For example,

1[[1,2,3,4],
2 [5,1,2,3],
3 [6,5,1,2]]

is a Toeplitz matrix, so we should return true, while

1[[1,2,3,4],
2 [5,1,9,3],
3 [6,5,1,2]]

Isnt a Toeplitz matrix, so we should return false.

This is the solution i came up with the first time i encountered this problem:

1def isToeplitz(A):
2  is_toep = True
3  for i in range(len(A)):
4    for j in range(len(A[i])):
5      if i > 0 and j > 0:
6        if not (A[i][j] == A[i-1][j-1]):
7                is_toep = False
8                break
9  return is_toep

Same solution, in Javascript:

 1function isToeplitz(A){
 2  var is_toep = true
 3  for (var i = 0; i < A.length; i++)
 4    for (var j = 0; j < A.length; j++)
 5      if (i > 0 && j > 0)
 6        if (A[i][j] != A[i-1][j-1]){
 7                is_toep = False
 8                break
 9        }
10  return is_toep
11}
12
13var m = [[1,2,3,4],
14         [5,1,2,3],
15         [6,5,1,2]];
16
17console.log(isToeplitz(m))

I believe it to be the optimal solution to this problem. I'm simply exploiting the fact that one can simply look backwards to check whether it's Toeplitz properties continue appearing. If the current row is in accordance with the previous row, albeit each cell shifted to the right, then by simply moving on to the next row, and repeating the same rearview check, we know the previous row is correct, so the Toeplitz correctness propagates down the rows as we progress.

Strangely i have yet to come across someone on Pramp who implements this solution. All the other candidates start with the first row, and instead of ahead, and end up with very complex code instead. Even more strangely, even the official answer is a lot more convoluted.

 1function isToeplitz(matrix):
 2    R, C = matrix.length, matrix[0].length
 3
 4    # For each diagonal starting in the first row at (0, c)
 5    for c from 0 to C - 1:
 6        start = matrix[0][c]
 7
 8        # For each element of that diagonal
 9        for k from 0 to min(R, C-c) - 1:
10            if matrix[k][c+k] != start:
11                return false
12
13    # Code repeated for starting in the first column
14    for r from 0 to R - 1:
15        start = matrix[r][0]
16        for k from 0 to min(R-r, C) - 1:
17            if matrix[r+k][k] != start:
18                return false
19
20    return true

So while sometimes i feel i am still behind, as other candidates code up better and more graceful solutions than i do, sometimes i feel i am ahead, and able to see simple solutions more rapidly than my counterparts.

This gives me hope.