Frontend School

Detect Connected Account Clusters

DSA
medium

Detect Connected Account Clusters

Medium
Union Find
Graph
Data Structures

Overview

At PhonePe, understanding the relationships between user accounts is paramount for various functions, including fraud detection, risk assessment, and personalized service delivery. When suspicious activities link accounts, it's crucial to identify all indirectly connected accounts to form 'clusters'. These clusters can indicate coordinated behavior or shared vulnerabilities.

This problem challenges you to implement an efficient algorithm to identify and count the total number of distinct connected account clusters based on a given set of direct linkages.

What you need to do / Task

Your task is to implement a function detectConnectedAccountClusters that takes a list of unique account IDs and a list of direct linkages between these accounts. You need to determine the total number of distinct groups (clusters) of accounts, where two accounts are considered to be in the same cluster if they are directly or indirectly linked.

Input & output

  • accounts: An array of unique string IDs, each representing a user account. All accounts involved in linkages will be present in this array.
  • linkages: An array of pairs [account_id_A, account_id_B]. Each pair signifies a direct linkage between account_id_A and account_id_B (e.g., through a suspicious transaction or shared activity).
  • Return: An integer representing the total count of distinct connected account clusters.

Clarifications

  • An account is considered linked to itself (implicitly). If an account has no direct linkages, it forms a cluster of size one.
  • The order of account_id_A and account_id_B in a linkage pair does not matter; the linkage is bidirectional.
  • All account_ids mentioned in linkages are guaranteed to exist in the accounts array.

Examples

1

Example 1

Input:

accounts = ["A1", "A2", "A3", "A4", "A5"], linkages = [["A1", "A2"], ["A3", "A4"]]

Output:

3

Note:

Accounts A1 and A2 form one cluster. Accounts A3 and A4 form another. Account A5 is standalone. Total 3 distinct clusters.

2

Example 2

Input:

accounts = ["U1", "U2", "U3", "U4", "U5", "U6"], linkages = [["U1", "U2"], ["U2", "U3"], ["U4", "U5"], ["U6", "U4"]]

Output:

2

Note:

U1, U2, U3 are connected (U1-U2, U2-U3). U4, U5, U6 are connected (U4-U5, U6-U4). This results in two distinct clusters.

3

Example 3

Input:

accounts = ["P1", "P2", "P3"], linkages = []

Output:

3

Note:

With no linkages, each account forms its own cluster. Total 3 distinct clusters.

Constraints

Constraints & assumptions

  • 1 <= accounts.length <= 10^5
  • 0 <= linkages.length <= 2 * 10^5
  • 1 <= account_id.length <= 10 for all account IDs.
  • All account_ids in the accounts array are unique.
  • The graph formed by linkages is undirected.

Out of scope

  • Handling non-existent account IDs in linkages (assume all are valid).
  • Advanced graph algorithms beyond basic connectivity detection.
  • Performance optimization for extremely large account_id string lengths.

What interviewers evaluate

  • Correctness of the Union-Find data structure implementation.
  • Efficient mapping of string account IDs to internal integer indices.
  • Proper handling of graph connectivity and disjoint set counting.
  • Code clarity, modularity, and adherence to best practices for data structures.

Loading editor...