Leetcode – Richest Customer Wealth Solution

The problem “Richest Customer Wealth” is a simple yet interesting Leetcode challenge that requires you to manipulate multidimensional arrays and compute aggregations. While it seems straightforward, the problem provides an opportunity to delve into various Python techniques for handling lists and offers a chance to ponder on code optimization. In this article, we’ll explore different approaches for solving this problem, including their time complexity, space complexity, and Python implementation.

Problem Statement

Given a 2D array accounts, where accounts[i][j] is the money the i-th customer has in the j-th bank, return the wealth that the richest customer has. A customer’s wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.

Example

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

Output: 6

The first customer has a wealth of 1+2+3=6, and the second customer has a wealth of 3+2+1=6, so both are the richest with a wealth of 6.

Brute-Force Approach: Nested Loops

The most naive approach is to use nested loops to iterate over each customer’s accounts, summing up their wealth and keeping track of the maximum wealth encountered.

Python Code

def maximumWealth(accounts):
    max_wealth = 0
    for account in accounts:
        customer_wealth = 0
        for money in account:
            customer_wealth += money
        max_wealth = max(max_wealth, customer_wealth)
    return max_wealth

Time Complexity

The time complexity of this approach is O(m×n), where m is the number of customers and n is the number of banks. This is because we need to loop through each customer and each of their bank accounts.

Optimized Approach: List Comprehension and Built-In Functions

Python provides various built-in functions that allow you to perform operations like summing a list in O(n) time. We can use these features to optimize our code.

Python Code

def maximumWealth(accounts):
    return max(sum(account) for account in accounts)

Time Complexity

The time complexity remains O(m×n), but the real-time execution is faster due to Python’s internal optimizations for built-in functions like sum and max.

Testing Your Solution

Before submitting your solution on Leetcode, it’s a good practice to test it against various test cases to ensure its correctness.

assert maximumWealth([[1, 2, 3], [3, 2, 1]]) == 6
assert maximumWealth([[1, 5], [7, 9]]) == 16
assert maximumWealth([[2, 8, 7], [7, 1, 3], [1, 9, 5]]) == 17
assert maximumWealth([[5, 5, 5]]) == 15

Conclusion

The “Richest Customer Wealth” problem serves as an excellent introduction to array manipulation and aggregation techniques in Python. Although the problem is straightforward, solving it helps cement a strong foundational understanding of Python lists and built-in functions like sum and max. While the problem might not seem too challenging, it’s a good warm-up problem that can prepare you for more complex challenges involving 2D arrays and data aggregation. The key takeaway is to not only solve the problem but also to understand the underlying Python features that can help you optimize your solution.