Graph Algorithms (Hard)Solve complex connectivity, pathfinding, and cycle detection problems in graphs.

276. Number of Islands

Problem Statement

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. **Example:** ```python Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 ```

Approach

1. **Traversal**: We need to traverse every "1" node and its neighbors. 2. **DFS/BFS**: When we find a "1", invoke a DFS/BFS to visit all connected "1"s and mark them as visited (e.g., turn them to "0" or usage a visited set). 3. **Count**: Each time we start a new DFS/BFS from the main loop, we have found a new island. Increment count.

Solution

def numIslands(grid):
    if not grid:
        return 0
        
    rows, cols = len(grid), len(grid[0])
    islands = 0
    
    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
            return
        
        grid[r][c] = '0' # Mark as visited
        
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
        
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                islands += 1
                
    return islands

278. Clone Graph

Problem Statement

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 value (`int`) and a list (`List[Node]`) of its neighbors. **Example:** ```python Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] ```

Approach

1. **Mapping**: We need to map original nodes to their copies to avoid cycles and redundant processing. Use a hash map `old_node -> new_node`. 2. **DFS Approach**: * Create a copy of the current node. * Store in map. * Iterate through neighbors. * If neighbor is already in map, append the stored copy to current node's neighbors. * If not, recurse and append the result.

Solution

`class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):
    if not node:
        return None
        
    old_to_new = {

285. Course Schedule

Problem Statement

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you must take course `bi` first if you want to take course `ai`. Return `true` if you can finish all courses. Otherwise, return `false`. **Example:** ```python Input: numCourses = 2, prerequisites = [[1,0]] Output: true ```

Approach

1. **Cycle Detection**: This is a Directed Acyclic Graph (DAG) problem. If there is a cycle, courses cannot be finished. 2. **Topological Sort / DFS**: * Build adjacency list. * Use states: 0 (unvisited), 1 (visiting/current path), 2 (visited/safe). * If we encounter a node in state 1 during DFS, there is a cluster. * If all nodes are checked and safe, return True.

Solution

`def canFinish(numCourses, prerequisites):
    pre_map = {i: [] for i in range(numCourses)

297. Network Delay Time (Dijkstra)

Problem Statement

You are given a network of `n` nodes, labeled from 1 to n. You are also given `times`, a list of travel times as directed edges `times[i] = (ui, vi, wi)`, where `ui` is the source node, `vi` is the target node, and `wi` is the time it takes for a signal to travel from source to target. We send a signal from a given node `k`. Return the minimum time it takes for all the `n` nodes to receive the signal. If it is impossible for all the `n` nodes to receive the signal, return `-1`. **Example:** ```python Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2 ```

Approach

1. **Shortest Path**: We need the shortest path from `k` to all other nodes. The "time" for the whole network is the maximum distance among those shortest paths. 2. **Dijkstra's Algorithm**: * Use a Min-Heap. * Initialize dists to infinity, dist[k] = 0. * Push `(0, k)` to heap. * While heap: pop min `(d, u)`. If visited, skip. Update neighbors `v` with `d + weight`. * If max(dists) is infinity, return -1. Else return max(dists).

Solution

`import heapq

def networkDelayTime(times, n, k):
    edges = { i: [] for i in range(1, n + 1)

286. Word Ladder

Problem Statement

A transformation sequence from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words where every adjacent pair differs by a single letter. Given two words, `beginWord` and `endWord`, and a dictionary `wordList`, return the number of words in the shortest transformation sequence from `beginWord` to `endWord`, or 0 if no such sequence exists. **Example:** ```python Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: "hit" -> "hot" -> "dot" -> "dog" -> "cog" ```

Approach

1. **Shortest Path in Unweighted Graph**: BFS is ideal. 2. **Graph Construction**: Nodes are words. Edges exist if words differ by 1 char. 3. **Optimization**: Instead of comparing every word pair (O(N^2 * L)), use a wildcard map (e.g., "*ot" -> ["hot", "dot", "lot"]) for O(N*L^2). 4. **BFS**: * Queue starts with `(beginWord, 1)`. * Visit neighbors via wildcard patterns. * Return level when `endWord` is found.

Solution

`from collections import deque

def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
        
    nei = {

Back

Graph Algorithms (Hard) / 276. Number of Islands

00:00

1/5

276. Number of Islands

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.

Example:

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

1
Traversal: We need to traverse every "1" node and its neighbors.
2
DFS/BFS: When we find a "1", invoke a DFS/BFS to visit all connected "1"s and mark them as visited (e.g., turn them to "0" or usage a visited set).
3
Count: Each time we start a new DFS/BFS from the main loop, we have found a new island. Increment count.

PYTHON PLAYGROUND

⏳ Loading editor…