Is Graph Bipartite?

🎯

Is Graph Bipartite?

mediumGRAPHAmazonGoogleFacebook

Imagine you are organizing a party and want to split guests into two groups such that no two guests who dislike each other end up in the same group. Can you determine if such a split is possible?

💡 This problem asks if a graph's nodes can be divided into two groups with no edges inside the same group. Beginners often struggle because it requires understanding graph traversal and how to assign groups (colors) consistently, especially when cycles exist.

📋

Problem Statement

Given an undirected graph, determine if it is bipartite. A graph is bipartite if its vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to the other. Input: An integer n representing the number of vertices (0-indexed), and an adjacency list graph where graph[i] is a list of vertices adjacent to vertex i. Output: Return true if the graph is bipartite, otherwise false.

1 ≤ n ≤ 10^50 ≤ graph[i].length ≤ n-10 ≤ graph[i][j] < ngraph[i] does not contain duplicate verticesgraph[i] does not contain i (no self loops)

💡

Example

Input"n = 4, graph = [[1,3],[0,2],[1,3],[0,2]]"

Outputtrue

We can split vertices into sets {0,2} and {1,3} with edges only between sets.

Input"n = 3, graph = [[1,2],[0,2],[0,1]]"

Outputfalse

The triangle cycle means no bipartition is possible.

• Graph with a single node → true (trivially bipartite)
• Graph with no edges → true (no edges to violate bipartite)
• Graph with disconnected components → true if all components are bipartite
• Graph with an odd-length cycle → false (cannot bipartition)

⚠️

Common Mistakes

Not checking all disconnected components

Misses conflicts in isolated parts, returns incorrect true

✅ Loop over all nodes and start DFS/BFS if uncolored

Assigning same color to neighbors

Fails to detect bipartite violation, returns true incorrectly

✅ Always assign opposite color to neighbors and check conflicts

Using recursion without base case for already colored nodes

Infinite recursion or stack overflow

✅ Check if node is colored before recursive calls

Not handling self loops or duplicate edges

May cause false conflict or infinite loops

✅ Validate input or handle self loops explicitly

🧠

Brute Force (Try All 2-Colorings via Backtracking)

💡 This approach tries every possible way to color the graph with two colors to check bipartiteness. It is extremely inefficient but helps understand the problem's nature and why smarter methods are needed.

Intuition

Try assigning colors to each node recursively, backtracking if a conflict arises. If any assignment works, the graph is bipartite.

Algorithm

1. Initialize a color array with -1 (uncolored) for all nodes.
2. Define a recursive function that tries to color a node with a given color.
3. For each neighbor, if uncolored, recursively assign the opposite color; if colored and same as current, return false.
4. Try all nodes (to cover disconnected graphs). If all succeed, return true.

💡 The recursion and backtracking make it hard to see efficiency, but it directly models the problem's definition.

</>

Code

from typing import List

def isBipartite(graph: List[List[int]]) -> bool:
    n = len(graph)
    color = [-1] * n

    def dfs(node: int, c: int) -> bool:
        if color[node] != -1:
            return color[node] == c
        color[node] = c
        for nei in graph[node]:
            if not dfs(nei, 1 - c):
                return False
        return True

    for i in range(n):
        if color[i] == -1:
            if not dfs(i, 0):
                return False
    return True

# Driver code
if __name__ == '__main__':
    graph1 = [[1,3],[0,2],[1,3],[0,2]]
    graph2 = [[1,2],[0,2],[0,1]]
    print(isBipartite(graph1))  # True
    print(isBipartite(graph2))  # False

Line Notes

color = [-1] * nInitialize all nodes as uncolored to track assignments

def dfs(node: int, c: int) -> bool:Recursive function tries to color node with color c

if color[node] != -1:If node already colored, check for color conflict

color[node] = cAssign color c to current node

for nei in graph[node]:Traverse all neighbors to assign opposite color

if not dfs(nei, 1 - c):If neighbor coloring fails, propagate failure

for i in range(n):Check all nodes to cover disconnected components

if color[i] == -1:Start DFS only from uncolored nodes

import java.util.*;

public class IsGraphBipartite {
    public static boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1);

        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!dfs(graph, color, i, 0)) return false;
            }
        }
        return true;
    }

    private static boolean dfs(int[][] graph, int[] color, int node, int c) {
        if (color[node] != -1) return color[node] == c;
        color[node] = c;
        for (int nei : graph[node]) {
            if (!dfs(graph, color, nei, 1 - c)) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] graph1 = {{1,3},{0,2},{1,3},{0,2}};
        int[][] graph2 = {{1,2},{0,2},{0,1}};
        System.out.println(isBipartite(graph1)); // true
        System.out.println(isBipartite(graph2)); // false
    }
}

Line Notes

int[] color = new int[n];Create color array to track node colors

Arrays.fill(color, -1);Mark all nodes uncolored initially

if (color[i] == -1)Start DFS from uncolored nodes to cover all components

if (color[node] != -1) return color[node] == c;Check for color conflict if already colored

color[node] = c;Assign color to current node

for (int nei : graph[node])Traverse neighbors to assign opposite color

if (!dfs(...)) return false;Propagate failure if neighbor coloring fails

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

bool dfs(int node, int c, vector<int>& color, const vector<vector<int>>& graph) {
    if (color[node] != -1) return color[node] == c;
    color[node] = c;
    for (int nei : graph[node]) {
        if (!dfs(nei, 1 - c, color, graph)) return false;
    }
    return true;
}

bool isBipartite(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> color(n, -1);
    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            if (!dfs(i, 0, color, graph)) return false;
        }
    }
    return true;
}

int main() {
    vector<vector<int>> graph1 = {{1,3},{0,2},{1,3},{0,2}};
    vector<vector<int>> graph2 = {{1,2},{0,2},{0,1}};
    cout << boolalpha << isBipartite(graph1) << endl; // true
    cout << boolalpha << isBipartite(graph2) << endl; // false
    return 0;
}

Line Notes

vector<int> color(n, -1);Initialize color vector with -1 for uncolored nodes

if (color[node] != -1) return color[node] == c;Check if node already colored and matches expected color

color[node] = c;Assign color to current node

for (int nei : graph[node])Iterate over neighbors to assign opposite color

if (!dfs(...)) return false;Return false if neighbor coloring fails

for (int i = 0; i < n; i++)Check all nodes to cover disconnected components

if (color[i] == -1)Start DFS only from uncolored nodes

function isBipartite(graph) {
    const n = graph.length;
    const color = new Array(n).fill(-1);

    function dfs(node, c) {
        if (color[node] !== -1) return color[node] === c;
        color[node] = c;
        for (const nei of graph[node]) {
            if (!dfs(nei, 1 - c)) return false;
        }
        return true;
    }

    for (let i = 0; i < n; i++) {
        if (color[i] === -1) {
            if (!dfs(i, 0)) return false;
        }
    }
    return true;
}

// Test cases
console.log(isBipartite([[1,3],[0,2],[1,3],[0,2]])); // true
console.log(isBipartite([[1,2],[0,2],[0,1]])); // false

Line Notes

const color = new Array(n).fill(-1);Initialize color array with -1 for uncolored nodes

if (color[node] !== -1) return color[node] === c;Check if node already colored and matches expected color

color[node] = c;Assign color to current node

for (const nei of graph[node])Traverse neighbors to assign opposite color

if (!dfs(nei, 1 - c)) return false;Return false if neighbor coloring fails

for (let i = 0; i < n; i++)Check all nodes to cover disconnected components

if (color[i] === -1)Start DFS only from uncolored nodes

⏱

Complexity

TimeO(V + E)

SpaceO(V)

Each node and edge is visited once during DFS. Color array uses O(V) space.

💡 For n=1000 nodes and m=2000 edges, this means roughly 3000 operations, which is efficient enough.

Interview Verdict: Accepted

Though called brute force here, this DFS coloring is the standard approach and runs efficiently for large graphs.

🧠

BFS Coloring Approach

💡 Instead of DFS, use BFS to assign colors level by level. This approach is often easier to understand and implement iteratively, avoiding recursion stack issues.

Intuition

Start from an uncolored node, assign a color, then assign the opposite color to all neighbors using a queue. If a conflict arises, the graph is not bipartite.

Algorithm

1. Initialize a color array with -1 for all nodes.
2. For each uncolored node, start BFS and assign color 0.
3. Use a queue to process nodes; assign opposite color to neighbors.
4. If a neighbor is already colored with the same color, return false.
5. If all nodes processed without conflict, return true.

💡 The queue-based approach is straightforward but requires careful color checks to avoid conflicts.

</>

Code

from collections import deque
from typing import List

def isBipartite(graph: List[List[int]]) -> bool:
    n = len(graph)
    color = [-1] * n

    for i in range(n):
        if color[i] == -1:
            queue = deque([i])
            color[i] = 0
            while queue:
                node = queue.popleft()
                for nei in graph[node]:
                    if color[nei] == -1:
                        color[nei] = 1 - color[node]
                        queue.append(nei)
                    elif color[nei] == color[node]:
                        return False
    return True

# Driver code
if __name__ == '__main__':
    graph1 = [[1,3],[0,2],[1,3],[0,2]]
    graph2 = [[1,2],[0,2],[0,1]]
    print(isBipartite(graph1))  # True
    print(isBipartite(graph2))  # False

Line Notes

color = [-1] * nInitialize all nodes as uncolored

for i in range(n):Check all nodes to cover disconnected components

queue = deque([i])Start BFS from uncolored node i

color[i] = 0Assign initial color 0 to start node

node = queue.popleft()Process nodes in FIFO order for BFS

if color[nei] == -1:If neighbor uncolored, assign opposite color

elif color[nei] == color[node]:If neighbor has same color, graph not bipartite

import java.util.*;

public class IsGraphBipartiteBFS {
    public static boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1);

        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(i);
                color[i] = 0;

                while (!queue.isEmpty()) {
                    int node = queue.poll();
                    for (int nei : graph[node]) {
                        if (color[nei] == -1) {
                            color[nei] = 1 - color[node];
                            queue.offer(nei);
                        } else if (color[nei] == color[node]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] graph1 = {{1,3},{0,2},{1,3},{0,2}};
        int[][] graph2 = {{1,2},{0,2},{0,1}};
        System.out.println(isBipartite(graph1)); // true
        System.out.println(isBipartite(graph2)); // false
    }
}

Line Notes

int[] color = new int[n];Create color array for all nodes

Arrays.fill(color, -1);Mark all nodes uncolored initially

if (color[i] == -1)Start BFS from uncolored nodes to cover all components

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

color[i] = 0;Assign initial color 0 to start node

for (int nei : graph[node])Traverse neighbors to assign colors

if (color[nei] == color[node])Detect conflict if neighbor has same color

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

bool isBipartite(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> color(n, -1);

    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            queue<int> q;
            q.push(i);
            color[i] = 0;

            while (!q.empty()) {
                int node = q.front(); q.pop();
                for (int nei : graph[node]) {
                    if (color[nei] == -1) {
                        color[nei] = 1 - color[node];
                        q.push(nei);
                    } else if (color[nei] == color[node]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

int main() {
    vector<vector<int>> graph1 = {{1,3},{0,2},{1,3},{0,2}};
    vector<vector<int>> graph2 = {{1,2},{0,2},{0,1}};
    cout << boolalpha << isBipartite(graph1) << endl; // true
    cout << boolalpha << isBipartite(graph2) << endl; // false
    return 0;
}

Line Notes

vector<int> color(n, -1);Initialize color vector with -1 for uncolored nodes

if (color[i] == -1)Start BFS from uncolored nodes to cover disconnected components

queue<int> q;Queue for BFS traversal

color[i] = 0;Assign initial color 0 to start node

for (int nei : graph[node])Traverse neighbors to assign opposite color

if (color[nei] == color[node])Detect conflict if neighbor has same color

q.push(nei);Add neighbor to queue for further processing

function isBipartite(graph) {
    const n = graph.length;
    const color = new Array(n).fill(-1);

    for (let i = 0; i < n; i++) {
        if (color[i] === -1) {
            const queue = [i];
            color[i] = 0;

            while (queue.length > 0) {
                const node = queue.shift();
                for (const nei of graph[node]) {
                    if (color[nei] === -1) {
                        color[nei] = 1 - color[node];
                        queue.push(nei);
                    } else if (color[nei] === color[node]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

// Test cases
console.log(isBipartite([[1,3],[0,2],[1,3],[0,2]])); // true
console.log(isBipartite([[1,2],[0,2],[0,1]])); // false

Line Notes

const color = new Array(n).fill(-1);Initialize color array with -1 for uncolored nodes

if (color[i] === -1)Start BFS from uncolored nodes to cover all components

const queue = [i];Initialize queue with start node

color[i] = 0;Assign initial color 0 to start node

for (const nei of graph[node])Traverse neighbors to assign colors

if (color[nei] === color[node])Detect conflict if neighbor has same color

queue.push(nei);Add neighbor to queue for BFS processing

⏱

Complexity

TimeO(V + E)

SpaceO(V)

Each node and edge is visited once during BFS. Color array and queue use O(V) space.

💡 For n=1000 nodes and m=2000 edges, this means roughly 3000 operations, which is efficient and avoids recursion.

Interview Verdict: Accepted

BFS is a robust alternative to DFS, especially useful to avoid recursion stack overflow in large graphs.

🧠

Union-Find (Disjoint Set) to Detect Odd Cycles

💡 This approach uses a Union-Find data structure to detect if an odd-length cycle exists, which breaks bipartiteness. It is less intuitive but efficient for large graphs.

Intuition

If we try to union neighbors of a node into the same set, and find a conflict, it means an odd cycle exists, so the graph is not bipartite.

Algorithm

1. Initialize Union-Find structure for all nodes.
2. For each node, union all its neighbors with the first neighbor.
3. If any neighbor is already in the same set as the node, return false.
4. If no conflicts found, return true.

💡 Union-Find efficiently detects cycles and conflicts without explicit coloring.

</>

Code

from typing import List

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[py] < self.rank[px]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        return True

def isBipartite(graph: List[List[int]]) -> bool:
    n = len(graph)
    uf = UnionFind(n)

    for node in range(n):
        for i in range(1, len(graph[node])):
            if uf.find(node) == uf.find(graph[node][i]):
                return False
            uf.union(graph[node][0], graph[node][i])
    return True

# Driver code
if __name__ == '__main__':
    graph1 = [[1,3],[0,2],[1,3],[0,2]]
    graph2 = [[1,2],[0,2],[0,1]]
    print(isBipartite(graph1))  # True
    print(isBipartite(graph2))  # False

Line Notes

self.parent = list(range(n))Initialize each node as its own parent

def find(self, x):Find root parent with path compression

if px == py: return FalseIf two nodes share parent, cycle detected

uf.union(graph[node][0], graph[node][i])Union neighbors with first neighbor to group sets

for node in range(n):Iterate all nodes to check neighbors

for i in range(1, len(graph[node])):Check all neighbors except first for union

import java.util.*;

class UnionFind {
    int[] parent, rank;
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[py] < rank[px]) parent[py] = px;
        else {
            parent[py] = px;
            rank[px]++;
        }
        return true;
    }
}

public class IsGraphBipartiteUF {
    public static boolean isBipartite(int[][] graph) {
        int n = graph.length;
        UnionFind uf = new UnionFind(n);
        for (int node = 0; node < n; node++) {
            for (int i = 1; i < graph[node].length; i++) {
                if (uf.find(node) == uf.find(graph[node][i])) return false;
                uf.union(graph[node][0], graph[node][i]);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] graph1 = {{1,3},{0,2},{1,3},{0,2}};
        int[][] graph2 = {{1,2},{0,2},{0,1}};
        System.out.println(isBipartite(graph1)); // true
        System.out.println(isBipartite(graph2)); // false
    }
}

Line Notes

parent = new int[n];Initialize parent array for Union-Find

if (px == py) return false;Detect cycle if two nodes share same parent

uf.union(graph[node][0], graph[node][i]);Union neighbors with first neighbor to group sets

for (int node = 0; node < n; node++)Iterate all nodes to check neighbors

for (int i = 1; i < graph[node].length; i++)Check all neighbors except first for union

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

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unionSet(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[py] < rank[px]) parent[py] = px;
        else {
            parent[py] = px;
            rank[px]++;
        }
        return true;
    }
};

bool isBipartite(const vector<vector<int>>& graph) {
    int n = graph.size();
    UnionFind uf(n);
    for (int node = 0; node < n; node++) {
        for (int i = 1; i < (int)graph[node].size(); i++) {
            if (uf.find(node) == uf.find(graph[node][i])) return false;
            uf.unionSet(graph[node][0], graph[node][i]);
        }
    }
    return true;
}

int main() {
    vector<vector<int>> graph1 = {{1,3},{0,2},{1,3},{0,2}};
    vector<vector<int>> graph2 = {{1,2},{0,2},{0,1}};
    cout << boolalpha << isBipartite(graph1) << endl; // true
    cout << boolalpha << isBipartite(graph2) << endl; // false
    return 0;
}

Line Notes

vector<int> parent, rank;Store parent and rank for Union-Find

if (px == py) return false;Detect cycle if two nodes share same parent

uf.unionSet(graph[node][0], graph[node][i]);Union neighbors with first neighbor to group sets

for (int node = 0; node < n; node++)Iterate all nodes to check neighbors

for (int i = 1; i < (int)graph[node].size(); i++)Check all neighbors except first for union

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }
    union(x, y) {
        let px = this.find(x), py = this.find(y);
        if (px === py) return false;
        if (this.rank[px] < this.rank[py]) this.parent[px] = py;
        else if (this.rank[py] < this.rank[px]) this.parent[py] = px;
        else {
            this.parent[py] = px;
            this.rank[px]++;
        }
        return true;
    }
}

function isBipartite(graph) {
    const n = graph.length;
    const uf = new UnionFind(n);

    for (let node = 0; node < n; node++) {
        for (let i = 1; i < graph[node].length; i++) {
            if (uf.find(node) === uf.find(graph[node][i])) return false;
            uf.union(graph[node][0], graph[node][i]);
        }
    }
    return true;
}

// Test cases
console.log(isBipartite([[1,3],[0,2],[1,3],[0,2]])); // true
console.log(isBipartite([[1,2],[0,2],[0,1]])); // false

Line Notes

this.parent = Array.from({length: n}, (_, i) => i);Initialize each node as its own parent

if (px === py) return false;Detect cycle if two nodes share same parent

uf.union(graph[node][0], graph[node][i]);Union neighbors with first neighbor to group sets

for (let node = 0; node < n; node++)Iterate all nodes to check neighbors

for (let i = 1; i < graph[node].length; i++)Check all neighbors except first for union

⏱

Complexity

TimeO((V + E) α(V))

SpaceO(V)

Union-Find operations are almost O(1) amortized (α is inverse Ackermann function). We process all edges and nodes once.

💡 For n=1000 nodes, α(n) is practically constant (∼4), so this is very efficient.

Interview Verdict: Accepted

Union-Find is a powerful alternative but less intuitive; good to mention if interviewer wants variety.

📊

All Approaches - One-Glance Tradeoffs

💡 DFS or BFS coloring approaches are best for interviews due to clarity and efficiency. Union-Find is advanced and less intuitive but useful in some contexts.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS Coloring)	O(V + E)	O(V)	Yes (deep recursion possible)	Yes (color array shows sets)	Standard approach to implement and explain
2. BFS Coloring	O(V + E)	O(V)	No (iterative)	Yes (color array shows sets)	Good alternative to DFS, preferred if recursion is a concern
3. Union-Find	O((V + E) α(V))	O(V)	No	No (only detects bipartiteness)	Mention as alternative; rarely code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force to show complexity, followed by DFS/BFS coloring approaches. Practice coding and testing edge cases.

How to Present

Clarify the problem and input format.Explain brute force approach to show problem complexity.Introduce DFS coloring as standard solution.Mention BFS as iterative alternative.Optionally discuss Union-Find for cycle detection.Write clean code and test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach explanation: 5min → Code: 10min → Testing & edge cases: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of graph traversal, coloring logic, handling disconnected components, and detecting conflicts. They also assess code correctness and efficiency.

Common Follow-ups

• What if the graph is directed? → Bipartite definition changes, approach differs.
• How to find the bipartition sets if graph is bipartite? → Use color array to separate nodes.

💡 These follow-ups test deeper understanding of bipartite graphs and variations.

🔍

Pattern Recognition

When to Use

1) Problem involves checking if graph can be split into two sets 2) Input is an undirected graph 3) Need to detect odd cycles or conflicts 4) Keywords like 'two-color', 'bipartite', or 'no edges within same set'

Signature Phrases

Is graph bipartite?Can vertices be divided into two sets?No edge connects vertices of the same set

NOT This Pattern When

Problems about shortest paths, strongly connected components, or directed graphs with different constraints

Similar Problems

Graph Coloring - generalizes bipartite to k colorsDetect Cycle in Undirected Graph - odd cycles break bipartiteness

Practice

1. You are given a 2D grid of 0s and 1s. For each cell containing 1, you need to find the distance to the nearest 0. Which algorithmic approach guarantees the shortest distance for all cells efficiently?

easy

A. Use a multi-source Breadth-First Search (BFS) starting from all 0s simultaneously.

B. Run a Depth-First Search (DFS) from each 1 to find the nearest 0.

C. Apply a greedy approach updating distances by scanning rows and columns once.

D. Use a brute force approach checking every cell independently for nearest 0.

Solution

1. Step 1: Understand the problem constraints

   We need shortest distances from each 1 to the nearest 0 in a grid, which is a shortest path problem on an unweighted graph.

2. Step 2: Identify the correct algorithm

   Multi-source BFS starting from all 0s simultaneously guarantees shortest distances because BFS explores neighbors in increasing order of distance.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multi-source BFS ensures shortest path in O(m*n) time [OK]

Hint: Shortest path in grid with multiple sources -> multi-source BFS [OK]

Common Mistakes:

• Using DFS which does not guarantee shortest path
• Greedy scanning misses some paths
• Brute force is too slow

2. You are given a connected undirected graph where each node contains a value and a list of its neighbors. The task is to create a deep copy of this graph such that the cloned graph has the same structure but no shared nodes with the original. Which algorithmic approach guarantees an optimal solution that handles cycles and multiple components correctly?

easy

A. Use a brute force DFS that recursively clones neighbors without tracking visited nodes.

B. Use BFS or DFS with a hash map to track visited nodes and clone each node exactly once.

C. Use a greedy approach that clones nodes only when their values are unique.

D. Use dynamic programming to store intermediate clone results indexed by node values.

Solution

1. Step 1: Understand the problem constraints

   The graph may contain cycles and multiple components, so naive recursion can cause infinite loops or duplicate clones.

2. Step 2: Identify the correct approach

   Using BFS or DFS with a hash map to track visited nodes ensures each node is cloned once, preventing infinite recursion and preserving graph structure.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Tracking visited nodes avoids infinite loops and duplicates [OK]

Hint: Track visited nodes to avoid infinite recursion [OK]

Common Mistakes:

• Not tracking visited nodes causes infinite recursion
• Using node values as keys fails with duplicate values

3. Consider the following Python code implementing Kahn's Algorithm for course scheduling. What is the return value of canFinish(3, [[1,0],[2,1]]) after the while loop completes?

easy

A. false

B. true

C. Raises an error due to empty queue

D. Returns true only if numCourses is 2

Solution

1. Step 1: Initialize graph and in-degree arrays

   Graph: 0 -> [1], 1 -> [2], 2 -> []. In-degree: [0,1,1]. Queue starts with nodes having in-degree 0 -> [0].

2. Step 2: Process queue and update count

   Pop 0, count=1; decrement in-degree of 1 to 0, enqueue 1. Pop 1, count=2; decrement in-degree of 2 to 0, enqueue 2. Pop 2, count=3; queue empty.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All courses processed, so return true [OK]

Hint: Count equals numCourses means no cycle [OK]

Common Mistakes:

• Off-by-one error in count increment
• Misunderstanding queue initialization
• Confusing in-degree decrement timing

4. What is the time complexity of the optimal DFS solution for the Keys and Rooms problem, where N is the number of rooms and E is the total number of keys across all rooms?

medium

A. O(N * E) -- because each room is visited and each key is processed multiple times

B. O(N^2) -- since keys can be in any room, worst case is quadratic

C. O(N + E) -- each room and each key is visited at most once

D. O(E) -- only keys matter, rooms are irrelevant

Solution

1. Step 1: Identify operations per room and key

   Each room is visited once, and each key (edge) is explored once during DFS.

2. Step 2: Combine to get total complexity

   Visiting all rooms and keys leads to O(N + E) time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Standard DFS complexity on graph with N nodes and E edges [OK]

Hint: DFS runs in O(N + E) on graphs [OK]

Common Mistakes:

• Assuming O(N * E) due to nested loops
• Confusing dense graph worst case with typical complexity
• Ignoring that visited prevents repeated work

5. The following code attempts to implement bidirectional BFS for Word Ladder. Identify the line containing the subtle bug that can cause incorrect results or infinite loops.

medium

A. Line checking if next_word in end_set to return level + 1

B. Line swapping begin_set and end_set when begin_set is larger

C. Line adding next_word to next_level and visited

D. Line initializing visited with only beginWord

Solution

1. Step 1: Examine initialization of visited set

   Visited is initialized with only beginWord, but endWord is also in end_set and should be marked visited to avoid revisiting.

2. Step 2: Consequences of missing endWord in visited

   Without marking endWord visited, the algorithm may revisit it, causing cycles or incorrect early termination.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Visited must include both beginWord and endWord [OK]

Hint: Visited must include both ends to prevent cycles [OK]

Common Mistakes:

• Forgetting to mark endWord visited
• Swapping frontiers incorrectly
• Returning too early on neighbor match