easy Problem 1 Richest Customer Wealth

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

• 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:

class Solution {

  public int maximumWealth(int[][] accounts) {
    int maxWealth = 0; // Initialize maxWealth to 0
    // Loop through each customer's accounts
    for (int[] customer : accounts) {
      int wealth = 0; // Variable to store the wealth of the current customer
      // Loop through each account of the current customer and sum them up
      for (int account : customer) {
        wealth += account;
      }
      // Update maxWealth if the current customer's wealth is greater
      if (wealth > maxWealth) {
        maxWealth = wealth;
      }
    }
    // Return the maximum wealth found
    return maxWealth;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    // Example test cases
    System.out.println(
      sol.maximumWealth(new int[][] { { 5, 2, 3 }, { 0, 6, 7 } })
    ); // 13
    System.out.println(
      sol.maximumWealth(new int[][] { { 1, 2 }, { 3, 4 }, { 5, 6 } })
    ); // 11
    System.out.println(
      sol.maximumWealth(
        new int[][] { { 5, 10, 15 }, { 10, 20, 30 }, { 15, 30, 45 } }
      )
    ); // 90
  }
}

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 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 times for each customer.

• Therefore, the total time complexity is , where M is the number of customers, and N is the number of accounts per customer.

Overall time complexity: .

Space Complexity

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

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

Overall space complexity: .