Leetcode problem: 766. Toeplitz Matrix

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

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

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 diagonal "[1, 2]" has different elements.

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 20
• 0 <= matrix[i][j] <= 99

Follow up:

• What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
• What if the matrix is so large that you can only load up a partial row into the memory at once?

Solution:

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int lenRow = matrix[0].length;
        int len = matrix.length;
        int match;
        int  j =0;
        int k;
        int start = 0;
        int l=0;

       
         while(l<lenRow-1){
             k = 0;
             j = l;
             l++;
             match= matrix[k][j];
            
            while(k<matrix.length-1 && j<lenRow-1){
                k++;
                j++;
                if(matrix[k][j] != match) return false;
            }
        }

        l = 0;
        while(l<matrix.length-1){
             k = l;
             j = 0;
             l++;
             match= matrix[k][j];
            
            while(k<matrix.length-1 && j<lenRow-1){
                k++;
                j++;
                if(matrix[k][j] != match) return false;
            }
        }

         
        return true;
    }
}

Approach:

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

Example:

1 2 3 4
5 1 2 3
9 5 1 2

Every diagonal (1-1-1, 2-2-2, 3-3, 4) contains identical elements → Toeplitz.

You want to check all diagonals of the matrix to ensure all elements on each diagonal are the same.

Step 1: Get matrix dimensions

int lenRow = matrix[0].length;  // number of columns
int len = matrix.length;        // number of rows

Step 2: Check diagonals starting from the top row

int l = 0;

while(l < lenRow - 1) {  // iterate over each column except the last one
    k = 0;               // start row
    j = l;               // start column
    l++;                 // move to next diagonal start
    match = matrix[k][j]; // value to match along the diagonal

    while(k < matrix.length - 1 && j < lenRow - 1) {
        k++; j++; 
        if(matrix[k][j] != match) return false; // if mismatch, not Toeplitz
    }
}

• Idea: For each diagonal starting at (0, l) (top row), move down-right (k++, j++) and check all elements.
• Stop when you reach the last row or last column.

Step 3: Check diagonals starting from the first column (except top-left)

l = 0;
while(l < matrix.length - 1) {  // iterate over each row except the last one
    k = l;     // start row
    j = 0;     // first column
    l++;
    match = matrix[k][j];  // value to match along the diagonal

    while(k < matrix.length - 1 && j < lenRow - 1) {
        k++; j++;
        if(matrix[k][j] != match) return false;
    }
}

• Idea: For diagonals starting in the first column (l, 0), check all down-right elements.
• This covers diagonals not starting in the top row.

Step 4: If no mismatches found

return true;

• If all diagonals have matching elements → matrix is Toeplitz.

✅ Key Points

1. Two sets of diagonals:
   • Starting from top row
   • Starting from first column
     This ensures all diagonals are checked without repeating the top-left diagonal.
2. Time Complexity:O(m * n)
   • Every element is visited exactly once on its diagonal.
3. Space Complexity:O(1)
   • No extra storage needed (only pointers k, j, match).