496. Toeplitz Matrix
A matrix is called Toeplitz when every diagonal running from the top-left toward the bottom-right carries a single repeated value — pick any cell, walk one step down and one step right, and you must see the same number again, all the way to the edge.
Your function receives matrix, an m × n grid of integers, and returns a boolean: true if the grid is Toeplitz, false otherwise.
Note the direction: only the ↘ diagonals must be constant. The ↗ anti-diagonals may contain anything.
Example 1:
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation: The ↘ diagonals read 9; 5,5; 1,1,1; 2,2,2; 3,3; 4 — each one is a single repeated value, so the matrix is Toeplitz.
Example 2:
Input: matrix = [[1,2],[2,2]]
Output: false
Explanation: The main diagonal holds 1 then 2 — two different values on one ↘ diagonal, so the matrix is not Toeplitz.
Constraints:
- 1 ≤ m, n ≤ 100
- -10⁹ ≤ matrix[i][j] ≤ 10⁹
Hints:
Two cells (i1, j1) and (i2, j2) sit on the same ↘ diagonal exactly when i1 - j1 == i2 - j2. That difference is a perfect hash-map key for grouping cells by diagonal.
You never need the whole diagonal at once: the constant-diagonal condition holds if and only if every cell equals its immediate upper-left neighbor. One pass over cells with i > 0 and j > 0 settles it.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Expected output: true