Richest Customer Wealth
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.
Examples:
Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation: Both customers are considered the richest with a wealth of 6 each, so return 6.
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.
Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Output: 17
Explanation: The first customer is the richest with a wealth 17.
Constraints:
- m == accounts.length
- n == accounts[i].length
- 1 <= m, n <= 50
- 1 <= accounts[i][j] <= 100
Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
To solve the problem of finding the wealth of the richest customer, we need to calculate the total wealth for each customer and then determine the maximum wealth among them.
For a single customer, we can compute their total wealth by summing up all the amounts in their accounts. To do this, we initialize a variable cur_wealth to 0. As we iterate through the accounts of a customer, we add each account's value to cur_wealth. This gives us the total wealth for that customer.
Now, to handle all customers, we use a loop to iterate through each row in the accounts grid (where each row represents a customer's accounts). For each row, we calculate the total wealth using the sum of its elements. If the current customer's wealth (cur_wealth) exceeds the maximum wealth encountered so far (max_wealth), we update max_wealth to reflect this new maximum.
By the end of the loop, max_wealth will contain the wealth of the richest customer, which is our desired output.
Let's walk through an example:
Step 1: Initialize Variable
- maxWealth = 0: Keeps track of the highest wealth found so far.
Step 2: Loop Through Each Customer's Accounts
We loop through each row in the grid, where each row represents a customer's accounts. For each customer, calculate their total wealth and compare it with the current maximum wealth.
Iteration 1: First Customer ([1, 5])
- Start with curWealth = 0 to calculate the total wealth of the current customer.
- Traverse the accounts:
- 1: Add to curWealth → curWealth = 1.
- 5: Add to curWealth → curWealth = 6.
- Total wealth for the first customer: curWealth = 6.
Compare curWealth with maxWealth:
- curWealth (6) is greater than maxWealth (0), so update:
- maxWealth = 6.
Iteration 2: Second Customer ([7, 3])
- Start with curWealth = 0 to calculate the total wealth of the current customer.
- Traverse the accounts:
- 7: Add to curWealth → curWealth = 7.
- 3: Add to curWealth → curWealth = 10.
- Total wealth for the second customer: curWealth = 10.
Compare curWealth with maxWealth:
- curWealth (10) is greater than maxWealth (6), so update:
- maxWealth = 10.
Iteration 3: Third Customer ([3, 5])
- Start with curWealth = 0 to calculate the total wealth of the current customer.
- Traverse the accounts:
- 3: Add to curWealth → curWealth = 3.
- 5: Add to curWealth → curWealth = 8.
- Total wealth for the third customer: curWealth = 8.
Compare curWealth with maxWealth:
- curWealth (8) is not greater than maxWealth (10), so no update is needed.
Step 3: Return the Result
At the end of all iterations:
- maxWealth = 10 is the highest wealth found.
The result is maxWealth, which is 10.
How to convert it in code:
- Set Up the Initial Variables
- Initialize maxWealth = 0 to keep track of the highest wealth encountered so far.
- Iterate Through Each Customer's Accounts
- Use a for loop to traverse each row in the accounts list.
- For each customer (row), calculate the total wealth in curWealth.
- Update the Maximum Wealth
- Compare the current customer's total wealth (curWealth) with maxWealth.
- If curWealth is greater than maxWealth, update maxWealth.
- Return the Maximum Wealth
- After processing all customers, return the value of maxWealth.
Code Implementation
C++
class Solution {
public:
int maximumWealth(vector<vector<int>>& accounts) {
int maxWealth = 0; // Initialize the maximum wealth variable
// Iterate through each customer's accounts
for (int i = 0; i < accounts.size(); i++) {
int curWealth = 0; // Variable to store the current customer's total wealth
// Calculate the total wealth for the current customer
for (int j = 0; j < accounts[i].size(); j++) {
curWealth += accounts[i][j];
}
// Update maxWealth if the current wealth is greater
if (curWealth > maxWealth) {
maxWealth = curWealth;
}
}
// Return the maximum wealth found
return maxWealth;
}
};
Java
class Solution {
public int maximumWealth(int[][] accounts) {
int maxWealth = 0; // Initialize the maximum wealth variable
// Iterate through each customer's accounts
for (int i = 0; i < accounts.length; i++) {
int curWealth = 0; // Variable to store the current customer's total wealth
// Calculate the total wealth for the current customer
for (int j = 0; j < accounts[i].length; j++) {
curWealth += accounts[i][j];
}
// Update maxWealth if the current wealth is greater
if (curWealth > maxWealth) {
maxWealth = curWealth;
}
}
// Return the maximum wealth found
return maxWealth;
}
}
Python
class Solution(object):
def maximumWealth(self, accounts):
"""
:type accounts: List[List[int]]
:rtype: int
"""
maxWealth = 0 # Initialize the maximum wealth variable
# Iterate through each customer's accounts
for customer in accounts:
curWealth = sum(customer) # Calculate the total wealth for the current customer
# Update maxWealth if the current wealth is greater
if curWealth > maxWealth:
maxWealth = curWealth
# Return the maximum wealth found
return maxWealth
Javascript
/**
* @param {number[][]} accounts
* @return {number}
*/
var maximumWealth = function(accounts) {
let maxWealth = 0; // Initialize the maximum wealth variable
// Iterate through each customer's accounts
for (let i = 0; i < accounts.length; i++) {
let curWealth = 0; // Variable to store the current customer's total wealth
// Calculate the total wealth for the current customer
for (let j = 0; j < accounts[i].length; j++) {
curWealth += accounts[i][j];
}
// Update maxWealth if the current wealth is greater
if (curWealth > maxWealth) {
maxWealth = curWealth;
}
}
// Return the maximum wealth found
return maxWealth;
};
Bonus Tip
The std::accumulate function in C++ is another useful function from the Standard Template Library (STL) that helps simplify the process of accumulating values in a range, which can be particularly useful when summing the elements of a container like a vector. It eliminates the need for an explicit loop to calculate sums, making the code more concise and readable.
For example, in this case, you can use std::accumulate to calculate the wealth of the current customer.
Syntax of std::accumulate: std::accumulate(start_iterator, end_iterator, initial_value);
Where:
- start_iterator: The iterator pointing to the beginning of the range.
- end_iterator: The iterator pointing to the end of the range.
- initial_value: The initial value to start the accumulation (typically 0 when summing).
Time Complexity : O(m*n)
- Outer Loop (Iterating through each customer):
- The outer loop iterates over each customer. Let's assume there are m customers.
- Therefore, the outer loop runs m times.
- Inner Loop (Summing the accounts of a customer):
- For each customer, the inner loop iterates over the accounts of that customer. Let’s assume each customer has n accounts (elements in the i-th row).
- Inside the inner loop, we are simply adding each account balance to curWealth. This operation takes constant time for each account.
- Therefore, the time complexity for summing the accounts for a single customer is O(n).
Total Time Complexity:
- The outer loop runs m times (one per customer).
- For each customer, we are summing their accounts using an inner loop that runs n times.
- Therefore, the total time complexity is: O(m×n)
Where:
- m is the number of customers (rows in the matrix).
- n is the number of accounts for each customer (columns in the matrix).
Space Complexity: O(1)
- Input Storage:
- The input is a 2D vector accounts, where accounts is a vector of vectors, representing the accounts of m customers, and each customer has n bank accounts.
- The space required to store the input accounts is O(m * n), where:
- m is the number of customers (the number of rows in the matrix).
- n is the number of accounts for each customer (the number of columns in each row).
- Note: This space is not considered in the space complexity of the algorithm because the input is already given, and we are focusing on the additional space used by the algorithm.
- Additional Variables:
- maxWealth: This is an integer used to store the maximum wealth found so far. It occupies O(1) space because it is a single integer.
- curWealth: This is also an integer used to store the current wealth for a customer in the inner loop. It occupies O(1) space as well since it is a single integer.
- i and j: These are loop variables used to iterate through the accounts matrix. Both variables are integers and each takes up O(1) space.
Total Space Complexity: O(1), this means the algorithm uses constant space regardless of the size of the input matrix.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with m rows and n columns using all the elements from original.
The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.
Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.
In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.
You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.
The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.