Understanding LeetCode Problem #1672: Richest Customer Wealth (JavaScript)

Hey y'all!

I've been grinding LeetCode lately in preparation for Technical Interviews, and I wanted to walkthrough a solution to an algorithm that I was able to discover.

Algorithm

First off, here's a screen shot of the algorithm, Richest Customer Wealth.

1) Talk To Yourself

First off, in any algorithm, take a step back and ask yourself what this algorithm is actually trying to solve.

Take the time to speak the problem into existence, out loud, and with intent. Yes, even in a live/coding interview!

You want to showcase your ability to verbalize code, talk through it, and also indicate you didn't just memorize this (even if you maybe did ;) )

Start by asking yourself:

• How would I phrase this in my own words?
• What data or information do I know I have?
• What is this problem actually asking me to do?

So, let's break down the prompt:

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.

Here's a rough recreation of my own thought process:

> Ok... wait, why do rich people need... ok... focus James... Ok.. Sounds like we have arrays... which could have other arrays in it... array all day amirite...focus james... and these bougie peeps, i mean banks, are asking me to find how much cheese is in their bougie peeps accounts... ahem... what's the total amount of money in each of those accounts which are those arrays... and then find out who got the most cheese... i mean moneys... i mean the maximum value...

(End scene... sorry, we like to have fun here...amirite?)

Speak and it shall be known

Just from speaking it into existence, a whole world of solutions open up for us.

Off the bat, we know:

1. We are dealing with Arrays.

Which is great because maybe now we can use built-in Array methods and/or solutions that Arrays give us by default (at least thanks in Javascript). At the very least, we know we are dealing with arrays.

2. We need to count that paper.

We know we need to find the sum of a numbers in an array. My first thought is a reduce method or some sort of for loop where we are simply taking the sum of all the elements of the array.

3. We need to find who got the most paper

Aka, we need to fine the maximum number of those sums. So, if I can get those sums, I know that there's this Math.max() method that JavaScript gives me that I could use which can be used on numbers... and also... arrays! #ArrayAllDay

And I haven't even touched my keyboard yet. I simply am planning my strategy and solution before I start.

But from taking this quick few minutes to breathe, think, and evaluate, I already know what I probably need to do:

1. Find a way to get the sum of the baby arrays within the big mama array (arrayception).
2. Put those totals into another array (papa array).
3. Find and return the maximum value of those totals (stack that cheese).

Jesse, Let's Code

Ok, so the part we all want to do. The coding.

I'm going to start with my solution and walk through it.

var maximumWealth = function(accounts) {
    let wealthArr = []
    accounts.forEach((account) => {wealthArr.push(account.reduce((a,b)=> a+b,0))})
    return Math.max(...wealthArr)

};

First, I initialize an empty array. I know I'm going to need an array to help me keep track of all the totals I'm going to sum.

Second, I use the forEach method. If you're not familiar with it, I highly recommend reviewing the method (and all Array methods), as I find them extremely helpful.

While I could go on, the TL;DR is it is basically a shortcut for a for loop. In humanspeak, for each element of the array, I want to do something.

Within the context of my algorithm, "for each" account within the "accounts" array, I am going to perform a function. Each account is the individual array of the account.

Which leads me to my function inside my forEach: a push method which is pushing a reduce method.

First, we are going to start "pushing" elements into my empty wealth array (wealthArr) with the push method.

Inside of the push method, I am using a reduce method.

Again, if you're unfamiliar, I highly, highly recommend reviewing the Javascript Array methods first. But, TL;DR, it is essentially another short cut for a loop that calculates the running total of an array.

In this instance, we are reducing all the elements of an array into one single value. We provide to the reduce method a function telling it how we want to reduce. In this instance, a simple function (a,b)=> a+b,0) where a and b are elements of the baby account array and we are adding them together (a + b), starting with value (0). The reduce method is going to perform that on all the elements of the baby account array until there are no more elements to add.

When we get to that singular value, we will push that into my wealthArr array.

And finally, going back to my 3rd point, I need to return the maximum value. So, I am taking my wealthArr which should have elements populated, and then calling the Math.max() method.

Pass The Talk Test

If you have the time, I highly recommend talking through a test of your solution. So, let's test this!

First, let's set grab one of the test accounts arrays that LeetCode gives us.

accounts = [[1,5],[7,3],[3,5]]

So, first, we are going to create an empty array called wealthArr. Simple enough.

wealthArr = []

And then we are going to call our forEach method on the accounts array, which is going to sum up every single value in one of those baby account arrays.The forEach is then going to start pushing into my empty wealthArr array the sum of each of those accounts, using my reduce method.

Each of those accounts are the individual arrays. The forEach is going to iterate through each of the elements of my accounts array and do stuff to them.

account1 = [1,5] 
account2 = [7,3] 
account3 = [3,5]

So, for instance:

account1 = [1,5] =>  1 + 5 = 6
account2 = [7,3] =>  7 + 3 = 10
account3 = [3,5] =>  3 + 5 = 8

So, at this point, after going through each of those accounts, I should have the following:

wealthArr = [6,10,8]

And then finally, I return the maximum value of the newly populated wealthArr. Be sure to use the spread operator (...)!

return Math.max(...wealthArr)
// return Math.max([6,10,8)
> 10

Voila!

Now, you could do this without array methods, using a regular for loop and creating your own running sum. There might be some interviews where they won't let you use built-in methods (which... is a discussion topic...)

That said, I highly recommend utilizing every tool at your disposal, and I find array methods both easier to understand, faster to implement, and also showcase your abilities in the language.

Enjoy, good luck, and please reach out if there are any questions!

Bonus: Time and Space Complexity (Big O)

The Time Complexity is O(n x m) or O (nm)
The Space Complexity is O(1)

Now, I do want to touch upon this for this algorithm, even though I am admittedly not an expert on Big O notation, since it's always important to know.

I like to think of Time Complexity as asking the question: how many operations am I performing on each input?

In this instance, I know I'm performing the following:

1. A loop (via my forEach method which is a looping method)
2. In each element of that loop, I'm performing another looping method via my reduce method.

For 1 and 2, we are performing one operation on one input (n) and then performing another operation on another different input (m).

As n grows, m could grow too. As m grows, this affects n as well.

In plain English, think of it this way:

The more accounts (arrays) we have, the more looping we have to do. The more numbers in each of the individual accounts we have, the more adding we have to do

This makes the Time Complexity O (n x m)

If we were doing another forEach within my original forEach, we'd be doing the same n operation, which would lead us to O(n * n) which is (On^2). Or if we needed to find a specific account/array, that also adds more complexity.

The Space complexity is O(1) which is constant. This means we are not creating more space the more we perform this function. If we were somehow saving the wealthArr into another array of arrays, then that would increase space complexity.