Clone Graph

🎯

Clone Graph

mediumGRAPHFacebookAmazonGoogle

Imagine you have a social network graph representing friendships, and you want to create an exact copy of this network to simulate new features without affecting the original.

💡 This problem involves copying a complex data structure - a graph - which can be tricky because nodes can be interconnected in cycles. Beginners often struggle with how to avoid infinite loops and how to keep track of already copied nodes. Think of it like making a photocopy of a map with roads connecting cities; you must ensure every city and road is copied exactly once without getting stuck going in circles.

📋

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 of its neighbors. The graph is represented using adjacency lists. The cloned graph should have the same structure and node values as the original graph.

The number of nodes in the graph is in the range [0, 100].1 <= Node.val <= 100Node.val is unique for each node.The graph is connected and undirected.

💡

Example

Input"adjList = [[2,4],[1,3],[2,4],[1,3]]"

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

The graph has 4 nodes. Node 1 is connected to nodes 2 and 4, node 2 to nodes 1 and 3, and so on. The output is a deep copy with the same adjacency structure.

• Empty graph (null input) → return null
• Graph with a single node and no neighbors → clone node with empty neighbors list
• Graph with a cycle → cloned graph must preserve cycle without infinite loop
• Graph with multiple disconnected components (not applicable here as input is connected, but good to consider) → ensure cloning handles connectivity

⚠️

Common Mistakes

Not tracking visited nodes

Infinite recursion or stack overflow on cyclic graphs

✅ Use a hash map to store cloned nodes and check before cloning

Modifying original graph nodes

Original graph structure changes, causing incorrect results or side effects

✅ Always create new nodes and do not alter original nodes' neighbors

Using node values as keys in map instead of node references

Incorrect cloning when multiple nodes have same value or graph structure is complex

✅ Use node object references as keys in the map, not just values

Forgetting to clone neighbors list properly

Cloned nodes have empty or incorrect neighbors, breaking graph structure

✅ Ensure neighbors list is populated with cloned neighbor nodes, not original neighbors

🧠

Brute Force (DFS without memoization)

💡 This approach tries to clone the graph by recursively visiting neighbors but does not keep track of visited nodes, leading to infinite recursion on cycles. It helps beginners understand why tracking visited nodes is essential.

Intuition

Try to clone each node by recursively cloning its neighbors. Without remembering which nodes are already cloned, the recursion will revisit nodes endlessly.

Algorithm

1. Start cloning from the given node.
2. For each neighbor of the current node, recursively clone the neighbor.
3. Assign the cloned neighbors to the current cloned node's neighbors list.
4. Return the cloned node.

💡 The recursion is straightforward but misses the critical step of remembering cloned nodes, which causes infinite loops in cyclic graphs.

</>

Code

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
    clone = Node(node.val)
    clone.neighbors = [cloneGraph(nei) for nei in node.neighbors]
    return clone

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

Line Notes

def cloneGraph(node):Defines the main cloning function

if not node:Handles the base case of empty input

clone = Node(node.val)Creates a new node with the same value

clone.neighbors = [cloneGraph(nei) for nei in node.neighbors]Recursively clones neighbors without tracking visited nodes, causing infinite recursion on cycles

import java.util.*;
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Node clone = new Node(node.val);
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }
        return clone;
    }

    // main method for testing
    public static void main(String[] args) {
        // Example usage can be added here
    }
}

Line Notes

public Node cloneGraph(Node node) {Main cloning method

if (node == null) return null;Handles empty graph input

Node clone = new Node(node.val);Creates a new node clone

clone.neighbors.add(cloneGraph(neighbor));Recursively clones neighbors without visited tracking, causing infinite recursion on cycles

#include <iostream>
#include <vector>
using namespace std;

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    Node* clone = new Node(node->val);
    for (auto neighbor : node->neighbors) {
        clone->neighbors.push_back(cloneGraph(neighbor));
    }
    return clone;
}

// int main() {
//     // Example usage
//     return 0;
// }

Line Notes

Node* cloneGraph(Node* node) {Function to clone graph starting from node

if (!node) return nullptr;Base case for empty input

Node* clone = new Node(node->val);Create new node clone

clone->neighbors.push_back(cloneGraph(neighbor));Recursively clone neighbors without visited tracking, causing infinite recursion on cycles

function Node(val, neighbors) {
    this.val = val === undefined ? 0 : val;
    this.neighbors = neighbors === undefined ? [] : neighbors;
}

var cloneGraph = function(node) {
    if (!node) return null;
    let clone = new Node(node.val);
    clone.neighbors = node.neighbors.map(nei => cloneGraph(nei));
    return clone;
};

// Example usage:
// let node = new Node(1, [new Node(2), new Node(3)]);
// console.log(cloneGraph(node));

Line Notes

var cloneGraph = function(node) {Defines cloning function

if (!node) return null;Handles null input

let clone = new Node(node.val);Creates new node clone

clone.neighbors = node.neighbors.map(nei => cloneGraph(nei));Recursively clones neighbors without visited tracking, causing infinite recursion on cycles

⏱

Complexity

TimeO(V + E) but infinite recursion on cyclic graphs

SpaceO(V) due to recursion stack but unbounded due to cycles

The algorithm tries to visit every node and edge once, but without visited tracking, cycles cause infinite recursion.

💡 For a graph with 5 nodes and 6 edges, this approach would ideally do about 11 operations, but cycles cause it to never finish.

Interview Verdict: TLE / Stack Overflow on cyclic graphs

This approach is useful to show why tracking visited nodes is necessary; it fails on cyclic graphs due to infinite recursion.

🧠

DFS with Hash Map to Track Visited Nodes

💡 This approach improves on brute force by using a hash map to remember cloned nodes, preventing infinite recursion and ensuring each node is cloned once.

Intuition

Use DFS to traverse the graph. For each node, if it is already cloned (in the map), return the clone. Otherwise, create a clone and recursively clone neighbors.

Algorithm

1. If the input node is null, return null.
2. If the node is already cloned (exists in the map), return the clone.
3. Create a clone of the current node and add it to the map.
4. Recursively clone all neighbors and add them to the clone's neighbors list.
5. Return the clone.

💡 The key is to check the map before cloning to avoid revisiting nodes and infinite loops.

</>

Code

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

def cloneGraph(node):
    visited = {}
    def dfs(n):
        if not n:
            return None
        if n in visited:
            return visited[n]
        clone = Node(n.val)
        visited[n] = clone
        for nei in n.neighbors:
            clone.neighbors.append(dfs(nei))
        return clone
    return dfs(node)

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

Line Notes

visited = {}Dictionary to store original node to clone mapping

def dfs(n):Helper function to perform DFS cloning

if n in visited:Return clone if node already cloned to avoid cycles

visited[n] = cloneStore clone in map before recursive calls to handle cycles

import java.util.*;
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Solution {
    private Map<Node, Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);
        Node clone = new Node(node.val);
        visited.put(node, clone);
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }
        return clone;
    }

    public static void main(String[] args) {
        // Example usage
    }
}

Line Notes

private Map<Node, Node> visited = new HashMap<>();Map to track cloned nodes

if (visited.containsKey(node)) return visited.get(node);Return clone if node already cloned

visited.put(node, clone);Add clone to map before recursion to handle cycles

for (Node neighbor : node.neighbors)Recursively clone neighbors

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

unordered_map<Node*, Node*> visited;

Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    if (visited.find(node) != visited.end()) return visited[node];
    Node* clone = new Node(node->val);
    visited[node] = clone;
    for (auto neighbor : node->neighbors) {
        clone->neighbors.push_back(cloneGraph(neighbor));
    }
    return clone;
}

// int main() {
//     // Example usage
//     return 0;
// }

Line Notes

unordered_map<Node*, Node*> visited;Hash map to store original to clone mapping

if (visited.find(node) != visited.end()) return visited[node];Return clone if already cloned

visited[node] = clone;Store clone before recursion to avoid cycles

for (auto neighbor : node->neighbors)Recursively clone neighbors

function Node(val, neighbors) {
    this.val = val === undefined ? 0 : val;
    this.neighbors = neighbors === undefined ? [] : neighbors;
}

var cloneGraph = function(node) {
    const visited = new Map();
    function dfs(n) {
        if (!n) return null;
        if (visited.has(n)) return visited.get(n);
        const clone = new Node(n.val);
        visited.set(n, clone);
        for (let nei of n.neighbors) {
            clone.neighbors.push(dfs(nei));
        }
        return clone;
    }
    return dfs(node);
};

// Example usage:
// let node = new Node(1, [new Node(2), new Node(3)]);
// console.log(cloneGraph(node));

Line Notes

const visited = new Map();Map to track cloned nodes

if (visited.has(n)) return visited.get(n);Return clone if node already cloned

visited.set(n, clone);Add clone to map before recursion to handle cycles

for (let nei of n.neighbors)Recursively clone neighbors

⏱

Complexity

TimeO(V + E)

SpaceO(V)

Each node and edge is visited once. The hash map prevents revisiting nodes, so recursion depth is limited to number of nodes.

💡 For a graph with 5 nodes and 6 edges, this approach does about 11 operations, and recursion depth is at most 5.

Interview Verdict: Accepted

This is the standard DFS approach for cloning graphs, efficient and safe against cycles.

🧠

BFS with Hash Map to Track Visited Nodes

💡 This approach uses BFS instead of DFS to clone the graph. It also uses a hash map to track cloned nodes, which is often easier to understand for iterative solutions.

Intuition

Use a queue to traverse nodes level by level. Clone nodes as they are discovered and use a map to avoid cloning nodes multiple times.

Algorithm

1. If the input node is null, return null.
2. Create a clone of the start node and add it to the map.
3. Initialize a queue and enqueue the start node.
4. While the queue is not empty, dequeue a node.
5. For each neighbor, if not cloned, clone and enqueue it.
6. Add the cloned neighbors to the current cloned node's neighbors list.
7. Return the clone of the start node.

💡 BFS avoids recursion and uses a queue to systematically clone nodes, ensuring no node is cloned twice.

</>

Code

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))

Line Notes

visited = {node: Node(node.val)}Initialize map with clone of start node

queue = deque([node])Queue for BFS traversal

if nei not in visited:Clone neighbor if not cloned yet

visited[n].neighbors.append(visited[nei])Add cloned neighbor to current clone's neighbors

import java.util.*;
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> visited = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        visited.put(node, new Node(node.val));
        queue.add(node);
        while (!queue.isEmpty()) {
            Node n = queue.poll();
            for (Node neighbor : n.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    visited.put(neighbor, new Node(neighbor.val));
                    queue.add(neighbor);
                }
                visited.get(n).neighbors.add(visited.get(neighbor));
            }
        }
        return visited.get(node);
    }

    public static void main(String[] args) {
        // Example usage
    }
}

Line Notes

Map<Node, Node> visited = new HashMap<>();Map to track cloned nodes

Queue<Node> queue = new LinkedList<>();Queue for BFS traversal

if (!visited.containsKey(neighbor)) {Clone neighbor if not cloned

visited.get(n).neighbors.add(visited.get(neighbor));Add cloned neighbor to current clone's neighbors

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    unordered_map<Node*, Node*> visited;
    queue<Node*> q;
    visited[node] = new Node(node->val);
    q.push(node);
    while (!q.empty()) {
        Node* n = q.front(); q.pop();
        for (auto neighbor : n->neighbors) {
            if (visited.find(neighbor) == visited.end()) {
                visited[neighbor] = new Node(neighbor->val);
                q.push(neighbor);
            }
            visited[n]->neighbors.push_back(visited[neighbor]);
        }
    }
    return visited[node];
}

// int main() {
//     // Example usage
//     return 0;
// }

Line Notes

unordered_map<Node*, Node*> visited;Map to track cloned nodes

queue<Node*> q;Queue for BFS traversal

if (visited.find(neighbor) == visited.end()) {Clone neighbor if not cloned

visited[n]->neighbors.push_back(visited[neighbor]);Add cloned neighbor to current clone's neighbors

function Node(val, neighbors) {
    this.val = val === undefined ? 0 : val;
    this.neighbors = neighbors === undefined ? [] : neighbors;
}

var cloneGraph = function(node) {
    if (!node) return null;
    const visited = new Map();
    const queue = [node];
    visited.set(node, new Node(node.val));
    while (queue.length > 0) {
        const n = queue.shift();
        for (let nei of n.neighbors) {
            if (!visited.has(nei)) {
                visited.set(nei, new Node(nei.val));
                queue.push(nei);
            }
            visited.get(n).neighbors.push(visited.get(nei));
        }
    }
    return visited.get(node);
};

// Example usage:
// let node = new Node(1, [new Node(2), new Node(3)]);
// console.log(cloneGraph(node));

Line Notes

const visited = new Map();Map to track cloned nodes

const queue = [node];Queue for BFS traversal

if (!visited.has(nei)) {Clone neighbor if not cloned

visited.get(n).neighbors.push(visited.get(nei));Add cloned neighbor to current clone's neighbors

⏱

Complexity

TimeO(V + E)

SpaceO(V)

Each node and edge is visited once. The queue ensures nodes are processed in BFS order.

💡 For a graph with 5 nodes and 6 edges, this approach does about 11 operations, with queue size at most number of nodes.

Interview Verdict: Accepted

BFS is an alternative to DFS for cloning graphs, often preferred for iterative solutions.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the DFS or BFS with hash map approach as it is efficient and handles cycles correctly.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS without visited tracking)	Infinite on cyclic graphs	Unbounded due to recursion	Yes	No	Mention only - never code
2. DFS with Hash Map	O(V + E)	O(V)	Possible but limited to graph depth	Yes	Preferred recursive solution
3. BFS with Hash Map	O(V + E)	O(V)	No	Yes	Preferred iterative solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding, and finally present the optimized DFS or BFS solutions.

How to Present

Clarify the problem and input/output format.Explain the brute force recursive approach and why it fails on cycles.Introduce the DFS with hash map approach to handle cycles.Optionally, discuss BFS approach as an iterative alternative.Write clean, tested code and explain your reasoning.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of graph traversal, handling cycles, use of hash maps for memoization, and ability to write clean recursive or iterative code.

Common Follow-ups

• What if the graph is directed? → The approach remains the same, just neighbors represent outgoing edges.
• Can you clone a disconnected graph? → Yes, by cloning each connected component separately or modifying input to a list of nodes.

💡 These follow-ups test your ability to generalize the solution and handle variations in graph structure.

🔍

Pattern Recognition

When to Use

1) You need to copy or clone a graph or complex linked structure. 2) The graph may contain cycles. 3) You must preserve the exact structure and node values. 4) You need to avoid infinite loops during traversal.

Signature Phrases

clone graphdeep copy of graphneighbors listavoid infinite recursion

NOT This Pattern When

This is not a shortest path or topological sort problem, though it uses graph traversal.

Similar Problems

Copy List with Random Pointer - similar cloning with pointers and cyclesNumber of Connected Components in an Undirected Graph - graph traversal with visited tracking

Practice

1. Consider the following Python code to find the center of a star graph. What is the value of freq after processing all edges for the input edges = [[1,2],[2,3],[4,2]]?

easy

A. {1: 1, 2: 3, 3: 1, 4: 1}

B. {1: 1, 2: 2, 3: 1, 4: 1}

C. {1: 1, 2: 4, 3: 1, 4: 1}

D. {1: 2, 2: 3, 3: 1, 4: 1}

Solution

1. Step 1: Count frequencies for each edge

   Edges are [1,2], [2,3], [4,2]. Counting occurrences: 1 appears once, 2 appears in all three edges (3 times), 3 once, 4 once.

2. Step 2: Construct frequency dictionary

   freq = {1:1, 2:3, 3:1, 4:1} after processing all edges.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Node 2 appears 3 times, matching n-1=3 for n=4 nodes [OK]

Hint: Count each node's appearance in edges [OK]

Common Mistakes:

• Miscounting frequency of node 2
• Adding extra counts for nodes
• Confusing node labels with counts

2. Examine the following buggy code snippet for the optimal BFS approach. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line that sets dist[nr][nc] = dist[r][c] + 1 without checking if dist[nr][nc] == -1

B. Line that initializes dist[r][c] = 0 for land cells

C. Line that appends initial land cells to the queue

D. Line that returns -1 if all cells are land or water

Solution

1. Step 1: Identify that updating dist[nr][nc] without checking if it was visited causes overwriting distances.

   This leads to revisiting cells multiple times, causing infinite loops or incorrect distances.

2. Step 2: The missing condition dist[nr][nc] == -1 before updating and enqueueing is the bug.

   Without it, BFS does not behave correctly as a shortest path search.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited check prevents infinite loops and ensures correct distances [OK]

Hint: Always check if neighbor is unvisited before updating distance [OK]

Common Mistakes:

• Forgetting visited check causes infinite loops
• Misplacing initialization lines
• Incorrect early return conditions

3. Consider the following buggy code for finding the cheapest flight within K stops. Which line contains the subtle bug that can cause incorrect results?

from collections import defaultdict
import heapq

def findCheapestPrice(n, flights, src, dst, K):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    heap = [(0, src, 0)]  # cost, node, stops
    while heap:
        cost, node, stops = heapq.heappop(heap)
        if node == dst:
            return cost
        if stops < K:  # BUG: should be stops <= K
            for nei, price in graph[node]:
                heapq.heappush(heap, (cost + price, nei, stops + 1))
    return -1

medium

A. Line with condition if stops < K:

B. Line initializing the heap with (0, src, 0)

C. Line checking if node == dst

D. Line pushing neighbors into the heap

Solution

1. Step 1: Understand stops constraint

   The problem allows up to K stops, meaning stops can be equal to K, not strictly less.

2. Step 2: Identify bug

   The condition 'if stops < K:' excludes paths with exactly K stops, missing valid solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to 'stops <= K' fixes the bug [OK]

Hint: Stops ≤ K allows exactly K stops, not less [OK]

Common Mistakes:

• Using stops < K instead of stops <= K
• Ignoring stops count in pruning
• Returning early without checking stops

4. What is the time complexity of the optimal BFS approach for the Pacific Atlantic Water Flow problem on an m x n grid, and why?

medium

A. O(m * n) because each cell is enqueued and processed at most once per ocean.

B. O(m * n * log(m * n)) due to priority queue operations in BFS.

C. O(m^2 * n^2) because BFS is run from every cell.

D. O(m + n) because BFS only processes border cells.

Solution

1. Step 1: Analyze BFS visits

   Each BFS starts from border cells and visits each cell at most once per ocean, so total visits ≤ 2 * m * n.

2. Step 2: Confirm no repeated work

   Visited arrays prevent revisiting cells, so BFS complexity is linear in number of cells.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each cell processed once per ocean -> O(m*n) [OK]

Hint: BFS visits each cell once per ocean [OK]

Common Mistakes:

• Confusing with brute force DFS from every cell
• Assuming BFS uses priority queue

5. Suppose the problem is modified so that diagonal neighbors (top-left, top-right, bottom-left, bottom-right) are also considered connected. Which of the following changes to the BFS algorithm correctly adapts to this new requirement without double counting or missing cells?

hard

A. Add diagonal neighbors to the neighbor list and keep the rest of the BFS code unchanged

B. Use DFS instead of BFS because BFS cannot handle diagonal connections

C. Keep neighbor list unchanged but run BFS twice, once for horizontal/vertical and once for diagonals

D. Add diagonal neighbors to the neighbor list and also mark visited cells immediately when enqueuing them

Solution

1. Step 1: Add diagonal neighbors to the neighbor list

   Include all 8 directions: horizontal, vertical, and diagonal neighbors.

2. Step 2: Mark cells as visited when enqueuing

   This prevents adding the same cell multiple times from different neighbors, avoiding double counting.

3. Step 3: Keep BFS traversal logic unchanged otherwise

   Running BFS twice or switching to DFS is unnecessary and inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Mark visited on enqueue avoids duplicates with expanded neighbors [OK]

Hint: Mark visited on enqueue when neighbors increase [OK]

Common Mistakes:

• Not marking visited on enqueue causing duplicates
• Running BFS multiple times unnecessarily
• Thinking BFS can't handle diagonals