How do you approach Is Graph Bipartite??

Try to 2-color the graph: a node and its neighbors must have opposite colors.

What are common mistakes on Is Graph Bipartite??

Building the adjacency list in one direction on an undirected graph. Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest. Ignoring self-loops and parallel edges when the constraints allow them.

gitGood.dev

← Back to problems

Is Graph Bipartite?

MediumAlgorithms

Description

Given an undirected graph as an adjacency list graph (where graph[u] lists the neighbors of u), return true if the graph is bipartite.

A graph is bipartite if its nodes can be split into two sets such that every edge connects a node in one set to a node in the other.

Example 1

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

Output: true

Explanation: Split into {0,2} and {1,3}.

Example 2

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

Output: false

Explanation: Odd cycle 0-1-2-0.

Constraints

- 1 <= graph.length <= 100 - graph[u] does not contain u and has no duplicates - The graph may be disconnected

Is Graph Bipartite?: approach, complexity and pitfalls

A medium graphs problem, graded against 7 test cases (5 of them hidden).

The pattern: Graphs

Nodes and edges - traversal, connectivity, cycles, and shortest paths.

Reach for it when you see: Explicit edges, a grid treated as a graph, or dependencies between items.

If you are stuck

Show the 2-step hint ladder

Try to 2-color the graph: a node and its neighbors must have opposite colors.
BFS/DFS each component; a conflict (a neighbor with the same color) means not bipartite.

The optimal approach

Show the approach: The approach

2-coloring via BFS. Color each uncolored node, then color its neighbors with the opposite color. If you ever find an edge whose endpoints share a color, the graph has an odd cycle and is not bipartite. Repeat for every component.

Time: O(V + E). Space: O(V).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Graphs mistakes

These apply to the pattern as a whole, not just this problem.

Building the adjacency list in one direction on an undirected graph.
Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest.
Ignoring self-loops and parallel edges when the constraints allow them.