#785 Is Graph Bipartite?

frequently reported atSamsung Meta Google

the problem

In plain words

An undirected graph is given as adjacency lists graph[u]. Return true if the nodes can be split into two sets so that every edge goes between the sets. The graph may be disconnected.

in graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

out false

0, 1, 2 form a triangle — an odd cycle can't be 2-coloured.

in graph = [[1,3],[0,2],[1,3],[0,2]]

out true

Sets {0, 2} and {1, 3}.

1 ≤ n ≤ 100
No self-loops or parallel edges; u ∈ graph[v] ⇔ v ∈ graph[u]

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBipartite check (two-colouring)

Paint the start A; every neighbour must be B, their neighbours A, and so on — the colouring is forced. A single edge with the same colour on both ends means "no".

solutions

From brute force to optimal

BFS from each unpainted node; paint neighbours the opposite colour; a same-colour neighbour is a conflict.

color[] = 0 (unpainted), 1 or -1.
For every unpainted start: paint 1, BFS.
Unpainted neighbour → paint -color[u], enqueue. Same colour → return false.

timeO(V + E)

Every node painted once, every edge checked twice.

spaceO(V)

Colour array plus queue.

javajava.util.*

1class Solution {2    public boolean isBipartite(int[][] graph) {3        int n = graph.length;4        int[] color = new int[n];5        for (int start = 0; start < n; start++) { // the graph may be disconnected6            if (color[start] != 0) continue;7            color[start] = 1;8            Deque<Integer> queue = new ArrayDeque<>();9            queue.offer(start);10            while (!queue.isEmpty()) {11                int u = queue.poll();12                for (int v : graph[u]) {13                    if (color[v] == 0) {14                        color[v] = -color[u];15                        queue.offer(v);16                    } else if (color[v] == color[u]) return false;17                }18            }19        }20        return true;21    }22}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public boolean isBipartite(int[][] graph) {3        int n = graph.length;4        int[] color = new int[n];5        for (int start = 0; start < n; start++) { // the graph may be disconnected6            if (color[start] != 0) continue;7            color[start] = 1;8            Deque<Integer> queue = new ArrayDeque<>();9            queue.offer(start);10            while (!queue.isEmpty()) {11                int u = queue.poll();12                for (int v : graph[u]) {13                    if (color[v] == 0) {14                        color[v] = -color[u];15                        queue.offer(v);16                    } else if (color[v] == color[u]) return false;17                }18            }19        }20        return true;21    }22}

Same forced colouring, recursively.

paint(u, c): color[u] = c; for each neighbour: same colour → false; unpainted → paint(v, -c).

timeO(V + E)

Same work as BFS.

spaceO(V)

Colour array plus recursion depth.

javajava.util.*

1class Solution {2    private int[] color; // 0 = unpainted, 1 / -1 = the two sides3 4    public boolean isBipartite(int[][] graph) {5        color = new int[graph.length];6        for (int s = 0; s < graph.length; s++)7            if (color[s] == 0 && !paint(graph, s, 1)) return false;8        return true;9    }10 11    private boolean paint(int[][] graph, int u, int c) {12        color[u] = c;13        for (int v : graph[u]) {14            if (color[v] == c) return false;                          // neighbour on my side15            if (color[v] == 0 && !paint(graph, v, -c)) return false; // paint it the other side16        }17        return true;18    }19}

All neighbours of u must be on the same side → union them together. If u ever shares a set with a neighbour, it fails.

For each u, for each neighbour v: if find(u) == find(v) → false.
Union v with u's first neighbour.

timeO(V + E · log V)

One find/union per edge; path halving alone keeps each O(log V) amortized.

spaceO(V)

The parent array.

javajava.util.*

1class Solution {2    /** All neighbours of u must end up on the same side → union them; u must not join that group. */3    public boolean isBipartite(int[][] graph) {4        int[] parent = new int[graph.length];5        for (int i = 0; i < parent.length; i++) parent[i] = i;6        for (int u = 0; u < graph.length; u++) {7            for (int v : graph[u]) {8                if (find(parent, u) == find(parent, v)) return false;9                parent[find(parent, v)] = find(parent, graph[u][0]); // join v with u's first neighbour10            }11        }12        return true;13    }14 15    private int find(int[] parent, int x) {16        while (parent[x] != x) x = parent[x] = parent[parent[x]];17        return x;18    }19}

in the room

How to say it in the interview

talk track

Say: "Bipartite ⇔ no odd cycle ⇔ 2-colourable. I'll try to 2-colour with BFS."
Explicitly loop over every node — the graph may be disconnected.

traps

Only starting from node 0 — a conflict in another component is missed.

what they ask next

Follow-ups

Possible Bipartition (LC 886)?

Build the graph from the dislike pairs, then run exactly this check.

before you submit

Edge cases to test

A node with no edges is fine on either side.
The graph may be disconnected — the odd cycle can hide in a component that doesn't contain node 0.
An even cycle (a square) is bipartite; any odd cycle (a triangle) is not.

practise next