algoadvance

Leetcode 1672. 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 i-th customer has in the j-th bank account. 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 = 1 + 5 = 6
2nd customer has wealth = 7 + 3 = 10
3rd customer has wealth = 3 + 5 = 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

Clarifying Questions

1. Can the accounts array be empty?
   • No, there will be at least one customer and one bank account.
2. What are the ranges of the values within the accounts array?
   • The typical constraints for such problems: 1 <= m, n <= 50 and 1 <= accounts[i][j] <= 100.

Strategy

• Iterate through each customer.
• For each customer, compute the sum of all bank accounts they have.
• Keep track of the maximum wealth encountered during these iterations.
• Return the maximum wealth.

Code

Here is the Java code implementation:

public class RichestCustomerWealth {
    public static int maximumWealth(int[][] accounts) {
        int maxWealth = 0;
        
        for (int i = 0; i < accounts.length; i++) {
            int currentWealth = 0;
            for (int j = 0; j < accounts[i].length; j++) {
                currentWealth += accounts[i][j];
            }
            if (currentWealth > maxWealth) {
                maxWealth = currentWealth;
            }
        }
        
        return maxWealth;
    }

    public static void main(String[] args) {
        int[][] accounts1 = { {1, 2, 3}, {3, 2, 1} };
        System.out.println(maximumWealth(accounts1)); // Output: 6
        
        int[][] accounts2 = { {1, 5}, {7, 3}, {3, 5} };
        System.out.println(maximumWealth(accounts2)); // Output: 10
        
        int[][] accounts3 = { {2, 8, 7}, {7, 1, 3}, {1, 9, 5} };
        System.out.println(maximumWealth(accounts3)); // Output: 17
    }
}

Time Complexity

• The time complexity of this solution is O(m * n), where m is the number of customers and n is the number of bank accounts per customer. This is because we need to traverse each entry in the accounts matrix once to compute the wealth of each customer.
• The space complexity is O(1) (constant space), since no additional space proportional to the input size is used. Only a few variables are used to keep track of the current and maximum wealth.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?