Graphs Flashcards
Number of Islands
Can use a simple BFS (or DFS) search of a graph where each new “level” just extends out inthe four cardinal directions. So you find a one, perform a BFS, adding the location of those ones to a set of visited nodes and then you go until you find the next one
Max Area of an Island
Essentially the same as Num Islands, just have to keep a count of area and return it in BFS to see if you have found a new largest landmass
Clone Graph
The key here is to maintain a mapping between the nodes given and our cloned nodes.
The queue should only ever be filled up with those existing nodes.
Each iteration, you pop a node and explore its neighbors. If a neighbor isn’t already in the map, we add it along with a cloned version (so we can access the clone later given the original) and we also add that neighbor to the queue. And then regardless of whether the neighbor is in the map, we add the cloned version (accessed via mapping neighbor to the clone) to the list of neighbors.
clone_map = {}
q = collections.deque([node])
clone_map[node] = Node(node.val)
while q:
curr = q.popleft()
for neighbor in curr.neighbors:
if neighbor not in clone_map:
clone_map[neighbor] = Node(neighbor.val)
q.append(neighbor)
clone_map[curr].neighbors.append(clone_map[neighbor])
Walls and Gates
A core idea here is that this is an unweighted graph. So BFS would easily tell you distance from one point to another as it goes out in one “step” each time.
We can start BFS from each gate so that we know that once we visit a empty room, we’ve had to have gotten there from the closest gate (as they all expand outward one step at a time)
So you go through all grids and add gates to your queues and visited set. Then you do BFS with a twist. You only want to do one level at a time before incrementing distance. So take the length of the queue and only iterate that many times before doing another top level while loop iteration.
Since all gates are starting points, you know that once you get to an empty room, it must have been from the closest gate, and then you can mark that room as visited so a later, larger distance won’t overwrite it.
Rotting Oranges
Using BFS again going one level at a time by only iterating through the queue by the length of the queue before you starting popping and appending.
Keep a counter for the amount of fresh fruit. This can be done in the initial step where you iterate through each grid to add all rotten ones to the queue. Then whenever you run into a grid containing a fresh orange (remember to continue if you find a blank space), simple decrement the count of fresh by one
Pacific Atlantic Water Flow
The real trick here is setting your starting points on the pacific and atlantic ocean and performing DFS from there to see which paths are valid.
So you maintain a set for both the pacific and atlantic that contains cells that have a path into there.
But how do you start from the neccesary grids?
for c in range(COLS):
dfs(0, c, pacific, 0)
dfs(ROWS - 1, c, atlantic, 0)
for r in range(ROWS):
dfs(r, 0, pacific, 0)
dfs(r, COLS - 1, atlantic, 0)
Your DFS should return if the prev_height is greater than the current as that indicates water would not be able to flow from the current to the prev cell. If it can flow, then you can add it to the visited set.
def dfs(r, c, visited, prev_height):
Finally you return the intersection of the pacific and atlantic sets
Surrounded Regions - https://leetcode.com/problems/surrounded-regions/description/
Here the trick is to start BFS on all O’s in the outer ring of the grid. Whatever O’s the outer O’s can reach cannot be surrounded so we can safely add them to the visited list and the queue.
At the end, we will go through every cell and if it hasn’t been visited, we ensure its an X.
In this way we essentially mark out what is safe from capture in our BFS step and then turn everything else into an X.
This seems to be a common pattern where the solution comes from figuring out where you start your BFS/DFS from.
Course Schedule - given a list of courses and their prereqs, see if its possible to complete all courses
What we are really checking for is if there is a cycle in the prereq list for any course
i.e. if a course shows up somewhere in its own prereq list
So first we build a hashmap that maps a course to a list of its prereqs
We then define our dfs function which returns False if a course is its own prereq and True if its not
We then loop through each course (just range(numCourses)) and if a single course returns false, we return False. Otherwise return True
So how does the DFS work specifically?
While it validates a course, it will keep that course added to a cycle set(). If at any point, the course we are running DFS on is in our cycle set, that means we have a cycle.
Once we validate a course by ensuring there are no cycles in its prereqs, we add the course to a validated_courses list so if we run into it again, we know we don’t have to check its entire prereq list so we can just return True
cycle.add(course)
for prereq in preMap[course]:
if not dfs(prereq): return False
cycle.remove(course)
validated_courses.add(course)
Course Schedule II
Here we are essentially being asked to find the topological sort of the graph where each course is a node and each prereq listing represents an edge.
A toplogical sort is where nodes are ordered such that each node is listed only after its predecessor nodes are listed
An undirected graph cannot have a topological sort because there is no sense of ordering to the nodes. Same with a cyclic graph, you can’t know which order to put the nodes in.
So this is essentially the same as Course Schedule I its just that we keep track of the output as an array. Every time we validate a course, we add it to the output.
cycle.add(course)
for pre in preMap[course]:
if not dfs(pre):
return False
cycle.remove(course)
visited.add(course)
output.append(course)
If while we loop through and perform dfs on each course, we ever have false returned, we immediately return an empty array as that means there is a cycle and a topological sort won’t be possible.
Is this Graph a valid tree.
We have to build an adjacency list here. This just maps a node to a list of nodes that it is connected to by edges. Keep in mind this is an undirected graph so connections go both ways.
Then you perform DFS a single time, we’ll start with 0 but it doesn’t really matter. We’ll keep track of what we’ve visited in a set. We never have to worry about removing fromt this set btw since we only start DFS from one node. If we run into the same node again, we of course return False. The issue is that we are guaranteed to run into the same node because of the two way connection. To solve this, keep track of the previously visited node and don’t call dfs on that again while you loop through connected nodes.
Finally if the length of the visited set equals the number of nodes, you know that you can get from one node to any node and if there was a cycle, you would’ve returned false already.
Number of Connected Components - A connected compponent is a group of nodes that are connected to each other. How many distinct groups are there?
Build adjacency list. Do DFS from that list. Keep a visited set(). Return false if a node is in visited. Return true if the function complets.
Note that when you are exploring all neighbor nodes (i.e. making recursive calls to dfs), you don’t care if it returns True or False. Cycles don’t matter, you are just trying to add all nodes connected to this one to your visited list.
So then you loop through every node and run dfs. If it returns False, here you will care as that means this node isn’t in a unexplored component. So everytime it returns true, you increment the result by 1
Find the redundant connection that occurs last in the edges provided as input
We’ll use BFS (continuing if the neighbor node equals the current node to avoid infinite looping. In the BFS, we will return True if a neighbor is in visited, indicating a loop. We then go through the edges one by one and on each iteration we will add that edge to the graph and run bfs. As soon as we add an edge and find that bfs returns True, that means that is the last edge in the list that created the cycle.
Word Ladder - basically that wordle game
First define your isAdjacent function to see if two words differ by just one character.
Then turn the word list into a set. If the endWord isn’t in the set, return 0.
Otherwise perform a BFS level by leve (using the for _ in range(len(q)) trick).
Loop through the wordList, if you find something that is adjacent, add it to the queue and remove it from the wordList. ALso if that word IS the endword, return sequence length then and there.
