# Richest Customer Wealth **Difficulty:** EASY [External](https://leetcode.com/problems/richest-customer-wealth) Canonical: https://scaleengineer.com/dsa/problems/richest-customer-wealth **Data structures:** Array, Matrix --- ## Problem You are given an `m x n` integer grid `accounts` where `accounts[i][j]` is the amount of money the `i​​​​​​​​​​​th​​​​` customer has in the `j​​​​​​​​​​​th`​​​​ 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 = 6 ` `2nd customer has wealth = 3 + 2 + 1 = 6 `Both 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.length` * `n == accounts[i].length` * `1 <= m, n <= 50` * `1 <= accounts[i][j] <= 100` # Approaches ## Brute Force with Nested For-Loops 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. **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. **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. ### Explanation 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. ```java 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; } } ``` ### Algorithm 1. Initialize a variable `maxWealth` to 0. 2. Get the dimensions of the `accounts` grid: `m` rows (customers) and `n` columns (banks). 3. Use an outer loop to iterate through each customer, from `i = 0` to `m-1`. 4. Inside the outer loop, initialize a `currentWealth` variable to 0 for the current customer. 5. Use an inner loop to iterate through the bank accounts of the current customer, from `j = 0` to `n-1`. 6. In the inner loop, add the value `accounts[i][j]` to `currentWealth`. 7. After the inner loop finishes, `currentWealth` holds the total wealth for customer `i`. 8. Compare `currentWealth` with `maxWealth`. If `currentWealth` is greater, update `maxWealth` to `currentWealth`. 9. After the outer loop completes, return `maxWealth`. ## Iteration with Enhanced For-Each Loops 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. **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. **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. ### Explanation 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. ```java 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; } } ``` ### Algorithm 1. Initialize `maxWealth = 0`. 2. Use an enhanced for-loop to iterate through each `customerAccounts` array (row) in the `accounts` grid. 3. For each `customerAccounts`, initialize `currentWealth = 0`. 4. Use a nested enhanced for-loop to iterate through each `money` amount in the `customerAccounts` array. 5. Add `money` to `currentWealth`. 6. After the inner loop, update `maxWealth` using `maxWealth = Math.max(maxWealth, currentWealth)`. 7. After iterating through all customers, return `maxWealth`. ## Optimal Functional Approach with Java Streams 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. **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. **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. ### Explanation 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 a `Stream` from the 2D `accounts` array. 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 our `Stream` into an `IntStream`. For each `int[]` 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 the `IntStream`. It returns an `OptionalInt` to handle the case where the stream might be empty (e.g., if the input `accounts` array is empty). - `.orElse(0)`: This is called on the `OptionalInt`. If a maximum value was found, it returns that value. Otherwise, it returns the default value of 0. ```java import java.util.Arrays; class Solution { public int maximumWealth(int[][] accounts) { return Arrays.stream(accounts) .mapToInt(customer -> Arrays.stream(customer).sum()) .max() .orElse(0); } } ``` ### Algorithm 1. Convert the `accounts` 2D array into a `Stream`. 2. Use the `mapToInt` intermediate operation to transform the stream. For each `int[]` array in the stream, calculate its sum. 3. This results in an `IntStream` where each element is the total wealth of a customer. 4. Use the `max()` terminal operation on the `IntStream` to find the maximum wealth. This returns an `OptionalInt`. 5. Use `orElse(0)` to extract the value from the `OptionalInt`, providing a default of 0 if the input array (and thus the stream) is empty. # Solutions ### Java ```java class Solution { public int maximumWealth(int[][] accounts) { int ans = 0; for (var e : accounts) { ``` ### CPP ```cpp class Solution { public: int maximumWealth(vector> &accounts) { int ans = 0; for (auto &v : accounts) { ans = max(ans, accumulate(v.begin(), v.end(), 0)); } return ans; } }; ``` ### Python ```python class Solution: def maximumWealth( self, accounts: List[List[int]]) -> int: return max(sum(v) for v in accounts) ```