Graphs Flashcards
Word Ladder (Medium)
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list.
Create dictionary of words with ‘*’ replacing one of the letters as key, and list of words that match that as values
i.e., *ot -> hot, not, lot
place first word and number 1 into queue,
add first word to visited set
bfs
grab word off queue
calculate * key for word check dictionary
iterate through list of adjacent words
if adjacent word equals end word, return level + 1
if visited does not have adjacent word, add it to visited set and push to queue with level + 1
Time - O(M^2 x N) where M is length of word and N is length of word list
Space - O(M^2 x N) (could optimize by storing index in Dictionary instead of each word)
Clone Graph (Medium)
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 val (int) and a list (List[Node]) of its neighbors.
create map of old nodes to new nodes
clone(node, visited)
if visited has node, return it
otherwise create new node (cloneNode), add to visited
iterate through neighbors and push cloned neighbors to node
return cloneNode
Time - O(n)
Space - O(n)
Number of Islands (Medium)
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count 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.
linear scan grind
if find a “1” for land, trigger dfs and increment island count
for dfs, check bounds and that its a 1, return if invalid
set grid[row][col] to 0 to mark “visited”
dfs for each of the four directions
Time - O(mn) where m is row, n is columns
Space - O(mn)
Course Schedule (Medium)
There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
topological sort create graph (adjacency list, course to children) create indegrees (course to in degree count) init sortedOrder = [] init graph and indegrees populate parent = prereq[1] child = prereq[0]
iterate through indegrees and grab sources (indegrees = 0)
BFS through sources
shift source off queue, iterate through children/neighbors and decrement indegree counts
add any new sources to queue
verify that sortedOrder.length === numCourses, otherwise cycle and can’t complete
Time - O(E + V)
Space - O(E + V)
Alien Dictionary (Hard)
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
topological sort
initialize graph and indegrees for each character
populate graph by grabbing two words at a time
if word1 is longer than word2 but word1 starts with word2, return empty string b/c can’t form valid graph
(this means first difference b/w words is that word2 is shorter)
find first difference b/w word1 and word2
j = 0; j < min(word1.length, word2.length)
parent = w1[j]
child = w2[j]
update graph and indegrees
break
iterate through indegrees and grab sources (indegrees = 0)
BFS through sources
shift source off queue, iterate through children/neighbors and decrement indegree counts
add any new sources to queue
verify that sortedOrder.length === inDegrees.size, otherwise cycle and can’t complete
Time - O(C) where C is total length of all words
Space - O(1)
Shortest Distance from All Buildings (Hard)
You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:
Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.
set minDistance to Infinity
create set of all buildings (${r}-${c}) with key of coordinates
create empty array to store minDistances
linear scan grid
if grid[r][c] = 0, trigger bfs and push result to minDistances
if grid[r][c] = 1, add to all buildings set
for all the mindistances, filter by those that equal all buildings set size (so they encounter all buildings)
then sum up all distances for each mindistane and keep track of overall minimum
bfs:
create 4-dirs, create visited set, create map for mindistances
BFS, queue up r, c, 1
shift off queue, check all 4 dirs, check for bounds
if grid[newRow][newCol] = 0 and not visited yet, add to visited and push to queue: newRow, newCol, level + 1
else if grid[newRow][newCol ] 1, if we don’t have entry yet in minDistances, add it (key, level), otherwise calc min and set that
return mindistances
Find Itinerary (Medium)
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
Note:
If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].
All airports are represented by three capital letters (IATA code).
You may assume all tickets form at least one valid itinerary.
One must use all the tickets once and only once.
create graph ([origin, destination] of tickets)
sort the lists of each origin lexicographically
(sort((a, b) => a.localeCompare(b))
dfs(‘JFK’)
dfs:
if flightMap has origin, shift items off destination list and dfs(dest) until destination list empty
result.unshift(origin)
return result
Time - O(E log (E/V))
Space - O(E + V)
Island Perimeter (Easy)
You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.
init perimeter as 0 linear scan grid if grid[r][c] = 0 continue check 4 directions if in bounds and grid[newRow][newCol] = 0, perimeter++ else out of bounds and perimeter++
Time - O(rc)
Space - O(1)
Accounts Merge (Medium)
Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.
Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.
After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.
create map of email to name create graph iterate through accounts [name, ...emails] emailToName.set(emails[0], name) iterate through emails graph.set(emails[0], new Set()) graph.get(emails[0]).add(email) graph.set(email, new Set()) graph.get(email).add(emails[0])
create set to track visited create array to hold result iterate through emails of graph.keys() if visited does not have email add to stack, add to visited account = [email] while (stack.length) pop start from stack iterate through graph.get(start) items if visited does not have item account.push(item) stack.push(item) visited.add(item)
once stack is empty, sort account
unshift emailToName.get(email) to add name to start of account
result.push(account)
return result
Is Graph Bipartite? (Medium)
Given an undirected graph, return true if and only if it is bipartite.
Recall that a graph is bipartite if we can split its set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.
create map of colors
assume isValid = true
iterate through each graph (so long as isValid)
dfs(graph, i, colors)
dfs:
grab node from graph by index
if colors does not have index, set it with default color
iterate through neighbors
neighborIndex = 0; neighborIndex < node.length
neighbor = graph[neighborIndex]
if colors does not have neighbor, set to opposite of node and dfs
if colors does have neighbor, return false if its same color as node
otherwise return true
Time - O(V + E)
Space - O(V) to store colors
Shortest Bridge (Medium)
In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)
Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.
Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)
create queue set discovered false linear scan to find first land, then dfs and pass in queue set discovered true and break break bfs(A, queue)
dfs: check bounds and that grid[r][c] = 1 otherwise return set to -1 to track visited push to queue to track for bfs later check 4 directions and dfs
bfs:
set step to 0,
while queue.length
size = queue.length
iterate through size, shift item from queue
check 4 directions
if in bounds
if grid[newRow][newCol] = 0, set to -1 and push newRow, newCol to queue
else if grid[newRow][newCol] = 1, we reached other island, return step
step++
Time - O(A)
Space - O(A)
Rotting Oranges (Medium)
In a given grid, each cell can have one of three values:
the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) 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 instead.
set fresh oranges to 0, create empty queue linear scan grid if grid[r][c] = 2 (rotten), push [r, c] to queue else if grid[r][c] = 1 (fresh), fresh oranges++ if fresh oranges = 0, return 0 set minutesElapsed to -1 while (queue.length) size = queue.length iterate through size shift off [r, c] check 4 directions if in bounds if newRow, newCol = 1 (fresh orange), set to 2 (rotten) decrement fresh oranges push newRow, newCol to queue minutesElapsed++
return minutesElapsed if all oranges rotten otherwise -1
Time - O(N)
Space - O(N)
Critical Connections in a Network (Hard)
There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some server unable to reach some other server.
Return all critical connections in the network in any order.
tarjans create graph iteration through [a, b] of connections undirected so set both graph.set(a, new Set()) graph.get(a).add(b) graph.set(b, new Set()) graph.get(b).add(a)
criticalEdges = [] times = new Map() time = 0 dfs(0, null) // vertex,parent return criticalEdges
dfs:
if times.has(vertex) return times.get(vertex)
val = time
times.set(vertex, time++)
get neighbors and iterate (graph.get(vertex))
if (neighbor = parent) continue
next = dfs(neighbor, vertex)
if (val < next) criticalEdges.push([vertex, neighbor])
times.set(vertex, min(next, times.get(vertex))
return times.get(vertex)
Minimum Time to Collect All Apples in a Tree (Medium)
Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend in order to collect all apples in the tree starting at vertex 0 and coming back to this vertex.
The edges of the undirected tree are given in the array edges, where edges[i] = [fromi, toi] means that exists an edge connecting the vertices fromi and toi. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple, otherwise, it does not have any apple.
create map sort edges a[0] - b[0] for const edge of edges if map has edge[1], map.set(edge[0], edge[1]) else map.set(edge[1], edge[0])
result = 0 i = 0 i < hasApple.length i++ if (!hasApple[i]) continue p = i while p != 0 and map.get(p) >= 0 temp = map.get(p) map.set(p, -1) p = temp result += 2
return result
