algoadvance

Leetcode 766. Toeplitz Matrix

Problem Statement

A matrix is called Toeplitz if every diagonal from top-left to bottom-right has the same elements.

Given an m x n matrix matrix, return true if the matrix is Toeplitz. Otherwise, return false.

You need to implement the following function:

public boolean isToeplitzMatrix(int[][] matrix);

Example 1:

Input:
matrix = [
  [1,2,3,4],
  [5,1,2,3],
  [9,5,1,2]
]

Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

Example 2:

Input:
matrix = [
  [1,2],
  [2,2]
]

Output: false
Explanation:
The bottom left value is different from the top right value in the diagonal starting from matrix[1][0].

Clarifying Questions

  1. Are there any constraints on the size of the matrix?
    • The matrix dimensions m and n can be any positive integers, including very large numbers.
  2. Are negative numbers allowed in the matrix?
    • Yes, the matrix can contain negative numbers.
  3. Can the matrix be non-square (i.e., m ≠ n)?
    • Yes, the matrix can be non-square.

Strategy

To determine if a matrix is Toeplitz, we need to check if every diagonal from top-left to bottom-right has the same elements. Specifically, for each element at matrix[i][j], we need to ensure that matrix[i][j] == matrix[i+1][j+1] (provided i+1 and j+1 are within bounds).

Steps:

  1. Traverse through the matrix:
    • Loop through each element up to the second-last row and second-last column since elements in the last row and column won’t have corresponding matrix[i+1][j+1] to compare.
  2. Check the diagonals:
    • For each element at matrix[i][j], verify that it is equal to matrix[i+1][j+1].
    • If any discrepancy is found, return false.
  3. If no discrepancies are found, return true.

Code

public class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        // Iterate over each element except for the last row and last column
        for (int i = 0; i < matrix.length - 1; i++) {
            for (int j = 0; j < matrix[0].length - 1; j++) {
                // Check if the current element is equal to the element diagonally below it
                if (matrix[i][j] != matrix[i + 1][j + 1]) {
                    return false;
                }
            }
        }
        return true;
    }
}

Time Complexity

The time complexity of this solution is O(m * n) where m is the number of rows and n is the number of columns in the matrix. This is because we are iterating through each element of the matrix once.

The space complexity is O(1) since we are using a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI