Toeplitz Matrix[Medium] (Pramp-Java)

Problem Description: 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,2,3,4],
 [5,1,2,3],
 [6,5,1,2]]

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

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

isn’t a Toeplitz matrix, so we should return false.

Constraints:

• [time limit] 5000ms
• [input] array.array.integer arr
• 0 ≤ arr.length ≤ 20
• 0 ≤ arr[i].length ≤ 20
• 0 ≤ arr[i][j] ≤ 20
• [output] boolean

Approach: Every element belongs to some diagonal, and it’s previous element (if it exists) is it’s top-left neighbor. Thus, for the square (r, c), we only need to check r == 0 OR c == 0 OR arr[r-1][c-1] == arr[r][c].

Solution:

public boolean isTopelitzMatrix(int[] arr)
{
  if(arr.length==0) return true;
  for(int r=0; r<arr.length; r++)
  {
    for(int c=0; c<arr[0].length; c++)
     {
       if(r>0 && c>0 && arr[r-1][c-1] != arr[r][c])
        {
           return false;
        }
     }
  }
  return true;
}

Time & Space complexity:

• Time Complexity: O(r*c), r-number of rows in matrix, c-number of columns in matrix.
• Space Complexity: O(1)