GRAPHS Flashcards
Number of Islands (** DFS)
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
’’’
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows, cols = len(grid), len(grid[0])
num_of_islands = 0
def dfs(r,c):
if r<0 or r>=rows or c<0 or c>=cols or grid[r][c] != ‘1’:
return
grid[r][c] = ‘#’
dfs(r+1,c)
dfs(r,c+1)
dfs(r-1,c)
dfs(r,c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == ‘1’:
dfs(r,c)
num_of_islands+=1
return num_of_islands
‘’’
- get the rows, cols in the grid, keep counter for island
- go through each cell (r,c)
- If it is ‘1’ then perform search (dfs). We assume each dfs call will result in counting an island
- in dfs, check if the given coord as out of bounds or are not ‘1’, then return
- If not, make the cell marked with special character, so that we dont visit that in future
- Then we call dfs on other 4 directions
Number of Islands (** BFS)
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
’’’
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows, cols = len(grid), len(grid[0])
num_of_islands = 0
visited = set()
def get_neigbhors(node):
r,c = node
delta_row = [-1,0,1,0]
delta_col = [0,1,0,-1]
neighbors = []
for i in range(len(delta_row)):
nr = r + delta_row[i]
nc = c + delta_col[i]
if 0<= nr< rows and 0<= nc< cols and grid[nr][nc] == ‘1’:
neighbors.append((nr,nc))
return neighbors
def bfs(r,c):
q = deque()
q.append((r,c))
visited.add((r,c))
while q:
current = q.popleft()
for neighbor in get_neigbhors(current):
if neighbor not in visited:
q.append(neighbor)
visited.add(neighbor)
for r in range(rows):
for c in range(cols):
if grid[r][c] == ‘1’ and (r,c) not in visited:
bfs(r,c)
num_of_islands+=1
return num_of_islands
‘’’
1. get the rows, cols in the grid, keep counter for island. Keep global variable of visited set
2. go through each cell (r,c)
3. If it is ‘1’ (** not in visited)then perform search (bfs). We assume each dfs call will result in counting an island
Max Area of Island (** DFS)
Number of islands problem, but we want to know the maximum area that a island has. Or in other words, find the area of biggest island
’’’
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
max_area = 0
def dfs(r,c):
if r < 0 or r >= rows or c <0 or c >= cols or grid[r][c] != 1:
return 0
area = 1
grid[r][c] = -999
area += dfs(r+1,c)
area += dfs(r,c+1)
area += dfs(r-1,c)
area += dfs(r,c-1)
return area
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
area = dfs(r,c)
max_area = max(max_area,area)
return max_area
‘’’
- get bounds - rows & cols. Keep variable of max_area
- go through each cell. If it is 1, then perform search , we assume to get back a value of their area and keep track of max_area
- in dfs, we check if (r,c) not in bounds or not 1 return 0 , set the (r,c) as visited by puttting any number apart from 0,1.
- Then set area = 1 and continue the dfs with adding the results of these dfs to the area. and return it at the end
Max Area of Island (** BFS)
Number of islands problem, but we want to know the maximum area that a island has. Or in other words, find the area of biggest island
’’’
from collections import deque
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
max_area = 0
visited = set()
def get_neighbors(node):
r,c = node
delta_row = [-1,0,1,0]
delta_col = [0,1,0,-1]
neighbors = []
for i in range(len(delta_row)):
nr = r + delta_row[i]
nc = c + delta_col[i]
if 0<= nr< rows and 0<= nc< cols and grid[nr][nc] == 1:
neighbors.append((nr,nc))
return neighbors
def bfs(r,c):
q = deque()
q.append((r,c))
visited.add((r,c))
area = 1
while q:
current = q.popleft()
for neighbor in get_neighbors(current):
if neighbor not in visited:
q.append(neighbor)
visited.add(neighbor)
area+=1
return area
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1 and (r,c) not in visited:
area = bfs(r,c)
max_area = max(max_area,area)
return max_area '''
- get the rows, cols in the grid, keep counter for island. Keep global variable of visited set
- go through each cell (r,c)
- If it is 1 (** not in visited)then perform search (bfs). We assume each dfs call will result in getting area
- in bfs, keep variable for area (** initialize at 1). Increment it at every valid neighbor found
area = 1 #to keep account of the node that started BFS
Clone Graph
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>
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
from collections import deque
class Solution:
def cloneGraph(self, node: Optional[‘Node’]) -> Optional[‘Node’]:
if not node:
return None
cloned_nodes = {}
q = deque()
q.append(node)
cloned_nodes[node] = Node(node.val)
while q:
current = q.popleft()
for neighbor in current.neighbors:
if neighbor not in cloned_nodes:
cloned_nodes[neighbor] = Node(neighbor.val)
q.append(neighbor)
cloned_nodes[current].neighbors.append(cloned_nodes[neighbor])
return cloned_nodes[node]
’’’
1.Our idea is to have a cloned_nodes dictionary that is original node : cloned node
2. as an when we find other original neighbor nodes, we make a clone. And we add these cloned neigbor nodes to the cloned original root node
======
Example Graph
Consider this simple graph with four nodes:
markdown
Copy code
1
/ \
2 3
\ /
4
Node 1 has neighbors 2 and 3.
Node 2 has neighbors 1 and 4.
Node 3 has neighbors 1 and 4.
Node 4 has neighbors 2 and 3.
Step-by-Step Execution of the BFS Cloning Process
Initialization:
Input Node: 1 (the node we start cloning from).
cloned_nodes Dictionary: {} (initially empty).
Queue: [1] (start BFS from the given input node).
Clone the Starting Node (1):
Create a clone of node 1 and store it in cloned_nodes:
python
Copy code
cloned_nodes[1] = Node(1) # Clone of node 1
Queue: [1].
cloned_nodes Dictionary:
python
Copy code
{ 1: Node(1) } # Node 1 has no neighbors cloned yet
Process Node 1:
Queue: [] (node 1 is dequeued for processing).
Current Node: 1.
Iterate over the neighbors of node 1 (nodes 2 and 3).
Clone Neighbor Node 2:
Neighbor: 2.
Node 2 is not in cloned_nodes, so clone it and add it to cloned_nodes:
python
Copy code
cloned_nodes[2] = Node(2)
Append cloned_nodes[2] to the neighbors of cloned_nodes[1]:
python
Copy code
cloned_nodes[1].neighbors.append(cloned_nodes[2])
Queue: [2] (add 2 to the queue for further processing).
cloned_nodes Dictionary:
python
Copy code
{ 1: Node(1, neighbors=[Node(2)]), 2: Node(2) }
Clone Neighbor Node 3:
Neighbor: 3.
Node 3 is not in cloned_nodes, so clone it and add it to cloned_nodes:
python
Copy code
cloned_nodes[3] = Node(3)
Append cloned_nodes[3] to the neighbors of cloned_nodes[1]:
python
Copy code
cloned_nodes[1].neighbors.append(cloned_nodes[3])
Queue: [2, 3] (add 3 to the queue for further processing).
cloned_nodes Dictionary:
python
Copy code
{ 1: Node(1, neighbors=[Node(2), Node(3)]), 2: Node(2), 3: Node(3) }
Process Node 2:
Queue: [3] (node 2 is dequeued for processing).
Current Node: 2.
Iterate over the neighbors of node 2 (nodes 1 and 4).
Neighbor Node 1 (already cloned):
Neighbor: 1.
Node 1 is already in cloned_nodes, so we don’t need to clone it.
Append cloned_nodes[1] to the neighbors of cloned_nodes[2]:
python
Copy code
cloned_nodes[2].neighbors.append(cloned_nodes[1])
Queue: [3] (no change).
cloned_nodes Dictionary:
python
Copy code
{
1: Node(1, neighbors=[Node(2), Node(3)]),
2: Node(2, neighbors=[Node(1)]),
3: Node(3)
} ………….so on
Walls and Gates
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]]
’’’
from collections import deque
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
“””
Do not return anything, modify rooms in-place instead.
“””
rows, cols = len(rooms), len(rooms[0])
INF = 2147483647
def get_neighbors(node):
r,c = node
delta_row = [-1,0,1,0]
delta_col = [0,1,0,-1]
neighbors = []
for i in range(len(delta_row)):
nr = r + delta_row[i]
nc = c + delta_col[i]
if 0<= nr< rows and 0<= nc< cols and rooms[nr][nc] == INF:
neighbors.append((nr,nc))
return neighbors
def bfs():
q= deque()
visited = set()
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0:
q.append((r,c))
visited.add((r,c))
while q:
node = q.popleft()
row,col = node
for neighbor in get_neighbors(node):
if neighbor not in visited:
nr,nc = neighbor
rooms[nr][nc] = rooms[row][col]+1
q.append((nr,nc))
visited.add((nr,nc))
bfs()
’’’
1. Scan through the grid, add cells that are 0 to queue and visited. These are gates. Multiple BFS starting scenario
2. And our aim is to perform BFS and find neighbors that are INF, i.e. empty rooms. Then replace the grid[empty room coord] = grid[current node in bfs coord] + 1. This is to indicate that we are changing empty room value from INF to finite number , in sets of 1 steps away from a gate.
When to declare visited set() inside or outside
Outside:
1. When we are passing single coordinates to bfs
ex : NUm of islands
Inside :
1. When we are calling bfs() without arguments
When to use the
for i in range(len(q))
We use it when we want level wise metric. That is we want to count the times that a bread search continues.
In many BFS problems , where we use BFS as a searching logic primarily we dont care about if the search is happening level wise or not, we just want to search.
But in problems where we want to know when a level (that is nodes at same level) are processed we use the for loop.
When WE DONT USE for loop, the nodes keep popping and pushing into queue, we dont know when the level stops.
Rotting Oranges
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.
’’’
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
def get_neighbors(node):
r,c = node
delta_row = [-1,0,1,0]
delta_col = [0,1,0,-1]
neighbors = []
for i in range(len(delta_row)):
nr = r + delta_row[i]
nc = c + delta_col[i]
if 0<=nr<rows and 0<=nc<cols and grid[nr][nc] == 1:
neighbors.append((nr,nc))
return neighbors
def bfs():
q = deque()
visited = set()
fresh_count = 0
minute = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
fresh_count +=1
if grid[r][c] == 2:
q.append((r,c))
visited.add((r,c))
while q and fresh_count>0:
for i in range(len(q)):
current = q.popleft()
for neighbor in get_neighbors(current):
if neighbor not in visited:
fresh_count-=1
q.append(neighbor)
visited.add(neighbor)
minute+=1
if fresh_count == 0:
return minute
else:
return -1
return bfs() ''' 1. get bounds - rows, column 2. We call bfs() no arguments 3. We keep track of fresh_count and push cells with rotten (==2) in queue and visited. 4. While q ** and fresh_count > 0. Only (while q) will end up searching entire grid. We need to stop when there isnt any fresh oranges left. 5. In get neigbors we need the neighbors to be fresh. 6. Minutes is a level wise variable. So we need the for loop to signify end of level. 7. return minutes, only fresh_count == 0, if not there wasnt any way to reach and rot all fresh ones
Pacific Atlantic Water Flow
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.
’’’
from collections import deque
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
rows, cols = len(heights), len(heights[0])
def get_neighbors(node):
print(node)
r,c = node
delta_row = [-1,0,1,0]
delta_col = [0,1,0,-1]
neighbors = []
for i in range(len(delta_row)):
nr = r + delta_row[i]
nc = c + delta_col[i]
if 0<= nr< rows and 0<= nc < cols and heights[nr][nc]>= heights[r][c]:
neighbors.append((nr,nc))
return neighbors
def bfs(start_nodes):
q = deque(start_nodes)
visited = set(start_nodes)
while q:
current = q.popleft()
for neighbor in get_neighbors(current):
if neighbor not in visited:
q.append(neighbor)
visited.add(neighbor)
return visited
pacific_starts = set()
atlantic_starts = set()
for r in range(rows):
pacific_starts.add((r,0))
atlantic_starts.add((r,cols-1))
for c in range(cols):
pacific_starts.add((0,c))
atlantic_starts.add((rows-1,c))
pacific_reachables = bfs(pacific_starts)
atlantic_reachables = bfs(atlantic_starts)
return list(pacific_reachables & atlantic_reachables)
‘’’
- Multiple start nodes bfs scenario
- We push all the cells from left and top edge into pacific_start set
and do similar for right and bottom for atlantic stat set - These points and in practical scenrio the last point from where water would flow out of. We trace our way back from these so called end points, calling it starting points and use BFS to search the path.
- When finding neighbors, make sure heights[nr][nc] >= heights[r][c], again, from a practical point it should be opposite. But when tracing back the neighbor cells should be equal or bigger
- After BFS we want to send back the visited set as these will be unique cells from where water can flow out to either of the oceans, we call it pacific_reachables and atlantics_reacheables.
- We do AND operations on these sets and the resultant are the common cells from where water can flow into both
Surrounded Regions (** BFS)
You are given an m x n matrix board containing letters ‘X’ and ‘O’, capture regions that are surrounded:
Connect: A cell is connected to adjacent cells horizontally or vertically.
Region: To form a region connect every ‘O’ cell.
Surround: The region is surrounded with ‘X’ cells if you can connect the region with ‘X’ cells and none of the region cells are on the edge of the board.
A surrounded region is captured by replacing all ‘O’s with ‘X’s in the input matrix board
’’’
class Solution:
def solve(self, grid: List[List[str]]) -> None:
rows, cols = len(grid),len(grid[0])
def get_neighbors(node):
r,c = node
delta_row = [-1,0,1,0]
delta_col = [0,1,0,-1]
neighbors = []
for i in range(len(delta_row)):
nr = r + delta_row[i]
nc = c + delta_col[i]
if 0<=nr<rows and 0<=nc<cols and grid[nr][nc] == ‘O’:
neighbors.append((nr,nc))
return neighbors
def bfs(start_nodes):
q = deque(start_nodes)
visited = set(start_nodes)
while q:
current = q.popleft()
for neighbor in get_neighbors(current):
if neighbor not in visited:
q.append(neighbor)
visited.add(neighbor)
return visited
start_nodes = set()
for r in range(rows):
if grid[r][0] == 'O':
start_nodes.add((r,0))
if grid[r][cols-1] == 'O':
start_nodes.add((r,cols-1))
for c in range(cols):
if grid[0][c] == 'O':
start_nodes.add((0,c))
if grid[rows-1][c] == 'O':
start_nodes.add((rows-1,c))
cells_connected_to_edge = bfs(start_nodes)
for r in range(rows):
for c in range(cols):
if (r,c) not in cells_connected_to_edge:
if grid[r][c] == 'O':
grid[r][c] = 'X' '''
- Logic - area which consists of ‘O’ cells that are present on edge, we keep those areas as ‘O’
- And the other ‘O’ cells that are not part of the edge will be converted to ‘X’
- Collect all cells from the edges that are ‘O’. Then perform BFS. Get the visited cells, those cells represents areas with edge cells.
- We iterate through the grid, if the cell in the edge_set, and top of that if the cell is ‘O’, then change it to ‘X’
Surrounded Regions (** DFS)
You are given an m x n matrix board containing letters ‘X’ and ‘O’, capture regions that are surrounded:
Connect: A cell is connected to adjacent cells horizontally or vertically.
Region: To form a region connect every ‘O’ cell.
Surround: The region is surrounded with ‘X’ cells if you can connect the region with ‘X’ cells and none of the region cells are on the edge of the board.
A surrounded region is captured by replacing all ‘O’s with ‘X’s in the input matrix board
class Solution:
def solve(self, grid: List[List[str]]) -> None:
“””
Do not return anything, modify board in-place instead.
“””
rows, cols = len(grid),len(grid[0])
def dfs(r,c):
if r<0 or r>=rows or c < 0 or c>= cols or grid[r][c] != ‘O’:
return
grid[r][c] = ‘T’
dfs(r+1,c)
dfs(r,c+1)
dfs(r-1,c)
dfs(r,c-1)
start_nodes = set()
for r in range(rows):
if grid[r][0] == 'O':
dfs(r,0)
if grid[r][cols-1] == 'O':
dfs(r,cols-1)
for c in range(cols):
if grid[0][c] == 'O':
dfs(0,c)
if grid[rows-1][c] == 'O':
dfs(rows-1,c)
for r in range(rows):
for c in range(cols):
if grid[r][c] == 'T':
grid[r][c] = 'O'
elif grid[r][c] == 'O':
grid[r][c] = 'X'
====
1.Basically num of island code.
2. Marking becomes keeping track of edge cell area
3. then mark all the temp marked as ‘O’ and all the ‘O’ marked as ‘X’
Course Schedule
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.
’’’
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = {i : [] for i in range(numCourses)}
def find_in_degree(graph):
indegree = {node : 0 for node in graph}
for node in graph:
for neighbor in graph[node]:
indegree[neighbor]+=1
return indegree
def topo_sort(graph):
q = deque()
res = []
indegree = find_in_degree(graph)
for node in indegree:
if indegree[node] == 0:
q.append(node)
while q:
current = q.popleft()
res.append(current)
for neighbor in graph[current]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
q.append(neighbor)
if len(res) == len(graph):
return True
else:
return False
for course,prereq in prerequisites:
graph[prereq].append(course)
return topo_sort(graph) '''
- Create a graph like –> {0:[1,2], 1:[2,4]…}, from the given list of list prerequistes
- [1,0] means to take 1 we need to take 0 first. Thus 0 -> 1. Thus graph = {o:[1]}
- Perform topo_sort on this graph. If the len(res) != len(graph) then we have a cycle and the course is not possible
** res, is the list , which represents the topologically sorted nodes of a graph
Course Schedule II
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].
Same as course Schedule 1. But here we return the topologically sorted list itself. Not just check if it is viable or not
