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.
This approach is functionally identical to the previous one but uses enhanced for-loops (or for-each loops) for a cleaner and more readable syntax. It abstracts away the index management, which can make the code less prone to errors and easier to read. The core logic of iterating, summing, and comparing remains the same.
Algorithm
- Initialize
maxWealth = 0. - Use an enhanced for-loop to iterate through each
customerAccountsarray (row) in theaccountsgrid. - For each
customerAccounts, initializecurrentWealth = 0. - Use a nested enhanced for-loop to iterate through each
moneyamount in thecustomerAccountsarray. -
Add `money` to `currentWealth`. - After the inner loop, update
maxWealthusingmaxWealth = Math.max(maxWealth, currentWealth). - After iterating through all customers, return
maxWealth.
Walkthrough
Instead of using index-based loops, we can use Java's for-each loop to iterate over the arrays. The outer loop iterates over each 1D array (customerAccounts) within the 2D array accounts. The inner loop then iterates over each integer (money) within the current customerAccounts array. This achieves the same result as the index-based approach but with more concise code. The Math.max() function is a convenient way to update the maximum wealth found so far.
class Solution { public int maximumWealth(int[][] accounts) { int maxWealth = 0; for (int[] customerAccounts : accounts) { int currentWealth = 0; for (int money : customerAccounts) { currentWealth += money; } maxWealth = Math.max(maxWealth, currentWealth); } return maxWealth; }}Complexity
Time
O(m * n) - The time complexity is identical to the nested for-loop approach, as we still iterate through every element of the grid.
Space
O(1) - Constant extra space is used, similar to the previous approach.
Trade-offs
Pros
More concise and often considered more readable than traditional for-loops.
Reduces the chance of off-by-one errors by abstracting away index management.
Cons
No performance benefit over traditional for-loops as it's syntactic sugar for the same underlying iteration.
This approach leverages Java 8 Streams to provide a more declarative and concise solution. It treats the data transformation as a pipeline of operations: converting the 2D array into a stream of 1D arrays, mapping each 1D array to its sum, and finally finding the maximum sum in the resulting stream. This functional style can lead to very clean code for data processing tasks.
Algorithm
- Convert the
accounts2D array into aStream<int[]>. - Use the
mapToIntintermediate operation to transform the stream. For eachint[]array in the stream, calculate its sum. - This results in an
IntStreamwhere each element is the total wealth of a customer. - Use the
max()terminal operation on theIntStreamto find the maximum wealth. This returns anOptionalInt. - Use
orElse(0)to extract the value from theOptionalInt, providing a default of 0 if the input array (and thus the stream) is empty.
Walkthrough
The Java Stream API allows us to process collections of data in a functional manner. We can solve this problem in a single, expressive statement.
Arrays.stream(accounts): This creates aStream<int[]>from the 2Daccountsarray. Each element of the stream is a 1D array representing one customer's accounts..mapToInt(customerAccounts -> Arrays.stream(customerAccounts).sum()): This is an intermediate operation that transforms ourStream<int[]>into anIntStream. For eachint[]array, it creates a new stream of its elements and calculates their sum..max(): This is a terminal operation that finds the maximum value in theIntStream. It returns anOptionalIntto handle the case where the stream might be empty (e.g., if the inputaccountsarray is empty)..orElse(0): This is called on theOptionalInt. If a maximum value was found, it returns that value. Otherwise, it returns the default value of 0.
import java.util.Arrays; class Solution { public int maximumWealth(int[][] accounts) { return Arrays.stream(accounts) .mapToInt(customer -> Arrays.stream(customer).sum()) .max() .orElse(0); }}Complexity
Time
O(m * n) - The stream operations still need to process each element. `mapToInt` iterates through `m` customers, and for each, `sum()` iterates through `n` banks.
Space
O(1) - For sequential streams, the operations are generally lazy and do not require significant extra space that scales with the input size.
Trade-offs
Pros
Extremely concise and expressive.
Follows a modern, functional programming paradigm.
Reduces boilerplate code and focuses on the 'what' rather than the 'how'.
Cons
May have a slight performance overhead compared to explicit loops due to the creation of stream objects and method calls.
Can be less readable for developers not familiar with Java Streams and functional programming concepts.
Solutions
Solution
class Solution {public int maximumWealth(int[][] accounts) { int ans = 0; for (var e : accounts) {class Solution {public: int maximumWealth(vector<vector<int>> &accounts) { int ans = 0; for (auto &v : accounts) { ans = max(ans, accumulate(v.begin(), v.end(), 0)); } return ans; }};class Solution: def maximumWealth( self, accounts: List[List[int]]) -> int: return max(sum(v) for v in 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.