Graph Algorithm Summaries
Jul 26, 2024
Here are the Blind 75 Graph Algorithm Summaries. Click to see previous post on binary algorithms. Graph data structures are used to represent relationships between data. The graph is composed of Nodes and Edges, where the Node holds some piece of data, and Edges connect Nodes together either with a directed or undirected relationship.
Clone Graph
Given a node from a connected graph, return a copy of the graph.
Solution with O(N) Time / O(N) Space
Recursively follow the starting node’s neighbors, making a copy of each node, and also saving the nodes to a hash map. When you encounter a node already in the hashmap, return the saved result.
Course Schedule
Given an array of course prerequisite pairs (i.e. graph nodes), find out if there's a cycle in the graph.
Solution with O(N+P) Time / O(N) Space where N is the number of courses and P is the number of prerequisites
Save a hash map of the courses → all the prerequisites. Follow each node until it either ends or leads to an already visited node. If you visit a node more than once then there is a cycle.
Pacific Atlantic Water Flow
Given a 2D array of height values, size m x n, find the peaks where height descends both to the top left and bottom right sides.
Solution with O(MN) Time / O(MN) Space
Start from the oceans, and recursively follow all ascending paths, the intersection of the visited paths from the top left and bottom right is the answer. Save visited paths in a set to reduce time complexity.
Number of Islands
Given a 2D array, size m x n, with 0’s representing water and 1’s representing land, find the number of islands.
Solution with O(MN) Time / O(MN) Space
Iterate through the entire array. For each land spot, search the array in all adjacent directions, saving land to a separate 2D array. Skip visited land in subsequent searches. The amount of times you start an adjacent land search is the answer.
Longest Consecutive Sequence
Given an unsorted array of integers, return the longest sequence of consecutive numbers within the array.
Solution with O(N) Time / O(N) Space
Add all numbers to a set. Iterate through the array, for each number, find the length of its sequence by incrementing/decrementing the number until the numbers aren't in the set. Remove those numbers from the set to avoid checking the same sequence again.
Alien Dictionary (Leetcode Premium)
Given a list of words from a foreign language ordered lexicographically (but still using latin characters), find the order of each letter.
Solution with O(N) Time / O(N) Space
Iterate through adjacent words, finding the first different letter of each word to determine all the combinations of letter orderings. Create an initial graph showing a set of all the characters that come before each letter in the words.
For each letter in the graph, recurse through all the letters that come before it, until you find the first letter with no letters before. End the recursion by adding the letters to a result list, giving you the order (which will be the reverse order that the calls were started).
Graph Valid Tree (Leetcode Premium)
Given a list of edges using numbers from 0 to the given number n, determine if the edges make up a valid tree that is: connected, and doesn’t have any cycles.
Solution with O(N) Time / O(N) Space
First, create a map from each node to all the nodes it connects to. Then, recurse the tree from any node (like 0), saving a set of all nodes visited. The tree is invalid if you ever visit a node twice, or if number of nodes visited is less than n.
Number of Connected Components in an Undirected Graph (Leetcode Premium)
Given n number of nodes in a graph, and an array of edges in the graph, find the number of separate disconnected components. (Note, to be clear, it seems like we can assume the nodes will be numbered 0 to n-1, so we can initialize helper data structures as arrays of size n instead of using a map)
Solution with O(N) Time / O(N) Space
Generate a “parent” array of size n, where each element’s value is equal to the index. The array will be used to track links between nodes, where the node is represented by the index, and the value is the linked node. Notice how we only care about which nodes are connected, so there a multiple valid ways to represent the connected components.
Iterate through the edges, linking the two nodes using the parent array, either by updating the value of the left node to the index of the right node, or vice versa.
Iterate through the nodes (i.e. 0 to n-1), for each node, check if the parent is still itself, if so, increment the result by 1 (because each disconnected component will have one starting node that wasn't updated above).