Understanding LeetCode Problem #1672: Richest Customer Wealth (JavaScript)
Tags: leetcode, algorithms, javascript, tutorial
Published: 2022-10-24 22:51:27

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](/problems/richest-customer-wealth/). 

![leetcode 1672](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3iev7mi3g0zjk207wit2.png)

# 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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/forEach). 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.