Toeplitz Matrix - Solution & Explanation

Problem Overview: A matrix is called a Toeplitz matrix if every diagonal from top-left to bottom-right contains the same element. Given an matrix, verify that each diagonal has identical values. If any diagonal contains different numbers, the matrix is not Toeplitz.

Approach 1: Iterative Check for Diagonal Consistency (Time: O(m*n), Space: O(1))

The simplest observation: every element should match the element diagonally above it. For any cell matrix[i][j], the previous element on the same diagonal is matrix[i-1][j-1]. Iterate through the matrix starting from row 1 and column 1. If you ever find matrix[i][j] != matrix[i-1][j-1], the Toeplitz property is violated.

This works because each diagonal progresses exactly one step down and one step right. Instead of explicitly traversing diagonals, you compare each element with its top-left neighbor during a single pass through the grid. The algorithm uses a straightforward nested loop over the array structure and performs constant-time comparisons.

This approach runs in O(m*n) time since every cell is visited once, and it uses O(1) extra space because no additional data structures are required. For most interview scenarios and production code, this is the cleanest and most efficient solution.

Approach 2: Use HashMap to Track Diagonals (Time: O(m*n), Space: O(m+n))

Each diagonal in a matrix can be uniquely identified by the difference row - col. All elements with the same value of row - col belong to the same diagonal. You can store the first value encountered for each diagonal in a hash map.

Traverse the matrix once. For each cell, compute key = row - col. If the key is not present in the map, store the current value as the expected value for that diagonal. If it already exists, compare the stored value with the current cell. A mismatch means the matrix is not Toeplitz.

This technique explicitly groups elements by diagonals instead of relying on neighbor comparisons. The time complexity remains O(m*n), but the map stores up to m+n-1 diagonals, giving O(m+n) space usage. It is useful when diagonal grouping logic is needed for extensions of the problem.

Recommended for interviews: The iterative comparison approach is what interviewers typically expect. It demonstrates that you recognize the diagonal relationship matrix[i][j] == matrix[i-1][j-1] and can validate the matrix in a single pass with constant space. The hash map method still works and shows understanding of diagonal indexing, but it introduces unnecessary memory overhead for this specific problem.