Check diagonal equality in a matrix
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an m x n integer matrix, determine whether every top-left to bottom-right diagonal contains identical values (all elements along each such diagonal are equal). Provide an O(mn) solution, discuss space trade-offs, and cover edge cases such as empty matrices, single row/column, and negative values.
Quick Answer: This question evaluates skill in matrix manipulation and algorithmic reasoning, specifically understanding diagonal traversal, equality checks, and handling boundary conditions such as empty matrices, single-row or single-column inputs, and negative values.
Given an m x n integer matrix, determine whether every top-left to bottom-right diagonal contains identical values. A diagonal of a matrix is a sequence of cells starting from some cell on the top row or left column and proceeding down-right (each next cell is one row down and one column right). The matrix is "diagonal-equal" (a Toeplitz matrix) if and only if all elements along each such diagonal are equal.
Return true if every diagonal has all-equal values, otherwise false.
Key observation: a cell (i, j) lies on the same diagonal as cell (i-1, j-1). So the whole matrix is diagonal-equal exactly when matrix[i][j] == matrix[i-1][j-1] for every cell that has an up-left neighbor (i >= 1 and j >= 1). This gives an O(m*n) time check with O(1) extra space.
Edge cases to handle: an empty matrix (no rows, or rows with no columns) is trivially true; a single row or single column has no diagonal of length > 1 and is trivially true; values may be negative.
Follow-up (space trade-off): if the matrix arrives one row at a time over a stream and you cannot revisit prior rows, keep only the previous row and compare each new row against it shifted by one, using O(n) extra space instead of O(1).
Example 1:
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation: The diagonals are [9], [5,5], [1,1,1], [2,2,2], [3,3], [4], each with identical values.
Example 2:
Input: matrix = [[1,2],[2,2]]
Output: false
Explanation: The main diagonal is [1,2], which is not all-equal.
Constraints
- 0 <= m, n
- matrix is rectangular: every row has the same number of columns
- -10^9 <= matrix[i][j] <= 10^9 (values may be negative)
- An empty matrix (m == 0 or n == 0) returns true
Examples
Input: ([[1,2,3,4],[5,1,2,3],[9,5,1,2]],)
Expected Output: True
Explanation: Every diagonal ([9],[5,5],[1,1,1],[2,2,2],[3,3],[4]) holds equal values, so it is a Toeplitz matrix.
Input: ([[1,2],[2,2]],)
Expected Output: False
Explanation: The main diagonal is [1,2]; matrix[1][1]=2 differs from matrix[0][0]=1, so it is not diagonal-equal.
Hints
- Two cells belong to the same diagonal exactly when their (row - column) value is equal.
- You do not need to walk full diagonals: cell (i, j) is on the same diagonal as cell (i-1, j-1), so just compare each cell to its top-left neighbor.
- Handle empty matrices, single rows, and single columns up front — they are trivially diagonal-equal because no diagonal has length greater than 1.