LeetCode Problem 1672

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

LeetCode 1672 - Richest Customer Wealth

Problem Understanding

This problem gives us a two dimensional integer array called accounts. Each row represents a customer, and each column represents one of that customer's bank accounts.

The value accounts[i][j] represents how much money the i-th customer has in the j-th bank account.

Our task is to compute the total wealth of every customer and return the maximum wealth among all customers.

A customer's wealth is simply the sum of all values in their row.

For example, if a customer has accounts [1, 2, 3], their total wealth is:

$1+2+3=6$

We repeat this process for every customer and return the largest sum.

The constraints are relatively small:

• 1 <= m, n <= 50
• m is the number of customers
• n is the number of bank accounts per customer
• Every balance is between 1 and 100

These constraints tell us that even a straightforward solution will run efficiently. At most, the matrix contains:

$50\times50=2500$

elements, which is very small for modern computation.

The problem also guarantees that:

• Every customer has at least one bank account
• Every balance is positive
• The matrix is rectangular, meaning all rows have the same number of columns

Important edge cases include:

• A matrix with only one customer
• A matrix with only one bank account per customer
• Multiple customers having the same maximum wealth
• Very small matrices such as [[5]]

Because the input is guaranteed to be non-empty, we never need to handle invalid or empty matrices.

Approaches

Brute Force Approach

The brute force solution is to calculate the total wealth for every customer independently and keep track of the largest value found so far.

For each row:

1. Iterate through all bank accounts
2. Add all balances together
3. Compare the sum against the current maximum wealth
4. Update the maximum if needed

This works because the richest customer must be one of the rows in the matrix, and computing every row sum guarantees we examine every possible candidate.

Although this approach is called brute force, it is already efficient enough for the problem constraints because we only visit each cell once.

Key Insight for the Optimal Solution

The important observation is that the problem only asks for the maximum row sum.

We do not need to store all customer wealth values. Instead, while computing each row sum, we can immediately compare it with the current best answer.

This allows us to process the matrix in a single pass with constant extra space.

Since every element must be examined at least once to know the true wealth values, any correct solution must have at least linear complexity relative to the number of cells. Therefore, the single traversal approach is optimal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n)	O(m)	Stores wealth for all customers before finding the maximum
Optimal	O(m × n)	O(1)	Computes row sums and maximum simultaneously

Algorithm Walkthrough

1. Initialize a variable called max_wealth to 0.

This variable keeps track of the richest customer found so far. 2. Iterate through every customer row in accounts.

Each row contains all bank balances for one customer. 3. Compute the total wealth for the current customer.

We add together all balances in the row. In Python, we can use the built in sum() function. In Go, we manually iterate through the row and accumulate the total. 4. Compare the current customer's wealth with max_wealth.

If the current wealth is larger, update max_wealth. 5. Continue until all customers have been processed.

By the end of the traversal, max_wealth contains the largest row sum in the matrix. 6. Return max_wealth.

Why it works

The algorithm works because every customer's wealth is exactly the sum of one row in the matrix. By computing every row sum and maintaining the maximum value seen so far, we guarantee that the final answer is the largest wealth among all customers.

The invariant throughout the algorithm is:

After processing the first k customers, max_wealth stores the maximum wealth among those k customers.

Once all customers have been processed, the invariant guarantees that max_wealth is the richest customer wealth in the entire matrix.

Python Solution

from typing import List

class 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

The solution begins by initializing max_wealth to 0. This variable stores the best answer found so far.

We then iterate through each row in accounts. Each row represents a single customer's bank balances.

For every customer, we compute their total wealth using Python's built in sum() function. This produces the row sum efficiently and clearly.

Next, we compare the current customer's wealth with the existing max_wealth. If the current customer is richer, we update the answer.

After processing all rows, the function returns the maximum wealth discovered during the traversal.

The implementation directly mirrors the algorithm walkthrough and uses only constant extra memory.

Go Solution

func maximumWealth(accounts [][]int) int {
    maxWealth := 0

    for _, customerAccounts := range accounts {
        currentWealth := 0

        for _, balance := range customerAccounts {
            currentWealth += balance
        }

        if currentWealth > maxWealth {
            maxWealth = currentWealth
        }
    }

    return maxWealth
}

The Go implementation follows the same logic as the Python version.

Because Go does not provide a built in sum() function for slices, we manually iterate through each customer's accounts and accumulate the total in currentWealth.

Go slices are used naturally for the matrix representation. Integer overflow is not a concern because the maximum possible wealth is:

$50\times100=5000$

which easily fits inside a standard Go int.

The input constraints also guarantee that the matrix is non-empty, so no special handling for empty slices is required.

Worked Examples

Example 1

Input:

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

We process each customer one by one.

Customer	Accounts	Wealth Calculation	Current Wealth	Max Wealth
1	[1,2,3]	1 + 2 + 3	6	6
2	[3,2,1]	3 + 2 + 1	6	6

Final answer:

6

Example 2

Input:

accounts = [[1,5],[7,3],[3,5]]

Customer	Accounts	Wealth Calculation	Current Wealth	Max Wealth
1	[1,5]	1 + 5	6	6
2	[7,3]	7 + 3	10	10
3	[3,5]	3 + 5	8	10

Final answer:

10

Example 3

Input:

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

Customer	Accounts	Wealth Calculation	Current Wealth	Max Wealth
1	[2,8,7]	2 + 8 + 7	17	17
2	[7,1,3]	7 + 1 + 3	11	17
3	[1,9,5]	1 + 9 + 5	15	17

Final answer:

17

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every matrix cell is visited exactly once
Space	O(1)	Only a few integer variables are used

The algorithm processes every bank balance exactly one time, so the runtime is proportional to the total number of elements in the matrix.

No auxiliary data structures are allocated that grow with the input size. Only variables such as current_wealth and max_wealth are maintained, so the extra space usage is constant.

Test Cases

sol = Solution()

assert sol.maximumWealth([[1,2,3],[3,2,1]]) == 6
# Multiple customers tied for richest

assert sol.maximumWealth([[1,5],[7,3],[3,5]]) == 10
# Standard multi-row example

assert sol.maximumWealth([[2,8,7],[7,1,3],[1,9,5]]) == 17
# Richest customer appears first

assert sol.maximumWealth([[5]]) == 5
# Single customer with single account

assert sol.maximumWealth([[1],[2],[3]]) == 3
# One bank account per customer

assert sol.maximumWealth([[10,10,10]]) == 30
# Single customer with multiple accounts

assert sol.maximumWealth([[100]*50]) == 5000
# Maximum possible wealth under constraints

assert sol.maximumWealth([[1,1],[1,1]]) == 2
# All customers have identical wealth

assert sol.maximumWealth([[1,2],[10,1],[2,2]]) == 11
# Richest customer in the middle

Test	Why
[[1,2,3],[3,2,1]]	Validates handling of ties
[[1,5],[7,3],[3,5]]	Standard example with clear maximum
[[2,8,7],[7,1,3],[1,9,5]]	Ensures earlier maximum is preserved
[[5]]	Smallest valid input
[[1],[2],[3]]	Tests single-column matrices
[[10,10,10]]	Tests single-row matrices
[[100]*50]	Tests upper constraint values
[[1,1],[1,1]]	Tests equal wealth values
[[1,2],[10,1],[2,2]]	Tests maximum in the middle row

Edge Cases

One important edge case is a matrix containing only one customer, such as [[10, 20, 30]]. A buggy implementation might incorrectly assume multiple rows exist or initialize the maximum improperly. Our solution handles this naturally because the loop processes the single row and returns its sum.

Another important case is when multiple customers share the same maximum wealth. For example:

[[1,2,3],[3,2,1]]

Both customers have wealth 6. Since the problem only asks for the maximum wealth value and not the customer index, our implementation works correctly by simply tracking the largest sum seen so far.

A third edge case is a matrix with only one bank account per customer, such as:

[[1],[5],[3]]

In this scenario, each row sum equals the single account value itself. The algorithm still works because summing a one element row is valid and produces the correct wealth.

Another subtle case involves maximum constraint values. A customer may have 50 accounts each containing 100 dollars. The maximum wealth becomes:

$50\times100=5000$

Our implementation safely handles this because both Python integers and Go integers easily support values far larger than 5000.