Richest Customer Wealth

Q: What is the time complexity of Richest Customer Wealth?

O(m × n) for m customers and n banks, because every balance is added once. No algorithm can skip a cell, since any skipped balance could be the one that makes its owner the richest. The running maximum uses O(1) extra space.

Q: Can the sums overflow a 32-bit integer?

Not here. A row has at most 100 balances of at most 10^4 , so a total is at most 10^6 , far below 2^31 - 1 . With larger limits you would add into a 64-bit integer.

BeginnerArrays and strings

+10

A bank keeps a grid accounts with m rows, one per customer, and n columns, one per bank: accounts[i][j] is the money customer i holds in bank j. A customer's wealth is the total of their row. Return the wealth of the richest customer.

Function

maximumWealth(accounts: integer-2d-array) → integer

accountsinteger-2d-array: the grid of balances, one row per customer and one column per bank
Returnsinteger: the largest row total

Constraints

1 ≤ accounts.length ≤ 100
1 ≤ accounts[i].length ≤ 100, and every row has the same length.
0 ≤ accounts[i][j] ≤ 10⁴

Examples

Input: accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
Output: 14
Explanation: The rows sum to 11, 14 and 10. The middle customer is the richest with 14, even though the largest single balance, 8, belongs to someone else.

Input: accounts = [[3], [9], [4]]
Output: 9
Explanation: Each customer uses one bank, so the totals are 3, 9 and 4, and the answer is 9.

Solution

Every balance belongs to exactly one customer, so you must read the whole grid: no approach beats O(m × n) time. The choice is how much you keep while you read. Only the largest total seen so far matters, so one number is enough.

List every total, then pick the largest

Intuition

Walk each row, add up its balances, and store one total per customer: [11, 14, 10] for the first example. Then scan that list for its largest value, 14.

Each of the m × n balances is added once, so the time is fine. The cost is the list, m extra numbers you keep only to throw away all but one.

Algorithm

Create an empty list totals.
For each row, add its balances and append the sum to totals.
Start richest at the first total.
Replace richest with any larger total, then return it.

def maximumWealth(accounts):
    # First pass: every customer's total wealth.
    totals = []
    for customer in accounts:
        wealth = 0
        for money in customer:
            wealth += money
        totals.append(wealth)
    # Second pass: the largest total.
    richest = totals[0]
    for wealth in totals:
        if wealth > richest:
            richest = wealth
    return richest

Keep a running maximum

Intuition

Once a row's total is known, the only question is whether it beats the best total so far. Compare it right away and keep one number, richest. In the first example richest goes 0 → 11 → 14 and stays at 14 when the last row sums to 10.

Starting richest at 0 is safe because no balance is negative, so every total is at least 0 and a grid of zeros returns 0. If balances could be negative, you would start from the first row's total.

Algorithm

Set richest to 0.
For each row, add up its balances into wealth.
If wealth > richest, set richest to wealth.
After the last row, return richest.

def maximumWealth(accounts):
    richest = 0  # money is never negative, so 0 is a safe start
    for customer in accounts:
        richest = max(richest, sum(customer))
    return richest

Pitfalls and edge cases

Summing columns instead of rows. A column is one bank across all customers. In the first example the columns sum to 14, 13 and 8, and the first matches the answer only by luck.
Returning the largest single balance. 8 is the biggest number in the first grid, but its owner has 11 in total, less than the 14 of a customer with no balance above 5.
Resetting the row total in the wrong place. Set wealth to 0 inside the row loop, before the inner loop. Set it once outside, and each customer inherits the previous one's money.

Frequently asked questions3

What is the time complexity of Richest Customer Wealth?

O(m × n) for m customers and n banks, because every balance is added once. No algorithm can skip a cell, since any skipped balance could be the one that makes its owner the richest. The running maximum uses O(1) extra space.

How do you find the maximum row sum of a 2D array?

Loop over the rows, sum each one, and keep the largest sum in a variable. Many languages shorten the inner loop with a built-in sum, like max(sum(row) for row in accounts) in Python. Either way you read each cell once.

Can the sums overflow a 32-bit integer?

Not here. A row has at most 100 balances of at most 10^4, so a total is at most 10^6, far below 2^31 - 1. With larger limits you would add into a 64-bit integer.

def maximumWealth(accounts):
    # Write code here

Test #1

Test #2

Argument

accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]

Expected Output