Matrix
- This kinda of questions don't usually have a fixed pattern, we usually just kinda have to treat it as a puzzle and solve it individually
- Matrix traversal usually have a strict pattern
Overview
- Sometimes the problem given a matrix, but it can be treated and solved like a [[9. Graph]], so we can use tactics like [[9. Graph#DFS]] or [[9. Graph#BFS]]
Tricks
Coordinate Diagonals For a grid of size n x n:
- Main Diagonal (Top-left to bottom-right):
- All cells on this diagonal have the property: row - col = constant
- For the main diagonal itself: row - col = 0
- Parallel diagonals above have row - col < 0
- Parallel diagonals below have row - col > 0
- Anti-Diagonal (Top-right to bottom-left):
- All cells share the property: row + col = constant
- For the main anti-diagonal: row + col = n - 1
- Parallel anti-diagonals above have row + col < n - 1
- Parallel anti-diagonals below have row + col > n - 1
https://leetcode.com/problems/design-tic-tac-toe
class TicTacToe:
def __init__(self, n: int):
self.size = n
self.grid = [[0] * n for _ in range(n)]
def move(self, row: int, col: int, player: int) -> int:
self.grid[row][col] = player
if self._checkCol(player, col) or self._checkRow(player, row) or self._checkDiagonal(player, row, col):
return player
return 0
def _checkRow(self, player, row):
curRow = self.grid[row]
for col in range(self.size):
if curRow[col] != player:
return False
return True
def _checkCol(self, player, col):
for row in range(self.size):
curRow = self.grid[row]
if curRow[col] != player:
return False
return True
def _checkDiagonal(self, player, row, col):
win = True
if row - col == 0:
startRow, startCol = 0, 0
while startRow < self.size and startCol < self.size:
if self.grid[startRow][startCol] != player:
win = False
break
startRow += 1
startCol += 1
if win:
return True
win = True
if row + col == self.size - 1:
startRow, startCol = 0, self.size - 1
while startRow < self.size and startCol >= 0:
if self.grid[startRow][startCol] != player:
win = False
break
startRow += 1
startCol -= 1
if win:
return True
return False
https://leetcode.com/problems/n-queens
def solveNQueens(self, n: int) -> List[List[str]]:
colSet = set()
diagSet = set()
antiDiagSet = set()
board = [["."] * n for _ in range(n)]
res = []
def backtrack(row):
if row == n:
copy = [''.join(row) for row in board]
res.append(copy)
return
for col in range(n):
if col in colSet or row - col in diagSet or row + col in antiDiagSet:
continue
colSet.add(col)
diagSet.add(row-col)
antiDiagSet.add(row + col)
board[row][col] = 'Q'
backtrack(row + 1)
colSet.remove(col)
diagSet.remove(row - col)
antiDiagSet.remove(row + col)
board[row][col] = '.'
backtrack(0)
return res
Problems
Basic
- These following questions are pretty straight-forward and easy enough to get started
- There's not any trick or pattern here
https://leetcode.com/problems/transpose-matrix
- Basic to get started
def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
rows, cols = len(matrix), len(matrix[0])
res = [[0] * rows for _ in range(cols)]
for row in range(rows):
for col in range(cols):
res[col][row] = matrix[row][col]
return res
# Alternative - More intuitive
def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
rows, cols = len(matrix), len(matrix[0])
res = []
for col in range(cols):
cur = []
for row in range(rows):
cur.append(matrix[row][col])
res.append(cur)
return res
https://leetcode.com/problems/flipping-an-image
def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
for row in image:
left, right = 0, len(row) - 1
while left <= right:
row[left], row[right] = 1 - row[right], 1 - row[left]
left += 1
right -= 1
return image
https://leetcode.com/problems/matrix-diagonal-sum
def diagonalSum(self, mat: List[List[int]]) -> int:
visit = set()
rows, cols = len(mat), len(mat[0])
def traverse(row, col, direction):
if row not in range(rows) or col not in range(cols):
return
visit.add((row, col))
if direction > 0:
traverse(row+1, col+1, direction)
else:
traverse(row+1, col-1, direction)
traverse(0, 0, 1)
traverse(0, cols-1, -1)
return sum([mat[row][col] for row, col in visit])
https://leetcode.com/problems/search-a-2d-matrix
- [[4. Binary Search]] twice
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
rows, cols = len(matrix), len(matrix[0])
top, down = 0, rows - 1
row = -1
while top <= down:
mid = top + (down - top)//2
curArr = matrix[mid]
if curArr[0] <= target <= curArr[-1]:
row = mid
break
elif target <= curArr[0]:
down = mid - 1
elif target >= curArr[-1]:
top = mid + 1
if row == -1:
return False
left, right = 0, cols - 1
curRow = matrix[row]
while left <= right:
mid = left + (right-left)//2
if curRow[mid] == target:
return True
elif curRow[mid] > target:
right = mid - 1
else:
left = mid + 1
return False
https://leetcode.com/problems/spiral-matrix
- Simple pattern
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
visit = set()
rows, cols = len(matrix), len(matrix[0])
row, col = 0, 0
res = []
direction = "right"
while len(res) < rows * cols:
res.append(matrix[row][col])
visit.add((row, col))
if direction == "right":
if col < cols - 1 and (row, col+1) not in visit:
col += 1
else:
direction = "down"
row += 1
elif direction == "down":
if row < rows - 1 and (row+1, col) not in visit:
row += 1
else:
direction = "left"
col -= 1
elif direction == "left":
if col > 0 and (row, col-1) not in visit:
col -= 1
else:
direction = 'up'
row -= 1
elif direction == "up":
if row > 0 and (row-1, col) not in visit:
row -= 1
else:
direction = "right"
col += 1
return res
https://leetcode.com/problems/spiral-matrix-ii
def generateMatrix(self, n: int) -> List[List[int]]:
target = n * n
res = [[0] * n for _ in range(n)]
num = 1
row, col = 0, 0
direction = "left"
visit = set()
while num <= target:
res[row][col] = num
visit.add((row, col))
if direction == "left":
if col < n - 1 and (row, col + 1) not in visit:
col += 1
else:
direction = "down"
row += 1
elif direction == "down":
if row < n - 1 and (row+1, col) not in visit:
row += 1
else:
direction = "right"
col -= 1
elif direction == "right":
if col > 0 and (row, col - 1) not in visit:
col -= 1
else:
direction = "up"
row -= 1
elif direction == "up":
if row > 0 and (row-1, col) not in visit:
row -= 1
else:
direction = "left"
col += 1
num += 1
return res
https://leetcode.com/problems/diagonal-traverse
- Simple pattern
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
res = []
rows, cols = len(mat), len(mat[0])
flip = False
for i in range(rows):
row, col = i, 0
curDiagonal = []
while row in range(rows) and col in range(cols):
curDiagonal.append(mat[row][col])
row -= 1
col += 1
if flip:
curDiagonal.reverse()
flip = not flip
res += curDiagonal
for i in range(1, cols):
row, col = rows-1, i
curDiagonal = []
while row in range(rows) and col in range(cols):
curDiagonal.append(mat[row][col])
row -= 1
col += 1
if flip:
curDiagonal.reverse()
flip = not flip
res += curDiagonal
return res
Intermediate
https://leetcode.com/problems/search-a-2d-matrix-ii
- Start at bottom because it gives information on both direction
- To right and below always give larger value
- To left and above always give smaller value
- With this starting point, we can always be confident on choosing the right direction to go
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or len(matrix[0]) == 0:
return False
rows, cols = len(matrix), len(matrix[0])
row, col = rows - 1, 0
while row in range(rows) and col in range(cols):
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
row -= 1
else:
col += 1
return False
https://leetcode.com/problems/rotate-image
- Really difficult problem, needs to be revisited multiple times
- https://www.youtube.com/watch?v=fMSJSS7eO1w
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
left, right = 0, len(matrix) - 1
while left < right:
for i in range(right-left):
top, bottom = left, right
topLeft = matrix[top][left + i]
matrix[top][left+i] = matrix[bottom-i][left]
matrix[bottom-i][left] = matrix[bottom][right-i]
matrix[bottom][right-i] = matrix[top+i][right]
matrix[top+i][right] = topLeft
left += 1
right -=1