DIY: Is Graph Bipartite?
Solve the interview question "Is Graph Bipartite?" in this lesson.
We'll cover the following
Problem statement
In this challenge, you will be given an undirected graph. Your task is to determine if this graph is bipartite or not.
A graph is bipartite if we can split its set of nodes into two independent subsets,
A
andB
, such that every edge in the graph has one node inA
and another node inB
.
Input
An undirected graph is given as input. This graph will be represented by a 2D array such that graph[i]
will contain a list of indices j
for which the edge between nodes i and j exists. Each node in the graph is denoted by integers from 0
to graph.Length-1
.
For example, the input can be:
graph = [[1], [0, 3], [3], [1, 2]]
This graph can be illustrated as:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.