Problem Description

You have a 2D grid called accounts with m rows and n columns. Each cell accounts[i][j] represents the amount of money that customer i has in bank j.

Your task is to find the richest customer. A customer's total wealth is calculated by adding up all the money they have across all their bank accounts (sum of all values in their row). The richest customer is the one with the maximum total wealth.

For example, if accounts = [[1,2,3],[3,2,1]]:

• Customer 0 has wealth = 1 + 2 + 3 = 6
• Customer 1 has wealth = 3 + 2 + 1 = 6
• The maximum wealth is 6

The solution uses a simple approach: calculate the sum for each row (each customer's total wealth) and return the maximum value among all these sums. The code max(sum(v) for v in accounts) does exactly this - it sums up each row v in accounts and finds the maximum of all these sums.

Intuition

Since we need to find the richest customer, and each customer's wealth is simply the sum of all their bank accounts, the problem breaks down into two straightforward steps:

1. Calculate each customer's total wealth by summing their row
2. Find the maximum among all these totals

We can think of this problem as finding the row with the largest sum in a 2D array. Each row represents a customer, and we need to sum all elements in that row to get their total wealth.

The natural approach is to iterate through each customer (each row), calculate their total wealth using sum(), and keep track of the maximum value we've seen. Python's max() function combined with a generator expression makes this elegant - we generate all the row sums and let max() find the largest one.

The expression sum(v) for v in accounts creates a generator that produces the sum of each row, and max() then finds the largest value from these sums. This is both intuitive and efficient, as we only need one pass through the data to find our answer.

Solution Approach

The solution uses a simple summation approach to find the maximum wealth among all customers.

Implementation Steps:

1. Iterate through each customer: We traverse through the accounts list where each element represents a customer's accounts across different banks.

2. Calculate individual wealth: For each customer (row) v in accounts, we calculate their total wealth using sum(v). This adds up all the money they have across different banks.

3. Find the maximum: We use Python's built-in max() function to find the largest sum among all customers.

The one-liner solution:

return max(sum(v) for v in accounts)

This implementation uses:

• Generator expression: (sum(v) for v in accounts) creates a generator that yields the sum of each row without creating an intermediate list, making it memory efficient
• Built-in functions: Both sum() and max() are optimized Python built-ins that handle the aggregation efficiently

Time Complexity: O(m × n) where m is the number of customers and n is the number of banks, as we need to visit each element once to calculate the sums.

Space Complexity: O(1) extra space, as we only use a generator expression which doesn't store all sums at once, just calculates them on-the-fly as max() requests them.

Example Walkthrough

Let's walk through the solution with a concrete example to see how it works step by step.

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

Step 1: Process Customer 0 (first row)

• Customer 0's accounts: [7, 1, 3]
• Calculate wealth: sum([7, 1, 3]) = 7 + 1 + 3 = 11

Step 2: Process Customer 1 (second row)

• Customer 1's accounts: [2, 8, 7]
• Calculate wealth: sum([2, 8, 7]) = 2 + 8 + 7 = 17

Step 3: Process Customer 2 (third row)

• Customer 2's accounts: [1, 9, 5]
• Calculate wealth: sum([1, 9, 5]) = 1 + 9 + 5 = 15

Step 4: Find the maximum wealth

• All calculated wealth values: 11, 17, 15
• Maximum wealth: max(11, 17, 15) = 17

Using the one-liner solution:

max(sum(v) for v in accounts)

The generator expression sum(v) for v in accounts produces:

• First iteration: v = [7,1,3] → yields 11
• Second iteration: v = [2,8,7] → yields 17
• Third iteration: v = [1,9,5] → yields 15

The max() function then compares these values (11, 17, 15) and returns 17.

Result: The richest customer has a wealth of 17 (Customer 1 in this example).

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the number of customers (rows) and n is the number of banks (columns) in the accounts list. This is because the algorithm needs to:

1. Iterate through each of the m customers
2. For each customer, sum up their wealth across n banks using sum(v)
3. Find the maximum among all m sums using max()

The space complexity is O(1) if we don't count the space used by the generator expression itself, as the algorithm only needs to keep track of the maximum value found so far without creating any additional data structures proportional to the input size. The generator expression (sum(v) for v in accounts) produces values one at a time rather than creating a list of all sums at once.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Empty Input Handling

The current solution will fail if the accounts list is empty, as max() cannot operate on an empty sequence and will raise a ValueError.

Example of the issue:

accounts = []
# This will raise: ValueError: max() arg is an empty sequence
return max(sum(v) for v in accounts)

Solution:

def maximumWealth(self, accounts: List[List[int]]) -> int:
    if not accounts:
        return 0
    return max(sum(customer_accounts) for customer_accounts in accounts)

2. None Values in the Grid

If any cell contains None instead of an integer, the sum() function will fail with a TypeError.

Example of the issue:

accounts = [[1, 2, None], [3, 4, 5]]
# This will raise: TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

Solution:

def maximumWealth(self, accounts: List[List[int]]) -> int:
    if not accounts:
        return 0
    return max(sum(val or 0 for val in customer_accounts) 
               for customer_accounts in accounts)

3. Alternative Iterative Approach for Better Debugging

While the one-liner is elegant, it can be harder to debug or extend. An iterative approach provides more flexibility:

More maintainable solution:

def maximumWealth(self, accounts: List[List[int]]) -> int:
    max_wealth = 0
    for customer_accounts in accounts:
        current_wealth = sum(customer_accounts)
        max_wealth = max(max_wealth, current_wealth)
    return max_wealth

This approach:

• Handles empty lists naturally (returns 0)
• Easier to add logging or validation
• More readable for team members unfamiliar with generator expressions
• Allows for early termination if needed in future modifications