766.Toeplitz_Matrix(Easy).md

766. Toeplitz Matrix (Easy)

Date and Time: Dec 26, 2024, 21:21 (EST)

Link: https://leetcode.com/problems/toeplitz-matrix

Question:

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.

Edge Case:

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

Output: true

Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 20

• 0 <= matrix[i][j] <= 99

Walk-through:

Brute Force:
Loop over matrix and check if each entry has bottom-right neighbor, if so, if they are not equal, return False. Otherwise, return True in the end.

Group pattern:
Observe that every entry on the same diagonal, their pos (r-c) will be the same, so we can save each (r-c) into hashmap with their value. If (r-c) exists in hashmap, we compare current value with hashmap[(r-c)], if they are not the same, return False.

Brute Force:

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        # Brute Force: compare each entry with if it has bottom-right neighbor

        # TC: O(m*n), m=rows, n=cols, SC: O(1)
        rows, cols = len(matrix), len(matrix[0])
        for r in range(rows):
            for c in range(cols):
                # Check if it has bottom-rigth neighbor
                if r+1 in range(rows) and c+1 in range(cols):
                    if matrix[r+1][c+1] != matrix[r][c]:
                        return False
        return True

Time Complexity: $O(m*n)$
Space Complexity: $O(1)$

Group Pattern:

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        # Every value on the same diagonal will have the same value of r-c, save its value into {} to compare with future entries

        # TC: O(m*n), m=rows, n=cols, SC: O(n)
        hashmap = {}
        rows, cols = len(matrix), len(matrix[0])
        for r in range(rows):
            for c in range(cols):
                if (r-c) not in hashmap:
                    hashmap[r-c] = matrix[r][c]
                elif hashmap[r-c] != matrix[r][c]:
                    return False
        return True

Time Complexity: $O(m*n)$
Space Complexity: $O(n)$