Frontend School

Consolidated Account Balances

DSA
medium

Consolidated Account Balances

Medium
Union Find
Graph
Data Structures

Overview

At Paytm, managing user accounts and their associated balances is fundamental. Users or entities might have multiple accounts that are linked due to various reasons, such as joint ventures, shared ownership, or related business operations. For accurate financial reporting, risk assessment, or even just providing a unified view to a customer, it's crucial to consolidate the balances of all accounts that belong to the same 'network' of related accounts.

This problem asks you to implement a system that takes a list of individual accounts and a list of known relationships between account IDs. Your task is to identify all distinct networks of related accounts and report the total consolidated balance for each network.

What you need to do / Task

Implement the function consolidateAccountBalances that:

  1. Initializes a data structure to manage account relationships and their balances.
  2. Processes a given list of relatedPairs, merging accounts that are directly or indirectly linked into larger networks.
  3. During the merging process, correctly aggregates the balances of accounts within each network.
  4. Finally, returns a list of the total consolidated balances for all distinct account networks.

Input & output

Input:

  • accounts: An array of Account objects. Each Account has two properties: id (a unique number representing the account ID) and balance (a number representing the current balance in that account).
    interface Account {
        id: number;
        balance: number;
    }
    
  • relatedPairs: An array of pairs of account IDs, where each inner array [id1, id2] signifies that account id1 and account id2 are related. This relationship is transitive; if A is related to B, and B is related to C, then A, B, and C are all part of the same network.

Output:

  • An array of numbers, where each number represents the total consolidated balance of a distinct network of related accounts. The order of balances in the output array does not matter.

Examples

1

Example 1

Input:

accounts = [{id: 1, balance: 100}, {id: 2, balance: 200}, {id: 3, balance: 300}], relatedPairs = [[1, 2]]

Output:

[300, 300]

Note:

Accounts 1 and 2 are related, forming a network with a total balance of 100 + 200 = 300. Account 3 is unrelated and forms its own network with a balance of 300. The order of balances in the output does not matter.

2

Example 2

Input:

accounts = [{id: 1, balance: 100}, {id: 2, balance: 200}, {id: 3, balance: 300}, {id: 4, balance: 400}], relatedPairs = [[1, 2], [3, 4], [2, 3]]

Output:

[1000]

Note:

Initially, (1,2) are linked, and (3,4) are linked. Then (2,3) links these two groups, making all four accounts part of a single network. The total balance is 100 + 200 + 300 + 400 = 1000.

3

Example 3

Input:

accounts = [{id: 1, balance: 50}, {id: 2, balance: -20}, {id: 3, balance: 100}], relatedPairs = []

Output:

[50, -20, 100]

Note:

No accounts are explicitly related. Each account forms its own network, and their individual balances are returned. The order of balances in the output does not matter.

Constraints

Constraints & assumptions

  • 1 <= accounts.length <= 10^4
  • 0 <= relatedPairs.length <= 10^4
  • 1 <= account.id <= 10^5 (Account IDs are positive integers)
  • -10^9 <= account.balance <= 10^9
  • All account IDs mentioned in relatedPairs are guaranteed to exist in the accounts input array.
  • A single account can appear in multiple relatedPairs.

Out of scope

  • Error handling for invalid input formats (e.g., relatedPairs containing non-existent account IDs).
  • Handling concurrent updates to account balances or relationships.

What interviewers evaluate

  • Correctness and efficiency of the Union-Find data structure implementation.
  • Accurate aggregation of balances across merged components.
  • Ability to handle various relationship patterns (e.g., disjoint networks, fully connected networks).
  • Clear understanding of time and space complexity.

Loading editor...