MediumDepth-First SearchBreadth-First SearchUnion FindGraphGraph ColoringBipartite GraphUpdated Sep 2026

785. Is Graph Bipartite?

Asked at Apple

Difficulty

Medium

Time

O(n + e)

Space

O(n)

Pattern

Depth-First Search

Companies

1

Problem

You are given an undirected graph with n nodes, numbered 0 to n - 1. The graph is given as an adjacency list: graph[u] lists every node that shares an edge with node u. Because the graph is undirected, if v appears in graph[u], then u appears in graph[v]. There are no self-edges and no duplicate edges.

A graph is bipartite if you can split all nodes into two groups, say group A and group B, so that every edge goes between the two groups. No edge may have both endpoints in the same group. Another way to say it: you can paint each node one of two colors so that neighbors always get different colors.

Return true if such a split exists, otherwise return false. Note the graph may be disconnected — some nodes may have no path to others — so you must check every separate piece of the graph.

A triangle cannot be 2-colored

graph[1,2,3][0,2][0,1,3][0,2]0123Node 0, 1 and 2 are all connected to each other — atriangle.0-1 edge: colors must differ1-2 edge: colors must differ0-2 edge: colors must differimpossible → false
In the first example, nodes 0, 1, 2 form a triangle, so no two-color split can make every edge cross between the groups.

Constraints

  • ●graph.length == n
  • ●1 <= n <= 100
  • ●0 <= graph[u].length < n
  • ●0 <= graph[u][i] <= n - 1
  • ●graph[u] does not contain u (no self-edges)
  • ●All values of graph[u] are unique (no parallel edges)
  • ●If graph[u] contains v, then graph[v] contains u (undirected)

Examples

Example 1
Inputgraph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Outputfalse
WhyNodes 0, 1 and 2 form a triangle: 0-1, 1-2 and 0-2 are all edges. In a two-coloring, 0 and 1 must differ, and 1 and 2 must differ, which forces 0 and 2 to have the same color. But 0-2 is also an edge, so they must differ. That is a contradiction, so no valid split exists.
Example 2
Inputgraph = [[1,3],[0,2],[1,3],[0,2]]
Outputtrue
WhyThe graph is a 4-cycle 0-1-2-3-0. Color 0 and 2 red, and 1 and 3 blue. Every edge joins a red node to a blue node, so the split {0,2} and {1,3} works.

Asked At

1 companies
CompanyDifficulty
AppleMediumView all Apple questions →

How to Think About It

1

Brute force: Try all possible 2-colorings of the nodes (exponential, not practical).

2

BFS or DFS coloring: Start from any uncolored node, color it red, then alternate colors for neighbors.

3

If you ever encounter a neighbor that is already colored with the same color, the graph is not bipartite.

4

The graph may be disconnected, so iterate over all nodes and start BFS/DFS from each unvisited node.

5

Union-Find approach: For each edge, if both endpoints are already in the same set, it is not bipartite.

Optimal Approach

Perform a BFS or DFS on each disconnected component, assigning alternating colors (0 and 1) to nodes. For each node, color all its neighbors with the opposite color. If any neighbor already has the same color as the current node, the graph is not bipartite. The array colors stores the assignment, with 0 meaning unvisited, 1 for one group, and -1 for the other.

BFS coloring with two colors

colors00000123startAll nodes start uncolored (0). Pick node 0 as thefirst start.colors1-1-1-10123Color node 0 with 1, and all its neighbors (1, 2, 3)with -1.colors1-1-1-10123node 1Node 1's neighbors are 0 and 2. Node 2 already hascolor -1, same as node 1 — a clash.neighbor uncolored → opposite colorneighbor same color → return falserepeat for every uncolored start
Start at any uncolored node, paint it color 1, then paint each neighbor the opposite color. A clash means the graph is not bipartite.
ComplexityTime O(n + e)Space O(n)Every node and every edge is looked at once during the BFS/DFS, and the color array holds one value per node.

What Trips People Up in Real Interviews

1

Clarify that the graph may contain disconnected components and multiple edges.

2

Confirm that self-loops immediately make a graph non-bipartite.

3

Explain the invariant: a node and all its neighbors must have opposite colors.

4

Discuss BFS vs DFS tradeoffs; both are O(V + E) time.

5

Mention the Union-Find alternative where each edge flips the parity of one endpoint.

Solution Code

O(n + e) time
from collections import deque
def isBipartite(graph):
    n = len(graph)
    colors = [0] * n
    for start in range(n):
        if colors[start] != 0:
            continue
        colors[start] = 1
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if colors[neighbor] == 0:
                    colors[neighbor] = -colors[node]
                    queue.append(neighbor)
                elif colors[neighbor] == colors[node]:
                    return False
    return True

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Is Graph Bipartite? problem?

Given an adjacency list representation of an undirected graph, determine if the graph is bipartite. A graph is bipartite if its nodes can be split into two groups such that every edge connects nodes from different groups.

How do you solve Is Graph Bipartite??

The optimal approach runs in O(n + e) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Is Graph Bipartite??

Is Graph Bipartite? is asked at Apple. It is a medium difficulty problem.

What are common mistakes on Is Graph Bipartite??
  • Clarify that the graph may contain disconnected components and multiple edges.
  • Confirm that self-loops immediately make a graph non-bipartite.
  • Explain the invariant: a node and all its neighbors must have opposite colors.
  • Discuss BFS vs DFS tradeoffs; both are O(V + E) time.
  • Mention the Union-Find alternative where each edge flips the parity of one endpoint.