Problem Statement You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1....
Problem Statement Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 Example 2: Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] DFS: Recursive class Solution: def numIslands(self, grid: List[List[str]]) -> int: # ROWS >= COLS >= 1 ROWS, COLS = len(grid), len(grid[0]) islands = 0 # T: O(N x M) for r in range(ROWS): for c in range(COLS): if grid[r][c] == "1": islands += 1 self....
Problem Statement There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses....
Problem Statement Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors. class Node { public int val; public List<Node> neighbors; } Test case format: For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on....
Problem Statement Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1. Input: mat = [[0,0,0],[0,1,0],[1,1,1]] Output: [[0,0,0],[0,1,0],[1,2,1]] BFS: Iterative from collections import deque class Solution: def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]: ROWS, COLS = len(mat), len(mat[0]) """ * we need to find the distance to the nearest 0 * we know that m >= n >= 1 ~ no need to check dims * add zeros to queue * we can change mat """ queue = deque() # Add locations of zero cells to queue with distance of 0 # T: O(N*M) # S: O(N*M) for r in range(ROWS): for c in range(COLS): if mat[r][c] == 0: # (row, col, distance) queue....