Difficulty: MediumGraphs

Is Graph Bipartite?

Problem in Plain English

Given an adjacency list of an undirected graph, decide whether its nodes split into two groups with every edge crossing between groups. Odd-length cycles make this impossible.

Problem Statement

You are given an undirected graph with n nodes (0 to n - 1) as an adjacency list graph, where graph[u] lists the neighbours of u.

Return true exactly when the graph is bipartite: its nodes split into two sets A and B so that every edge joins a node in A to a node in B.

Constraints

graph.length equals n.
$1 \le n \le 100$
$0 \le \text{graph[u].length} < n$
$0 \le \text{graph[u][i]} < n$
No self-edges: graph[u] does not contain u.
No parallel edges: every value in graph[u] is unique.
If graph[u] contains v, then graph[v] contains u; the graph is undirected.

Examples

Example 1

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false

Nodes 0, 1 and 2 form a triangle, and three mutually adjacent nodes cannot fit into two groups.

Example 2

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true

Split into {0, 2} and {1, 3}: every edge runs from one group to the other.

Example 3

Input: graph = [[]]
Output: true

There are no edges to violate the rule. The isolated node may be assigned to either group; the other group may be empty.

Example 4

Input: graph = [[1],[0],[3,4],[2,4],[2,3]]
Output: false

The component containing 0 and 1 splits cleanly, but nodes 2, 3 and 4 form a triangle. Every component must be bipartite, so checking only node 0's component would miss the failure.

Example 5

Input: graph = [[],[2],[1],[]]
Output: true

The single edge 1-2 puts its endpoints in opposite groups. Isolated nodes 0 and 3 impose no additional constraints.

Intuition

Place one node in group 0 and every neighbor in group 1; repeat this forced alternation along paths. A triangle creates a contradiction because two adjacent neighbors of 0 must both receive group 1. Example 1 exposes exactly that conflict. Different connected components can choose their starting group independently, so the traversal must restart at every unassigned node. The numbers 0 and 1 are group labels, and -1 means unassigned.

Approaches

BFS Coloring

Solution Details

Reveal BFS Coloring: intuition, complexity, and code

Intuition

Use breadth-first search to assign every newly discovered neighbor the opposite group before enqueueing it. This keeps each vertex in the queue at most once. A same-group edge is a contradiction; restarting from each unassigned vertex covers isolated nodes and disconnected components. Example 1 fails while processing node 1, whose neighbor 2 already shares its group.

Step-by-Step Logic

Initialize all assignments to -1. Scan start nodes in index order and skip those already assigned; for a new component assign its start to group 0 and enqueue it. Example 1 starts at 0 with assignments [0,-1,-1,-1].
Remove the next node from the queue and inspect its neighbors in input order. Assign each unseen neighbor to 1 - color[current] before enqueueing it; from 0 this assigns 1, 2 and 3 to group 1.
For an already assigned neighbor, compare groups instead of enqueueing again. Node 1 first sees node 0 in the opposite group, which is valid, then sees node 2 in the same group, which proves a conflict.
Return false immediately on that conflict; Example 1 does not need to dequeue nodes 2 or 3. If a component empties its queue without conflict, continue the outer scan to inspect every other component.
Return true only after all components pass. In Example 2 the assignments [0,1,0,1] satisfy all four edges; isolated nodes are assigned during the outer scan.

Why It Works

Within a connected component, choosing its first group fixes every later group along a discovery path: each edge must flip the assignment. The algorithm maintains this forced assignment and checks every encountered edge between assigned vertices. If both endpoints have the same group, any valid split would have to preserve the discovery-path assignments or flip the entire component; either choice leaves that edge equal, so no valid split exists. If no conflict appears, every vertex is assigned and every edge has opposite groups, which directly supplies a valid partition. The outer loop extends this argument to all components. Assigning before enqueueing prevents duplicate work without losing any edge checks.

Dry Run

BFS Coloring: variable states at each step
Action	Queue waiting after action	Assignment array	Result
Start component at 0	[0]	[0,-1,-1,-1]	continue
Dequeue 0	[]	[0,-1,-1,-1]	inspect neighbors 1,2,3
Edge 0-1: assign opposite group	[1]	[0,1,-1,-1]	continue
Edge 0-2: assign opposite group	[1,2]	[0,1,1,-1]	continue
Edge 0-3: assign opposite group	[1,2,3]	[0,1,1,1]	continue
Dequeue 1	[2,3]	[0,1,1,1]	inspect neighbors 0,2
Edge 1-0	[2,3]	[0,1,1,1]	opposite groups: valid
Edge 1-2	[2,3]	[0,1,1,1]	equal groups: return false

Complexity Analysis

Time Complexity

O(V + E)

Space Complexity

O(V)

V = graph.length and E is the number of undirected edges, so the supplied adjacency lists contain 2E entries. Each vertex is assigned and enqueued once, and each adjacency entry is checked at most once. The color array and queue allocate O(V) extra space; the input adjacency list is reused unchanged. Java and Python use constant-time deque removal. JavaScript advances a head index through its queue instead of shift(), avoiding repeated array movement; processed entries stay allocated until the component finishes, still at most V entries.

Code

Solution.java

1import java.util.Arrays;2import java.util.ArrayDeque;3import java.util.Queue;4
5class Solution {6    public boolean isBipartite(int[][] graph) {7        int n = graph.length;8        int[] color = new int[n];9        Arrays.fill(color, -1);10        Queue<Integer> queue = new ArrayDeque<>();11        // Disconnected components impose independent group choices.12        for (int start = 0; start < n; start++) {13            if (color[start] != -1) {14                continue;15            }16            color[start] = 0;17            queue.offer(start);18            while (!queue.isEmpty()) {19                int curr = queue.poll();20                for (int next : graph[curr]) {21                    if (color[next] == -1) {22                        // Assign before enqueueing so several neighbors cannot enqueue it twice.23                        color[next] = 1 - color[curr];24                        queue.offer(next);25                    } else if (color[next] == color[curr]) {26                        // This edge contradicts the forced assignments along paths.27                        return false;28                    }29                }30            }31        }32        return true;33    }34}

Hints

Hint 1

Think of group 0 and group 1 as two labels. If a node uses one label, what must every neighbor use?

Hint 2

A triangle makes the forced assignments collide. Detect that collision by comparing the labels on every already assigned edge.

Hint 3

Start another traversal whenever the outer scan finds an unassigned vertex. The graph may be disconnected, and every component must pass.

Edge Cases

A single isolated node and an entirely edgeless graph return true; empty groups are allowed.
A disconnected graph fails if any component contains an odd cycle, even when node 0 belongs to a valid component. Example 4 illustrates this.
An even cycle such as Example 2 is bipartite: a cycle does not automatically mean failure. An odd cycle forces a same-group closing edge.
A 100-node path reaches the maximum recursive depth; a complete bipartite graph with 50 vertices per group checks many edges without conflict.
Self-edges and repeated neighbors are excluded by the input contract. A defensive same-group check would reject a self-edge, but authored examples should use valid inputs.

Common Mistakes and Interview Tips

Checking only the component containing node 0; a later triangle can make the whole graph fail.
Treating any cycle as failure. Bipartiteness rejects odd cycles, while a four-node cycle has a valid alternating partition.
Using 0 for both unassigned and group 0. Keep -1 as the unassigned sentinel so a legitimate group is never mistaken for unseen.
Marking a node only when it leaves the BFS queue can enqueue it many times. Assign the group before enqueueing, and use a head index in JavaScript instead of shift().
Ignoring the false result of a recursive child, which allows a detected contradiction to disappear on the way back to the caller.
Interview tip: explain why flipping all groups in one connected component cannot resolve a same-group edge, and why separate components may choose their starting labels independently.

Key Takeaway

Bipartiteness is two-colouring by force: propagate opposite colours and read the first conflict as proof of an odd cycle.