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 add up to 2 + 8 + 1 = 11, 5 + 5 + 4 = 14 and 7 + 0 + 3 = 10. The middle customer has the most, 14, even though the single largest 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.

+14 hidden tests on Submit

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. A list of all totals works, but only the largest total seen so far matters, so one number is enough.

List every total, then pick the largest

Intuition

Split the task in two. First walk each row and add up its balances, storing one total per customer. For the first example that gives [11, 14, 10]. Then scan that list for its largest value, 14.

The work is fine: each of the m × n balances is added once, and the second pass reads m totals. For a 100 × 100 grid that is 10^4 additions. The cost is the list itself, m extra numbers you keep only to throw away all but one of them.

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. So 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.

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

The largest possible total is 100 × 10^4 = 10^6, so a 32-bit integer holds every sum.

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

The loops are short. The bugs come from mixing up which direction a customer runs in.

Summing columns instead of rows. A column is one bank across all customers; its total answers a different question. In the first example the columns sum to 14, 13 and 8, and the first one only matches the right answer 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 the 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.

Python

def maximumWealth(accounts):
    # Write code here

Test cases

Case 1

Case 2

Input

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

Expected