Leetcode 207 Course Schedule

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....

December 3, 2022 · 2 min · 229 words · Me

Leetcode 133 Clone Graph

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....

December 3, 2022 · 3 min · 522 words · Me

Leetcode 542 01 Matrix

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....

December 3, 2022 · 2 min · 214 words · Me

Leetcode 733: Flood Fill

Problem Statement An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc]. To perform a flood fill, consider the starting pixel, plus any pixels connected >4-directionally to the starting pixel of the same color as the starting pixel, >plus any pixels connected 4-directionally to those pixels (also with the same >color), and so on....

December 3, 2022 · 3 min · 443 words · Me