A Practical Guide to Algorithms with JavaScript Unique Sort Solution

[00:00:00]
>> Bianca: All right, so let's take a look at our solution. So we're going to use the breadcrumbs method. Which is a way of caching values, so that we can keep track and remember values that we've already seen. And this method has a trade-off between, it speeds up our algorithm, but it does something with our space complexity.

[00:00:29] So as in rows, we are caching more values to our breadcrumb object. Which means that we have a linear space complexity that we need to consider with this algorithm. So we're doing a trade-off, time for space. Which in most cases is fine, but it's just something to be aware of.

[00:00:50] So our task was to take a sorting algorithm and turn it into a unique sort algorithm, which means that we wanna return an array with no duplicates. And so you can see our demo data here has a bunch of 2s in it. And we simply wanna return 2, 3, 4.

[00:01:10] And any duplicates, we want to ignore. So how are we gonna go about doing that? So first thing we're gonna do is, we're gonna set up our breadcrumbs object here. You can also call this cache, if you want. And this is where we're gonna keep track of all values that we've seen before.

[00:01:27] If we've seen it before and we come across it again, we know that we don't need to push that value to our result. So we'll start our result of here, right? And this is another thing to keep a note of in terms of the trade-off between time complexity and space complexity, is that we're creating a brand new array here.

[00:01:47] So not only are we creating a new object, we're are also creating an array to push into all of our results. There are other ways that you can do this without pushing into a new array, but this is the easiest way to get started. But just keep that in mind.

[00:02:04] So the first thing we're gonna do is, we're gonna loop through the length of our list, and we're gonna check if we haven't seen it before. How do we know we haven't seen it before? It's because when we look up array of i, so i is gonna start at 1, right?

[00:02:27] We're just assuming the very first one is not a duplicate, right? So then we're gonna start at the second one, which is gonna be this 2. So array at one is actually 2. And so if we do a lookup of breadcrumbs with the key 2, what is it gonna return for us at this point where i is 1?

[00:02:54] Our very first loop.
>> Bianca: At this point, so i is 1. We haven't actually saved anything yet to our breadcrumbs. So it's the very first scenario. So we initialize it as empty. And so we're saying, what is breadcrumbs at 2? It's gonna be undefined, because breadcrumbs is empty at this point.

[00:03:20]
>> Speaker 2: This is where I'm getting tripped up. So if it's an object, I'm used to thinking of an object as a key value pair, right? So how are we saving this? Are we saying this index of i, this is the value?
>> Bianca: Well, this is a lookup. This isn't, so we're not saving any data right now.

[00:03:35] At this point, we're just looking up. We're like, is this data on our object.
>> Speaker 2: Okay.
>> Bianca: And so we do a lookup. And if it returns undefined, then we know that we haven't-
>> Speaker 2: Found it.
>> Bianca: Yeah, we haven't seen it yet, so good question. So this says, if this is false or undefined, right, we're gonna force this into a boolean.

[00:03:57] So undefined is gonna be false. So this condition is true. Since this condition is true, we're gonna enter it into the body of this if block. And so, since we haven't seen it before, we're gonna push that item into our result array. So now our result array has,

[00:04:17]
>> Bianca: It has 4, and it also has 2. Can you guys see this on the bottom?
>> Bianca: And then our cache is empty, we're only here.
>> Bianca: I found a bug already.
>> Bianca: Then we're going to run this operation. This is a constant time operation, where we're saving a value to our breadcrumbs object.

[00:04:44] So array at i is what again?
>> Bianca: 2, and then we're giving it the value true. That way, when we run into this condition again, we look up 2 in the very next one. So i is now 2, array at 2 is 2. There's a lot of 2s going on, so our very next one is 2.

[00:05:08] And have we seen that before?
>> Speaker 2: No.
>> Bianca: So does array at i, which is 2, what does this evaluate to? We're gonna look up on our breadcrumbs object. We see 2 is there, and it's gonna evaluate to true. So is it false? No, since it's not false, we're going to skip this condition.

[00:05:33] And we'll go to the next one. Yep?
>> Speaker 3: I have a question.
>> Bianca: Sure.
>> Speaker 3: So you haven't, you never-
>> Bianca: Can you speak up just a little bit more?
>> Speaker 3: Yeah, you never push 4 to breadcrumbs, and so it is never true. So if you have another 4, I feel that the breadcrumbs would evaluate to false and then push the 4 in?

[00:05:55]
>> Bianca: Yeah, absolutely, so that's the bug-
>> Speaker 3: Okay.
>> Bianca: In our code, yeah, good finding. So how do we manage that bug, how do we fix that?
>> Speaker 2: Just start at i equals 0, and then empty result array, no?
>> Bianca: Well, that's what I would do. I see, so you're saying we could do this?

[00:06:16] Yeah, that's another way.
>> [CROSSTALK]
>> Bianca: Mm-hm, so we could do it that way. We can also just initialize breadcrumbs with the first one in there. Both are good, cool.
>> Bianca: Cool, we can do it like that. But I don't wanna ruin the solution for everyone. Okay, so I'm gonna keep the bug in there.

[00:06:45] Because as I edit these slides, it's gonna update them for the other people who use it.
>> Bianca: Okay, so cool. So then as we go through all these 2s, we already found it. So we're gonna keep skipping this if, until we get to which index? Zero, one, two, the third index, which is inconveniently valued at 3.

[00:07:12] Or very conveniently, even. So where I is 3, array at i is 3. So then we do the lookup, breadcrumbs at 3, does it exist? No, it's undefined. So then we're gonna push it to our result. And then we're going to cache it, or simply save that value into our object breadcrumbs.

[00:07:39] And so this is a way for us to remember and keep track of values that we've seen in the past. A couple hiccups, just like we saw the bug with, we forgot to cache the first one. There is also the problem of objects, the keys of an object are always a string.

[00:07:55] And so it might be wise to JSON.stringify a value before you save it as a key in an object. Otherwise, you can use a different data structure. If you're using ES6, you can use a map data structure, where the keys can have different values, not just a string.

[00:08:13] So those are a couple things to keep in mind with this technique. But this is just a cool way to speed up your algorithms from quadratic to linear, all right? So this is linear because we have a loop, this lookup is gonna be constant. This push is constant, this saving is constant, in terms of timing complexity.

[00:08:42] This is gonna be linear, however our sorting is a little bit more complex. And sorting we can think of as inlogging a general sense.