I'm going to create more algorithm videos for you.

Well, as you can see, I took a little while to get to that.

And I'm sorry about that, but I promise you that it is definitely worth the wait.

This is the best algorithm video I've made so far.

And in this video, we're gonna take a look at solving a problem that actually is great because it doesn't test your knowledge of remembering a bunch of really contrived algorithms.

But it actually test you at the core of your problem solving skills and a really unique and challenging way.

And I can't wait to show it to you.

So without any further ado, let's get started.

Now.

My name's Kyle and this is Webb.

Have simplified where I simplified the web for you.

So if you're new around here, make sure you subscribe for more videos of me.

Simple.

Find the web for you.

Let's get started by actually looking at the problem that we're gonna be solving today.

And this problem is called add two numbers, which at face value that appears to be incredibly easy.

But I promise you it's much more challenging than it looks.

And essentially what we're given is to non empty, linked list, and what a link list is is essentially.

It's kind of like an array.

But each element in the array has a reference to the next element in that array.

So instead of access in it by index, you access it by going from one element to the next element into the next element and so on until you get to the end of the array.

So it's really easy to go sequentially through the array.

So what we have is with these two linked list, and they were just full of non negative numbers imagers, to be exact.

So whole numbers and these whole numbers are actually representing the digits of a full number, and these digits are stored in reverse order inside of the array.

So if you have the number 120 for example, the very first element in the ray would be zero.

The second element in the array would be too, and in the last third element in that array would be one.

It's just that number 1 20 in reverse, which each of the digits taken up their own element inside that wait list.

And the goal of this algorithm is to take the two length list we get and to add them together and then to return another length list, which has the number that adds together, too.

So let's take a quick look at the example that they're showing us down below.

As you can see, we have a link list, which is 243 which is the number 342 because it's in reverse order and we also have the link list 564 which is 465 since it's in reverse order.

As you can see, we're adding those two numbers together to get 807 and what we're doing returned from our function that we create is we want to return that 807 number.

But of course, in reverse order Sogo seven, then zero and then ate so immediately.

Just by looking at this, we can kind of already brainstorm and initial solution to this problem and the way that it works is just by doing normal addition.

You start with the bottom number, which in our case here is the very first element in our raise.

And we add those two almost together to get seven.

As you can see down here, we then go to the next element, which is four and six.

When we add those, we get 10.

So what we need to do, just like a normal addition as we keep the zero.

So as you can see zero here, we actually carry over that additional one.

So when we get to three and 43 plus 47 plus, that carryover of one gives us the eight for our final output, and that's essentially the initial solution to our problem.

We're gonna run into a bunch of edge cases as we actually solved this problem.

But let's just start coating up our initial solution to see where the edge cases are as we run into them.

So here we have our initial code, and as you can see at the top here we have our class, which is our list.

Note.

It's a little bit confusing cause they put function here, but it's really just a class.

And essentially this list note is going to take a value, and that's going to have that value.

And then it's going to have a next value.

And this next is essentially just a pointer that leads to the next element inside this list node.

So every list note will have a next which points to another list node.

Or if it's the very last part of the array, it'll actually just point to nothing.

So Knoll and just to kind of generate how this works.

Imagine you have an array of zero and one.

This would be exactly the same here as having what's called a new list node with a value of zero.

And then we wanted the list note.

Next.

So this list minute, let's just set it to a variable here is going to be just called one.

Such is the first element in our ray, and we're gonna have to here is gonna be equal to a new list node of one, and we want to do is we want to put one dot next is going to equal to.

So essentially, now what we have is we have a link list where the first element here has a value of zero, and it's got a next property which points to two, which has the value of one.

So this is exactly the same as our ray up here, but we actually access E as elements here by using the dot next property, and that's where we're being passed in here.

We have to link list, which we're going to be our two different elements that were adding together.

So it's clear out all this, coach that we have a base value to start with here.

Here we go.

And the first thing we need to do is actually figure out howto loop through our link list that we have and a really easy way to look over a link list is to use a wild for example.

We can say while and we just want to put a value here, we just call it L one, which is our first link list.

So while L one is not equal to know, we want to do everything inside of this loop and then inside of this loop.

We just want to set out one here equal to l one dot next, and it's just going to get the next element inside about one.

And this is going to look through all of the elements of l one.

But we actually want to look through the elements of l one and L two.

And while in the example were shown, they both were the exact same length.

It is possible that l one will be short of a knell to, for example, adding 420 to 25.

Your second moment here, 25 is only gonna be two elements, so it'll actually end first.

So we need to do in here is we did actually put in and or l two is not equal to know.

So what this is going to do is going to look through this wild statement as long as we have elements in either l one or L too.

And we also need to make sure that down here we put l too equal to l two dot next just so we know that our linguist are constantly iterating over themselves.

One thing to know, though, is as I mentioned before, we have potential for one link list to be shorter than the other.

So, for example, if l to a shorter the l two dot Next is gonna be no.

While l one is not going to be no for dot Next.

So we actually need to make sure that we do a check here.

So you want to say If l one is not equal to know, then we can actually call this dot next function on it and we wanted to the exact same thing down here for L too.

It's just essentially make sure that we don't ever accidentally try to access the next element when there is no next element to access.

And there we go.

We're not actually going to run into these no error exceptions anymore.

So now that we're able to actually end our wild loop by implementing on our link list here, the next thing we need to do is get the value from our length list.

And this is actually really easy.

As we could stay up here, we have a dot v A l method, which is our value.

So we can just say that we're gonna create a variable called the one which is this l one dot vow and we could do the exact same thing.

We're gonna do this for RV too, so we can just say V two is going to be equal to l two dot bow.

But again, we have a very similar problem.

Are linked list.

Could be different links.

For example, three digits and two digits.

So we need to also do this.

Check here for a no check.

So let's make sure we copy that down.

If l one is equal, not equal to know, then we can actually set here.

V 12 R l one dot value Otherwise, by default, we want to set V 1 to 0 with studios accent thing for V two.

By default.

Copy this down books.

There we go.

Make sure it's indented properly.

And if l two is not equal to know that RV to be equal to l to Davao and now here we already have essentially the basis for our algorithm complete.

We have the values for our different numbers and we can add these together.

So we consider the some down here is just going to be equal to V one plus v two and just a show.

What we have done so far.

Let's create a default array here.

Just gonna set it to an empty array and we want to do is actually just want to take our son here and put that into our race.

We're gonna push our son into our ray, and then at the end here, we're just gonna log out that Ray council about log of our array and essentially, this array.

What it's going to be is just going to be the reversed some of all the different numbers in our length list.

So let's run our code and see what we get is a result.

You'll see that we get in a rug.

Let's check this error says Assignment to constant variable.

So obviously we need to make these.

Let's because we're trying to assign a value to them later, as you can see here.

So we need to make sure Let was tried running that again.

And as you can see, we get the output of 7 10 and seven.

And so far that looks really good to post.

Five is 74.6 is 10 and three.

Post forced seven.

We just need to make sure that we have the carry over working properly And then we also return this as a length list instead of a normal or right like this.

So let's get working on the carry over first.

That's gonna be actually pretty easy.

We just need to create a variable out here, which is going to be our carry over and by default, are carry over is gonna be zero.

On the very first instance, we're not gonna have anything carrying over.

So we're gonna set this to zero, and down here, we want to actually add our carry over to our addition.

So anything we carried over from the previous edition is now going to be put into our some here.

But how do we actually get that carry over?

And luckily, this is actually incredibly straightforward.

We just need to divide our number by 10 and then take whatever we have before the vestment point.

Essentially want to get anything.

That's a whole number when we divide by 10.

By coming down here, we can say our carry over is going to be equal to some divided by 10 and we just want to make sure that we get the floor so we could just save math.

Thought floor of that number on what this essentially is going to do is going to take our some Let's say that this is seven is going to divide it by 10 which is going to give this 100.7.

And then Matt, that floor is going to round that down.

So 0.7 will round down to zero, so our carryover will still be zero.

If, for example, our number was 11 though 11 divided by 10 is 1.1, and that'll round down with math out for and give us one as the overall number of leftover.

So now that we have our carry over being taken care of, what's actually do this run again and see what we get printed out.

As you can see now we get 7 10 and eight, and that's perfect because our one is being carried over.

So three plus four plus one is eight, but this number 10 should actually be zero.

So we actually want to make sure that if we have a number larger than 10 we actually need to roll that down to the smallest number here after the decimal point.

And to do that is also really straightforward.

We can just come down here after our carry over and we can say that are some which we're gonna change here, tow a Let we just want to say or some is equal to some module 0 10 And essentially, what this does is it says divide this number over here by the number on the right as many times as possible and tell me what the remainder is.

So, for example, some divided by 10.

So if we had 11 divided by 10 are remainder is going to be one left over after we've divided as many times as we possibly can.

And now it's just run that one last time again to see if that works.

We should get zero in that slot.

And as you can see, we got 708 which is perfect.

That's exactly what the output is expected to be.

All we need to do now with our output is actually make sure that it's a linked list instead of a normal array, because that's what they're expecting us to return.

And that becomes a little bit trickier because we can't just have a default of Ray like this.

What we need is to have the beginning of our link list.

So let's create the beginning of our length list.

We're just gonna put this into a Let variable and we're just gonna call this result, and the result is going to be equal to a new list note.

And it's just gonna be a list note of zero.

This is the very beginning of our link list.

We also need to make sure we keep track of what the current element in our link twist is so we need to have here, which is going to be our current node.

We just want to set that equal toe a result, because by default, our current note is just this beginning of our length list.