Skip to main content

785. Is Graph Bipartite?

medium

Decide whether a graph's nodes can be split into two groups with all edges crossing between the groups. Equivalent to 2-coloring — BFS/DFS and color alternately, fail on any same-color edge.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. The graph has the following properties: there are no self-edges, there are no parallel edges, and the graph may not be connected. A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B. Return true if and only if it is bipartite.

Constraints

  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • graph[u] does not contain u.
  • All the values of graph[u] are unique.
  • If graph[u] contains v, then graph[v] contains u.

Examples

Example 1

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

Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2

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

Explanation: We can partition into {0, 2} and {1, 3}.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Bipartite is equivalent to 2-colorable. Can you color every node red or blue so that no edge has both endpoints the same color?

Hint 2

BFS or DFS from any unvisited node, color it red, color all neighbors blue, then alternate. If you ever try to color a node a color different from what it already has, return false.

Hint 3

Repeat for every unvisited node since the graph may be disconnected.

Solution approach

Reveal approach

BFS-coloring across every connected component. Maintain a color array initialized to 0 (uncolored). Iterate over all n nodes — for each uncolored node, push it into a queue and color it 1. BFS: pop a node, look at neighbors; if a neighbor is uncolored, color it the opposite color (-current) and enqueue; if it's already colored the same as the current node, return false (odd cycle detected). After all components are processed without conflict, return true. DFS works equivalently with recursion. The graph being possibly disconnected is the trap to remember — wrap the BFS in an outer loop over all nodes. O(V + E) time, O(V) space for the color array plus the queue.

Complexity

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

Related patterns

  • graph-bfs
  • graph-dfs
  • union-find
  • graph-coloring

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Is Graph Bipartite? and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →