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:
Input: accounts = [[1,2,3],[3,2,1]] Output: 6 Explanation:1st customer has wealth = 1 + 2 + 3 = 62nd customer has wealth = 3 + 2 + 1 = 6Both customers are considered the richest with a wealth of 6 each, so return 6.
Example 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] <= 100Problem Overview: You receive a 2D matrix where accounts[i][j] represents the money the i-th customer has in the j-th bank. The task is to compute each customer's total wealth (sum of their row) and return the maximum wealth among all customers.
Approach 1: Iterative Calculation (O(m*n) time, O(1) space)
The most direct solution iterates through every customer row and calculates the sum of their accounts. For each row in the matrix, accumulate values using a simple loop and track the maximum sum encountered so far. This works because each row represents one customer's wealth distribution across banks. After computing the row total, compare it with the current maximum and update if necessary. The algorithm scans every cell exactly once, giving O(m*n) time complexity where m is the number of customers and n is the number of banks. Since only a few variables are used for tracking totals, the space complexity remains O(1). This approach relies on basic traversal of a array and is the most common interview implementation.
Approach 2: Matrix Map-Reduce Pattern (O(m*n) time, O(m) space)
Languages with strong functional utilities allow a compact solution using a map-reduce style pipeline. First compute the sum of each row using operations like sum() or reduce(). This produces an intermediate list where each value represents a customer's total wealth. Then apply a max() operation to find the richest customer. Conceptually, this is a two-step process: map each row to its total wealth, then reduce the results to the largest value. The time complexity remains O(m*n) because every element of the matrix must still be processed. Space complexity becomes O(m) if the intermediate wealth list is stored. This style is common in Python and JavaScript and demonstrates familiarity with functional transformations on collections.
Recommended for interviews: The iterative row-sum approach is what interviewers typically expect. It clearly shows you understand how to traverse a 2D array and maintain running aggregates. The map-reduce variant is concise and expressive in languages that support it well, but interviews usually prioritize the explicit loop implementation because it demonstrates control over iteration and memory usage.
This approach involves iterating over each customer's accounts, calculating their total wealth by summing up the amounts, and keeping track of the maximum wealth found during these calculations. This method is simple and direct, leveraging basic iteration and comparison.
The code sums each row's elements in the accounts grid to calculate the wealth of each customer. The variable maxWealth keeps track of the highest wealth encountered.
Time Complexity: O(m * n), where m is the number of customers and n is the number of banks.
Space Complexity: O(1), as we only use a few extra variables irrespective of input size.
This approach considers a more functional programming style by mapping over the initial list to compute each customer's wealth, thereby generating an array of wealth values, which is in turn reduced (or simply searched) to obtain the maximum wealth.
Here, map is used to apply the sum function across all customers in accounts, and then max finds the highest resulting sum.
Python
JavaScript
Java
Time Complexity: O(m * n)
Space Complexity: O(m)
We traverse accounts and find the maximum sum of each row.
The time complexity is O(m times n), where m and n are the number of rows and columns in the grid, respectively. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Calculation Approach | Time Complexity: O(m * n), where m is the number of customers and n is the number of banks. |
| Matrix Utilization via Map-Reduce | Time Complexity: O(m * n) |
| Summation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Row Summation | O(m*n) | O(1) | Best general solution; interview-friendly and memory efficient |
| Matrix Map-Reduce | O(m*n) | O(m) | Useful in Python/JavaScript for concise functional-style code |
1672 Richest Customer Wealth | Zero to FAANG Kunal | Assignment Solution | Leetcode | Shapnesh • Programmers Zone • 10,363 views views
Watch 9 more video solutions →Practice Richest Customer Wealth with our built-in code editor and test cases.
Practice on FleetCode