Heist

TIP102 Unit 1 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Nested Loops

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the function?

  • A: The input is an m x n 2D integer matrix accounts where accounts[i][j] represents the amount of money the ith customer has in the jth bank.

• Q: What is the expected output of the function?

  • A: The function should return a list [i, w] where i is the 0-based index of the wealthiest customer and w is their total wealth.

• Q: How is the wealth of a customer calculated?

  • A: A customer's wealth is calculated by summing all the amounts in their row (i.e., sum(accounts[i])).

• Q: What if multiple customers have the same wealth?

  • A: If multiple customers have the same wealth, the function can return the index of any one of them.

• Q: Are there any constraints on the matrix?

  • A: The problem assumes that the matrix is not empty and that all customers have at least one bank account.

• The function wealthiest_customer() should take a 2D integer matrix accounts and return a list [i, w] where i is the index of the wealthiest customer and w is their total wealth.

HAPPY CASE
Input: accounts = [[1,2,3],[3,2,1]]
Expected Output: [0, 6] or [1, 6]

Input: accounts = [[1,5],[7,3],[3,5]]
Expected Output: [1, 10]

EDGE CASE
Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Expected Output: [0, 17]

Input: accounts = [[0,0,0],[0,0,0]]
Expected Output: [0, 0] or [1, 0]

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse each customer's accounts, sum their wealth, and track the maximum wealth and the corresponding customer index.

1. Initialize `max_wealth` to 0 and `wealthiest_index` to 0.
2. Iterate through each customer in `accounts`.
    a. Calculate the sum of wealth for the current customer.
    b. If the current wealth is greater than `max_wealth`, update `max_wealth` and `wealthiest_index`.
3. Return `[wealthiest_index, max_wealth]`.

⚠️ Common Mistakes

• Not handling the case where multiple customers have the same maximum wealth.
• Incorrectly summing the wealth of each customer.

I-mplement

Implement the code to solve the algorithm.

def wealthiest_customer(accounts):
    max_wealth = 0
    wealthiest_index = 0
    
    for i in range(len(accounts)):
        current_wealth = sum(accounts[i])
        if current_wealth > max_wealth:
            max_wealth = current_wealth
            wealthiest_index = i
    
    return [wealthiest_index, max_wealth]