Quick Overview

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.

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

  1. Two cells belong to the same diagonal exactly when their (row - column) value is equal.
  2. 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.
  3. Handle empty matrices, single rows, and single columns up front — they are trivially diagonal-equal because no diagonal has length greater than 1.

Loading coding console...