Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Is Graph Bipartite? (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a 2D array graph[][], representing the undirected graph, where graph[u] is an array of nodes that are connected with node u.

Determine whether a given undirected graph is a bipartite graph.

The graph is a bipartite graph, if we can split the set of nodes into two distinct subsets such that no two nodes within the same subset are adjacent (i.e., no edge exists between any two nodes within a single subset).

Examples

  1. Example 1:
    • Input: graph = [[1,3], [0,2], [1,3], [0,2]]
Image
  • Expected Output: true
  • Justification: The nodes can be divided into two groups: {0, 2} and {1, 3}. No two nodes within each group are adjacent, thus the graph is bipartite.
  1. Example 2:
    • Input: graph =[[1], [0], [3], [2]]
Image
  • Expected Output: true
  • Justification: The graph is a simple chain of 4 nodes. It's clearly bipartite as we can have {0, 2} and {1, 3} as the two subsets.
  1. Example 3:
    • Input: graph =[[1,2,3],[0,2],[0,1,3],[0,2]]
Image
  • Expected Output: false
  • Justification: We found that edges (1, 2), (0, 3), and (2, 3) connect nodes within the same set, which violates the condition for a bipartite graph where each edge must connect nodes in different subsets. Thus, there's no way to divide this graph into two subsets that satisfy the bipartite condition.

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 of graph[u] are unique.
  • If graph[u] contains v, then graph[v] contains u.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible