Check diagonal equality in a matrix
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
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.
Input: ([],)
Expected Output: True
Explanation: Empty matrix edge case: no diagonals to violate equality, so it returns true.
Input: ([[7]],)
Expected Output: True
Explanation: Single cell: each diagonal has length 1, trivially all-equal.
Input: ([[3,3,3,3,3]],)
Expected Output: True
Explanation: Single row: no diagonal exceeds length 1, so true regardless of values.
Input: ([[5],[5],[5]],)
Expected Output: True
Explanation: Single column: no diagonal exceeds length 1, so true regardless of values.
Input: ([[-1,-2,-3],[-4,-1,-2],[-7,-4,-1]],)
Expected Output: True
Explanation: Negative-value Toeplitz matrix: diagonals [-1,-1,-1], [-2,-2], [-3], [-4,-4], [-7] are each constant.
Input: ([[-1,-2,-3],[-4,0,-2]],)
Expected Output: False
Explanation: matrix[1][1]=0 differs from matrix[0][0]=-1, breaking the main diagonal.
Input: ([[1,2,3],[4,5,6],[7,8,9]],)
Expected Output: False
Explanation: Strictly increasing grid: matrix[1][1]=5 differs from matrix[0][0]=1, so 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.