Frontend School

Consolidate User Communities

DSA
easy

Consolidate User Communities

Easy
Union Find
Graph
Data Structures

Overview

In a large social platform, users can be part of many different groups. Over time, groups might become highly interconnected through shared users. To streamline communication and management, we need a way to identify and consolidate all groups that are effectively part of a larger "super-group" due to shared members. This problem focuses on efficiently determining the total number of distinct, consolidated user communities.

What you need to do / Task

You are given a list of user groups, where each groups[i] represents a distinct group and contains a list of user IDs belonging to that group. Your task is to implement a function that returns the total number of distinct, consolidated communities. Two groups are considered part of the same community if they share at least one common user, or if they are transitively linked through other groups that share common users.

Input & output

The function countConsolidatedCommunities takes one argument:

  • groups: An array of arrays of numbers. groups[i] is a list of unique user IDs belonging to the i-th group.

The function should return:

  • An integer representing the total number of distinct consolidated communities.

Clarifications

  • An empty groups array implies 0 communities.
  • An empty inner group groups[i] means that group has no users and cannot connect to any other group through users.
  • User IDs can be large, so direct array indexing using user IDs is not feasible.

Examples

1

Example 1

Input:

groups = [[1,2], [2,3], [4,5]]

Output:

2

Note:

Groups [1,2] and [2,3] share user 2, forming one community. Group [4,5] forms a separate community. Total 2 communities.

2

Example 2

Input:

groups = [[10,20], [30,40], [10,30], [50]]

Output:

2

Note:

Groups [10,20], [30,40], and [10,30] are all interconnected (10 links first and third, 30 links second and third). They form one large community. Group [50] forms a separate community. Total 2 communities.

3

Example 3

Input:

groups = [[1], [2], [3]]

Output:

3

Note:

No groups share users. Each group forms its own community. Total 3 communities.

Constraints

Constraints & assumptions

  • 0 <= groups.length <= 1000
  • 0 <= groups[i].length <= 1000
  • 1 <= user_id <= 10^9 for any user ID.
  • Each user_id within a single groups[i] is unique.
  • The total number of unique user IDs across all groups will not exceed 10^5.

Out of scope

  • Handling concurrent updates to group memberships.
  • Optimizing for extremely sparse group data where most groups have very few users.

What interviewers evaluate

  • Correct application of the Union-Find data structure to model group connectivity.
  • Efficient handling of user IDs and group relationships.
  • Clarity and correctness of the Union-Find implementation (e.g., path compression, union by rank/size).
  • Ability to analyze time and space complexity.

Loading editor...