Matrix
Valid Sudoku (Medium)
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without repetition.
Note:
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
def isValidSudoku(board: List[List[str]]) -> bool: rows = [set() for _ in range(9)] cols = [set() for _ in range(9)] grid = [[set() for _ in range(3)] for _ in range(3)] for row in range(9): for col in range(9): val = board[row][col] if val == ".": continue if val in rows[row]: return False rows[row].add(val) if val in cols[col]: return False cols[col].add(val) gridRow, gridCol = row // 3, col // 3 if val in grid[gridRow][gridCol]: return False grid[gridRow][gridCol].add(val) return True
Time: O(1)
Space: O(1)
Alternative solution:
def isValidSudoku(board: List[List[str]]) -> bool: visited = set() for row in range(9): for col in range(9): val = board[row][col] if val == ".": continue rowStr = "r" + str(row) + val colStr = "c" + str(col) + val gridStr = "g" + str(row // 3) + str(col // 3) + val if rowStr in visited or colStr in visited or gridStr in visited: return False visited.add(rowStr) visited.add(colStr) visited.add(gridStr) return True
Time: O(1)
Space: O(1)
Spiral Matrix (Medium)
Given an m x n matrix, return all elements of the matrix in spiral order.
def spiralOrder(matrix: List[List[int]]) -> List[int]: answer = [] rows, cols = len(matrix), len(matrix[0]) row = col = 0 dRow, dCol = 0, 1 # Directions for _ in range(rows * cols): answer.append(matrix[row][col]) matrix[row][col] = None nextRow = row + dRow nextCol = col + dCol if not 0 <= nextRow < rows or not 0 <= nextCol < cols or matrix[nextRow][nextCol] == None: dRow, dCol = dCol, -dRow # Change directions row += dRow col += dCol return answer
Time: O(n * m)
Space: O(n * m) including output
Alternative solution:
def spiralOrder(matrix: List[List[int]]) -> List[int]: answer = [] rows, cols = len(matrix), len(matrix[0]) layers = -(-min(rows, cols) // 2) # Number of spirals in matrix for layer in range(layers): rowStart = colStart = layer rowEnd = rows - layer - 1 colEnd = cols - layer - 1 for i in range(colStart, colEnd + 1): # Right answer.append(matrix[rowStart][i]) for i in range(rowStart + 1, rowEnd): # Down answer.append(matrix[i][colEnd]) if rowStart == rowEnd: continue for i in range(colEnd, colStart - 1, -1): # Left answer.append(matrix[rowEnd][i]) if colStart == colEnd: continue for i in range(rowEnd - 1, rowStart, -1): # Up answer.append(matrix[i][colStart]) return answer
Time: O(n * m)
Space: O(n * m) including output
Rotate Image (Medium)
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
Rotate the image in-place.
def rotate(matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ # To rotate clockwise, reverse list, then flip diagonal symmetry # 1 2 3 7 8 9 7 4 1 # 4 5 6 => 4 5 6 => 8 5 2 # 7 8 9 1 2 3 9 6 3 matrix.reverse() for row in range(len(matrix)): for col in range(row + 1, len(matrix)): matrix[row][col], matrix[col][row] = matrix[col][row], matrix[row][col]
Time: O(n * n)
Space: O(1)
Set Matrix Zeroes (Medium)
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
Modify the matrix in place.
def setZeroes(matrix: List[List[int]]) -> None: # Use first row and column to track flags for entire matrix # Check first row and column for pre-existing 0 zeroFirstRow = False for val in matrix[0]: if val == 0: zeroFirstRow = True break zeroFirstCol = False for i in range(len(matrix)): if matrix[i][0] == 0: zeroFirstCol = True break # Check entire matrix and set flags for row in range(1, len(matrix)): for col in range(1, len(matrix[0])): if matrix[row][col] == 0: matrix[0][col] = 0 matrix[row][0] = 0 # Use flags to set all rows and columns to 0 as needed for row in range(1, len(matrix)): if matrix[row][0] == 0: for col in range(1, len(matrix[0])): matrix[row][col] = 0 for col in range(1, len(matrix[0])): if matrix[0][col] == 0: for row in range(1, len(matrix)): matrix[row][col] = 0 # Set first row and column to 0 if needed if zeroFirstRow: for col in range(len(matrix[0])): matrix[0][col] = 0 if zeroFirstCol: for row in range(len(matrix)): matrix[row][0] = 0
Time: O(n * m)
Space: O(1)
Game of Life (Medium)
"The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules:
- Any live cell with fewer than two live neighbors dies as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population.
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.
def gameOfLife(self, board: List[List[int]]) -> None: directions = [(-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)] # 2 = is dead, will live; 3 = is live, will die for row in range(len(board)): for col in range(len(board[0])): # Count live neighbors of current cell liveNeighbors = 0 for d in directions: r = row + d[0] c = col + d[1] if not 0 <= r < len(board) or not 0 <= c < len(board[0]): continue if board[r][c] == 1 or board[r][c] == 3: liveNeighbors += 1 # Apply rules to get next state without overwriting current state if board[row][col] == 0: board[row][col] = 2 if liveNeighbors == 3 else 0 else: if liveNeighbors != 2 and liveNeighbors != 3: board[row][col] = 3 # 2 -> 1; 3 -> 0 for row in range(len(board)): for col in range(len(board[0])): if board[row][col] == 2: board[row][col] = 1 elif board[row][col] == 3: board[row][col] = 0
Time: O(n * m)
Space: O(1)