Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Try to 2-color the graph so every edge joins two differently colored nodes. Walk each component with BFS or DFS: color a start node, then force every neighbor to the opposite color. If you ever hit a neighbor already wearing the same color, the graph is not bipartite. A graph is bipartite exactly when it has no odd-length cycle. Both traversals run in O(V + E).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize 'split into two sides' as graph 2-coloring, handle disconnected components, and know the odd-cycle characterization.
Where candidates slip
Coloring only the component containing node 0 and returning true, or conflating the 'uncolored' sentinel with one of the two real colors.
How to stand out
State the odd-cycle equivalence, show both BFS and DFS, and explain that `color ^ 1` flips between the two sides in one operation.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewSplit nodes into two sides?Iterative or recursive?IterativeRecursiveExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
BFS Two-Coloring (Optimal)
1Hint 1Explore hintHide hint
If you place one node on side A, where must all its neighbors go? And their neighbors after that?
2Hint 2Explore hintHide hint
Color a start node 0. BFS its neighbors: any uncolored neighbor gets the opposite color; enqueue it.
3Hint 3Explore hintHide hint
If you reach a neighbor that already has the SAME color as the current node, two adjacent nodes share a side — not bipartite. Repeat from every uncolored node for disconnected components.
A · Core idea
Spread two colors outward in waves and fail the instant two neighbors share one.
The forcing rule. Bipartite means two sides with every edge crossing between them. Once you place a node on side A (color 0), all of its neighbors are forced onto side B (color 1) — there is no choice. Their neighbors are forced back to A, and so on. BFS naturally explores in these expanding layers, and the colors alternate layer by layer.
The clash test. As you dequeue a node u and scan its neighbors v, two cases arise. If v is uncolored, paint it color[u] ^ 1 (the opposite side) and enqueue it. If v already has a color and it equals color[u], two adjacent nodes landed on the same side — the graph cannot be split, so return false immediately.
Why it detects odd cycles. A graph is bipartite exactly when it has no odd-length cycle. Walking an even cycle, the colors alternate and meet consistently. Walking an odd cycle, the alternation wraps around and forces a node to clash with a same-colored neighbor — which is precisely the failure the clash test catches.
Why the outer loop. Because components are independent, you start a fresh BFS from every still-uncolored node. Missing this is the classic bug: coloring only node 0's component and declaring the whole graph bipartite.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
graph = [[1,3],[0,2],[1,3],[0,2]]Interactive diagram
Even cycle colors cleanly (bipartite)
startThe 4-cycle alternates 0,1,0,1 and closes consistently — no clash.
trueC · Code with teaching comments
D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
The coloring is fully forced once you pick a start: there are no decisions to make, only consistency to verify. That is why a single linear pass suffices — you are not searching among colorings, you are checking whether the one forced coloring holds together.
ComplexityO(V + E) time, O(V + E) space — Each node is enqueued once and colored once: O(V). Each edge is examined once from each endpoint as nodes are dequeued: O(E). Total O(V + E). The color array and queue are O(V); the adjacency list is O(V + E).
E · Edge cases and pitfalls7single node, no edges — Colored 0, no neighbors to clash → true.Explore edge casesHide edge cases
Edge cases handled
single node, no edgesColored 0, no neighbors to clash → true.graph = [[1],[0]] (single edge)0→A, 1→B, edge crosses → true.triangle [[1,2],[0,2],[0,1]]0→A,1→B, then 2 is forced opposite both → clash → false.two components, one odd cycleOuter loop starts BFS in the second component and catches the clash → false.
Pitfalls
- Coloring only node 0's component and returning true — disconnected components go unchecked.
- Using 0 as both 'uncolored' and a real color, corrupting the clash test.
- Returning false on any re-seen node instead of only on a same-color one.
Approach 2 of 2
DFS Two-Coloring (Recursive Alternative)
1Hint 1Explore hintHide hint
Recursively color a node, then color each neighbor with the opposite and recurse into it.
2Hint 2Explore hintHide hint
Pass the expected color down the recursion; if a neighbor is already colored, it must match the expected opposite color.
3Hint 3Explore hintHide hint
Return false the moment a recursive call detects a clash, and bubble that up.
A · Core idea
Color depth-first, carrying the side each node must take.
The recursive contract. dfs(u, c) paints u with color c and then demands that every neighbor take c ^ 1. For an uncolored neighbor it recurses with the flipped color; for an already-colored neighbor it checks the color matches what it should be.
Where the clash surfaces. If a neighbor v is already colored and its color equals color[u] (not the opposite), the recursion returns false. That false propagates straight up the call stack and out of the function.
Same odd-cycle logic. Whether you go breadth-first or depth-first, the forced coloring is identical. DFS just discovers the clash while deep in a path rather than while expanding a layer; both find an odd cycle if one exists.
Driver over components. As with BFS, you call dfs(start, 0) for every uncolored node so disconnected components are all verified.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]Interactive diagram
DFS recursion coloring a path
dfs(0,0)Color alternates as the recursion descends; a clash returns false up the stack.
falseC · Code with teaching comments
Reference implementation previewprivate int[] color; public boolean isBipartite(int[][] graph) { int n = graph.length; color = new int[n];Explore the full codeHide the full code
D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
BFS and DFS produce the very same two-coloring because the coloring has no free choices — only the traversal order differs. Pick whichever control flow you find less error-prone under interview pressure.
ComplexityO(V + E) time, O(V + E) space — Every node is colored once and each edge is traversed once across the recursion: O(V + E). The color array is O(V), and recursion depth is O(V) in the worst case (a long path).
E · Edge cases and pitfalls3Recursing into an already-colored neighbor instead of just checking it — causes infinite recursion.Explore edge casesHide edge cases
Pitfalls
- Recursing into an already-colored neighbor instead of just checking it — causes infinite recursion.
- Forgetting the driver loop, so disconnected components are never colored.
- Deep recursion on a long path can overflow the stack — BFS avoids that.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean isBipartite(int[][] graph) { int n = graph.length; int[] color = new int[n]; Arrays.fill(color, -1); // -1 = uncolored for (int start = 0; start < n; start++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Only coloring one component
If you BFS from node 0 alone and return true, a non-bipartite component you never entered is missed entirely.
Explore the code comparisonHide the code comparison
Only coloring one component
If you BFS from node 0 alone and return true, a non-bipartite component you never entered is missed entirely.
Don't write this
color = [-1] * n
color[0] = 0
# BFS from 0 only...
return True # WRONG: other components uncheckedWrite this instead
for start in range(n):
if color[start] != -1:
continue
color[start] = 0
# BFS from start covers every component2Uncolored sentinel collides with a real color
If uncolored is 0 and a real side is also 0, an uncolored neighbor looks like it already shares the current node's side, producing false clashes.
Explore the code comparisonHide the code comparison
Uncolored sentinel collides with a real color
If uncolored is 0 and a real side is also 0, an uncolored neighbor looks like it already shares the current node's side, producing false clashes.
Don't write this
int[] color = new int[n]; // all 0 = looks pre-colored
// ... color[v] == color[u] fires on uncolored nodesWrite this instead
int[] color = new int[n];
Arrays.fill(color, -1); // distinct uncolored marker
// now color[v] == color[u] only on real same-side clashesRevise
Carry the pattern into the interview
Pattern to remember
2-coloring by BFS/DFS — neighbors must get the opposite color
Code pattern to memorize
color[] = -1 (uncolored)
for each uncolored start s:
color[s] = 0; BFS/DFS
for edge u→v:
if color[v] == -1: color[v] = color[u] ^ 1
elif color[v] == color[u]: return False
return TrueRules to remember
- 1Color a neighbor with
color[u] ^ 1— the opposite of the current node. - 2A clash (neighbor already has the same color) is the only failure condition.
- 3Loop over every node as a start — the graph may be disconnected, and each component must be checked.
- 4Use
-1(or a separate visited array) for 'uncolored'; don't confuse uncolored with color 0. - 5Bipartite ⇔ no odd-length cycle. An odd cycle is exactly what forces a same-color clash.
Use this pattern when
- Splitting nodes into two groups with all edges crossing between groups
- Conflict / 'these two can't share' problems modeled as 'opposite sides'
- Checking if a relationship graph is two-sided (e.g. two teams, like/dislike)
- Detecting odd cycles in an undirected graph
Choose another pattern when
- Need 3+ groups → general graph coloring, which is NP-hard, not 2-coloring
- Directed cycle detection → three-color DFS, a different problem
- Matching within a bipartite graph → Hungarian / Hopcroft-Karp, not just the check
- Weighted partitioning → not a coloring problem at all
Interview takeaway
Bipartite testing is just 2-coloring: paint neighbors opposite and watch for a clash. A clash means an odd cycle, the one thing that makes two-sided coloring impossible. BFS and DFS both nail it in O(V+E).
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternBipartite check = graph 2-coloring: paint neighbors opposite via BFS or DFS and fail on a same-color clash, which signals an odd cycle. Same coloring idea appears in Possible Bipartition and bipartite-matching setups.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Possible BipartitionComing soonBuild the dislike graph and run the same 2-coloring; can the people split into two groups?
- Flower Planting With No AdjacentComing soonA bounded-degree coloring variant — 4 colors always suffice when each node has ≤3 neighbors.
- Course ScheduleDifferent coloring story: three-color DFS for directed cycle detection, not two-side partition.
- Maximum Students Taking ExamComing soonWhen 2-coloring isn't enough, bipartite structure feeds maximum-matching / independent-set techniques.