Approach #1: Group by Category [Accepted]
Intuition and Algorithm
We ask what feature makes two coordinates (r1, c1)
and (r2, c2)
belong to the same diagonal?
It turns out two coordinates are on the same diagonal if and only if r1  c1 == r2  c2
.
This leads to the following idea: remember the value of that diagonal as groups[rc]
. If we see a mismatch, the matrix is not Toeplitz; otherwise it is.
Complexity Analysis

Time Complexity: . (Recall in the problem statement that are the number of rows and columns in
matrix
.) 
Space Complexity: .
Approach #2: Compare With TopLeft Neighbor [Accepted]
Intuition and Algorithm
For each diagonal with elements in order , we can check . The matrix is Toeplitz if and only if all of these conditions are true for all (topleft to bottomright) diagonals.
Every element belongs to some diagonal, and it's previous element (if it exists) is it's topleft neighbor. Thus, for the square (r, c)
, we only need to check r == 0 OR c == 0 OR matrix[r1][c1] == matrix[r][c]
.
Complexity Analysis

Time Complexity: , as defined in the problem statement.

Space Complexity: .
Analysis written by: @awice.