How to Check if a Matrix is a Toeplitz Matrix?

Given a two-dimensional matrix of integers matrix, determine whether it’s a Toeplitz matrix. A Toeplitz is one where every diagonal descending from left to right has the same value.

For example, this is a Toeplitz matrix:
[0, 1, 2]
[3, 0, 1]
[4, 3, 0]
[5, 4, 3]

This is not a Toeplitz matrix:
[0, 1, 2]
[3, 0, 7]
[4, 3, 0]

Since matrix[0][1] = 1 but matrix[1][2] = 7

Example 1
Input

1 2 3 4 5

matrix = [     [13, 83, 15],     [86, 13, 83],     [63, 86, 13] ]

matrix = [
    [13, 83, 15],
    [86, 13, 83],
    [63, 86, 13]
]

Output
true

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

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example 1
Input:

1 2 3 4 5

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

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:

1 2 3 4

matrix = [   [1,2],   [2,2] ]

matrix = [
  [1,2],
  [2,2]
]

Output: False
Explanation:
The diagonal “[1, 2]” has different elements.
Note:
matrix will be a 2D array of integers.
matrix will have a number of rows and columns in range [1, 20].
matrix[i][j] will be integers in range [0, 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?

Compare with Bottom-Right Neighbour

We can iterate the matrix elements by O(MN) time complexity where M and N are the number of rows and columns of the matrix. At each element, we check its bottom-right neighbour (if it is not the last row or last column), if we find unmatched, the matrix is not a Toeplitz matrix.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>&got;& matrix) {
        for (int row = 0; row < matrix.size() - 1; row ++) {
            for (int col = 0; col < matrix[row].size() - 1; col ++) {
                if (matrix[row][col] != matrix[row + 1][col + 1]) {
                    return false;
                }
            }
        }
        return true;
    }   
};

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>&got;& matrix) {
        for (int row = 0; row < matrix.size() - 1; row ++) {
            for (int col = 0; col < matrix[row].size() - 1; col ++) {
                if (matrix[row][col] != matrix[row + 1][col + 1]) {
                    return false;
                }
            }
        }
        return true;
    }   
};

Group by Category using Hash table

The above solution takes O(1) constant space complexity however, it requires accessing two rows of matrix at the same time to perform the checks. If the matrix is large and memory is limited that you can access one row at a time, we need to do this a bit differently.

What features make elements on a same diagonal? It turns out the row-column is the same for all elements on the same diagonals. Then we can use a hash table with key set to the group i.e. row-column and value set to the matrix element. As we go through the entire matrix, we update the entry on the first element of a diagonal, if it appears before, and the value isn’t the same as current element, it is simply not a Toeplitz matrix.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        unordered_map<int, int> group;
        for (int row = 0; row < matrix.size(); row ++) {
            for (int col = 0; col < matrix[row].size(); col ++) {
                if (group.find(row - col) == group.end()) {
                    group[row - col] = matrix[row][col];
                } else {
                    if (group[row - col] != matrix[row][col]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }   
};

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        unordered_map<int, int> group;
        for (int row = 0; row < matrix.size(); row ++) {
            for (int col = 0; col < matrix[row].size(); col ++) {
                if (group.find(row - col) == group.end()) {
                    group[row - col] = matrix[row][col];
                } else {
                    if (group[row - col] != matrix[row][col]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }   
};

Time complexity is O(MN) and the space complexity is O(M+N) e.g. a hash table (unordered_map in C++). This approach requires reading one row of the matrix at a time.

We can proceed comparing the diagonals only. This will give O(M + N) time and O(1) space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

bool solve(vector<vector<int>>& matrix) {
    if (matrix.empty()) return true;
    function<bool(int, int)> checkDiag = [&](int r, int c) {
        int v = matrix[r][c];
        while (r < matrix.size() && c < matrix[0].size()) {
            if (matrix[r][c] != v) return false;
            r ++;
            c ++;
        }
        return true;
    };
    for (int r = 0; r < matrix.size(); ++ r) {
        if (!checkDiag(r, 0)) return false;
    }
    for (int c = 0; c < matrix[0].size(); ++ c) {
        if (!checkDiag(0, c)) return false;
    }
    return true;
}

bool solve(vector<vector<int>>& matrix) {
    if (matrix.empty()) return true;
    function<bool(int, int)> checkDiag = [&](int r, int c) {
        int v = matrix[r][c];
        while (r < matrix.size() && c < matrix[0].size()) {
            if (matrix[r][c] != v) return false;
            r ++;
            c ++;
        }
        return true;
    };
    for (int r = 0; r < matrix.size(); ++ r) {
        if (!checkDiag(r, 0)) return false;
    }
    for (int c = 0; c < matrix[0].size(); ++ c) {
        if (!checkDiag(0, c)) return false;
    }
    return true;
}

–EOF (The Ultimate Computing & Technology Blog) —