Coding · Graphs and grids
Is Graph Bipartite?
- Appears on company lists
- Medium
- 1 source
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
An undirected graph has nodes numbered 0 to n - 1 and is given as an adjacency list, where graph[i] holds the neighbours of node i. Decide whether the nodes can be split into two groups so that every edge joins a node of one group to a node of the other. For graph [[1, 2], [0, 2], [0, 1, 3], [2]], a triangle with a tail, the answer is false. The graph may be disconnected and has up to 10,000 nodes.
Restated in our own words, not a quote from Apple or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: can the graph be disconnected, so that I must check every component? Can a node list itself as a neighbour, and can an edge be listed twice? Is the adjacency list guaranteed to be symmetric, so that if j is in graph[i] then i is in graph[j]? What should an empty graph or a graph with no edges return?
I would assume a symmetric list, possible disconnected components, and no promise about self loops, so I will handle them. An empty graph and a graph with no edges are both bipartite, so they return true. I will return a boolean and nothing else.
Brute force
Say the obvious answer and why it is too slow.
The direct approach assigns each node to group A or group B in every possible way and checks that no edge has both ends in the same group. That is 2 to the power n assignments, each checked in O(n + e), so exponential in the number of nodes.
It is fine for 10 nodes and hopeless for 40, since 2 to the power 40 is about a trillion assignments. With 10,000 nodes it can never finish. The brute force also ignores that the assignment is not really free: once you place one node, every neighbour of that node is forced to the other group, so almost all of those assignments are doomed from the first step.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(2^V · (V + E))
- Time
- O(V + E)
- Space
- O(V)
The forcing is the whole idea. Put a start node in group 0. Every neighbour must then be in group 1, every neighbour of those must be in group 0, and so on. Inside one connected component there is no choice left: the first node's group fixes all the others, and swapping the two groups gives the only other valid answer. So one attempt per component is enough, and the work is a graph traversal.
Use breadth-first search with a colour array where -1 means unseen. When you pop a node and look at a neighbour, there are two cases. If the neighbour is unseen, give it the opposite colour and queue it. If it already has a colour, that colour must be the opposite of the current node's. If the colours are equal, an edge joins two nodes that the forcing put in the same group, so no valid split exists and we return false at once.
Why this is sufficient: if the whole traversal finishes with no conflict, every edge was examined from at least one end and found to join different colours, so the colouring is a valid split. Why a conflict is final: the colours were forced, not chosen, so no other colouring could do better. The same fact says a graph is bipartite exactly when it has no cycle of odd length.
The one loop that people drop is the outer one: after finishing a component, scan for the next unseen node and start again. A self loop is detected for free, because the neighbour of a node is itself and has the same colour. The pattern is graph two-colouring with BFS, O(V + E) time and O(V) memory. Out loud: "colour by BFS level parity, fail on a same-colour edge."
Walk it through
A dry run on the example, step by step.
| Node popped | Neighbour | Colours of 0..3 | Action |
|---|---|---|---|
| start at 0 | - | 0 - - - | colour 0, queue [0] |
| 0 | 1 (unseen) | 0 1 - - | colour 1, queue [1] |
| 0 | 2 (unseen) | 0 1 1 - | colour 1, queue [1, 2] |
| 1 | 0 (colour 0) | 0 1 1 - | differs, fine |
| 1 | 2 (colour 1) | 0 1 1 - | same as node 1: false |
The graph is the triangle 0-1-2 with a tail 2-3. We start at node 0, give it colour 0, and queue it. Popping node 0 shows two uncoloured neighbours: node 1 gets colour 1 and node 2 gets colour 1, and both enter the queue. At this point the colour column reads "0 1 1 -".
Now pop node 1. Its neighbour 0 has colour 0, which differs from 1, so that edge is fine. Its other neighbour is node 2, and node 2 already has colour 1, the same as node 1. That edge joins two nodes in the same group, which proves an odd cycle, the triangle, so the function returns false immediately. Node 3 is never reached, and the answer does not depend on it. A bipartite graph, such as a square, would instead drain the queue with no conflict.
The code
Runnable JavaScript, checked against test cases.
function isBipartite(graph) {
const colour = new Array(graph.length).fill(-1);
for (let start = 0; start < graph.length; start++) {
if (colour[start] !== -1) continue;
colour[start] = 0;
const queue = [start];
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
for (const next of graph[node]) {
if (colour[next] === -1) {
colour[next] = 1 - colour[node];
queue.push(next);
} else if (colour[next] === colour[node]) {
return false;
}
}
}
}
return true;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
No nodes: the outer loop does not run, so the result is true. A node with no neighbours: it is coloured and the inner loop is empty. Disconnected components: the outer loop starts a new traversal at every unseen node, and a failure in any one component fails the whole graph, including components that come after a bipartite one.
A self loop such as node 0 listing 0: the neighbour has the same colour as the node itself, so it returns false, which is correct because an edge cannot join a node to its own group. Duplicate neighbours are harmless since the second look sees opposite colours. Large trees and paths are bipartite, and a long chain does not overflow anything, because the queue is a plain array and not a recursion stack.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return the two groups instead of only a boolean?
- How would you solve it with union-find, and what do you store besides the parent?
- How would you return an odd cycle as proof when the answer is false?
- Does a depth-first version change the answer, and what is the stack risk?
- How does this relate to splitting people into two teams when some pairs dislike each other?
Where candidates slip
The mistakes this problem punishes.
The biggest slip is starting from node 0 only. If the graph has several components, the others are never checked and an odd cycle hides in one of them. The next is marking the colour when popping from the queue instead of when pushing, which lets one node be queued several times and can colour it twice with different values.
Candidates also compare the colour of the neighbour to a fixed number instead of to the current node, treat an already coloured neighbour as automatically fine, or use queue.shift() in a hot loop, which can make the traversal slow on large inputs; an index pointer avoids it. Finally, some report "false" as soon as they see any cycle, but even cycles are allowed: only odd cycles break the split.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.