FastPrep
Problem · Graph

Connected Groups

Learn this problem
● MediumFivetran logoFivetranFULLTIMEONSITE INTERVIEW

Problem statement

You are given a square binary matrix related. Each row and column represents one person at the same party.

  • related[i][j] == 1 means that person i and person j have a direct connection.
  • related[i][j] == 0 means that they do not have a direct connection.

Connections are transitive. If person a is connected to person b, and person b is connected to person c, then all three people belong to the same group.

Return the number of distinct groups. If related is empty, return 0.

Function

countConnectedGroups(related: int[][]) → int

Examples

Example 1

related = [[1,1,0],[1,1,1],[0,1,1]]return = 1

Person 0 is directly connected to person 1, and person 1 is directly connected to person 2. Transitivity places all three people in one group.

Example 2

related = [[1,0,0],[0,1,1],[0,1,1]]return = 2

Person 0 forms one group. Persons 1 and 2 form the other group.

Example 3

related = [[1,0,1,0],[0,1,0,1],[1,0,1,0],[0,1,0,1]]return = 2

Persons 0 and 2 form one group, while persons 1 and 3 form the other. Group members do not need consecutive indices.

Constraints

  • Let n = related.length.
  • 0 <= n <= 1000.
  • related has exactly n rows, and every row has exactly n entries.
  • Every entry in related is either 0 or 1.
  • related[i][i] == 1 for every valid index i.
  • related[i][j] == related[j][i] for all valid indices i and j.

More Fivetran problems

drafts saved locally
public int countConnectedGroups(int[][] related) {
    // Write your code here.
}
related[[1,1,0],[1,1,1],[0,1,1]]
expected1
checking account