Richest Customer Wealth
EasyPrompt
You are given an m x n integer grid accounts where accounts[i][j] is the amount of money the ith customer has in the jth 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 1:
1st customer has wealth = 1 + 2 + 3 = 6Example 2:
Input: accounts = [[1,5],[7,3],[3,5]]
Output: 10
Explanation:
1st customer has wealth = 6
2nd customer has wealth = 10
3rd customer has wealth = 8
The 2nd customer is the richest with a wealth of 10.Example 3:
Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Output: 17
Constraints:
m == accounts.lengthn == accounts[i].length1 <= m, n <= 501 <= accounts[i][j] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most fundamental and straightforward approach. We use two nested, index-based for-loops to iterate through the 2D array. The outer loop iterates through each customer, and the inner loop calculates the wealth for that customer by summing up their bank account balances. We keep track of the maximum wealth found so far and update it whenever we find a customer with greater wealth.
Algorithm
- Initialize a variable
maxWealthto 0. - Get the dimensions of the
accountsgrid:mrows (customers) andncolumns (banks). - Use an outer loop to iterate through each customer, from
i = 0tom-1. - Inside the outer loop, initialize a
currentWealthvariable to 0 for the current customer. - Use an inner loop to iterate through the bank accounts of the current customer, from
j = 0ton-1. - In the inner loop, add the value
accounts[i][j]tocurrentWealth. - After the inner loop finishes,
currentWealthholds the total wealth for customeri. - Compare
currentWealthwithmaxWealth. IfcurrentWealthis greater, updatemaxWealthtocurrentWealth. - After the outer loop completes, return
maxWealth.
Walkthrough
In this approach, we explicitly manage the iteration process using indices. We start by initializing a variable, maxWealth, to zero. We then iterate through each row of the accounts matrix, which represents a customer. For each customer, we calculate their total wealth by iterating through all the columns in that row and summing up the values. This sum is stored in a temporary variable, currentWealth. After calculating the wealth for a customer, we compare it with maxWealth and update maxWealth if the current customer's wealth is higher. This process is repeated for all customers, ensuring that by the end of the iteration, maxWealth holds the highest wealth value among all customers.
class Solution { public int maximumWealth(int[][] accounts) { int maxWealth = 0; int m = accounts.length; // Number of customers if (m == 0) { return 0; } int n = accounts[0].length; // Number of banks for (int i = 0; i < m; i++) { int currentWealth = 0; for (int j = 0; j < n; j++) { currentWealth += accounts[i][j]; } // Update maxWealth if current customer is richer if (currentWealth > maxWealth) { maxWealth = currentWealth; } } return maxWealth; }}Complexity
Time
O(m * n) - Where `m` is the number of customers (rows) and `n` is the number of banks (columns). We need to visit every element in the 2D array once to calculate the sums.
Space
O(1) - We only use a few extra variables (`maxWealth`, `currentWealth`, `i`, `j`) to store the state. The space required does not grow with the size of the input.
Trade-offs
Pros
Very easy to understand, even for beginners.
The logic is explicit and follows the problem description directly.
Highly efficient in practice with no overhead from creating extra objects or function calls.
Cons
The code is more verbose compared to using enhanced for-loops or streams.
Managing loop indices manually can sometimes lead to off-by-one errors, although it's straightforward in this case.
Solutions
Solution
class Solution {public int maximumWealth(int[][] accounts) { int ans = 0; for (var e : accounts) {Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.