Graphs, Advanced Graphs

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

Graphはその場で考えるのももちろん必要だけど、DFS, BFSはもちろん、Union Find、トポロジカルソート、ダイクストラ、ベルマンフォードなどなど覚えなきゃいけないアルゴリズムも多いので、こういう風にまとめておいて定期的に振り返るのが大事。ちょっと量が多くなるがGraphs, Advanced Graphsは一緒に振り返りたいので同じ記事にまとめておく。NeetCodeのRoadMap的にはBacktrackingの後に来ているが、BacktrackingはDPの直前にまとめておきたいのと、DPは個人的には最難関なので気合いを入れてやりたいので、先にGraphからやる。

86. Number of Islands

Problem

Given a 2D grid grid where '1' represents land and '0' represents water, count and return the number of islands.

An island is formed by connecting adjacent lands horizontally or vertically and is surrounded by water. You may assume water is surrounding the grid (i.e., all the edges are water).

Example 1:

Input: grid = [
    ["0","1","1","1","0"],
    ["0","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
  ]
Output: 1

Copy

Example 2:

Input: grid = [
    ["1","1","0","0","1"],
    ["1","1","0","0","1"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
  ]
Output: 4

Copy

Constraints:

• 1 <= grid.length, grid[i].length <= 100
• grid[i][j] is '0' or '1'.

Solution

DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        # up, right, down, left
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]
        count = 0
        visited = set()

        def dfs(r: int, c: int) -> None:
            if (r not in range(ROWS) or
                c not in range(COLS) or
                (r,c) in visited or 
                grid[r][c] == '0'
                ):
                return
            
            visited.add((r,c))

            for dr, dc in DIRECTIONS:
                nr, nc = r + dr, c + dc
                dfs(nr, nc)
        
        for r in range(ROWS):
            for c in range(COLS):
                if (grid[r][c] == '1' and 
                    (r,c) not in visited):
                    dfs(r, c)
                    count += 1
        
        return count

BFS

from collections import deque
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        # up, right, down, left
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]
        count = 0
        visited = set()

        def bfs(r: int, c: int) -> None:
            queue = deque([(r,c)])

            while queue:
                q_size = len(queue)
                for i in range(q_size):
                    old_r, old_c = queue.popleft()
                    visited.add((old_r, old_c))

                    for dr, dc in DIRECTIONS:
                        nr, nc = old_r + dr, old_c + dc
                        
                        if (nr not in range(ROWS) or
                            nc not in range(COLS) or
                            (nr,nc) in visited or 
                            grid[nr][nc] == '0'
                            ):
                            continue

                        queue.append((nr, nc))
        
        for r in range(ROWS):
            for c in range(COLS):
                if (grid[r][c] == '1' and 
                    (r,c) not in visited):
                    bfs(r, c)
                    count += 1
        
        return count

87. Max Area of Island

Problem

You are given a matrix grid where grid[i] is either a 0 (representing water) or 1 (representing land).

An island is defined as a group of 1's connected horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

The area of an island is defined as the number of cells within the island.

Return the maximum area of an island in grid. If no island exists, return 0.

Example 1:

Input: grid = [
  [0,1,1,0,1],
  [1,0,1,0,1],
  [0,1,1,0,1],
  [0,1,0,0,1]
]

Output: 6

Copy

Explanation: 1's cannot be connected diagonally, so the maximum area of the island is 6.

Constraints:

• 1 <= grid.length, grid[i].length <= 50

Solution

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        # up, right, down, left
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]
        visited = set()
        max_area = 0

        def dfs(r: int, c: int) -> int:
            if (r not in range(ROWS) or
                c not in range(COLS) or
                (r,c) in visited or
                grid[r][c] == 0
                ):
                return 0

            visited.add((r,c))
            
            area = 1
            for dr, dc in DIRECTIONS:
                nr, nc = r + dr, c + dc
                area += dfs(nr, nc)
            
            return area
        
        for r in range(ROWS):
            for c in range(COLS):
                if ((r,c) not in visited and
                    grid[r][c] == 1
                    ):
                    max_area = max(max_area, dfs(r, c))
        
        return max_area    

ちなみに以下だとだめ！以下のようなパターンの時に破綻する(本当は3なのに、累積値だけを見ているのでmax_areaが2になる)

[

[0, 1, 1],

[0, 1, 0]

]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        # up, right, down, left
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]
        max_area = 0
        visited = set()

        def dfs(r: int, c: int, area: int) -> None:
            nonlocal max_area

            if (r not in range(ROWS) or
                c not in range(COLS) or
                (r,c) in visited or
                grid[r][c] == 0
                ):
                return
            
            area += 1
            max_area = max(max_area, area)
            visited.add((r,c))

            for dr, dc in DIRECTIONS:
                nr, nc = r + dr, c + dc
                dfs(nr, nc, area)
            
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1 and (r,c) not in visited:
                    dfs(r, c, 0)

        return max_area
    

88. Clone Graph

Problem

Given a node in a connected undirected graph, return a deep copy of the graph.

Each node in the graph contains an integer value and a list of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

Copy

The graph is shown in the test cases as an adjacency list. An adjacency list is a mapping of nodes to lists, used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

For simplicity, nodes values are numbered from 1 to n, where n is the total number of nodes in the graph. The index of each node within the adjacency list is the same as the node's value (1-indexed).

The input node will always be the first node in the graph and have 1 as the value.

Example 1:

Input: adjList = [[2],[1,3],[2]]

Output: [[2],[1,3],[2]]

Copy

Explanation: There are 3 nodes in the graph.
Node 1: val = 1 and neighbors = [2].
Node 2: val = 2 and neighbors = [1, 3].
Node 3: val = 3 and neighbors = [2].

Example 2:

Input: adjList = [[]]

Output: [[]]

Copy

Explanation: The graph has one node with no neighbors.

Example 3:

Input: adjList = []

Output: []

Copy

Explanation: The graph is empty.

Constraints:

• 0 <= The number of nodes in the graph <= 100.
• 1 <= Node.val <= 100
• There are no duplicate edges and no self-loops in the graph.

Solution

"""
# 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 []
"""

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        old_new_map = {}
        
        def dfs(n: Node) -> Node:
            if not n:
                return None
            
            if n in old_new_map:
                return old_new_map[n]
        
            copy = Node(n.val)
            old_new_map[n] = copy
            
            for nei in n.neighbors:
                copy_nei = dfs(nei)
                old_new_map[n].neighbors.append(copy_nei)

            return old_new_map[n]
        
        return dfs(node)

89. Walls And Gates

Problem

You are given a m×nm×n 2D grid initialized with these three possible values:

1. -1 - A water cell that can not be traversed.
2. 0 - A treasure chest.
3. INF - A land cell that can be traversed. We use the integer 2^31 - 1 = 2147483647 to represent INF.

Fill each land cell with the distance to its nearest treasure chest. If a land cell cannot reach a treasure chest than the value should remain INF.

Assume the grid can only be traversed up, down, left, or right.

Example 1:

Input: [
  [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]
]

Copy

Example 2:

Input: [
  [0,-1],
  [2147483647,2147483647]
]

Output: [
  [0,-1],
  [1,2]
]

Copy

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• grid[i][j] is one of {-1, 0, 2147483647}

Solution

from collections import deque

class Solution:
    def islandsAndTreasure(self, grid: List[List[int]]) -> None:
        ROWS, COLS = len(grid), len(grid[0])
        queue = deque()        
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]
        INF = 2147483647

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 0:
                    queue.append((r,c))
        
        while queue:
            q_size = len(queue)
            for i in range(q_size):
                r, c = queue.popleft()

                for dr, dc in DIRECTIONS:
                    nr, nc = r + dr, c + dc
                    if (nr in range(ROWS) and
                        nc in range(COLS) and
                        grid[nr][nc] == INF
                        ):
                        grid[nr][nc] = grid[r][c] + 1
                        queue.append((nr,nc))

90. Rotting Oranges

Problem

You are given a 2-D matrix grid. Each cell can have one of three possible values:

• 0 representing an empty cell
• 1 representing a fresh fruit
• 2 representing a rotten fruit

Every second, if a fresh fruit is horizontally or vertically adjacent to a rotten fruit, then the fresh fruit also becomes rotten.

Return the minimum number of seconds that must elapse until there are zero fresh fruits remaining. If this state is impossible within the grid, return -1.

Example 1:

Input: grid = [[1,1,0],[0,1,1],[0,1,2]]

Output: 4

Copy

Example 2:

Input: grid = [[1,0,1],[0,2,0],[1,0,1]]

Output: -1

Copy

Constraints:

• 1 <= grid.length, grid[i].length <= 10

Solution

from collections import deque
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        queue = deque()
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]
        fresh_count = 0
        rotten_count = 0

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 2:
                    queue.append((r,c))
                    rotten_count += 1
                elif grid[r][c] == 1:
                    fresh_count += 1
        
        if fresh_count == 0:
            return 0
            
        if rotten_count == 0:
            return -1

        count = -1
        while queue:
            q_size = len(queue)
            count += 1
            for _ in range(q_size):
                r, c = queue.popleft()
                for dr, dc in DIRECTIONS:
                    nr, nc = r + dr, c + dc
                    
                    if (nr in range(ROWS) and
                        nc in range(COLS) and
                        grid[nr][nc] == 1
                        ):
                        grid[nr][nc] = 2
                        fresh_count -= 1
                        queue.append((nr,nc))
        
        return count if fresh_count == 0 else -1

91. Pacific Atlantic Water Flow

Problem

You are given a rectangular island heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The islands borders the Pacific Ocean from the top and left sides, and borders the Atlantic Ocean from the bottom and right sides.

Water can flow in four directions (up, down, left, or right) from a cell to a neighboring cell with height equal or lower. Water can also flow into the ocean from cells adjacent to the ocean.

Find all cells where water can flow from that cell to both the Pacific and Atlantic oceans. Return it as a 2D list where each element is a list [r, c] representing the row and column of the cell. You may return the answer in any order.

Example 1:

Input: heights = [
  [4,2,7,3,4],
  [7,4,6,4,7],
  [6,3,5,3,6]
]

Output: [[0,2],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4],[2,0]]

Copy

Example 2:

Input: heights = [[1],[1]]

Output: [[0,0],[0,1]]

Copy

Constraints:

• 1 <= heights.length, heights[r].length <= 100
• 0 <= heights[r][c] <= 1000

Solution

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        ROWS, COLS = len(heights), len(heights[0])
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]
        pac = set()
        atl = set()

        def dfs(r: int, c: int, visited: set, prev: int) -> None:
            if (r not in range(ROWS) or
                c not in range(COLS) or
                (r,c) in visited or
                heights[r][c] < prev
                ):
                return
            
            visited.add((r,c))
            for dr, dc in DIRECTIONS:
                nr, nc = r + dr, c + dc
                dfs(nr, nc, visited, heights[r][c])

        for r in range(ROWS):
            for c in range(COLS):
                if r == 0 or c == 0:
                    # pac沿岸
                    dfs(r, c, pac, -1)
                if r == ROWS-1 or c == COLS-1:
                    # atl沿岸
                    dfs(r, c, atl, -1)
        
        res = []
        for r in range(ROWS):
            for c in range(COLS):
                if (r,c) in pac and (r,c) in atl:
                    res.append([r,c])
            
        return res

92. Surrounded Regions

Problem

You are given a 2-D matrix board containing 'X' and 'O' characters.

If a continous, four-directionally connected group of 'O's is surrounded by 'X's, it is considered to be surrounded.

Change all surrounded regions of 'O's to 'X's and do so in-place by modifying the input board.

Example 1:

Input: board = [
  ["X","X","X","X"],
  ["X","O","O","X"],
  ["X","O","O","X"],
  ["X","X","X","O"]
]

Output: [
  ["X","X","X","X"],
  ["X","X","X","X"],
  ["X","X","X","X"],
  ["X","X","X","O"]
]

Copy

Explanation: Note that regions that are on the border are not considered surrounded regions.

Constraints:

• 1 <= board.length, board[i].length <= 200
• board[i][j] is 'X' or 'O'.

Solution

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        ROWS, COLS = len(board), len(board[0])
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]

        def dfs(r: int, c: int) -> None:
            if (r not in range(ROWS) or
                c not in range(COLS) or
                board[r][c] != 'O'
                ):
                return
            
            board[r][c] = 'T'

            for dr, dc in DIRECTIONS:
                nr, nc = dr + r, dc + c
                dfs(nr, nc)
        
        for r in range(ROWS):
            for c in range(COLS):
                if ((r == 0 or 
                    c == 0 or 
                    r == ROWS-1 or 
                    c == COLS-1) and
                    board[r][c] == 'O'
                    ):
                    dfs(r, c)
        
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
        
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == 'T':
                    board[r][c] = 'O'

93. Course Schedule

Problem

You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a.

The pair [0, 1], indicates that must take course 1 before taking course 0.

There are a total of numCourses courses you are required to take, labeled from 0 to numCourses - 1.

Return true if it is possible to finish all courses, otherwise return false.

Example 1:

Input: numCourses = 2, prerequisites = [[0,1]]

Output: true

Copy

Explanation: First take course 1 (no prerequisites) and then take course 0.

Example 2:

Input: numCourses = 2, prerequisites = [[0,1],[1,0]]

Output: false

Copy

Explanation: In order to take course 1 you must take course 0, and to take course 0 you must take course 1. So it is impossible.

Constraints:

• 1 <= numCourses <= 1000
• 0 <= prerequisites.length <= 1000
• All prerequisite pairs are unique.

Solution

from collections import defaultdict, deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        from_to_map = defaultdict(list) # from -> to
        in_degrees = [0] * numCourses # 自分に向かってくる矢印の数

        for from_c, to_c in prerequisites:
            from_to_map[from_c].append(to_c)
            in_degrees[to_c] += 1

        queue = deque()
        for i in range(len(in_degrees)):
            if in_degrees[i] == 0:
                # 自分に向かってくる矢印がないコースを追加
                queue.append(i)

        ordered = []

        while queue:
            course = queue.popleft()
            ordered.append(course)

            for to_course in from_to_map[course]:
                in_degrees[to_course] -= 1
                if in_degrees[to_course] == 0:
                    queue.append(to_course)
        
        # トポロジカルソートされた後の配列とコース数が等しければ
        # Cycleは検知されなかったので終了できる
        return len(ordered) == numCourses

94. Course Schedule II

Problem

You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

There are a total of numCourses courses you are required to take, labeled from 0 to numCourses - 1.

Return a valid ordering of courses you can take to finish all courses. If there are many valid answers, return any of them. If it's not possible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 3, prerequisites = [[1,0]]

Output: [0,1,2]

Copy

Explanation: We must ensure that course 0 is taken before course 1.

Example 2:

Input: numCourses = 3, prerequisites = [[0,1],[1,2],[2,0]]

Output: []

Copy

Explanation: It's impossible to finish all courses.

Constraints:

• 1 <= numCourses <= 1000
• 0 <= prerequisites.length <= 1000
• All prerequisite pairs are unique.

Solution

from collections import defaultdict

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        from_to_map = defaultdict(list)
        in_degrees = [0] * numCourses

        for from_c, to_c in prerequisites:
            from_to_map[from_c].append(to_c)
            in_degrees[to_c] += 1
        
        queue = deque()
        for i in range(len(in_degrees)):
            if in_degrees[i] == 0:
                queue.append(i)
        
        ordered = []

        while queue:
            course = queue.popleft()
            ordered.append(course)

            for to_c in from_to_map[course]:
                in_degrees[to_c] -= 1

                if in_degrees[to_c] == 0:
                    queue.append(to_c)
        
        if len(ordered) == numCourses:
            ordered.reverse()
            return ordered
        else:
            return []

95. Graph Valid Tree

Problem

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Example 1:

Input:
n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]

Output:
true

Copy

Example 2:

Input:
n = 5
edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]

Output:
false

Copy

Note:

• You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Constraints:

• 1 <= n <= 100
• 0 <= edges.length <= n * (n - 1) / 2

Solution

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        parents = [i for i in range(n)]
        ranks = [1] * n

        def find(c: int) -> int:
            while c != parents[c]:
                parents[c] = parents[parents[c]]
                c = parents[c]
            return c
        
        def unite(c1: int, c2: int) -> bool:
            p1 = findParent(c1)
            p2 = findParent(c2)

            if p1 == p2:
                # 同じ親である場合はサイクルがある
                return False
            
            r1 = ranks[p1]
            r2 = ranks[p2]
            if r1 <= r2:
                parents[p1] = p2
                ranks[p2] += r1
            else:
                parents[p2] = p1
                ranks[p1] += r2
            
            return True
        
        for e1, e2 in edges:
            if not unite(e1, e2):
                return False
        
        for i in range(n):
            findParent(i)

        return len(set(parents)) == 1

96. Number of Connected Components In An Undirected Graph

Problem

There is an undirected graph with n nodes. There is also an edges array, where edges[i] = [a, b] means that there is an edge between node a and node b in the graph.

The nodes are numbered from 0 to n - 1.

Return the total number of connected components in that graph.

Example 1:

Input:
n=3
edges=[[0,1], [0,2]]

Output:
1

Copy

Example 2:

Input:
n=6
edges=[[0,1], [1,2], [2,3], [4,5]]

Output:
2

Copy

Constraints:

• 1 <= n <= 100
• 0 <= edges.length <= n * (n - 1) / 2

Solution

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parents = [i for i in range(n)]
        ranks = [1] * n

        def find(c: int) -> int:
            while c != parents[c]:
                parents[c] = parents[parents[c]]
                c = parents[c]
            return c
        
        def unite(c1: int, c2: int) -> bool:
            p1 = find(c1)
            p2 = find(c2)

            if p1 == p2:
                return False
            
            r1 = ranks[p1]
            r2 = ranks[p2]

            if r1 >= r2:
                parents[p2] = p1
                ranks[p1] += r2
            else:
                parents[p1] = p2
                ranks[p2] += r1
            
            return True
        
        for e1, e2 in edges:
            unite(e1, e2)
        
        for i in range(n):
            find(i)

        return len(set(parents))

97. Redundant Connection

Problem

You are given a connected undirected graph with n nodes labeled from 1 to n. Initially, it contained no cycles and consisted of n-1 edges.

We have now added one additional edge to the graph. The edge has two different vertices chosen from 1 to n, and was not an edge that previously existed in the graph.

The graph is represented as an array edges of length n where edges[i] = [ai, bi] represents an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the graph is still a connected non-cyclical graph. If there are multiple answers, return the edge that appears last in the input edges.

Example 1:

Input: edges = [[1,2],[1,3],[3,4],[2,4]]

Output: [2,4]

Copy

Example 2:

Input: edges = [[1,2],[1,3],[1,4],[3,4],[4,5]]

Output: [3,4]

Copy

Constraints:

• n == edges.length
• 3 <= n <= 100
• 1 <= edges[i][0] < edges[i][1] <= edges.length
• There are no repeated edges and no self-loops in the input.

Solution

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges) + 1
        parents = [i for i in range(n)]
        ranks = [1] * n

        def find(c: int) -> int:
            while c != parents[c]:
                parents[c] = parents[parents[c]]
                c = parents[c]
            return c
        
        def unite(c1: int, c2: int) -> bool:
            p1 = find(c1)
            p2 = find(c2)

            if p1 == p2:
                return False
            
            r1 = ranks[p1]
            r2 = ranks[p2]

            if r1 >= r2:
                parents[p2] = p1
                ranks[p1] += r2
            else:
                parents[p1] = p2
                ranks[p2] += r1

            return True
        
        for e1, e2 in edges:
            if not unite(e1, e2):
                return [e1, e2]

98. Word Ladder

Problem

You are given two words, beginWord and endWord, and also a list of words wordList. All of the given words are of the same length, consisting of lowercase English letters, and are all distinct.

Your goal is to transform beginWord into endWord by following the rules:

• You may transform beginWord to any word within wordList, provided that at exactly one position the words have a different character, and the rest of the positions have the same characters.
• You may repeat the previous step with the new word that you obtain, and you may do this as many times as needed.

Return the minimum number of words within the transformation sequence needed to obtain the endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sag","dag","dot"]

Output: 4

Copy

Explanation: The transformation sequence is "cat" -> "bat" -> "bag" -> "sag".

Example 2:

Input: beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sat","dag","dot"]

Output: 0

Copy

Explanation: There is no possible transformation sequence from "cat" to "sag" since the word "sag" is not in the wordList.

Constraints:

• 1 <= beginWord.length <= 10
• 1 <= wordList.length <= 100

Solution

from collections import defaultdict, deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)
        if endWord not in wordSet:
            # endWordは必ず wordList に含まれている必要がある
            return 0
        
        asta_org_map = defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                asta = word[:i] + '*' + word[i+1:]
                asta_org_map[asta].append(word)
        
        count = 0
        queue = deque([beginWord])
        visited = set()

        while queue:
            q_size = len(queue)
            count += 1
            for i in range(q_size):
                word = queue.popleft()
                if word == endWord:
                    return count
                visited.add(word)

                for j in range(len(word)):
                    asta = word[:j] + '*' + word[j+1:]
                    for next_word in asta_org_map[asta]:
                        if next_word not in visited:
                            queue.append(next_word)
        
        return 0

99. Min Cost to Connect All Points

Problem

You are given a 2-D integer array points, where points[i] = [xi, yi]. Each points[i] represents a distinct point on a 2-D plane.

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between the two points, i.e. |xi - xj| + |yi - yj|.

Return the minimum cost to connect all points together, such that there exists exactly one path between each pair of points.

Example 1:

Input: points = [[0,0],[2,2],[3,3],[2,4],[4,2]]

Output: 10

Copy

Constraints:

• 1 <= points.length <= 1000
• -1000 <= xi, yi <= 1000

Solution

import heapq

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        total_cost = 0
        min_heap = [] # (cost, index)
        heapq.heappush(min_heap, (0, 0))
        visited = set() # index

        while len(visited) != len(points):
            cost, index = heapq.heappop(min_heap)
            if index not in visited:
                # 重複してindexが入る可能性があるため
                total_cost += cost
                visited.add(index)

            x1, y1 = points[index]
            for i in range(len(points)):
                if i not in visited:
                    x2, y2 = points[i]
                    cost = abs(x2 - x1) + abs(y2 - y1)
                    heapq.heappush(min_heap, (cost, i))
        
        return total_cost

100. Network Delay Time

Problem

You are given a network of n directed nodes, labeled from 1 to n. You are also given times, a list of directed edges where times[i] = (ui, vi, ti).

• ui is the source node (an integer from 1 to n)
• vi is the target node (an integer from 1 to n)
• ti is the time it takes for a signal to travel from the source to the target node (an integer greater than or equal to 0).

You are also given an integer k, representing the node that we will send a signal from.

Return the minimum time it takes for all of the n nodes to receive the signal. If it is impossible for all the nodes to receive the signal, return -1 instead.

Example 1:

Input: times = [[1,2,1],[2,3,1],[1,4,4],[3,4,1]], n = 4, k = 1

Output: 3

Copy

Example 2:

Input: times = [[1,2,1],[2,3,1]], n = 3, k = 2

Output: -1

Copy

Constraints:

• 1 <= k <= n <= 100
• 1 <= times.length <= 1000

Solution

from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        time = 0
        min_heap = [] # (time, target)
        visited = set()
        from_to_map = defaultdict(list) # (time, target)

        for src, tgt, ti in times:
            from_to_map[src].append((ti, tgt))

        visited.add(k)
        # time = 0 で、kから始める
        min_heap.append((0, k))

        while len(visited) != n:
            if not min_heap:
                # 全てのノードを訪れることができない
                return -1

            from_time, from_node = heapq.heappop(min_heap)
            if from_node not in visited:
                visited.add(from_node)
                time = from_time

            for take_time, to_node in from_to_map[from_node]:
                if to_node not in visited:
                    heapq.heappush(min_heap, (time + take_time, to_node))

        return time

101. Reconstruct Itinerary

Problem

You are given a list of flight tickets tickets where tickets[i] = [from_i, to_i] represent the source airport and the destination airport.

Each from_i and to_i consists of three uppercase English letters.

Reconstruct the itinerary in order and return it.

All of the tickets belong to someone who originally departed from "JFK". Your objective is to reconstruct the flight path that this person took, assuming each ticket was used exactly once.

If there are multiple valid flight paths, return the lexicographically smallest one.

• For example, the itinerary ["JFK", "SEA"] has a smaller lexical order than ["JFK", "SFO"].

You may assume all the tickets form at least one valid flight path.

Example 1:

Input: tickets = [["BUF","HOU"],["HOU","SEA"],["JFK","BUF"]]

Output: ["JFK","BUF","HOU","SEA"]

Copy

Example 2:

Input: tickets = [["HOU","JFK"],["SEA","JFK"],["JFK","SEA"],["JFK","HOU"]]

Output: ["JFK","HOU","JFK","SEA","JFK"]

Copy

Explanation: Another possible reconstruction is ["JFK","SEA","JFK","HOU","JFK"] but it is lexicographically larger.

Constraints:

• 1 <= tickets.length <= 300
• from_i != to_i

Solution

from collections import defaultdict, deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)
        if endWord not in wordSet:
            # endWordは必ず wordList に含まれている必要がある
            return 0
        
        asta_org_map = defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                asta = word[:i] + '*' + word[i+1:]
                asta_org_map[asta].append(word)
        
        count = 0
        queue = deque([beginWord])
        visited = set()

        while queue:
            q_size = len(queue)
            count += 1
            for i in range(q_size):
                word = queue.popleft()
                if word == endWord:
                    return count
                visited.add(word)

                for j in range(len(word)):
                    asta = word[:j] + '*' + word[j+1:]
                    for next_word in asta_org_map[asta]:
                        if next_word not in visited:
                            queue.append(next_word)
        
        return 0

102. Cheapest Flights Within K Stops

Problem

There are n airports, labeled from 0 to n - 1, which are connected by some flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] represents a one-way flight from airport from_i to airport to_i with cost price_i. You may assume there are no duplicate flights and no flights from an airport to itself.

You are also given three integers src, dst, and k where:

• src is the starting airport
• dst is the destination airport
• src != dst
• k is the maximum number of stops you can make (not including src and dst)

Return the cheapest price from src to dst with at most k stops, or return -1 if it is impossible.

Example 1:

Input: n = 4, flights = [[0,1,200],[1,2,100],[1,3,300],[2,3,100]], src = 0, dst = 3, k = 1

Output: 500

Copy

Explanation:
The optimal path with at most 1 stop from airport 0 to 3 is shown in red, with total cost 200 + 300 = 500.
Note that the path [0 -> 1 -> 2 -> 3] costs only 400, and thus is cheaper, but it requires 2 stops, which is more than k.

Example 2:

Input: n = 3, flights = [[1,0,100],[1,2,200],[0,2,100]], src = 1, dst = 2, k = 1

Output: 200

Copy

Explanation:
The optimal path with at most 1 stop from airport 1 to 2 is shown in red and has cost 200.

Constraints:

• 1 <= n <= 100
• fromi != toi
• 1 <= pricei <= 1000
• 0 <= src, dst, k < n

Solution

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        prices = [math.inf] * n
        prices[src] = 0

        for _ in range(k+1):
            tmp_prices = prices.copy()
            for from_i, to_i, price_i in flights:
                if prices[from_i] == math.inf:
                    continue
                
                if prices[from_i] + price_i < tmp_prices[to_i]:
                    tmp_prices[to_i] = prices[from_i] + price_i
            prices = tmp_prices
        
        return prices[dst] if prices[dst] != math.inf else -1

103. Swim In Rising Water

Problem

You are given a square 2-D matrix of distinct integers grid where each integer grid[i][j] represents the elevation at position (i, j).

Rain starts to fall at time = 0, which causes the water level to rise. At time t, the water level across the entire grid is t.

You may swim either horizontally or vertically in the grid between two adjacent squares if the original elevation of both squares is less than or equal to the water level at time t.

Starting from the top left square (0, 0), return the minimum amount of time it will take until it is possible to reach the bottom right square (n - 1, n - 1).

Example 1:

Input: grid = [[0,1],[2,3]]

Output: 3

Copy

Explanation: For a path to exist to the bottom right square grid[1][1] the water elevation must be at least 3. At time t = 3, the water level is 3.

Example 2:

Input: grid = [
  [0,1,2,10],
  [9,14,4,13],
  [12,3,8,15],
  [11,5,7,6]]
]

Output: 8

Copy

Explanation: The water level must be at least 8 to reach the bottom right square. The path is [0, 1, 2, 4, 8, 7, 6].

Constraints:

• grid.length == grid[i].length
• 1 <= grid.length <= 50
• 0 <= grid[i][j] < n^2

Solution

import heapq

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]
        min_heap = []
        min_heap.append((grid[0][0],0,0))
        visited = set()

        while min_heap:
            num, r, c = heapq.heappop(min_heap)
            if r == ROWS-1 and c == COLS-1:
                return num
            
            visited.add((r, c))

            for dr, dc in DIRECTIONS:
                nr, nc = dr + r, dc + c

                if (nr in range(ROWS) and
                    nc in range(COLS) and
                    (nr, nc) not in visited
                    ):
                    new_num = grid[nr][nc]
                    heapq.heappush(min_heap, (max(num, new_num), nr, nc))

104. Alien Dictionary

Problem

There is a foreign language which uses the latin alphabet, but the order among letters is not "a", "b", "c" ... "z" as in English.

You receive a list of non-empty strings words from the dictionary, where the words are sorted lexicographically based on the rules of this new language.

Derive the order of letters in this language. If the order is invalid, return an empty string. If there are multiple valid order of letters, return any of them.

A string a is lexicographically smaller than a string b if either of the following is true:

• The first letter where they differ is smaller in a than in b.
• There is no index i such that a[i] != b[i] and a.length < b.length.

Example 1:

Input: ["z","o"]

Output: "zo"

Copy

Explanation:
From "z" and "o", we know 'z' < 'o', so return "zo".

Example 2:

Input: ["hrn","hrf","er","enn","rfnn"]

Output: "hernf"

Copy

Explanation:

• from "hrn" and "hrf", we know 'n' < 'f'
• from "hrf" and "er", we know 'h' < 'e'
• from "er" and "enn", we know get 'r' < 'n'
• from "enn" and "rfnn" we know 'e'<'r'
• so one possibile solution is "hernf"

Constraints:

• The input words will contain characters only from lowercase 'a' to 'z'.
• 1 <= words.length <= 100
• 1 <= words[i].length <= 100

Solution

from collections import defaultdict, deque

class Solution:
    def foreignDictionary(self, words: List[str]) -> str:
        src_dst_map = defaultdict(set) # from -> to
        in_degrees = { c: 0 for word in words for c in word }

        for i in range(len(words)-1):
            word1, word2 = words[i], words[i+1]
            min_len = min(len(word1), len(word2))

            if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
                # abc が ab よりも先に来るようなパターンは無効
                return ''
            
            for j in range(min_len):
                if word1[j] != word2[j]:
                    if word2[j] not in src_dst_map[word1[j]]:
                        src_dst_map[word1[j]].add(word2[j])
                        in_degrees[word2[j]] += 1
                    break
            
        queue = deque()
        for c, d in in_degrees.items():
            if d == 0:
                queue.append(c)
        
        ordered = []
        while queue:
            c = queue.popleft()
            ordered.append(c)

            for dst in src_dst_map[c]:
                in_degrees[dst] -= 1
                if in_degrees[dst] == 0:
                    queue.append(dst)
        
        return ''.join(ordered) if len(ordered) == len(in_degrees) else ''