Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Richest Customer Wealth (easy)
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

You are given an m x n matrix accounts where accounts[i][j] is the amount of money the i​​​​​​​​​​​th​​​​ customer has in the j​​​​​​​​​​​th​​​​ bank.

Return the wealth that the richest customer has.

Imagine every customer has multiple bank accounts, with each account holding a certain amount of money. The total wealth of a customer is calculated by summing all the money across all their multiple.

Examples

  1. Example 1:

    • Input: accounts = 
      [[5,2,3],
 [0,6,7]]
    • Expected Output: 13
    • Justification: The total wealth of the first customer is 10 and of the second customer is 13. So, the output is 13 as it's the maximum among all customers.

  2. Example 2:

    • Input: accounts = 
      [[1,2],
 [3,4],
 [5,6]]
    • Expected Output: 11
    • Justification: Total wealth for each customer is [3, 7, 11]. Maximum of these is 11.

  3. Example 3:

    • Input: accounts =
     [[5,10,15],
  [10,20,30],
  [15,30,45]]
    • Expected Output: 90
    • Justification: Total wealth for each customer is [30, 60, 90]. The wealthiest customer has 90.

Constraints:

  • m == accounts.length
  • n == accounts[i].length
  • 1 <= m, n <= 50
  • 1 <= accounts[i][j] <= 100

Solution

The algorithm aims to traverse each customer's accounts, compute their total wealth by summing up the balances, and track the wealthiest customer found so far. We utilize a straightforward iterative method, whereby we loop through each customer and their respective accounts, calculating the sum of each customer's accounts, and then making a comparison against a stored maximum wealth variable. If the current customer's total wealth surpasses our stored maximum, we update our stored value. Upon completion of the iteration through all customers, our stored maximum wealth value represents the wealth of the richest customer. Simplicity and a single-pass solution make this algorithm appealing, ensuring computational efficiency by avoiding nested loops and minimizing computational steps where possible.

Step-by-Step Algorithm

Step 1: Initialize a variable maxWealth to store and track the maximum wealth found during the iteration. Set its initial value to 0 as we will use it for comparison.

Step 2: Iterate through the 2D-array of accounts using a loop. Each sub-array represents one customer's accounts.

Step 3: For each customer, calculate their total wealth by summing up all the values in their respective sub-array. Utilize another loop or a sum function for this.

Step 4: Compare the computed sum of the current customer with maxWealth. If it’s greater, update maxWealth with the new value.

Step 5: Repeat steps 3-4 for all customers in the array.

Step 6: Once the iteration is complete, maxWealth holds the maximum wealth among all customers. Return this value as the output.

Algorithm Walkthrough

Image

  • Initialize maxWealth to 0: This will store the maximum wealth we find as we traverse through the accounts.

    maxWealth = 0

  • Iterating through the customer arrays:

    • First customer: [5,10,15]

      • Calculate total wealth: 5 + 10 + 15 = 30
      • Compare and update maxWealth: maxWealth (0) < 30 => Update maxWealth to 30

    • Second customer: [10,20,30]

      • Calculate total wealth: 10 + 20 + 30 = 60
      • Compare and update maxWealth: maxWealth (30) < 60 => Update maxWealth to 60

    • Third customer: [15,30,45]

      • Calculate total wealth: 15 + 30 + 45 = 90
      • Compare and update maxWealth: maxWealth (60) < 90 => Update maxWealth to 90

  • Conclusion: The final value of maxWealth is 90, which represents the richest customer's wealth. So, 90 is returned as the output.

This approach guarantees we evaluate the total wealth of each customer and always maintain the wealthiest customer's wealth encountered thus far in our maxWealth variable, ensuring we find the correct answer by the end of our iterations.

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Outer loop (customers): The outer loop iterates over each customer in the accounts array. If there are M customers, this loop runs O(M) times.

  • Inner loop (accounts): For each customer, the inner loop iterates over the accounts to sum them. If each customer has N accounts, the inner loop runs O(N) times for each customer.

  • Therefore, the total time complexity is O(M \times N), where M is the number of customers, and N is the number of accounts per customer.

Overall time complexity: O(M \times N).

Space Complexity

  • Constant space: The algorithm uses a few extra variables (maxWealth and wealth), both of which require constant space, O(1).

  • No additional data structures that depend on the input size are used.

Overall space complexity: O(1).

.....

.....

.....

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