What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

11. Bipartite Graph Validation: Is Graph Bipartite? • Invariant Proof & Speed-Run

Theory Context•Graph Algorithms

MediumLC 785

Is Graph Bipartite? (LeetCode 785)

Target Frequency:MetaAmazonGoogleApple

You're given an undirected graph on n nodes (numbered 0 to n - 1) as an adjacency list graph, where graph[u] lists every node u shares an edge with. There are no self-loops, no duplicate edges, edges are listed symmetrically on both endpoints, and the graph doesn't need to be one connected piece.

Decide whether the nodes can be split into two groups A and B such that no edge ever connects two nodes in the same group — i.e., whether the graph is bipartite.

Return true if such a split exists, false otherwise.

Worked Examples

Example 1

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

Output:false

Explanation: Nodes 0, 1 and 2 are all linked to each other in a triangle. Whichever way you split them into two groups, two of them land in the same group while sharing an edge.

Example 2

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

Output:true

Explanation: Grouping {0, 2} on one side and {1, 3} on the other leaves every edge crossing between the two groups.

⚖️Formal Constraints & Bounds

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.

Deep-Dive & Conceptual Insights

Core Insight

One side for the first node forces every other side in its component, so a same-side edge (color[nxt] == color[node]) is the only way to fail, and it means an odd cycle; start a search from every uncolored node, since the graph may be disconnected.

Real-World Scenario & Production Applications

Conflict-scheduling problems (can every task be split into two non-conflicting shifts?) and matching-market validity checks (can buyers and sellers be cleanly separated with no same-side edges?).

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Open a Search at Every Uncolored Node

The graph may be disconnected, so every node still at color[start] == -1 opens its own search, and its first node takes side 0. A search from node 0 alone never checks a component that doesn't touch node 0.

Mathematical Recurrence / Code Invariant

color = [-1] * len(graph)
for start in range(len(graph)):
    if color[start] != -1:
        continue
    color[start] = 0
    queue = deque([start])

Step-by-Step Execution Trace Table

Step-by-Step Two-Coloring (graph = [[1,3],[0,2],[1,3],[0,2]])

Step 1 (Nothing Colored): color = [-1, -1, -1, -1]: no node has a side yet.
Step 2 (Open a Component): start = 0 has color[0] == -1, so color[0] = 0 and queue = [0].
Step 3 (Pop 0, Color Its Neighbours): Neighbours 1 and 3 have no side, so color[1] = 1 - 0 = 1 and color[3] = 1. queue = [1, 3].
Step 4 (Pop 1): Neighbour 0 is on side 0, the other side from 1: the edge crosses, fine. Neighbour 2 has no side, so color[2] = 1 - 1 = 0. queue = [3, 2].
Step 5 (Pop 3): Neighbours 0 and 2 are both on side 0, the other side from 3: no clash.
Step 6 (Pop 2): Neighbours 1 and 3 are both on side 1, the other side from 2: no clash. The queue is empty.
Step 7 (Every Start Checked): start = 1, 2, 3 are already colored, so no new search opens. Search Complete: side 0 = {0, 2}, side 1 = {1, 3}, return true ✅.

Full Walkthrough7 Steps

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

1⚡ STEP(Nothing Colored)

color = [-1, -1, -1, -1]: no node has a side yet.

2⚡ STEP(Open a Component)

queue = [0]

start = 0 has color[0] == -1, so color[0] = 0 and queue = [0].

3⚡ FIFO DRAIN(Pop 0, Color Its Neighbours)

queue = [1, 3]

Neighbours 1 and 3 have no side, so color[1] = 1 - 0 = 1 and color[3] = 1. queue = [1, 3].

4⚡ FIFO DRAIN(Pop 1)

queue = [3, 2]

Neighbour 0 is on side 0, the other side from 1: the edge crosses, fine. Neighbour 2 has no side, so color[2] = 1 - 1 = 0. queue = [3, 2].

5⚡ FIFO DRAIN(Pop 3)

Neighbours 0 and 2 are both on side 0, the other side from 3: no clash.

6⚡ FIFO DRAIN(Pop 2)

Neighbours 1 and 3 are both on side 1, the other side from 2: no clash. The queue is empty.

7✅ RECORD / GOAL(Every Start Checked)

start = 1, 2, 3 are already colored, so no new search opens. Search Complete: side 0 = {0, 2}, side 1 = {1, 3}, return true ✅.

Code Shape

Archetype Code Shape

Python

1	color = [-1] * len(graph)
2	for start in range(len(graph)):
3	if color[start] != -1:
4	continue
5	color[start] = 0
6	queue = deque([start])
7	while queue:
8	node = queue.popleft()
9	for nxt in graph[node]:
10	if color[nxt] == -1:
11	color[nxt] = 1 - color[node]
12	queue.append(nxt)
13	elif color[nxt] == color[node]:
14	return False
15	return True

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

A graph is bipartite when its nodes can be split into two sides so that every edge runs between the sides, never inside one. The check is a two-coloring: the first node of a component takes side 0 with color[start] = 0, and every neighbour the search reaches with no side yet takes the other side, color[nxt] = 1 - color[node]. Every color is forced by that first choice, so the only question left is whether some edge ends up with the same side on both ends, and that happens exactly when the graph has a cycle of odd length.

👕 The Analogy: Two Sports Teams Where Rivals Never Share a Jersey

Imagine trying to split a friend group into two rival teams such that no two friends who know each other end up on the same team. Pick anyone, put them on Team A. Everyone they know must go on Team B. Everyone those people know (who isn't already placed) must go back on Team A, and so on, alternating outward. If you ever discover two people who know each other but got assigned to the same team, the split is impossible, and that failure specifically happens when there's an odd-length cycle of friendships, since alternating colors around a cycle only lands back on the start color cleanly when the cycle length is even. And if some people know nobody from the first group, you still have to place them: pick one of them and start alternating again.

🔑 The Key Idea in the Code

BFS's level structure lines up with the alternation: color is the parity of a node's distance from start, so nodes at an even distance sit on side 0 and nodes at an odd distance on side 1. An edge between two nodes of the same parity closes a loop of odd length, which is why the clash check is an odd-cycle detector. The outer loop matters as much as the inner one: the graph may be disconnected, and a search from node 0 alone never colors a component that doesn't touch node 0.

Starting the search from node 0 only
Filling color with 0 instead of -1
Giving every new neighbour side 1 instead of 1 - color[node]
Comparing with color[start] instead of color[node]

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

The nodes must be "split into two groups" so that "no edge ever connects two nodes in the same group", in an undirected graph given as an adjacency list that "doesn't need to be one connected piece": two groups with a rule on every edge is a two-coloring, which is a Bipartite Check.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

color[u] is -1 until the search first reaches u and never changes after; every edge checked so far joins a side-0 node to a side-1 node. A neighbour with no side takes 1 - color[node]; a neighbour with color[nxt] == color[node] means return False.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

for start in range(len(graph)): the graph may be disconnected, so every node still at color[start] == -1 must start its own search; a search from node 0 only never checks a component that doesn't touch node 0.
color = [-1] * len(graph): with [0] * len(graph) every node already looks colored, so if color[start] != -1: continue skips every start, no search runs, and every graph is reported bipartite.
elif color[nxt] == color[node]: compare with the current node, not with color[start]; a node two edges from start is supposed to share its side.
color[nxt] = 1 - color[node] goes right before queue.append(nxt): coloring on push means a node is queued once and always has a side when a later edge reaches it.

The 60-Second Interview Pitch

Say this out loud before you type a single line

This is a Bipartite Check, so I two-color the graph with BFS. The first node of a component takes side 0, and every neighbour I reach with no side yet goes on the other side, one minus the current node's side. That first choice forces every other color, so the only way to fail is an edge whose two ends already share a side. That means the two paths from the start plus that edge form a loop of odd length, and no two-group split survives an odd loop, so I return false right there. The trap is that the graph may be disconnected: I loop over every node and start a new search at each one that still has no side, otherwise an odd cycle away from node 0 would slip through. Each node and each edge is handled a constant number of times, so it's O(V plus E) time and O(V) extra space for the colors and the queue.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(V + E)

Look at the code: for start in range(len(graph)) runs V times and does O(1) work for a node that already has a side. A node is colored exactly once, when it first gets a side (color[start] = 0 or color[nxt] = 1 - color[node]), and it enters queue only at that moment, so node = queue.popleft() runs at most V times in total. Each pop walks graph[node] once, so over the whole run the inner loop sees every adjacency entry once: 2E entries for E undirected edges, each with O(1) work. Total: O(V + E).

SPACE COMPLEXITY

O(V)

color holds V entries. queue holds only nodes that have a side but haven't been popped, at most V at once. There is no recursion, so the call stack is O(1). The input adjacency list is not counted.

Formal Recurrence Relation

T(V, E) = V (outer loop) + V (pops) + 2E (adjacency entries) = O(V + E)

Derivation Progression

Outer loop over every start

for start in range(len(graph)): V iterations, O(1) each when color[start] != -1

Every node is tried as a start, but only an uncolored one opens a search; the others cost one comparison.

Each node is queued and popped once

color[x] is set once, right before queue.append(x): at most V pops

A node gets its side when it joins the queue and never loses it, so color[nxt] == -1 is true for it only once.

Each adjacency entry is checked once

sum over popped nodes of len(graph[node]) = 2E

Every edge sits in two lists and each list is walked once, with O(1) work per entry: the -1 test, the flip or the clash test.

Variable Definitions

$V$

Number of nodes, len(graph)

$E$

Number of undirected edges; the adjacency lists hold 2E entries in total

Memory Architecture & Bounds

🟣 Call Stack

O(1): an iterative BFS, no recursion

🔵 Auxiliary Heap

O(V): color has V entries and queue never holds more than V nodes

🟢 Output Space

O(1): one boolean

Boundary Best / Worst Cases

Best Case

$O(1)$ after setup: a clash on the first edges checked returns False at once (allocating color is still O(V)).

Average Case

$O(V + E)$ .

Worst Case

$O(V + E)$ : a bipartite graph, where every node and every edge must be checked before return True.

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Scale signal: trying all $2^V$ side assignments is hopeless even at $V = 100$ ; one search per component checks every edge from both ends, $O(V + E)$ , and still fits conflict graphs with millions of nodes.

CONSTRAINTS & BOUNDS

$V \le 100$ nodes, so at most $\binom{100}{2} = 4950$ edges; the adjacency list is symmetric with no self-loops or repeats. Budget: $O(V + E)$ time, $O(V)$ extra space.

FAANG PRODUCTION TRAPS & EDGE CASES

Very large graphs: keep the search iterative (as here), since a recursive DFS can pass the recursion limit on long paths. When edges arrive one at a time, a union-find that stores each node's parity to its root answers the same question per edge without re-running the search.

Core Algorithmic State Invariants

Example 2 Colored Step by Step

Node 0 takes side 0, its neighbours 1 and 3 take side 1, and node 2, reached from 1, takes side 0. Every edge then joins {0, 2} to {1, 3}, so the answer is true.

Example 1's Clash

Node 0 takes side 0, and 1, 2 and 3 all take side 1. Popping node 1, its neighbour 2 is already on side 1 too: the triangle 0-1-2 is an odd cycle, so the answer is false.

Queue or Stack, Same Answer

The order in which nodes get their side doesn't matter: a DFS with a stack forces the same sides, because in a bipartite graph every path from a component's first node to a node has the same parity.

Theory Context•Graph Algorithms

MediumLC 785

Is Graph Bipartite? (LeetCode 785)

Target Frequency:MetaAmazonGoogleApple

Decide whether the nodes can be split into two groups A and B such that no edge ever connects two nodes in the same group — i.e., whether the graph is bipartite.

Return true if such a split exists, false otherwise.

Worked Examples

Example 1

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

Output:false

Explanation: Nodes 0, 1 and 2 are all linked to each other in a triangle. Whichever way you split them into two groups, two of them land in the same group while sharing an edge.

Example 2

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

Output:true

Explanation: Grouping {0, 2} on one side and {1, 3} on the other leaves every edge crossing between the two groups.

⚖️Formal Constraints & Bounds

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.

Deep-Dive & Conceptual Insights

Core Insight

Real-World Scenario & Production Applications

Conflict-scheduling problems (can every task be split into two non-conflicting shifts?) and matching-market validity checks (can buyers and sellers be cleanly separated with no same-side edges?).

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Open a Search at Every Uncolored Node

Mathematical Recurrence / Code Invariant

color = [-1] * len(graph)
for start in range(len(graph)):
    if color[start] != -1:
        continue
    color[start] = 0
    queue = deque([start])

Step-by-Step Execution Trace Table

Step-by-Step Two-Coloring (graph = [[1,3],[0,2],[1,3],[0,2]])

Step 1 (Nothing Colored): color = [-1, -1, -1, -1]: no node has a side yet.
Step 2 (Open a Component): start = 0 has color[0] == -1, so color[0] = 0 and queue = [0].
Step 3 (Pop 0, Color Its Neighbours): Neighbours 1 and 3 have no side, so color[1] = 1 - 0 = 1 and color[3] = 1. queue = [1, 3].
Step 4 (Pop 1): Neighbour 0 is on side 0, the other side from 1: the edge crosses, fine. Neighbour 2 has no side, so color[2] = 1 - 1 = 0. queue = [3, 2].
Step 5 (Pop 3): Neighbours 0 and 2 are both on side 0, the other side from 3: no clash.
Step 6 (Pop 2): Neighbours 1 and 3 are both on side 1, the other side from 2: no clash. The queue is empty.
Step 7 (Every Start Checked): start = 1, 2, 3 are already colored, so no new search opens. Search Complete: side 0 = {0, 2}, side 1 = {1, 3}, return true ✅.

Full Walkthrough7 Steps

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

1⚡ STEP(Nothing Colored)

color = [-1, -1, -1, -1]: no node has a side yet.

2⚡ STEP(Open a Component)

queue = [0]

start = 0 has color[0] == -1, so color[0] = 0 and queue = [0].

3⚡ FIFO DRAIN(Pop 0, Color Its Neighbours)

queue = [1, 3]

Neighbours 1 and 3 have no side, so color[1] = 1 - 0 = 1 and color[3] = 1. queue = [1, 3].

4⚡ FIFO DRAIN(Pop 1)

queue = [3, 2]

Neighbour 0 is on side 0, the other side from 1: the edge crosses, fine. Neighbour 2 has no side, so color[2] = 1 - 1 = 0. queue = [3, 2].

5⚡ FIFO DRAIN(Pop 3)

Neighbours 0 and 2 are both on side 0, the other side from 3: no clash.

6⚡ FIFO DRAIN(Pop 2)

Neighbours 1 and 3 are both on side 1, the other side from 2: no clash. The queue is empty.

7✅ RECORD / GOAL(Every Start Checked)

start = 1, 2, 3 are already colored, so no new search opens. Search Complete: side 0 = {0, 2}, side 1 = {1, 3}, return true ✅.

Code Shape

Archetype Code Shape

Python

1	color = [-1] * len(graph)
2	for start in range(len(graph)):
3	if color[start] != -1:
4	continue
5	color[start] = 0
6	queue = deque([start])
7	while queue:
8	node = queue.popleft()
9	for nxt in graph[node]:
10	if color[nxt] == -1:
11	color[nxt] = 1 - color[node]
12	queue.append(nxt)
13	elif color[nxt] == color[node]:
14	return False
15	return True

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

👕 The Analogy: Two Sports Teams Where Rivals Never Share a Jersey

🔑 The Key Idea in the Code

Starting the search from node 0 only
Filling color with 0 instead of -1
Giving every new neighbour side 1 instead of 1 - color[node]
Comparing with color[start] instead of color[node]

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

for start in range(len(graph)): the graph may be disconnected, so every node still at color[start] == -1 must start its own search; a search from node 0 only never checks a component that doesn't touch node 0.
color = [-1] * len(graph): with [0] * len(graph) every node already looks colored, so if color[start] != -1: continue skips every start, no search runs, and every graph is reported bipartite.
elif color[nxt] == color[node]: compare with the current node, not with color[start]; a node two edges from start is supposed to share its side.
color[nxt] = 1 - color[node] goes right before queue.append(nxt): coloring on push means a node is queued once and always has a side when a later edge reaches it.

The 60-Second Interview Pitch

Say this out loud before you type a single line

This is a Bipartite Check, so I two-color the graph with BFS. The first node of a component takes side 0, and every neighbour I reach with no side yet goes on the other side, one minus the current node's side. That first choice forces every other color, so the only way to fail is an edge whose two ends already share a side. That means the two paths from the start plus that edge form a loop of odd length, and no two-group split survives an odd loop, so I return false right there. The trap is that the graph may be disconnected: I loop over every node and start a new search at each one that still has no side, otherwise an odd cycle away from node 0 would slip through. Each node and each edge is handled a constant number of times, so it's O(V plus E) time and O(V) extra space for the colors and the queue.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(V + E)

SPACE COMPLEXITY

O(V)

Formal Recurrence Relation

T(V, E) = V (outer loop) + V (pops) + 2E (adjacency entries) = O(V + E)

Derivation Progression

Outer loop over every start

for start in range(len(graph)): V iterations, O(1) each when color[start] != -1

Every node is tried as a start, but only an uncolored one opens a search; the others cost one comparison.

Each node is queued and popped once

color[x] is set once, right before queue.append(x): at most V pops

A node gets its side when it joins the queue and never loses it, so color[nxt] == -1 is true for it only once.

Each adjacency entry is checked once

sum over popped nodes of len(graph[node]) = 2E

Every edge sits in two lists and each list is walked once, with O(1) work per entry: the -1 test, the flip or the clash test.

Variable Definitions

$V$

Number of nodes, len(graph)

$E$

Number of undirected edges; the adjacency lists hold 2E entries in total

Memory Architecture & Bounds

🟣 Call Stack

O(1): an iterative BFS, no recursion

🔵 Auxiliary Heap

O(V): color has V entries and queue never holds more than V nodes

🟢 Output Space

O(1): one boolean

Boundary Best / Worst Cases

Best Case

$O(1)$ after setup: a clash on the first edges checked returns False at once (allocating color is still O(V)).

Average Case

$O(V + E)$ .

Worst Case

$O(V + E)$ : a bipartite graph, where every node and every edge must be checked before return True.

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

$V \le 100$ nodes, so at most $\binom{100}{2} = 4950$ edges; the adjacency list is symmetric with no self-loops or repeats. Budget: $O(V + E)$ time, $O(V)$ extra space.

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

Example 2 Colored Step by Step

Node 0 takes side 0, its neighbours 1 and 3 take side 1, and node 2, reached from 1, takes side 0. Every edge then joins {0, 2} to {1, 3}, so the answer is true.

Example 1's Clash

Node 0 takes side 0, and 1, 2 and 3 all take side 1. Popping node 1, its neighbour 2 is already on side 1 too: the triangle 0-1-2 is an odd cycle, so the answer is false.

Queue or Stack, Same Answer

The order in which nodes get their side doesn't matter: a DFS with a stack forces the same sides, because in a bipartite graph every path from a component's first node to a node has the same parity.

Theory Context•Graph Algorithms

MediumLC 785

Is Graph Bipartite? (LeetCode 785)

Target Frequency:MetaAmazonGoogleApple

Decide whether the nodes can be split into two groups A and B such that no edge ever connects two nodes in the same group — i.e., whether the graph is bipartite.

Return true if such a split exists, false otherwise.

Worked Examples

Example 1

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

Output:false

Explanation: Nodes 0, 1 and 2 are all linked to each other in a triangle. Whichever way you split them into two groups, two of them land in the same group while sharing an edge.

Example 2

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

Output:true

Explanation: Grouping {0, 2} on one side and {1, 3} on the other leaves every edge crossing between the two groups.

⚖️Formal Constraints & Bounds

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.

Deep-Dive & Conceptual Insights

Core Insight

Real-World Scenario & Production Applications

Conflict-scheduling problems (can every task be split into two non-conflicting shifts?) and matching-market validity checks (can buyers and sellers be cleanly separated with no same-side edges?).

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Open a Search at Every Uncolored Node

Mathematical Recurrence / Code Invariant

color = [-1] * len(graph)
for start in range(len(graph)):
    if color[start] != -1:
        continue
    color[start] = 0
    queue = deque([start])

Step-by-Step Execution Trace Table

Step-by-Step Two-Coloring (graph = [[1,3],[0,2],[1,3],[0,2]])

Step 1 (Nothing Colored): color = [-1, -1, -1, -1]: no node has a side yet.
Step 2 (Open a Component): start = 0 has color[0] == -1, so color[0] = 0 and queue = [0].
Step 3 (Pop 0, Color Its Neighbours): Neighbours 1 and 3 have no side, so color[1] = 1 - 0 = 1 and color[3] = 1. queue = [1, 3].
Step 4 (Pop 1): Neighbour 0 is on side 0, the other side from 1: the edge crosses, fine. Neighbour 2 has no side, so color[2] = 1 - 1 = 0. queue = [3, 2].
Step 5 (Pop 3): Neighbours 0 and 2 are both on side 0, the other side from 3: no clash.
Step 6 (Pop 2): Neighbours 1 and 3 are both on side 1, the other side from 2: no clash. The queue is empty.
Step 7 (Every Start Checked): start = 1, 2, 3 are already colored, so no new search opens. Search Complete: side 0 = {0, 2}, side 1 = {1, 3}, return true ✅.

Full Walkthrough7 Steps

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

1⚡ STEP(Nothing Colored)

color = [-1, -1, -1, -1]: no node has a side yet.

2⚡ STEP(Open a Component)

queue = [0]

start = 0 has color[0] == -1, so color[0] = 0 and queue = [0].

3⚡ FIFO DRAIN(Pop 0, Color Its Neighbours)

queue = [1, 3]

Neighbours 1 and 3 have no side, so color[1] = 1 - 0 = 1 and color[3] = 1. queue = [1, 3].

4⚡ FIFO DRAIN(Pop 1)

queue = [3, 2]

Neighbour 0 is on side 0, the other side from 1: the edge crosses, fine. Neighbour 2 has no side, so color[2] = 1 - 1 = 0. queue = [3, 2].

5⚡ FIFO DRAIN(Pop 3)

Neighbours 0 and 2 are both on side 0, the other side from 3: no clash.

6⚡ FIFO DRAIN(Pop 2)

Neighbours 1 and 3 are both on side 1, the other side from 2: no clash. The queue is empty.

7✅ RECORD / GOAL(Every Start Checked)

start = 1, 2, 3 are already colored, so no new search opens. Search Complete: side 0 = {0, 2}, side 1 = {1, 3}, return true ✅.

Code Shape

Archetype Code Shape

Python

1	color = [-1] * len(graph)
2	for start in range(len(graph)):
3	if color[start] != -1:
4	continue
5	color[start] = 0
6	queue = deque([start])
7	while queue:
8	node = queue.popleft()
9	for nxt in graph[node]:
10	if color[nxt] == -1:
11	color[nxt] = 1 - color[node]
12	queue.append(nxt)
13	elif color[nxt] == color[node]:
14	return False
15	return True

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

👕 The Analogy: Two Sports Teams Where Rivals Never Share a Jersey

🔑 The Key Idea in the Code

Starting the search from node 0 only
Filling color with 0 instead of -1
Giving every new neighbour side 1 instead of 1 - color[node]
Comparing with color[start] instead of color[node]

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

for start in range(len(graph)): the graph may be disconnected, so every node still at color[start] == -1 must start its own search; a search from node 0 only never checks a component that doesn't touch node 0.
color = [-1] * len(graph): with [0] * len(graph) every node already looks colored, so if color[start] != -1: continue skips every start, no search runs, and every graph is reported bipartite.
elif color[nxt] == color[node]: compare with the current node, not with color[start]; a node two edges from start is supposed to share its side.
color[nxt] = 1 - color[node] goes right before queue.append(nxt): coloring on push means a node is queued once and always has a side when a later edge reaches it.

The 60-Second Interview Pitch

Say this out loud before you type a single line

This is a Bipartite Check, so I two-color the graph with BFS. The first node of a component takes side 0, and every neighbour I reach with no side yet goes on the other side, one minus the current node's side. That first choice forces every other color, so the only way to fail is an edge whose two ends already share a side. That means the two paths from the start plus that edge form a loop of odd length, and no two-group split survives an odd loop, so I return false right there. The trap is that the graph may be disconnected: I loop over every node and start a new search at each one that still has no side, otherwise an odd cycle away from node 0 would slip through. Each node and each edge is handled a constant number of times, so it's O(V plus E) time and O(V) extra space for the colors and the queue.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(V + E)

SPACE COMPLEXITY

O(V)

Formal Recurrence Relation

T(V, E) = V (outer loop) + V (pops) + 2E (adjacency entries) = O(V + E)

Derivation Progression

Outer loop over every start

for start in range(len(graph)): V iterations, O(1) each when color[start] != -1

Every node is tried as a start, but only an uncolored one opens a search; the others cost one comparison.

Each node is queued and popped once

color[x] is set once, right before queue.append(x): at most V pops

A node gets its side when it joins the queue and never loses it, so color[nxt] == -1 is true for it only once.

Each adjacency entry is checked once

sum over popped nodes of len(graph[node]) = 2E

Every edge sits in two lists and each list is walked once, with O(1) work per entry: the -1 test, the flip or the clash test.

Variable Definitions

$V$

Number of nodes, len(graph)

$E$

Number of undirected edges; the adjacency lists hold 2E entries in total

Memory Architecture & Bounds

🟣 Call Stack

O(1): an iterative BFS, no recursion

🔵 Auxiliary Heap

O(V): color has V entries and queue never holds more than V nodes

🟢 Output Space

O(1): one boolean

Boundary Best / Worst Cases

Best Case

$O(1)$ after setup: a clash on the first edges checked returns False at once (allocating color is still O(V)).

Average Case

$O(V + E)$ .

Worst Case

$O(V + E)$ : a bipartite graph, where every node and every edge must be checked before return True.

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

$V \le 100$ nodes, so at most $\binom{100}{2} = 4950$ edges; the adjacency list is symmetric with no self-loops or repeats. Budget: $O(V + E)$ time, $O(V)$ extra space.

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

Example 2 Colored Step by Step

Node 0 takes side 0, its neighbours 1 and 3 take side 1, and node 2, reached from 1, takes side 0. Every edge then joins {0, 2} to {1, 3}, so the answer is true.

Example 1's Clash

Node 0 takes side 0, and 1, 2 and 3 all take side 1. Popping node 1, its neighbour 2 is already on side 1 too: the triangle 0-1-2 is an odd cycle, so the answer is false.

Queue or Stack, Same Answer

The order in which nodes get their side doesn't matter: a DFS with a stack forces the same sides, because in a bipartite graph every path from a component's first node to a node has the same parity.

Theory Context•Graph Algorithms

MediumLC 785

Is Graph Bipartite? (LeetCode 785)

Target Frequency:MetaAmazonGoogleApple

Decide whether the nodes can be split into two groups A and B such that no edge ever connects two nodes in the same group — i.e., whether the graph is bipartite.

Return true if such a split exists, false otherwise.

Worked Examples

Example 1

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

Output:false

Explanation: Nodes 0, 1 and 2 are all linked to each other in a triangle. Whichever way you split them into two groups, two of them land in the same group while sharing an edge.

Example 2

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

Output:true

Explanation: Grouping {0, 2} on one side and {1, 3} on the other leaves every edge crossing between the two groups.

⚖️Formal Constraints & Bounds

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.

Deep-Dive & Conceptual Insights

Core Insight

Real-World Scenario & Production Applications

Conflict-scheduling problems (can every task be split into two non-conflicting shifts?) and matching-market validity checks (can buyers and sellers be cleanly separated with no same-side edges?).

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Open a Search at Every Uncolored Node

Mathematical Recurrence / Code Invariant

color = [-1] * len(graph)
for start in range(len(graph)):
    if color[start] != -1:
        continue
    color[start] = 0
    queue = deque([start])

Step-by-Step Execution Trace Table

Step-by-Step Two-Coloring (graph = [[1,3],[0,2],[1,3],[0,2]])

Step 1 (Nothing Colored): color = [-1, -1, -1, -1]: no node has a side yet.
Step 2 (Open a Component): start = 0 has color[0] == -1, so color[0] = 0 and queue = [0].
Step 3 (Pop 0, Color Its Neighbours): Neighbours 1 and 3 have no side, so color[1] = 1 - 0 = 1 and color[3] = 1. queue = [1, 3].
Step 4 (Pop 1): Neighbour 0 is on side 0, the other side from 1: the edge crosses, fine. Neighbour 2 has no side, so color[2] = 1 - 1 = 0. queue = [3, 2].
Step 5 (Pop 3): Neighbours 0 and 2 are both on side 0, the other side from 3: no clash.
Step 6 (Pop 2): Neighbours 1 and 3 are both on side 1, the other side from 2: no clash. The queue is empty.
Step 7 (Every Start Checked): start = 1, 2, 3 are already colored, so no new search opens. Search Complete: side 0 = {0, 2}, side 1 = {1, 3}, return true ✅.

Full Walkthrough7 Steps

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

1⚡ STEP(Nothing Colored)

color = [-1, -1, -1, -1]: no node has a side yet.

2⚡ STEP(Open a Component)

queue = [0]

start = 0 has color[0] == -1, so color[0] = 0 and queue = [0].

3⚡ FIFO DRAIN(Pop 0, Color Its Neighbours)

queue = [1, 3]

Neighbours 1 and 3 have no side, so color[1] = 1 - 0 = 1 and color[3] = 1. queue = [1, 3].

4⚡ FIFO DRAIN(Pop 1)

queue = [3, 2]

Neighbour 0 is on side 0, the other side from 1: the edge crosses, fine. Neighbour 2 has no side, so color[2] = 1 - 1 = 0. queue = [3, 2].

5⚡ FIFO DRAIN(Pop 3)

Neighbours 0 and 2 are both on side 0, the other side from 3: no clash.

6⚡ FIFO DRAIN(Pop 2)

Neighbours 1 and 3 are both on side 1, the other side from 2: no clash. The queue is empty.

7✅ RECORD / GOAL(Every Start Checked)

start = 1, 2, 3 are already colored, so no new search opens. Search Complete: side 0 = {0, 2}, side 1 = {1, 3}, return true ✅.

Code Shape

Archetype Code Shape

Python

1	color = [-1] * len(graph)
2	for start in range(len(graph)):
3	if color[start] != -1:
4	continue
5	color[start] = 0
6	queue = deque([start])
7	while queue:
8	node = queue.popleft()
9	for nxt in graph[node]:
10	if color[nxt] == -1:
11	color[nxt] = 1 - color[node]
12	queue.append(nxt)
13	elif color[nxt] == color[node]:
14	return False
15	return True

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

👕 The Analogy: Two Sports Teams Where Rivals Never Share a Jersey

🔑 The Key Idea in the Code

Starting the search from node 0 only
Filling color with 0 instead of -1
Giving every new neighbour side 1 instead of 1 - color[node]
Comparing with color[start] instead of color[node]

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

for start in range(len(graph)): the graph may be disconnected, so every node still at color[start] == -1 must start its own search; a search from node 0 only never checks a component that doesn't touch node 0.
color = [-1] * len(graph): with [0] * len(graph) every node already looks colored, so if color[start] != -1: continue skips every start, no search runs, and every graph is reported bipartite.
elif color[nxt] == color[node]: compare with the current node, not with color[start]; a node two edges from start is supposed to share its side.
color[nxt] = 1 - color[node] goes right before queue.append(nxt): coloring on push means a node is queued once and always has a side when a later edge reaches it.

The 60-Second Interview Pitch

Say this out loud before you type a single line

This is a Bipartite Check, so I two-color the graph with BFS. The first node of a component takes side 0, and every neighbour I reach with no side yet goes on the other side, one minus the current node's side. That first choice forces every other color, so the only way to fail is an edge whose two ends already share a side. That means the two paths from the start plus that edge form a loop of odd length, and no two-group split survives an odd loop, so I return false right there. The trap is that the graph may be disconnected: I loop over every node and start a new search at each one that still has no side, otherwise an odd cycle away from node 0 would slip through. Each node and each edge is handled a constant number of times, so it's O(V plus E) time and O(V) extra space for the colors and the queue.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(V + E)

SPACE COMPLEXITY

O(V)

Formal Recurrence Relation

T(V, E) = V (outer loop) + V (pops) + 2E (adjacency entries) = O(V + E)

Derivation Progression

Outer loop over every start

for start in range(len(graph)): V iterations, O(1) each when color[start] != -1

Every node is tried as a start, but only an uncolored one opens a search; the others cost one comparison.

Each node is queued and popped once

color[x] is set once, right before queue.append(x): at most V pops

A node gets its side when it joins the queue and never loses it, so color[nxt] == -1 is true for it only once.

Each adjacency entry is checked once

sum over popped nodes of len(graph[node]) = 2E

Every edge sits in two lists and each list is walked once, with O(1) work per entry: the -1 test, the flip or the clash test.

Variable Definitions

$V$

Number of nodes, len(graph)

$E$

Number of undirected edges; the adjacency lists hold 2E entries in total

Memory Architecture & Bounds

🟣 Call Stack

O(1): an iterative BFS, no recursion

🔵 Auxiliary Heap

O(V): color has V entries and queue never holds more than V nodes

🟢 Output Space

O(1): one boolean

Boundary Best / Worst Cases

Best Case

$O(1)$ after setup: a clash on the first edges checked returns False at once (allocating color is still O(V)).

Average Case

$O(V + E)$ .

Worst Case

$O(V + E)$ : a bipartite graph, where every node and every edge must be checked before return True.

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

$V \le 100$ nodes, so at most $\binom{100}{2} = 4950$ edges; the adjacency list is symmetric with no self-loops or repeats. Budget: $O(V + E)$ time, $O(V)$ extra space.

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

Example 2 Colored Step by Step

Node 0 takes side 0, its neighbours 1 and 3 take side 1, and node 2, reached from 1, takes side 0. Every edge then joins {0, 2} to {1, 3}, so the answer is true.

Example 1's Clash

Node 0 takes side 0, and 1, 2 and 3 all take side 1. Popping node 1, its neighbour 2 is already on side 1 too: the triangle 0-1-2 is an odd cycle, so the answer is false.

Queue or Stack, Same Answer

The order in which nodes get their side doesn't matter: a DFS with a stack forces the same sides, because in a bipartite graph every path from a component's first node to a node has the same parity.