What is the brute force approach and complexity for Is Graph Bipartite??

Try all 2^n colourings; accept the first one where no edge has equal colours with time complexity O(2^N · (N + E)) and space complexity O(1).

What is the optimal approach and complexity for Is Graph Bipartite??

Colour a node, give its neighbours the other colour; start a new BFS for each uncoloured node with optimal time complexity O(N + E) and space complexity O(N).

How do you identify the pattern for Is Graph Bipartite??

Look for key signals in the prompt: "split the nodes into two groups" indicates Two groups are two colours: a 2-colouring.; "every edge joins a node in one group to a node in the other" indicates A rule on every edge: its two ends must get different colours.; "several separate pieces, nodes with no edges" indicates Start a new BFS in every piece, not only the one that holds node 0..

Is Graph Bipartite?

Medium·LeetCode #785Basic Anchor

LeetCode

Jump:

30-Second Mental ModelBipartite / two-colouring (BFS colours each piece)

Complexity:O(2^N · (N + E))→O(N + E)

Key Insight

Run a breadth-first search from each node that has no colour yet. Give the start colour 0. Every neighbour without a colour gets the opposite colour. If a neighbour already has the same colour as the node being popped, the answer is false. The outer loop covers every piece of the graph.

Core Validity Invariant

Every edge joins two nodes with different colours. Each edge is checked when its first end is popped, and by then both ends have colours.

Problem

You are given an undirected graph as an adjacency list. graph[u] lists every node that node u is joined to by an edge.

Can the nodes be split into two groups so that every edge joins a node in one group to a node in the other? Nodes inside one group may not be joined to each other.

Return true if such a split exists, otherwise false. The graph may have several separate pieces, and a node may have no edges at all.

Input

graph, an adjacency list of n nodes numbered 0 to n − 1.

Output

true if the nodes can be split into two groups with no edge inside a group, otherwise false.

Example 1

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

Output: false

Nodes 0, 1 and 2 are all joined to each other, a triangle. Each pair in the triangle must be in different groups, but with only two groups one pair always shares a group.

Example 2

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

Output: true

Put nodes 0 and 2 in one group and nodes 1 and 3 in the other. Every edge joins the two 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
• All the values in graph[u] are unique
• If graph[u] contains v, then graph[v] contains u

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
What does an edge tell me about two nodes: must they be in the same group, or in different groups?
2.
If I give one node a group, which groups are forced on its neighbours?
3.
What goes wrong if I only look at the piece that contains node 0?
4.
How does a clash show up: between a node and a neighbour that already has a group?
5.
With n nodes and two groups, how many splits are there to try?

Brute force approach

Idea

Try every way to give each node colour 0 or 1. A colouring is valid when no edge has both ends the same colour. If one is valid, return true; if none is, return false. There are 2^n colourings, so this only works for tiny graphs.

Thinking process

1
The two groups are the two colours. We want one colouring in which every edge changes colour.
2
Each node has two choices, so n nodes give 2^n colourings. The masks enumerate them: bit u of the mask is the colour of node u.
3
Check on the triangle 0–1–2: each of the 8 colourings has an edge with both ends the same colour, because three nodes cannot each take a different colour from the other two when only two colours exist. So all 8 are rejected, and the answer is false.
4
Stop as soon as one colouring works. If none works, every colouring was tried and the answer is false.

Visual

Each step is one colouring of all nodes (bit u = colour of node u). Red edge = the clash that rejects it. The first colouring with no clash ends the search.

Brute force: try every colouringgraph = [[1, 3], [0, 2, 4], [1], [0], [1]]step 1/11

graph

Try

mask: 00000
colours: AAAAA
result: clash on 0–1

Colouring AAAAA: 0 and 1 clash → reject

Try colouring AAAAA. Nodes 0 and 1 are joined by an edge but have the same colour, so this split is rejected.

Code & Implementation

brute.cpp

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        // Try every colouring: bit u of mask is the colour (0 or 1) of node u.
        for (int mask = 0; mask < (1 << n); mask++) {
            bool ok = true;
            for (int u = 0; u < n && ok; u++) {
                for (int v : graph[u]) {
                    // Both ends of an edge must get different colours.
                    if (((mask >> u) & 1) == ((mask >> v) & 1)) { ok = false; break; }
                }
            }
            if (ok) return true;      // found one valid split into two sets
        }
        return false;                 // no colouring works
    }
};

import java.util.*;

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        // Try every colouring: bit u of mask is the colour (0 or 1) of node u.
        int total = 1 << n;
        for (int mask = 0; mask < total; mask++) {
            boolean ok = true;
            for (int u = 0; u < n && ok; u++) {
                for (int v : graph[u]) {
                    // Both ends of an edge must get different colours.
                    if (((mask >> u) & 1) == ((mask >> v) & 1)) {
                        ok = false;
                        break;
                    }
                }
            }
            if (ok) return true; // found one valid split into two sets
        }
        return false; // no colouring works
    }
}

from typing import List

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        # Try every colouring: bit u of mask is the colour (0 or 1) of node u.
        for mask in range(1 << n):
            ok = True
            for u in range(n):
                if not ok:
                    break
                for v in graph[u]:
                    # Both ends of an edge must get different colours.
                    if ((mask >> u) & 1) == ((mask >> v) & 1):
                        ok = False
                        break
            if ok:
                return True  # found one valid split into two sets
        return False  # no colouring works

export function isBipartite(graph: number[][]): boolean {
    const n = graph.length;
    // Try every colouring: bit u of mask is the colour (0 or 1) of node u.
    const total = 1 << n;
    for (let mask = 0; mask < total; mask++) {
        let ok = true;
        for (let u = 0; u < n && ok; u++) {
            for (const v of graph[u]) {
                // Both ends of an edge must get different colours.
                if (((mask >> u) & 1) === ((mask >> v) & 1)) {
                    ok = false;
                    break;
                }
            }
        }
        if (ok) return true; // found one valid split into two sets
    }
    return false; // no colouring works
}

Complexity

Time O(2^N · (N + E))Space O(1)

N is the number of nodes and E the number of edges. There are 2^N colourings, and each one checks every edge once, so the work is 2^N times the size of the graph. The mask is the only extra storage. Fine for small graphs only (the tests use up to 9 nodes).

Optimized approach

Idea

Start from brute force

Brute force tries all 2^n colourings. Most of them break on the same edge, and one colour choice forces the colours of the nodes next to it.

Find the repeated work

Once a node has a colour, each neighbour's colour is fixed too. Brute force re-checks these forced choices again in every colouring that agrees with them.

Define the state — what variables do I need?

color[u]: 0 or 1 for the group of node u, or -1 if node u has no group yet.
queue: Coloured nodes whose neighbours have not been checked yet.
s: The start of the next BFS. The outer loop visits every node, so each piece gets one start.

Define validity

Every edge joins two nodes with different colours. Each edge is checked when its first end is popped, and by then both ends have colours.

Define the transitions — when does each pointer move, and why is it safe?

An uncoloured node s

color[s] = 0; start a BFS from s

A new piece needs a start. Its colour is arbitrary, so 0 is fine.

Pop u, and a neighbour v has no colour

color[v] = 1 − color[u]; push v

The edge u–v must join two different colours, and v has no colour yet.

Pop u, and a neighbour v has the same colour as u

Return false

The edge u–v joins two nodes in the same group, which is not allowed.

Every node has a colour and no clash appeared

Return true

Every edge was checked, and each one joins two different colours.

What does the current window add to the answer?

Each node is coloured once. The answer changes to false only at a clash, and a clash always means an odd cycle, which no split can handle.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, -1);             // -1 = not coloured yet

        // The graph may be split into pieces, so start a BFS from every uncoloured node.
        for (int s = 0; s < n; s++) {
            if (color[s] != -1) continue;
            color[s] = 0;
            queue<int> q;
            q.push(s);
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (int v : graph[u]) {
                    if (color[v] == -1) {
                        color[v] = 1 - color[u];     // a neighbour takes the other colour
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        return false;                // an edge joins two nodes of the same colour
                    }
                }
            }
        }
        return true;
    }
};

import java.util.*;

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n]; // -1 = not coloured yet
        Arrays.fill(color, -1);

        // The graph may be split into pieces, so start a BFS from every uncoloured node.
        for (int s = 0; s < n; s++) {
            if (color[s] != -1) continue;
            color[s] = 0;
            Queue<Integer> q = new LinkedList<>();
            q.offer(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : graph[u]) {
                    if (color[v] == -1) {
                        color[v] = 1 - color[u]; // a neighbour takes the other colour
                        q.offer(v);
                    } else if (color[v] == color[u]) {
                        return false; // an edge joins two nodes of the same colour
                    }
                }
            }
        }
        return true;
    }
}

from typing import List
from collections import deque

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [-1] * n  # -1 = not coloured yet

        # The graph may be split into pieces, so start a BFS from every uncoloured node.
        for s in range(n):
            if color[s] != -1:
                continue
            color[s] = 0
            q = deque([s])
            while q:
                u = q.popleft()
                for v in graph[u]:
                    if color[v] == -1:
                        color[v] = 1 - color[u]  # a neighbour takes the other colour
                        q.append(v)
                    elif color[v] == color[u]:
                        return False  # an edge joins two nodes of the same colour

        return True

export function isBipartite(graph: number[][]): boolean {
    const n = graph.length;
    const color: number[] = Array(n).fill(-1); // -1 = not coloured yet

    // The graph may be split into pieces, so start a BFS from every uncoloured node.
    for (let s = 0; s < n; s++) {
        if (color[s] !== -1) continue;
        color[s] = 0;
        const q: number[] = [s];
        let head = 0;
        while (head < q.length) {
            const u = q[head++];
            for (const v of graph[u]) {
                if (color[v] === -1) {
                    color[v] = 1 - color[u]; // a neighbour takes the other colour
                    q.push(v);
                } else if (color[v] === color[u]) {
                    return false; // an edge joins two nodes of the same colour
                }
            }
        }
    }
    return true;
}

Complexity

Time O(N + E)Space O(N)

N is the number of nodes and E the number of edges. Each node gets a colour once and is popped once, and each edge is looked at from both ends. The colour array and the queue take O(N).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Try all 2^n colourings; accept the first one where no edge has equal colours	O(2^N · (N + E))	O(1)
Optimal	Colour a node, give its neighbours the other colour; start a new BFS for each uncoloured node	O(N + E)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“split the nodes into two groups”Two groups are two colours: a 2-colouring.
“every edge joins a node in one group to a node in the other”A rule on every edge: its two ends must get different colours.
“several separate pieces, nodes with no edges”Start a new BFS in every piece, not only the one that holds node 0.

Graph of nodes and edges+two colours+a neighbour must take the other colour→Bipartite / two-colouring (BFS colours each piece)

Colour one node and the rest of its piece is forced. That turns the check into a BFS: colour as you go, and a clash on any edge means false. This is the anchor of the Bipartite sub-pattern. The next question uses the same check, after building the graph from a list of pairs.

Don't make this mistake

Pattern confusion: checking only the piece with node 0

✗ color[0] = 0; BFS from 0 only; return true;

✓ for (int s = 0; s < n; s++) if (color[s] == -1) { color[s] = 0; BFS from s; }

On [[1],[0],[3,4],[2,4],[2,3]] (an edge 0–1 and a triangle 2–3–4), a BFS from node 0 alone colours 0 and 1, finds no clash, and returns true. The triangle is never looked at. The correct answer is false.

Checking only neighbours that have no colour yet

✗ if (color[v] == -1) { color[v] = 1 - color[u]; q.push(v); } // no else branch

✓ if (color[v] == -1) { color[v] = 1 - color[u]; q.push(v); } else if (color[v] == color[u]) return false;

On the triangle [[1,2],[0,2],[0,1]], popping 0 colours nodes 1 and 2 with colour B. Popping 1 finds node 2 already coloured B, the same colour as 1, but the wrong version does not look at it. Popping 2 checks nothing, because its neighbour 1 is skipped the same way. It returns true, but a triangle cannot be split.

Using 1 << n for large n

✗ for (int mask = 0; mask < (1 << n); mask++) // n up to 100

✓ // use the BFS two-colouring instead; the mask loop is only for tiny n

1 << n is undefined for n of 31 or more, and 2^100 colourings would never finish. The mask loop only works for small graphs, which is why it is the brute force and not the answer.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track

C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track

Possible Bipartition