Graphs Flashcards
- Number of Islands
Solved
Medium
Topics
Companies: Facebook Microsoft Amazon TikTok Google
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”]
]
Output: 3
Constraints:
m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] is '0' or '1'.
https://leetcode.com/problems/number-of-islands/description/
from collections import deque
class Solution(object):
def numIslands(self, grid):
“””
:type grid: List[List[str]]
:rtype: int
“””
seen = set()
q = deque()
q.append((0,0))
ROWS = len(grid)
COLS = len(grid[0])
directions = [[0,1], [0,-1], [1,0], [-1,0]]
def bfs(ir, ic):
q.append((ir, ic))
while q:
r,c = q.popleft()
for rm, cm in directions:
row, col = rm + r, cm + c
if row in range(ROWS) and col in range(COLS) and (row, col) not in seen and grid[r][c] == "1":
seen.add((row, col))
q.append((row, col))
islands = 0
for r in range(ROWS):
for c in range(COLS):
if (r,c) not in seen and grid[r][c] == "1":
bfs(r, c)
islands += 1
return islands
DFS
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
rows = len(grid)
cols = len(grid[0])
visited = set()
directions = [[0,1], [0,-1], [-1,0], [1,0]]
islands = 0
def dfs(ir, ic):
visitstack = []
visitstack.append((ir, ic))
visited.add((ir, ic))
while visitstack:
r,c = visitstack.pop()
for rm, cm in directions:
row, col = rm+r, cm+c
if row in range(rows) and col in range(cols) and (row, col) not in visited and grid[row][col] == "1":
visited.add((row,col))
visitstack.append((row, col))
for r in range(rows):
for c in range(cols):
if (r,c) not in visited and grid[r][c] == "1":
dfs(r,c)
islands += 1
return islands
- Max Area of Island
Solved
Medium
Topics
Companies
You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.
Example 1:
Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
Constraints:
m == grid.length n == grid[i].length 1 <= m, n <= 50 grid[i][j] is either 0 or 1.
https://leetcode.com/problems/max-area-of-island/
class UnionFind:
def \_\_init\_\_(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [0] * n
def find(self, node):
if self.parent[node] != node:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa != pb:
if self.rank[pa] > self.rank[pb]:
self.parent[pb] = pa
self.size[pa] += self.size[pb]
elif self.rank[pa] < self.rank[pb]:
self.parent[pa] = pb
self.size[pb] += self.size[pa]
else:
self.parent[pb] = pa
self.rank[pa] += 1
self.size[pa] += self.size[pb]
return True
else:
# They are already connected
return False
def init_component(self, c):
if self.size[c] == 0:
self.size[c] = 1
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ROWS = len(grid)
COLS = len(grid[0])
total = ROWS * COLS
uf = UnionFind(total)
def idx(r, c):
return r * COLS + c
directions = [[0, 1], [0,-1], [1,0], [-1,0]]
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 1:
uf.init_component(idx(r,c))
for rm, cm in directions:
row = rm + r
col = cm + c
if row in range(ROWS) and col in range(COLS) and grid[row][col] == 1:
uf.init_component(idx(row,col))
uf.union(idx(r,c), idx(row, col))
area = max(uf.size)
return area
BFS
from collections import deque
class Solution(object):
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
seen = set()
rows = len(grid)
cols = len(grid[0])
max_area = 0
def bfs(r, c):
q = deque()
q.append((r,c))
seen.add((r,c))
directions = [[0,1], [0,-1], [1,0], [-1,0]]
area = 0
while q:
row,col = q.popleft()
area += 1
for dr, dc in directions:
r = dr + row
c = dc + col
if ((r,c ) not in seen and r in range(rows) and c in range(cols) and grid[r][c] == 1):
q.append((r,c))
seen.add((r,c))
return area
for r in range(rows):
for c in range(cols):
if ((r,c) not in seen and grid[r][c] == 1):
max_area = max(max_area, bfs(r,c))
return max_area
- Clone Graph
Solved
Medium
Topics
Companies: FB
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;
}</Node>
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. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Example 1:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)’s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)’s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)’s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)’s neighbors are 1st node (val = 1) and 3rd node (val = 3).
Example 2:
Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:
Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
Constraints:
The number of nodes in the graph is in the range [0, 100]. 1 <= Node.val <= 100 Node.val is unique for each node. There are no repeated edges and no self-loops in the graph. The Graph is connected and all nodes can be visited starting from the given node.
https://leetcode.com/problems/clone-graph/description/
Definition for a Node.
from collections import deque
"""
# Definition for a Node.
class Node:
def \_\_init\_\_(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
from typing import Optional
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node:
return None
copy_dict = defaultdict(lambda: Node())
def get_clone(original):
clone = copy_dict[original]
clone.val = original.val
return clone
q = deque()
q.append(node)
seen = set()
ret = get_clone(node)
while q:
cur = q.popleft()
if cur in seen:
continue
new_cur = get_clone(cur)
for neighbor in cur.neighbors:
new_cur_neighbor = get_clone(neighbor)
new_cur.neighbors.append(new_cur_neighbor)
q.append(neighbor)
seen.add(cur)
return ret
- Walls and Gates
Solved
Medium
Topics
Companies
You are given an m x n grid rooms initialized with these three possible values.
-1 A wall or an obstacle. 0 A gate. INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
Example 1:
Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
Example 2:
Input: rooms = [[-1]]
Output: [[-1]]
Constraints:
m == rooms.length n == rooms[i].length 1 <= m, n <= 250 rooms[i][j] is -1, 0, or 231 - 1.
https://leetcode.com/problems/walls-and-gates/description/
Multiple BFS start points, each time a cell is discovered, it has to be discovered from it’s nearest gate. So once it’s seen, it does not need to be visited again. Seen can be done by either storing row,cols or by just checking if the distance is not infinity.
Saves some space.
from collections import deque
class Solution(object):
def wallsAndGates(self, rooms):
"""
:type rooms: List[List[int]]
:rtype: None Do not return anything, modify rooms in-place instead.
"""
rows = len(rooms)
cols = len(rooms[0])
q = deque()
movements = [[0,1], [1,0], [-1, 0], [0,-1]]
is_valid = lambda r,c: (r >= 0 and r < rows) and (c >= 0 and c < cols) and rooms[r][c] == 2147483647
def bfs(q):
dist = 0
while q:
qlen = len(q)
for _ in range(qlen):
r, c = q.popleft()
for rm, cm in movements:
row, col = r + rm, c + cm
if is_valid(row, col):
q.append((row, col))
# This is important here, as soon as you see the neighbor set its distance so the is_valid will act like
# seen set. The first time a cell is seen is from the closest gate.
rooms[row][col] = dist+1
dist += 1
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0:
q.append((r, c))
bfs(q)
return rooms
Standard BFS with seen
from collections import deque
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
gates = []
valid_rooms = set()
rows = len(rooms)
cols = len(rooms[0])
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0:
gates.append([r,c])
elif rooms[r][c] == 2147483647:
valid_rooms.add((r,c))
directions = [[0,1], [1,0], [0,-1], [-1,0]]
def bfs(start_i, start_j):
seen = set()
q = deque()
q.append((start_i, start_j))
distance = 1
while q:
qlen = len(q)
for _ in range(qlen):
r,c = q.popleft()
for dr, dc in directions:
row, col = dr + r, dc + c
if (row, col) in valid_rooms and (row, col) not in seen and rooms[row][col] > distance:
q.append((row, col))
seen.add((row, col))
rooms[row][col] = distance
distance += 1
for gr, gc in gates:
bfs(gr, gc)
return rooms
- Rotting Oranges
Solved
Medium
Topics
Companies
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.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Constraints:
m == grid.length n == grid[i].length 1 <= m, n <= 10 grid[i][j] is 0, 1, or 2.
https://leetcode.com/problems/rotting-oranges/description/
from collections import deque
class Solution(object):
def orangesRotting(self, grid):
“””
:type grid: List[List[int]]
:rtype: int
“””
fresh = 0
q = deque()
rows = len(grid)
cols = len(grid[0])
visited = set() # maybe not needed.
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
fresh += 1
elif grid[r][c] == 2:
q.append((r,c))
time = -1
is_valid = lambda r,c: 0 <= r < rows and 0 <= c < cols and grid[r][c] == 1
directions = [[0,1], [0,-1], [1,0], [-1,0]]
while q:
qlen = len(q)
time += 1
for _ in range(qlen):
rv, cv = q.popleft()
for rm, cm in directions:
row, col = rm + rv, cm + cv
if is_valid(row, col):
grid[row][col] = 2
q.append((row, col))
fresh -= 1
if fresh > 0:
return -1
else:
return max(0, time)
- Pacific Atlantic Water Flow
Solved
Medium
Topics
Companies
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 island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
Example 1:
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean
[0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean
[1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean
[1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean
[2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean
[3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean
[3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean
[4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.
Example 2:
Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.
Constraints:
m == heights.length n == heights[r].length 1 <= m, n <= 200 0 <= heights[r][c] <= 105
https://leetcode.com/problems/pacific-atlantic-water-flow/description/
Double BFS/DFS from each coast find intersection
from collections import defaultdict
class Solution(object):
def pacificAtlantic(self, heights):
“””
:type heights: List[List[int]]
:rtype: List[List[int]]
“””
rows = len(heights)
cols = len(heights[0])
p_starts = set()
a_starts = set()
for r in range(rows):
p_starts.add((r, 0))
a_starts.add((r, cols-1))
for c in range(cols):
p_starts.add((0, c))
a_starts.add((rows-1, c))
p_seen = set()
a_seen = set()
directions = [[0,1], [1,0], [0, -1], [-1,0]]
def dfs(r,c, seen):
visit_stack = []
visit_stack.append((r,c))
seen.add((r, c))
is_valid = lambda r, c: 0 <= r < rows and 0 <= c < cols and (r,c) not in seen
while visit_stack:
ir, ic = visit_stack.pop()
for rm, cm in directions:
row, col = ir + rm, ic + cm
if is_valid(row, col) and heights[ir][ic] <= heights[row][col]:
seen.add((row, col))
visit_stack.append((row,col))
for r,c in p_starts:
dfs(r,c, p_seen)
for r,c in a_starts:
dfs(r,c, a_seen)
output = p_seen.intersection(a_seen)
return output
- Surrounded Regions
Solved
Medium
Topics
Companies
Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
Example 1:
Input: board = [[“X”,”X”,”X”,”X”],[“X”,”O”,”O”,”X”],[“X”,”X”,”O”,”X”],[“X”,”O”,”X”,”X”]]
Output: [[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”O”,”X”,”X”]]
Explanation: Notice that an ‘O’ should not be flipped if:
- It is on the border, or
- It is adjacent to an ‘O’ that should not be flipped.
The bottom ‘O’ is on the border, so it is not flipped.
The other three ‘O’ form a surrounded region, so they are flipped.
Example 2:
Input: board = [[“X”]]
Output: [[“X”]]
Constraints:
m == board.length n == board[i].length 1 <= m, n <= 200 board[i][j] is 'X' or 'O'.
https://leetcode.com/problems/surrounded-regions/description/
Start from the border, mark all you can reach as “E” then go over board again and replace any E with O and any O with X.
# Similar to the atlantic ocean problem, start on the coast.
class Solution(object):
def solve(self, board):
“””
:type board: List[List[str]]
:rtype: None Do not return anything, modify board in-place instead.
“””
directions = [(0, 1), (1, 0), (-1,0), (0,-1)]
seen = set()
rows = len(board)
cols = len(board[0])
is_border = lambda r,c: (r == 0 or r == rows -1) or (c == 0 or c == cols -1)
is_valid = lambda r, c: 0 <= r < rows and 0 <= c < cols and (r,c) not in seen and board[r][c] == “O” and not is_border(r,c)
def dfs(r,c):
board[r][c] = "E"
for rm, cm in directions:
row, col = r + rm, c + cm
if is_valid(row, col):
seen.add((row, col))
dfs(row, col)
for r in range(rows):
for c in range(cols):
if is_border(r, c) and board[r][c] == "O":
seen.add((r, c))
dfs(r,c)
for r in range(rows):
for c in range(cols):
if board[r][c] == "E":
board[r][c] = "O"
else:
board[r][c] = "X"
return board
- Course Schedule
Solved
Medium
Topics
Companies
Hint
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.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Constraints:
1 <= numCourses <= 2000 0 <= prerequisites.length <= 5000 prerequisites[i].length == 2 0 <= ai, bi < numCourses All the pairs prerequisites[i] are unique.
https://leetcode.com/problems/course-schedule/description/
from collections import defaultdict
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
adj = defaultdict(list)
for course, preq in prerequisites:
adj[course].append(preq)
ncourses = numCourses
# Global Seen, we do not need to re-visit courses that have been completed.
seen = set()
def dfs(c):
if not adj[c]:
## Course has no preq.
return True
# This represents the current dfs stack.
cur_seen = set()
stack = []
stack.append(c)
while stack:
course = stack[-1]
# We do not pop the course yet because we do not if it's processed or not
# One way to see it is that it needs to be popped twice first to add it's children and
# second when all nodes bellow it are processed.
if course not in seen:
# Seeing this node the first time.
cur_seen.add(course)
seen.add(course)
else:
course = stack.pop()
if course in cur_seen:
cur_seen.remove(course)
for preq in adj[course]:
if preq not in seen:
stack.append(preq)
elif preq in cur_seen:
# Cycle
return False
return True
for c in range(numCourses):
canComplete = dfs(c)
if not canComplete:
return False
else:
ncourses -= 1
if ncourses > 0:
return False
return True- Course Schedule II
Solved
Medium
Topics
Companies
Hint
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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
Example 2:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
Example 3:
Input: numCourses = 1, prerequisites = []
Output: [0]
Constraints:
1 <= numCourses <= 2000 0 <= prerequisites.length <= numCourses * (numCourses - 1) prerequisites[i].length == 2 0 <= ai, bi < numCourses ai != bi All the pairs [ai, bi] are distinct.
https://leetcode.com/problems/course-schedule-ii/description/
Topological Sort
from collections import defaultdict
~~~
class Solution(object):
def findOrder(self, numCourses, prerequisites):
“””
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
“””
order = []
seen = set()
m = defaultdict(list)
ncourses = numCourses
for course, preq in prerequisites:
m[course].append(preq)
def dfs(start):
if start in seen:
return True
cur_seen = set()
stack = [start]
while stack:
course = stack[-1]
if course not in seen:
seen.add(course)
cur_seen.add(course)
else:
course = stack.pop()
if course in cur_seen:
order.append(course)
cur_seen.remove(course)
m[course] = []
for preq in m[course]:
if preq not in seen:
stack.append(preq)
else:
if preq in cur_seen:
return False
return True
for c in range(numCourses):
if not dfs(c):
return []
ncourses -= 1
if ncourses > 0:
return []
return order ~~~
BFS Top Sort
from collections import deque, defaultdict
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# BFS
q = deque()
order = []
indegree = [0] * numCourses
adj = defaultdict(list)
for course, preq in prerequisites:
# Note this is preq -> courses it feeds into
# So we can reduce their indegrees.
adj[preq].append(course)
indegree[course] += 1
for course in range(numCourses):
if indegree[course] == 0:
q.append(course)
seen = set()
while q:
course = q.popleft()
seen.add(course)
for preq in adj[course]:
indegree[preq] -= 1
if indegree[preq] == 0:
q.append(preq)
order.append(course)
if len(order) != numCourses:
return []
return order
- Graph Valid Tree
Solved
Medium
Topics
Companies
Hint
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.
Example 1:
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Example 2:
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Constraints:
1 <= n <= 2000 0 <= edges.length <= 5000 edges[i].length == 2 0 <= ai, bi < n ai != bi There are no self-loops or repeated edges.
https://leetcode.com/problems/graph-valid-tree/description/
from collections import defaultdict
class Solution(object):
def validTree(self, n, edges):
“””
:type n: int
:type edges: List[List[int]]
:rtype: bool
“””
stack = []
visited = set()
adj = defaultdict(list)
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
stack.append((0, -1))
while stack:
node, parent = stack.pop()
visited.add(node)
for neighbor in adj[node]:
if neighbor not in visited:
stack.append((neighbor, node))
elif neighbor != parent:
return False
return len(visited) == n
- Number of Connected Components in an Undirected Graph
Solved
Medium
Topics
Companies
You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.
Return the number of connected components in the graph.
Example 1:
Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Example 2:
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Constraints:
1 <= n <= 2000 1 <= edges.length <= 5000 edges[i].length == 2 0 <= ai <= bi < n ai != bi There are no repeated edges.
https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/description/
Can use DFS or BFS or Union Find
DFS
class Solution(object):
def countComponents(self, n, edges):
“””
:type n: int
:type edges: List[List[int]]
:rtype: int
“””
seen = set()
adj_list = defaultdict(list)
for i, j in edges:
adj_list[i].append(j)
adj_list[j].append(i)
def dfs(i):
seen.add(i)
neighbors = adj_list[i]
for neighbor in neighbors:
if neighbor not in seen:
dfs(neighbor)
cc = 0
for v in range(n):
if v not in adj_list:
cc += 1
elif v not in seen:
dfs(v)
cc += 1
return cc
Union Find
from collections import defaultdict
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
parent = [i for i in range(n)]
rank = [0] * n
def find(node):
if parent[node] != node:
parent[node] = find(parent[node])
return parent[node]
def union(a, b):
pa, pb = find(a), find(b)
if pa != pb:
if rank[pa] > rank[pb]:
parent[pb] = pa
elif rank[pb] > rank[pa]:
parent[pa] = pb
else:
parent[pb] = pa
rank[pa] += 1
adj = defaultdict(list)
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
for a in range(n):
for b in adj[a]:
union(a,b)
cc = sum(1 for i in range(n) if parent[i] == i)
return cc
- Redundant Connection
Solved
Medium
Topics
Companies
In this problem, a tree is an undirected graph that is connected and has no cycles.
You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.
Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.
Example 1:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Example 2:
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Constraints:
n == edges.length 3 <= n <= 1000 edges[i].length == 2 1 <= ai < bi <= edges.length ai != bi There are no repeated edges. The given graph is connected.
https://leetcode.com/problems/redundant-connection/description/
DFS BFS you need to run the search as you encounter each connection, and then build the graph.
```Union find or DFS/BFS
#DFS
from collections import defaultdict
class Solution(object):
def findRedundantConnection(self, edges):
“””
:type edges: List[List[int]]
:rtype: List[int]
“””
adj = defaultdict(list)
output = []
def dfs(start, target):
stack = []
seen = set()
stack.append(start)
while stack:
node = stack.pop()
if node == target:
output.append([start, target])
return True
seen.add(node)
for neighbor in adj[node]:
if neighbor not in seen:
stack.append(neighbor)
return False
for a,b in edges:
if dfs(a,b):
return output[-1]
adj[a].append(b)
adj[b].append(a) ~~~
Union Find, return if you find parent of both are same.
class Solution(object):
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
par = {}
rank = {}
ret = []
n_edges = len(edges)
for i in range(1, n_edges + 1):
par[i] = i
rank[i] = 1
def find(node):
p = node
while p != par[p]:
par[p] = par[par[p]]
p = par[p]
return p
def union(a, b):
par_a, par_b = find(a), find(b)
rank_a, rank_b = rank[par_a], rank[par_b]
if par_a == par_b:
return [a,b]
if rank_a > rank_b:
par[par_b] = par_a
rank[par_a] += rank_b
elif rank_b > rank_a:
par[par_a] = par_b
rank[par_b] += rank_a
else:
par[par_b] = par_a
for a,b in edges:
redundant = union(a,b)
if redundant:
ret = redundant
return ret
- Word Ladder
Solved
Hard
Topics
Companies
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:
Every adjacent pair of words differs by a single letter. Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
Example 1:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
Output: 5
Explanation: One shortest transformation sequence is “hit” -> “hot” -> “dot” -> “dog” -> cog”, which is 5 words long.
Example 2:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
Output: 0
Explanation: The endWord “cog” is not in wordList, therefore there is no valid transformation sequence.
Constraints:
1 <= beginWord.length <= 10 endWord.length == beginWord.length 1 <= wordList.length <= 5000 wordList[i].length == beginWord.length beginWord, endWord, and wordList[i] consist of lowercase English letters. beginWord != endWord All the words in wordList are unique.
https://leetcode.com/problems/word-ladder/description/
Create wildcard words from each word with one char replaced with * for each chars and use them to find neighbors. Then do a BFS
from collections import defaultdict, deque
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
“””
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
“””
adj = defaultdict(list)
wl = set(wordList)
wl.add(beginWord)
visited = set()
for word in wl:
for i in range(len(word)):
modified = word[:i] + “*” + word[i+1:]
adj[modified].append(word)
adj[word].append(modified)
q = deque()
q.append(beginWord)
level = 0
while q:
level += 1
looplen = len(q)
for _ in range(looplen):
w = q.popleft()
if w == endWord:
return level
dup = set()
dup.add(w)
for alternative in adj[w]:
for neighbor in adj[alternative]:
if neighbor not in dup:
if neighbor not in visited:
visited.add(neighbor)
q.append(neighbor)
dup.add(neighbor)
return 0
- Min Cost to Connect All Points
Medium
You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].
The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.
Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
Example 1:
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation:
We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.
Example 2:
Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18
Constraints:
1 <= points.length <= 1000 -106 <= xi, yi <= 106 All pairs (xi, yi) are distinct.
https://leetcode.com/problems/min-cost-to-connect-all-points/description/
select 0 as start node
Prims Algo,
~~~
# insert it in heap with dist 0
# while heap, pop the top most element,
# mark visited, else continue
# calculate its distance from all other points
# add them to min heap.
# This ensures we always pick the min distance from each point to the other and once we visited all of them, then we just finish through the loop.
# we track num vertices we have connected, so we can shortcut once we reach n-1
~~~
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
root = 0
heap = [(0, root)]
max_vertices = len(points) - 1
vertices = 0
seen = set()
cost = 0
while heap and vertices <= (len(points) - 1):
dist, dest = heapq.heappop(heap)
if dest in seen:
continue
seen.add(dest)
cost += dist
vertices += 1
for ip, point in enumerate(points):
if ip not in seen:
dist = abs(points[dest][0]-point[0]) + abs(points[dest][1]- point[1])
heapq.heappush(heap, (dist, ip))
return cost
- Network Delay Time
Solved
Medium
Topics
Companies
Hint
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Example 2:
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Example 3:
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Constraints:
1 <= k <= n <= 100 1 <= times.length <= 6000 times[i].length == 3 1 <= ui, vi <= n ui != vi 0 <= wi <= 100 All the pairs (ui, vi) are unique. (i.e., no multiple edges.)
https://leetcode.com/problems/network-delay-time/
DJikstra
from collections import defaultdict
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
heap = []
adj = defaultdict(list)
for src, dest, time in times:
adj[src].append((time,dest))
visited = set()
heap.append((0, k))
while heap:
time, dest = heapq.heappop(heap)
if dest in visited:
continue
visited.add(dest)
if len(visited) == n:
return time
for t, neighbor in adj[dest]:
if neighbor not in visited:
heapq.heappush(heap, (t+time, neighbor))
return -1
