Clone Graph

▶

Steps

setup

Initialize - clone node 1, seed queue

Node 1 (the start) is cloned immediately. visited = {node1: clone(1)}. Queue initialized with node1. This clone will eventually get its neighbors wired in step 3.

💡 We clone the start node upfront before the BFS loop so we have somewhere to return at the end.

Line:

visited = {node: Node(node.val)}
queue = deque([node])

💡 The visited map maps original→clone. Starting with node 1 ensures we can return its clone at the end.

expand

Dequeue node 1 - process neighbors [2, 4]

Dequeue node1 from queue. Its neighbors are nodes 2 and 4. Neither is in visited yet. Clone both: visited[node2]=clone(2), visited[node4]=clone(4). Add both to queue.

💡 When we process a node, we look at ALL its neighbors. Any neighbor not yet cloned gets a fresh clone and is enqueued.

Line:

n = queue.popleft()
for nei in n.neighbors:
    if nei not in visited:
        visited[nei] = Node(nei.val)
        queue.append(nei)
    visited[n].neighbors.append(visited[nei])

💡 The clone neighbor wiring (visited[n].neighbors.append) uses the visited map to find the existing clone - crucial for when a neighbor was already cloned by a previous node.

expand

Dequeue node 2 - neighbors [1, 3]; node 1 already cloned

Dequeue node2. Neighbors are nodes 1 and 3. Node1 IS in visited - don't re-clone, just wire: clone(2).neighbors.append(visited[node1]) = clone(1). Node3 is NOT in visited - clone(3), enqueue.

💡 This step shows the hash map's cycle-handling: node1 was already cloned in step 2. We look it up in visited and wire directly without creating a second clone.

Line:

if nei not in visited:
    visited[nei] = Node(nei.val)
    queue.append(nei)
visited[n].neighbors.append(visited[nei])  # wire existing clone

💡 Without the hash map, we'd create duplicate clone(1) objects and get an incorrect graph with broken connectivity.

expand

Dequeue node 4 - neighbors [1, 3]; both already cloned

Dequeue node4. Neighbors are nodes 1 and 3. Both are in visited. Wire only: clone(4).neighbors = [clone(1), clone(3)]. No new clones, no new enqueues.

💡 All neighbors of node4 were already cloned earlier. The hash map finds them instantly and the wiring is done without any new BFS work.

Line:

for nei in n.neighbors:
    # nei already in visited - just wire
    visited[n].neighbors.append(visited[nei])

💡 This is the cycle completion step. The graph has a cycle (1-2-3-4-1) and the hash map ensures we wire correctly without infinite loops.

expand

Dequeue node 3 - wire clone(2) and clone(4), queue empty

Dequeue node3. Neighbors are nodes 2 and 4. Both already in visited. Wire: clone(3).neighbors = [clone(2), clone(4)]. Queue is now empty. BFS complete.

💡 Node 3 is the last node. After wiring its neighbors the queue empties and the BFS loop ends.

Line:

while queue:
    n = queue.popleft()
    for nei in n.neighbors:
        visited[n].neighbors.append(visited[nei])
# queue empty → BFS done

💡 All 4 clone nodes are now fully wired. The cloned graph is structurally identical to the original.

from collections import deque

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
    visited = {node: Node(node.val)}
    queue = deque([node])
    while queue:
        n = queue.popleft()
        for nei in n.neighbors:
            if nei not in visited:
                visited[nei] = Node(nei.val)
                queue.append(nei)
            visited[n].neighbors.append(visited[nei])
    return visited[node]

# Example usage:
# node = Node(1, [Node(2), Node(3)])
# print(cloneGraph(node))

📊

Clone Graph - Watch BFS + Hash Map Cloning Execute, Step by Step

The hash map visited serves two purposes: it prevents re-visiting nodes (like a standard BFS set) AND stores the mapping from original node to its clone so we can wire neighbors without re-cloning.

Visiting: none

1

2

3

4

Queue / Stack

1

Visiting: 1

1

2

3

4

Queue / Stack

24

Visiting: 2

Edge: 2 → 3

1

2

3

4

Queue / Stack

43

Visiting: 4

1

2

3

4

Queue / Stack

3

Visiting: 3

1

2

3

4

Key Takeaways

✓ The hash map visited serves dual purpose: cycle detection (don't re-clone) and clone registry (wire neighbors to existing clones).

Without the map you'd either get infinite recursion on cycles or disconnected duplicate nodes.

✓ BFS guarantees every node is dequeued exactly once, so every node's neighbors are wired exactly once.

The neighbor wiring happens at dequeue time, not at clone time - this is why all clones exist in visited before wiring.

✓ The algorithm works for any graph topology - DAG, undirected, cyclic - because the hash map handles all cases uniformly.

The cycle test case (1-2-3-4-1) specifically validates the hash map lookup path in visited[n].neighbors.append(visited[nei]).

Practice

1. You are given a graph with n nodes and n-1 edges, where exactly one node is connected to all other nodes, forming a star shape. Which approach guarantees finding the center node in O(n) time without unnecessary graph traversal?

easy

A. Count the frequency of each node in the edges and return the node appearing n-1 times.

B. Apply dynamic programming to store intermediate results of node degrees and find the maximum.

C. Use a greedy approach by picking the first node in the first edge as the center without verification.

D. Perform a depth-first search (DFS) from each node to count its neighbors and identify the center.

Solution

1. Step 1: Understand the star graph property

   In a star graph with n nodes, the center node appears in every edge, so it has degree n-1.

2. Step 2: Use frequency counting

   Counting how many times each node appears in the edges lets us find the node with degree n-1 efficiently in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Frequency counting directly identifies the center without traversal [OK]

Hint: Center node appears in all edges [OK]

Common Mistakes:

• Assuming the first node in edges is always center
• Using DFS from every node causing O(n²) time
• Applying DP unnecessarily for a simple counting problem

2. Consider the following code snippet that finds the smallest set of vertices to reach all nodes in a DAG. Given n = 4 and edges = [[0,1],[1,2],[2,3]], what is the final returned list?

easy

A. [0]

B. [3]

C. [0, 1]

D. [1]

Solution

1. Step 1: Initialize in-degree and queue

   Nodes: 0,1,2,3; in-degree: [0,1,1,1]. Only node 0 has zero in-degree, so queue = [0], result = [0].

2. Step 2: Process queue

   Pop 0, decrement in-degree of 1 to 0, enqueue 1. Pop 1, decrement in-degree of 2 to 0, enqueue 2. Pop 2, decrement in-degree of 3 to 0, enqueue 3. Pop 3, no neighbors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only node 0 has zero in-degree initially, so result is [0] [OK]

Hint: Only nodes with zero in-degree initially are in the result [OK]

Common Mistakes:

• Returning nodes that become zero in-degree later
• Returning all nodes visited in BFS
• Confusing final queue state with result

3. The following code attempts to find the town judge but contains a subtle bug:

def findJudge(n, trust):
    trust_score = [0] * (n + 1)
    for a, b in trust:
        trust_score[a] -= 1
        trust_score[b] += 1
    for i in range(1, n + 1):
        if trust_score[i] == n - 1:
            return i
    return -1

# Bug: Does not handle n=1 correctly

What is the bug and how to fix it?

medium

A. Line 6: The condition should check if trust_score[i] == n instead of n-1

B. Missing special case for n=1 where the single person is the judge by default

C. Line 3: trust_score array should be size n instead of n+1

D. Line 5: trust_score[a] should be incremented instead of decremented

Solution

1. Step 1: Identify edge case for n=1

   If there is only one person and no trust pairs, that person is trivially the judge.

2. Step 2: Fix by adding a check before main logic

   Return 1 immediately if n == 1 and trust is empty, else proceed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without this, code returns -1 incorrectly for single person town [OK]

Hint: Single person town judge must be handled explicitly [OK]

Common Mistakes:

• Ignoring n=1 edge case
• Incorrect trust_score size
• Wrong condition for trust_score check

4. The following BFS code attempts to find the max area of an island in a grid. Identify the line that contains a subtle bug that can cause incorrect area calculation or runtime errors.

from collections import deque

def maxAreaOfIsland(grid):
    rows, cols = len(grid), len(grid[0])
    visited = set()
    max_area = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in visited:
                queue = deque([(r, c)])
                area = 0
                while queue:
                    row, col = queue.popleft()
                    # Bug: Missing visited check here
                    visited.add((row, col))
                    area += 1
                    for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
                        if grid[nr][nc] == 1 and (nr, nc) not in visited:
                            queue.append((nr, nc))
                max_area = max(max_area, area)
    return max_area

medium

A. Line that adds neighbors to the queue without boundary checks

B. Line that adds (row, col) to visited without checking if already visited

C. Line that initializes the queue with the starting cell

D. Line that updates max_area after BFS completes

Solution

1. Step 1: Check neighbor addition line

   The code adds neighbors without verifying if nr, nc are within grid boundaries, risking index out of range errors.

2. Step 2: Confirm other lines are correct

   Visited check before adding to queue is present, queue initialization and max_area update are correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Boundary checks missing cause runtime errors [OK]

Hint: Always check grid boundaries before accessing neighbors [OK]

Common Mistakes:

• Forgetting boundary checks
• Not checking visited before adding to queue
• Adding visited check after popping queue

5. What is the worst-case time complexity of the DFS-based solution for the Rotting Oranges problem on an m x n grid, considering pruning and recursive calls?

medium

A. O(m * n * 4) due to each cell visited once with up to 4 neighbors

B. O(m * n * m * n) because each cell can be revisited multiple times

C. O(m * n) ignoring recursion stack and repeated visits

D. O(m * n * T) where T is the number of minutes until no change

Solution

1. Step 1: Identify number of cells and neighbors

   Grid has m*n cells; each cell has up to 4 neighbors to explore.

2. Step 2: Consider pruning and repeated visits

   Pruning ensures each cell is visited at most once per time update, bounding calls to O(m*n*4).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS with pruning limits repeated visits, so complexity is O(m*n*4) [OK]

Hint: Pruning limits DFS calls to constant neighbors per cell [OK]

Common Mistakes:

• Assuming exponential revisits
• Confusing time steps with grid size
• Ignoring recursion stack space