Graphs

A graph is a collection of nodes (vertices) and connections (edges) between those nodes.

Edges can be directed or undirected:

• Directed means we can only traverse in one direction
• Undirected means we can traverse in both directions

Other concepts:

• Connected Component: Group of nodes that are connected by edges.
• Indegree: The number of edges that can be used to reach the node.
• Outdegree: The number of edges that can be used to leave the node.

Input format:

• Array of edges
• Adjacency list
• Adjacency matrix

Graphs - DFS

Note

Time complexity of DFS is usually O(n + e) where n is number of nodes and e is number of edges since we visit each node once and iterate through each edge once.

547. Number of Provinces

Problem Description - Medium

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

from collections import defaultdict

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        # Build the graph, use a set seen to keep tracks of visited node; 
        # Iterate through all nodes, for each un-visited node, run the dfs traversal from node
        # which will visit all nodes in connected component
        # The number of times we start dfs traversal = number of connected components

        # Build the graph
        n = len(isConnected)
        graph = defaultdict(list)
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    graph[i].append(j)
                    graph[j].append(i)

        seen = set()  # keep tracks of visited nodes
        ans = 0

        def dfs(node):
            # Using DFS to visit every node in a connected component
            for neighbor in graph[node]:
                if neighbor not in seen:
                    # Add to seen to prevent cycles
                    seen.add(neighbor)
                    dfs(neighbor)

        # Traverse the nodes
        for i in range(n):
            if i not in seen:
                # Add all nodes of a connected component to a set
                seen.add(i)
                dfs(i)
                ans += 1
        return ans

        # Time for DFS on the graphs: O(n + e) where n is the number of nodes; e is number of edges
        # worst case: when all nodes connected together e = n^2
        # Time building the graph hashmap: O(n^2)
        # Total: O(n^2)
        # Space: Build hash map store all edges O(e); recursion stack O(n) => total O(n+e)

200. Number of islands

Problem Description - Medium

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.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)  # number of rows
        n = len(grid[0])  # number of columns
        directions = [(0, 1), (1,0), (0, -1), (-1, 0)]
        seen = set()

        def valid(row, col):
            # Helper function to check if a square is in bounds and is land
            return 0 <= row < m and 0 <= col < n and grid[row][col] == '1'

        def dfs(row, col):
            for dx, dy in directions:
                next_row, next_col = row + dy, col + dx
                if valid(next_row, next_col) and (next_row, next_col) not in seen:
                    seen.add((next_row, next_col))
                    dfs(next_row, next_col)

        ans = 0
        for row in range(m):
            for col in range(n):
                if grid[row][col] == '1' and (row, col) not in seen:
                    ans += 1
                    seen.add((row, col))
                    dfs(row, col)                    

        return ans
        # Time: O(mn) - visit each node once
        # Space: use set seen, worst case contains all nodes => O(mn)

1466. Reorder Routes to Make All Paths Lead to the City Zero

Problem Description - Medium

There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city `0. Return the minimum number of edges changed.

It's guaranteed that each city can reach city 0 after reorder.

from collections import defaultdict

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        # There is only one way to travel btw 2 cities. For every city to reach 0, all edges must point
        # toward 0
        # Build a graph, Start a dfs from node 0, iterate through all neighbors that are unvisited,
        # if (node, neighbor) in roads, meaning moving away from 0, need to swap, increase ans by 1
        # Continue DFS on neighbor

        # Build the graph
        roads = set()

        graph = defaultdict(list)
        for x, y in connections:
            graph[x].append(y)
            graph[y].append(x)
            roads.add((x, y))

        seen = {0}

        def dfs(node):
            ans = 0
            for neighbor in graph[node]:
                if neighbor not in seen:
                    if (node, neighbor) in roads:
                        ans += 1
                    seen.add(neighbor)
                    ans += dfs(neighbor)

            return ans
        return dfs(0)
        # Time: O(n) - visit each city once
        # Space: all edges n - 1 => graph, seen, roads all at most n => O(n)

841. Keys and Rooms

Problem Description - Medium

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        # Travel all rooms, use a set seen to record visited nodes
        # Return true if len(seen) equal len(rooms)
        seen = set()
        def dfs(node):
            for neighbor in rooms[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    dfs(neighbor)
        seen = {0}
        dfs(0)
        return len(seen) == len(rooms)

1557. Minimum Number of Vertices to Reach All Nodes

Problem Description - Medium

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi.

Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        # The  node with indegree = 0 cannot be reached from other nodes => that node
        # can reach other nodes
        # Find the number of nodes that can not be reached from other nodes
        indegrees = [0] * n
        for _, y in edges:
            indegrees[y] += 1

        return [node for node in range(n) if indegrees[node] == 0]

1971. Find if Path Exists in Graph

Problem Description - Easy

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

from collections import defaultdict

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = defaultdict(list)
        seen = {source}
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)

        def dfs(node):
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    dfs(neighbor)
        dfs(source)
        return destination in seen

323. Number of Connected Components in an Undirected Graph

Problem Description - Medium

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.

from collections import defaultdict

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        seen = set()
        graph = defaultdict(list)
        ans = 0
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)

        def dfs(node):
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    dfs(neighbor)

        for i in range(n):
            if i not in seen:
                seen.add(i)
                ans += 1
                dfs(i)
        return ans

695. Max Area of Island

Problem Description - Medium

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.

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        seen = set()
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n and grid[row][col] == 1

        def dfs(row, col):
            if not (valid(row, col) and (row, col) not in seen):
                return 0
            seen.add((row, col))
            return 1 + dfs(row+1, col) + dfs(row-1, col) + dfs(row, col+1) + dfs(row, col-1)

        ans = 0
        for row in range(m):
            for col in range(n):
                ans = max(ans, dfs(row, col))
        return ans

2368. Reachable Nodes With Restrictions

Problem Description - Medium

There is an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.

You are given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given an integer array restricted which represents restricted nodes.

Return the maximum number of nodes you can reach from node 0 without visiting a restricted node.

Note that node 0 will not be a restricted node.

from collections import defaultdict

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        graph = defaultdict(list)
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)

        seen = {0}
        for node in restricted:
            seen.add(node)
        self.ans = 0
        def dfs(node):
            self.ans += 1
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    dfs(neighbor)

        dfs(0)
        return self.ans

Graph - BFS

Note

BFS visits nodes according to distance from the starting point. Every time, a node is visited, BFS guarantees the shortest path from starting point. We use queue to implement BFS.

1091. Shortest Path in Binary Matrix

Problem Description - Medium

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.
• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1:
            return -1

        def valid(row, col):
            return 0 <= row < n and 0 <= col < n and grid[row][col] == 0

        directions = [(0,1), (1, 0), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        seen = {(0, 0)}
        queue = deque([(0, 0, 1)])  # row, col, steps
        while queue:
            row, col, steps = queue.popleft()
            if (row, col) == (n -1, n - 1):
                return steps
            for dx, dy in directions:
                next_row, next_col = row + dy, col + dx
                if valid(next_row, next_col) and (next_row, next_col) not in seen:
                    seen.add((next_row, next_col))
                    queue.append((next_row, next_col, steps + 1))

        return -1
        # Time: visit each node once, O(n^2)
        # Space: seen can grow to O(n^2)

863. All Nodes Distance K in Binary Tree

Problem Description - Medium

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

You can return the answer in any order.

from collections import deque

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        # Convert a tree to undirected graph using dfs, assign parent pointer to each node
        # Using bfs from target node and return all nodes at distance k
        # Build graph
        def dfs(node, parent):
            if not node:
                return
            node.parent = parent
            dfs(node.left, node)
            dfs(node.right, node)

        dfs(root, None)
        # Use bfs
        seen = {target}
        queue = deque([target])
        distance = 0
        while queue and distance < k:
            curr_len = len(queue)
            for _ in range(curr_len):
                node = queue.popleft()
                for neighbor in [node.left, node.right, node.parent]:
                    if neighbor and neighbor not in seen:
                        seen.add(neighbor)
                        queue.append(neighbor)
            distance += 1
        return [node.val for node in queue]
        # Time: dfs, bfs visit each node once => O(n)
        # Time: seen can grow to n => O(n); dfs recursion stack = height of tree, worst case O(n)

542. 01 Matrix

Problem Description - Medium

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

from collections import deque

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        # Only need to update for cells with value of 1, all 0 cells don't need to update
        # Use a set seen to record visited nodes
        # Doing BFS, start from all zeros, when visit 1, update mat with value of steps
        # to reach 1
        m = len(mat)
        n = len(mat[0])
        directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
        seen = set()
        queue = deque()
        # Add all zeros to queue to start BFS from zeros
        for row in range(m):
            for col in range(n):
                if mat[row][col] == 0:
                    seen.add((row, col))
                    queue.append((row, col, 1))

        def valid(row, col):
            return 0 <= row < m and 0 <= col < n and mat[row][col] == 1
        # Doing BFS
        while queue:
            row, col, steps = queue.popleft()
            for dx, dy in directions:
                next_row, next_col = row + dy, col + dx
                if valid(next_row, next_col) and (next_row, next_col) not in seen:
                    seen.add((next_row, next_col))                    
                    queue.append((next_row, next_col, steps + 1))
                    # Update mat with steps value
                    mat[next_row][next_col] = steps
        return mat
        # Time - Visit each node once O(mn)
        # Space - Both seen, queue can grow up to mn => O(mn)

1293. Shortest Path in a Grid with Obstacles Elimination

Problem Description - Hard

You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

from collections import deque

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        # Associate extra info remain to node (remain removals on current path)
        # Use seen to store state with (row, col, remain)
        # when visiting 0, check state has not been seen, not modify remain
        # when visiting 1, check state has not been seen and remain > 0, reduce remain by 1
        # Use BFS with queue to store (row, col, steps, remain), when visit (m-1, n-1)
        # return current steps
        m = len(grid)
        n = len(grid[0])
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        seen = set()
        queue = deque([(0, 0, 0, k)])  # row, col, steps, remain removals

        def valid(row, col):
            return 0 <= row < m and 0 <= col < n

        while queue:
            row, col, steps, remain = queue.popleft()
            if (row, col) == (m - 1, n - 1) and remain >= 0:
                return steps
            for dx, dy in directions:
                next_row, next_col = row + dy, col + dx
                if valid(next_row, next_col):
                    if grid[next_row][next_col] == 0:
                        if (next_row, next_col, remain) not in seen:
                            seen.add((next_row, next_col, remain))
                            queue.append((next_row, next_col, steps + 1, remain))
                    elif remain and (next_row, next_col, remain - 1) not in seen:
                            seen.add((next_row, next_col, remain - 1))
                            queue.append((next_row, next_col, steps + 1, remain - 1))

        return -1
        # Time: Visit all states: O(m.n.k)
        # Space: Seen can grows up to m.n.k => O(m.n.k)

1129. Shortest Path with Alternating Colors

Problem Description - Medium

You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays redEdges and blueEdges where:

• redEdges[i] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and
• blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in the graph.

Return an array answer of length n, where each answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or -1 if such a path does not exist.

from collections import defaultdict, deque

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        # Add extra info color to node, record state (node, color) indicate the expecting color of next edge
        # assign RED, BLUE = 0, 1. Initiate with (0, BLUE) and (0, RED)
        # Using BFS, when visiting node x, checking the color alternate conditions
        # update ans[x] with min steps
        RED, BLUE = 0, 1
        graph = defaultdict(lambda : defaultdict(list))
        for x, y in redEdges:
            graph[RED][x].append(y)
        for x, y in blueEdges:
            graph[BLUE][x].append(y)
        seen = set({(0, RED), (0, BLUE)})  # node, color
        queue = deque([(0, 0, RED), (0, 0, BLUE)])  # node, steps, color
        ans = [float('inf')] * n
        while queue:
            node, steps, color = queue.popleft()
            ans[node] = min(ans[node], steps)
            # Flip color by checking 1 - color
            for neighbor in graph[color][node]:
                if (neighbor, 1 - color) not in seen:
                    seen.add((neighbor, 1 - color))
                    queue.append((neighbor, steps + 1, 1 - color))
        return [x if x != float('inf') else -1 for x in ans]
        # Time: O(n+e)
        # Space: O(n+e)

1926. Nearest Exit from Entrance in Maze

Problem Description - Medium

You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

from collections import deque

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        # Start BFS at entrance, traverse only on the empty cells,
        # if it can reach the border, return min steps; -1 if can not reach
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        m, n = len(maze), len(maze[0])
        seen = set()
        start_row, start_col = entrance
        seen.add((start_row, start_col))
        queue = deque([(start_row, start_col, 0)])
        def valid(row, col):
            return 0 <= row < m and 0 <= col < n and maze[row][col] == '.'

        while queue:
            row, col, steps = queue.popleft()
            # if we hit the border, return steps
            if (row in {0 , m - 1} or col in {0, n - 1}) and steps:
                return steps
            for dx, dy in directions:
                next_row, next_col = row + dy, col + dx

                if valid(next_row, next_col) and (next_row, next_col) not in seen:
                    seen.add((next_row, next_col))
                    queue.append((next_row, next_col, steps + 1))

        return -1
        # Time and space: O(m.n)

909. Snake and Ladders

Problem Description - Medium

You are given an n x n integer matrix board where the cells are labeled from 1 to \(n^2\) in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

• Choose a destination square next with a label in the range \([curr + 1, min(curr + 6, n^2)]\).
• This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
• If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
• The game ends when you reach the square \(n^2\).

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and \(n^2\) do not have a snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

• For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of moves required to reach the square \(n^2\). If it is not possible to reach the square, return -1.