Richest Customer Wealth - Solution & Explanation
Problem Statement
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] <= 100
Approach Overview
Problem 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.
Approach 1: Iterative Calculation Approach
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.
Complexity
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.
Approach 2: Matrix Utilization via Map-Reduce
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.
Code
Python
JavaScript
Java
Complexity
Time Complexity: O(m * n)
Space Complexity: O(m)
Approach 3: Summation
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).
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode Solution - 1672 Richest Customer Wealth • John Leonardo • 2,506 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Richest Customer Wealth easy or hard?
Richest Customer Wealth Python/Java solution
How to solve Richest Customer Wealth in O(n)?
What is the best approach for Richest Customer Wealth?
Is Richest Customer Wealth asked at Google/Amazon/Meta?
What data structure is used in Richest Customer Wealth?
What is the time complexity of Richest Customer Wealth?
Ready to solve this problem?
Practice Richest Customer Wealth with our built-in code editor and test cases.
Practice on FleetCode