The problem You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph. Return true if the edges of the given graph make up a valid tree, and false otherwise. Examples Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true ...
The problem 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. Otherwise, return false. ...
The problem There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges. The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c). ...
The Problem Given a reference to 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 has val == 1, the second node has val == 2, and so on. The graph is represented in the test case using an adjacency list. ...
The Problem 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 surrounded by water. Examples Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3 Constraints m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] is '0' or '1'. Depth-First Search Solution func numIslands(_ grid: [[Character]]) -> Int { var grid = grid let ROWS = grid.count let COLS = grid[0].count let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] var islands = 0 func dfs(_ r: Int, _ c: Int) { if (r < 0 || c < 0 || r >= ROWS || c >= COLS || grid[r][c] == "0" ) { return } grid[r][c] = "0" for direction in directions { let dr = direction[0] let dc = direction[1] dfs(r + dr, c + dc) } } for r in 0 ..< ROWS { for c in 0 ..< COLS { if grid[r][c] == "1" { dfs(r, c) islands += 1 } } } return islands } Explanation From the description of the problem, we can see that we have islands formed by connecting adjacent land horizontally or vertically. If we draw a visual representation, we can find islands that are connected vertically or horizontally and surrounded by water. ...