Richest Customer Wealth
Easy Nested loops
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A grid lists how much money each customer (row) has in each bank (column). A customer's wealth is the sum of their row. Return the largest wealth.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: add up each row, and report the biggest row total.
Why this works: every cell is read exactly once, so the cost is rows × columns. Nested loops are not always "n squared"; they are the product of the two sizes.
Example: accounts = [[1,5],[7,3],[3,5]]
row 0: 1 + 5 = 6 best = 6row 1: 7 + 3 = 10 best = 10row 2: 3 + 5 = 8 best = 10answer: 10
✦Hints open one at a time
↗Approach
For every row add up the values and compare with the best so far. Every cell is touched once, so the cost is O(m·n) — nested loops are not automatically "O(n²)", they are the product of the two loop sizes.
</>Solution (Java)
class Solution {
public int maximumWealth(int[][] accounts) {
int best = 0;
for (int[] customer : accounts) {
int wealth = 0;
for (int money : customer) {
wealth += money; // total of this row
}
best = Math.max(best, wealth);
}
return best;
}
}!Common mistake
Calling nested loops "O(n²)" without thinking. Here it is rows × columns, which can be very different numbers.
- Time: O(m·n) where m = customers, n = banks.
- Space: O(1).
