toeplitz_matrix
1from collections import defaultdict 2 3 4# @leet start 5class Solution: 6 def isToeplitzMatrix(self, matrix: list[list[int]]) -> bool: 7 """ 8 This question asks us to return true if the given matrix is toeplitz, 9 where every diagonal from top-left to bottom-right has the same elements. 10 11 We can do this by iterating through the matrix and grouping items that 12 are in the same diagonal, and then we find out if the diagonal all have 13 the same items. 14 15 To do so, note that all items on the same diagonal have the same slope. 16 17 Imagine a matrix like: 18 [1, 2] 19 [2, 2] 20 21 In this case, we want three groups: 22 [2], [1, 2], [2]. 23 24 They have the (y, x) coordinates of: 25 [(0, 0)] 26 [(0, 1), (1, 0)] 27 [(1, 1)] 28 29 We can see that the middle set has the same slant if we do (y - x) or 30 (x - y). We can then group them by that. 31 This takes $O(M * N)$ time, with $O(M + N)$ space. 32 33 We can, however, get rid of the space requirement by simply checking 34 each matrix with its top-left or bottom-right corresponding member. 35 This would take the same amount of time, but $O(1)$ space. 36 """ 37 m, n = len(matrix), len(matrix[0]) 38 39 slants = defaultdict(set) 40 41 for y in range(m): 42 for x in range(n): 43 slants[y - x].add(matrix[y][x]) 44 45 return all([len(x) == 1 for x in slants.values()]) 46 47 48# @leet end 49 50 51def test(): 52 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def isToeplitzMatrix(self, matrix: list[list[int]]) -> bool: 8 """ 9 This question asks us to return true if the given matrix is toeplitz, 10 where every diagonal from top-left to bottom-right has the same elements. 11 12 We can do this by iterating through the matrix and grouping items that 13 are in the same diagonal, and then we find out if the diagonal all have 14 the same items. 15 16 To do so, note that all items on the same diagonal have the same slope. 17 18 Imagine a matrix like: 19 [1, 2] 20 [2, 2] 21 22 In this case, we want three groups: 23 [2], [1, 2], [2]. 24 25 They have the (y, x) coordinates of: 26 [(0, 0)] 27 [(0, 1), (1, 0)] 28 [(1, 1)] 29 30 We can see that the middle set has the same slant if we do (y - x) or 31 (x - y). We can then group them by that. 32 This takes $O(M * N)$ time, with $O(M + N)$ space. 33 34 We can, however, get rid of the space requirement by simply checking 35 each matrix with its top-left or bottom-right corresponding member. 36 This would take the same amount of time, but $O(1)$ space. 37 """ 38 m, n = len(matrix), len(matrix[0]) 39 40 slants = defaultdict(set) 41 42 for y in range(m): 43 for x in range(n): 44 slants[y - x].add(matrix[y][x]) 45 46 return all([len(x) == 1 for x in slants.values()])
def
isToeplitzMatrix(self, matrix: list[list[int]]) -> bool:
7 def isToeplitzMatrix(self, matrix: list[list[int]]) -> bool: 8 """ 9 This question asks us to return true if the given matrix is toeplitz, 10 where every diagonal from top-left to bottom-right has the same elements. 11 12 We can do this by iterating through the matrix and grouping items that 13 are in the same diagonal, and then we find out if the diagonal all have 14 the same items. 15 16 To do so, note that all items on the same diagonal have the same slope. 17 18 Imagine a matrix like: 19 [1, 2] 20 [2, 2] 21 22 In this case, we want three groups: 23 [2], [1, 2], [2]. 24 25 They have the (y, x) coordinates of: 26 [(0, 0)] 27 [(0, 1), (1, 0)] 28 [(1, 1)] 29 30 We can see that the middle set has the same slant if we do (y - x) or 31 (x - y). We can then group them by that. 32 This takes $O(M * N)$ time, with $O(M + N)$ space. 33 34 We can, however, get rid of the space requirement by simply checking 35 each matrix with its top-left or bottom-right corresponding member. 36 This would take the same amount of time, but $O(1)$ space. 37 """ 38 m, n = len(matrix), len(matrix[0]) 39 40 slants = defaultdict(set) 41 42 for y in range(m): 43 for x in range(n): 44 slants[y - x].add(matrix[y][x]) 45 46 return all([len(x) == 1 for x in slants.values()])
This question asks us to return true if the given matrix is toeplitz, where every diagonal from top-left to bottom-right has the same elements.
We can do this by iterating through the matrix and grouping items that are in the same diagonal, and then we find out if the diagonal all have the same items.
To do so, note that all items on the same diagonal have the same slope.
Imagine a matrix like: [1, 2] [2, 2]
In this case, we want three groups: [2], [1, 2], [2].
They have the (y, x) coordinates of: [(0, 0)] [(0, 1), (1, 0)] [(1, 1)]
We can see that the middle set has the same slant if we do (y - x) or (x - y). We can then group them by that. This takes $O(M * N)$ time, with $O(M + N)$ space.
We can, however, get rid of the space requirement by simply checking each matrix with its top-left or bottom-right corresponding member. This would take the same amount of time, but $O(1)$ space.
def
test():