Code Implementation

class Solution:
    def maximumWealth(self, accounts):
        # For each customer, sum up their wealth and find the maximum
        return max(map(sum, accounts))
      

class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int maxWealth = 0;
        for (const auto& customer : accounts) {
            int sum = 0;
            for (int money : customer) {
                sum += money;
            }
            if (sum > maxWealth) {
                maxWealth = sum;
            }
        }
        return maxWealth;
    }
};
      

class Solution {
    public int maximumWealth(int[][] accounts) {
        int max = 0;
        for (int[] customer : accounts) {
            int sum = 0;
            for (int money : customer) {
                sum += money;
            }
            if (sum > max) {
                max = sum;
            }
        }
        return max;
    }
}
      

var maximumWealth = function(accounts) {
    let max = 0;
    for (let customer of accounts) {
        let sum = customer.reduce((a, b) => a + b, 0);
        if (sum > max) max = sum;
    }
    return max;
};
      

Problem Description

You are given a 2D array accounts where each row represents a customer, and each column represents the amount of money that customer has in a particular bank. The value accounts[i][j] is the amount of money the i-th customer has in the j-th bank.

The task is to find the wealthiest customer. A customer's wealth is the sum of money they have in all their banks. Return the maximum wealth among all customers.

• Each customer must be considered independently.
• There is always at least one customer and one bank.
• There is only one correct answer for each input.

Thought Process

The first step is to understand that we need to compute the sum of each customer's bank accounts, and then determine which customer has the highest total.

A brute-force approach would involve iterating through every customer, summing up their accounts, and keeping track of the largest sum seen so far. This is straightforward because the problem is small in scope and doesn't require complex data structures.

There isn't much room for further optimization because each value must be visited at least once to compute the sums. However, we can make the code concise by using built-in functions, like sum in Python or reduce in JavaScript.

Solution Approach

• Initialize a variable to keep track of the maximum wealth found so far.
• Iterate through each customer (each row in the accounts array).
• For each customer, sum up all their bank balances.
• Compare this sum with the current maximum wealth. If it's larger, update the maximum.
• After checking all customers, return the highest wealth found.

This method ensures that every customer is considered, and the correct answer is returned efficiently. The use of a running maximum is a common technique for problems where you need to find the largest (or smallest) value in a collection.

Example Walkthrough

Suppose accounts = [[1,2,3], [3,2,1]].

1. First customer: 1 + 2 + 3 = 6
2. Second customer: 3 + 2 + 1 = 6
3. Maximum wealth is the greater of 6 and 6, which is 6.

If accounts = [[2,8,7], [7,1,3], [1,9,5]]:

1. First customer: 2 + 8 + 7 = 17
2. Second customer: 7 + 1 + 3 = 11
3. Third customer: 1 + 9 + 5 = 15
4. Maximum wealth is the greatest of 17, 11, and 15, which is 17.

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(m * n), where m is the number of customers and n is the number of banks. Each account value must be visited once.
• Space Complexity: O(1), since we only store a constant number of variables (the running sum and maximum).

• The optimized approach is essentially the same as the brute-force here, since every account must be checked. There is no way to avoid visiting each entry.

Summary

The problem is a classic example of aggregating data across a 2D array and finding a maximum. By summing each customer's accounts and tracking the largest sum, we efficiently determine the wealthiest customer. The approach is simple, elegant, and leverages basic iteration and comparison. This is a great introduction to array manipulation and maximum-finding patterns in programming.