Can a Web Developer Solve LeetCode?

In this video, I'm going to be going through some of the top interview 150 questions on leak code. This isn't going to be your standard leak code video. I don't know the answer beforehand. Everything I'm doing is entirely from scratch live to see if I can solve it. And also, I don't have a lot of data structures and algorithms experience. Most of my experience comes from building real world projects. So, I'm going to be taking my knowledge building real world projects and applying that to these different algorithms and showing you how some of these algorithms and the knowledge you can learn from them actually can be applied to real world projects. [Music] Welcome back to WebDev Simplified. My name is Kyle and my job is to simplify the web for you so you can start building your dream project sooner. And in this one, we're going to be taking a look at the remove element question first because it's a rather simple one to take a start with. So, we're going to be given an array of numbers and a value. And all we need to do is remove all instances of that value from our number array. And specifically, we need to do it in place, which means instead of returning a new array, we modify the array that we're working with. For this particular function, we also need to return a value, which is the number of elements in our array which are not equal to the value. So, essentially, we just return the length of our brand new array. That's all we're doing inside this function. They also specify we can change the array. And the important thing is we don't actually need to remove the bad elements from the array. Essentially, if our array is 1 2 3 4 and we need to remove the value of one, we could return an array that says 2 3 and four and that would be fine. Or we could return an array that says 2 3 4 and just put one at the very end. And that'll also work fine because they only look at the first few elements of your array based on the numbers that are not supposed to be there. So essentially, if your array is four values and you're supposed to remove one, it'll only look at the first three values of your array. So we can actually take advantage of that inside of our function if we want to. Other than that, the rest of this isn't really super important. So let's go ahead and actually start implementing what this function should look like. Now, the most naive approach to something like this would be taking your numbers and just looping through them. So we could do a simple for each loop for each one of our numbers. And then for each one of our numbers, we could remove it if it's equal to that value. So we could say if val is equal to num, well then we know that we need to remove it. So we could just come in here and say nums. remove. And of course, remove is actually not a function in JavaScript. So, we would need to use splice, which allows us to do essentially removing. Now, also, I don't really like coding in this leak code format because there's no autocomplete or anything. So, I'm going to do is I'm just going to copy my code over to a editor here. Let's just zoom this in so it's a little bit larger. And now we have some autocomplete we can use. And we can see if we take a look at this splice function, it essentially removes elements from array. We can tell it where we want to start and the number of elements we want to delete. So, we just need to get the index we're starting at. So, let's come in here. We're going to get the index just like that. Pass in i. Say we want to delete one element and this should delete one single element from our array at that index which is the element that we're trying to get rid of. Also, we would need to make sure we keep track of the number of elements that are correct inside of our array. So, we can just say inside of here, we'll call this K because that's what they actually call it inside the thing. We'll set it to zero to start. And then we would just need to increment that value. So, inside of here, I think I'll just do a little not equal. And we can just say k++ and we could do a simple return. Otherwise, we could remove that element. And then down here, we would return K. Now, you may think this is all you need to do to actually solve this problem, but this actually won't solve the problem quite like we expect. Let's come over and actually submit this as our leak code solution and see exactly what this looks like. We'll just click run to see what happens when we run it. And we should see that it won't actually quite work properly. So, we just got that to finish running. And if we look down here, you can see we're being passed 3 22. And we want to remove the element three. The expected output should be two and two. But ours actually gave an output of just two. If we look at case number two here again, we're missing some different elements. We have entirely wrong elements inside of our array that are being returned. The big reason for this is if we bring back our code, we're essentially looping through our array and we're modifying that array in place. And whenever you modify an array, as you're looping through it, it loops through essentially what the original version of your array was. But as you change your array, different things happen. So different elements are moved and jumped around. So essentially if we remove an element now when we try to access an element at a certain index it's going to be accessing a different element because we removed an element inside of our array. It just gets kind of messy what's going on inside your array. So doing it with this naive for each loop is not going to work because for example if I remove an element at index one well now the old element that was at index two is going to be at index one. So when I increment my count to two, instead of going to get the correct element, it's actually going to skip whatever element was next because I removed an element but still incremented my counter to go to the very next element. So you never want to modify an array in place, which is why this naive approach will not actually work as you expect it to. Now let's go back to our actual code inside of a better editor and think about a better way that we can actually approach this problem. First of all, generally when you're modifying arrays in place, it's better to use a standard for loop just because you have better access and control over what the iterator variable is going to be. So we're going to say let I equal zero. Then we want to increment or make I be less than or equal to nums.length. And then we'll increment i by one every single time. So essentially this is doing the exact same thing. We can move our code directly inside of here. But the nice thing about doing this is we now essentially have access to that I variable that we can modify however we want. Also, this should be changed to continue instead of return to make sure that works properly. There we go. And we don't have access to num yet. So, let's say const num is going to be equal to nums of i. There we go. And if I just fix my brackets here, we now essentially have the exact same thing. But we can modify this code a little bit. Now I know that if I'm removing an element from my array, I can just come in here and subtract one from I to kind of offset the fact that I'm increasing it every single time. So when I remove an element, also remove one from I to keep track of the fact that I removed an element. Now, I'm not 100% sure if this will solve all of our problems, but we can go ahead and actually just test this to see what the output is. This is really important when you're trying to run code, you're not really sure what's going to happen. Constantly testing your code, seeing what the output looks like is really important to understand what's going on. Now, if we look at here, you can see that actually both of our test cases have passed because we fixed that naive approach by making sure our index counter is always at the proper location. So, let's go ahead and actually submit that and see if that gives us the result that we want. And then I can take a look at an alternate approach that we could do as well. It looks like all of our different test cases passed, which is great. Now, I want to go ahead and look at that alternate approach that I was talking about. Because we don't actually care about what the other elements inside of our array are. For example, we don't care about the last few elements inside of our array. we can actually do some swapping around instead of just a straight deletion. And this may be better for certain use cases because you just want to keep your array exactly the same without modifying the length of it or anything. So instead, we're just going to swap elements instead. So here where we're doing a splice, we're actually going to be doing a swap. Now, this is actually really easy to do inside of JavaScript because the nice thing is that with splice, we can actually add on an additional parameter that allows us to pass new items in that'll be inserted at the place where we're deleting items. So essentially, we can swap one item with another item. This may not be the most performant though because it may delete the item, create a new array, and then add an item, which creates a new array. So instead of actually doing this deletion, and then insertion, all we're going to do is just take the item at this exact index, and set it to a brand new item, which is going to essentially be the last item in our array. So we're going to say nums of, and we want to get the very last item in our array. So what we can do is we can essentially take our k value and get that by removing it from our nums.length. So we can say nums.length minus one because that will give us the last element. And then we subtract K, which is essentially the number of items that we know we're keeping inside of our array. And actually, this won't quite work like I expect because K is actually the number of elements we're keeping and not the number of elements that we're removing. And I would want to essentially get the last element, swap it around, and then I would want to get the second to last element and swap it around and so on until we finally get to the last element inside of our array. So instead, I need to essentially keep track of a new ele value here, I can say items removed instead. We'll set that equal to zero and we'll subtract that value from here. And then I would just add on items removed and add one to it every single time. So now what I'm doing is I'm taking whatever element I want to remove, I'm putting it at the end of my list and I'm taking whatever is at the end of my list and putting it back inside this spot. So the list never changes size which could be better for certain performance because I'm never actually changing or recreating that array which could be costly on performance related stuff. And every time I move an element, I create essentially a counter to tell me, okay, I've already swapped the last element of my array, so I want to make sure I get the second to last and then the third to last and then the fourth to last. So every time I swap, I'm constantly getting one element inside from my array. So let's actually see if that will work like we expect it to. We can paste that in. We can give it a quick run and hopefully this actually runs successfully because essentially all we're doing instead of removing elements, we're just swapping them into our array. But of course, it looks like we are getting a little bit of a problem. So let's actually try to dive into our code. Whenever you run into problems like this, the best thing to do is step through your code step by step to see what could possibly be happening. So in our case, we have 3 2 3 and we want to remove the element three. So let's actually just go ahead and run through our code to see what it does on each individual line. We have 3 2 3 and we want to remove the element three. So the very first time we enter this, our array is going to be at 3 22 3 and the value is three. We're looping through. So i is going to be zero to start and our num value here is going to be three cuz that's the first value in our array. Obviously our value here three is equal to three. So we can completely skip this and we're moving on to this next section. So I'm taking my value at index zero which is three and I'm replacing it with whatever this value is right here. This is nums.length minus one minus my items removed which is zero. So that should be the last element in my array. So essentially I'm taking three and I'm putting it right here inside of my array overriding my current three. So that doesn't really change much because I'm just changing three to be three. But I am incrementing my items removed by one and I'm bringing my i back down to zero. And actually just by talking that through I already see the problem. The problem right here is since I'm not removing elements from my array, my nums.length actually never changes. So it stays the same length of four. So instead I actually need to subtract my items removed from here to compensate for the fact that I'm no longer removing them. So I just need to say, hey, all those items later on in my array, I don't care about them. Completely ignore them. That should actually fix my problem. So just me walking through step by step what my code did, I immediately saw what my problem was. So now we can give that a save. Let's copy over our code, paste it in here, and now that should actually solve the particular problem we are running into. And the nice thing with this is we have different performance characteristics because now we should hopefully be using less space. But of course, it looks like we still have a little bit of a problem. I believe that problem is simply due to the fact here that I should be using a minus one here or just less than instead of less than or equal to because essentially if I do less than or equal to, I'm going to be getting one extra value for my array than I actually want to. In the other case, it didn't matter because in JavaScript, if you try to get a value that's past the end of your array, it's just going to return undefined. It'll work. Other languages would throw an error, but I just messed up my symbol right here. So, let's actually copy paste that over and see if that actually works instead. So just a small mistake on my part which hopefully should be fixed as soon as we run this. And as you can see I don't do a lot of you know for loops normally inside my code. So I I do make these kinds of mistakes. Let's submit that. See if it works. And I think leak code has different ways you can compare the characteristics of your submitted code. Let's see it did submit. So we can hopefully take a look at the differences between these. So I was able to actually find where these different sections are. And as you can see we can compare these two different results. They have pretty much the same characteristics. The first one actually does slightly better on a memory performance characteristic. And probably the main reason for that is we define one less variable inside of this situation right here. And we're obviously removing elements from our array. So our array is constantly getting smaller. So there's the benefit in that particular use case. And if you can see the runtime here, it says 0 milliseconds. I don't know if there's a bug in the system or what it is, but it definitely takes longer than 0 milliseconds. In this newer version, you can see it takes slightly more memory than the other one. Again, that's pretty much entirely due to the fact we're creating a new variable and the fact that we're not actually removing elements from our array. We're keeping it the exact same length. But depending on what your actual use case is, either one of these are going to solve the problem for you. I would personally go with the very first one. When I was actually implementing this myself, I would just be removing the elements from the array. But if you need it to stay the same length for certain reasons, then you could do the other solution instead. Now, this next question is called remove duplicates from sorted array. This is the easy version. I'm only showing this because I want to show something that's really important about these data structures and algorithms is that they essentially make you write a lot of stuff from scratch that languages already give for you. In this one, we're going to be getting an integer array of numbers. They're sorted in a particular order, which for this particular case doesn't matter. And all we want to do is remove the duplicates. It says that we want to do it in place such that each unique element appears only once. Now, I'm going to show you a way to do this that's not in place before we jump to a harder version of this exact same question just to show you how there's built-in tools in the browser that make doing some of these things incredibly easy. For example, in JavaScript or TypeScript in our particular case, you can use a set. And a set is essentially just a way of creating an array of numbers or values or anything that does not have any duplicates. So if I pass in my number array right here and I get my new nums right here, this new nums array is essentially going to be the exact same array that I had inside of nums, but it's going to remove all the duplicates from it. And it's going to be an actual set value that I can use. And if I wanted to return this as a normal array, I could just say return. And I could take my new nums. There we go. and return them as an array just like this. And essentially what that's going to do is it's going to take this value that's as set and turn it into an array. This doesn't do any in place manipulation or anything like that. But as you can see in the browser and a lot of other languages, there's these tools built in that make some of these things already really easy for you. For example, I never need to write a quick sort algorithm because I can just use the dotsort function on any array inside of JavaScript and it'll do the sorting in the most efficient way possible for me. So understanding these built-in tools is honestly more important in a lot of cases, especially for real world apps, than understanding how to write the underlying algorithms. Now, with that said, I do want to look at a more complicated version of this problem that cannot be solved in that way that we just talked about. And essentially, it's the exact same thing. We're given an array of numbers that are sorted in a non-dereasing order, which is very important. And we want to remove some of the duplicates, but not all of them. And it must be done in place. Essentially, we want to make sure that there are never more than two of the same element inside of our array. And the order of the array must be kept the same. So essentially what I want to do if my array goes one, two, two, two, three, four, five, I would remove one of those two values because I can never have more than two of the same value. In our case, I had three twos. So I would need to remove one so that I now only have two twos instead of three. Now there's a lot of different ways to solve this particular problem, but there's one key ingredient here, and it says do not allocate extra space for another array. You must do this by modifying the input array in place and using an 01 of extra memory. Essentially, that means that if I have an array of 10 different elements, I can't just create a brand new array to keep track of all the duplicates and then use that for my removal. I have to essentially not add any additional memory unless it's really small amounts of memory, like an individual counter or something like that. So, this may seem like a simple problem, but this extra caveat right here adds a little bit of extra complexity. So, let's go ahead. We're going to take this code. We're going to copy it into a real code editor so we can actually work with it. and we want to start brainstorming how we would go about solving this particular problem. Now, the naive approach would be essentially to create a separate list of elements and keep track of how many times each list shows up. So, every time a two shows up, I increment it by one. And if my count is two or greater, I just start removing twos. But since I can't allocate extra space, that doesn't work. So, when you're thinking about these more complicated problems, the thing to look for is the clues they give you inside of the question itself. If we go back over to the question, the really important part here is that it gives you an array that is sorted in nondereasing order. If they give you these specific keys where they say it's sorted in a particular order, there's something in particular about how the elements are laid out, that is almost always going to be a clue to how you actually answer this problem. So, we can look at the fact that they're sorted in a specific order, and that should clue us into actually how we solve this particular problem. Now, I want to jump over to a diagramming tool to kind of help you explain exactly what I'm seeing in this particular problem. So, let's say that we have an array of particular elements. So, we have an array that has a value of one. Then, we're going to say that the array has a value of two. Let's just copy this down. three. Copy this down again. Four. Let's say it's got another four. Another four. And let's actually say this one's a three here. Oops. Three. There we go. So, we essentially have 1 2 3 3 4 4. The final version of this array should essentially just keep these elements. These are the elements that we want to keep because these are the non double duplicated. So, all these have two or less of their value and we remove the extra number four that at the end right here. So, the way that I see this to keep track of it is our array is always ordered in a non-dereasing value. Which means if we have multiple of the same number, they're always going to show up right next to each other in the array. So, we can keep track of what our current element is, what the next element is, as well as what the element after that is. And that makes it really easy for us to do our different removal tasks. So, let's say that we start looping through our array and we're going to start at this very first value of one right here. What I can do is I can then look at the next element as well as the element after that. And if both of these elements are one, well then I remove this first element right here. Otherwise, if they're not both one, then I know that I don't have two or more ones. I essentially have one or two ones and no more than that. So I can say, okay, one's fine. So I can completely remove this and move on. Now I'm going to check two and essentially I'm going to check the next two elements. If both of these are not two, well, I'm good to go and I can move on to the very next one. So now in this case, I'm on three and I'm checking my three and my four and I can say, oh, I have one three, but I don't have a second three. So again, I'm good to go. And this continues on and on until I get to this final element here, which is going to be four and four. So now I'm checking four. This is the element that I'm currently on right now. And I'm checking it against this four. And I'm checking it against this four. And I notice that both of these are the exact same number. So what I do is I just remove one of these fours completely from my array. And now I'm good to go. I'm moving on to checking the next element and the next element and so on until I get to the very end of my list. So that's what I want to implement inside of our code. So let's go ahead and do exactly that. So we need to do our simple for loop. So we can say let I that's going to be equal to zero. I is going to be less than or equal to and actually less than nums.length. And then we can increment i by one. And immediately there's actually one small optimization we can do here. We technically don't need to check the last two elements of our array because if the last two elements of our array are the same number, that's okay because we already checked the element before that. So we can actually skip the last two elements of our array. So, we're just going to come in here with a minus two to skip those last two elements of our array. Just a small optimization that we can do. Now, I forgot what we were supposed to actually return from this function. So, I'm just going to read real quick. If there are k elements after removing the duplicates, we essentially, okay, we return essentially how many numbers there are inside of our array. So, that makes sense. So, we're just keeping track of how many numbers we keep inside that k value. Now, technically, we don't even need to create a k variable because we can just return our array length once we're done actually iterating through everything inside of our array. So the very first thing we need to do is we need to get num which is just going to be nums of i. That's the value that we're currently checking right now. And then we need to get the next two values after that inside of our array to check if those are the same value. So we can have a little simple check here. If num is equal to nums of i + 1 and make this a little easier to read, our num is equal to nums of i + 2. Well, that means that the current element, the next element, and the element after that are all exactly the same. We need to remove one of these elements. So, we can go ahead and we can just do a simple spice. So, we can say splice, we want to remove at the index of i and we want to remove one single element and we want to subtract one from i. We can actually clean this up memory-wise a little bit by instead of creating a variable just doing this by directly accessing our array. Personally, if I was writing this code in a real world project, I would create a variable. Makes the code much easier to read. I would even probably create variables for both of these potentially how my code looks. But in this case, since we're really trying to optimize for memory and performance, we're not going to create any additional arrays values than we need to. So that should be all we need to do down here. We can just return nums.length to actually get the length of the number of values we're keeping inside of our array. And that should be everything to solve this problem. Let's see if this actually works. I'm a little skeptical. I probably missed something or messed something up. But we can just do a quick run and then we can compare against those actual test cases, which is a great way to figure out, okay, are we right or wrong? In our case, it looks like we did get everything right. So, let's actually submit this and then see how we did on all the different time performance scales cuz that's really what we're trying to work on. So, there we go. Let's click this button to view the different details. And we can see here that this evaluated in 138 milliseconds, which is pretty much at the bottom of the pack. So, there's definitely some improvement we can do there. And you can see for memory performance, we actually did quite well. We're all the way up here in the memory performance. So, we're slightly above average for memory. Now, if we quickly bring back our code, one thing that I immediately think of is that we're currently doing more checks than we actually need to. We're currently checking the next element as well as the next next element when we're doing our checking. But since we know that these arrays are always sorted in this proper order that we're expecting them to be in, we can kind of skip checking the next element. Because if we have an array that goes, for example, 1 2 3 3 4 4, whatever it is, it doesn't matter. You can see when we're checking this value three here, we can essentially ignore the second three and immediately just check the third three to see if it's there. Because if this third three is here, we already know that the second three is also here. So it saves us a little bit of checking. So this very first check, we can actually completely remove from our array. And we should hopefully see that we get some better performance from doing this particular check. So let's move this back over. Let's go ahead and submit our brand new code inside of here. We're going to submit that. Hopefully, we can see we get a little bit better performance because we're essentially doing half the number of checks that we were doing before. Let's view these details. And you can see that now we're a slightly better. We're in the top 15 or the bottom 15% essentially. So, we're slightly better than we were before. And we actually did quite a bit better on memory in this one because again, we're not allocating a bunch of different resources. I think pretty much the only way we can improve our performance further is by swapping how we do this algorithm essentially just like we did be to the previous one where we're actually keeping track of what items we're removing and so on and actually not modifying the length of our array but instead just swapping around which elements were where. So we don't even need to do the whole swapping thing I was doing in the last one. That was kind of a red herring. I don't know why I actually decided to do that. Instead, all we need to do is just overwrite the value inside the array at the index that we're currently at. So what we're going to do is we're actually going to keep track of all the values that we're keeping. We're going to put that in that K variable. By default, we're actually going to set this to two because instead of skipping the last two elements in our array, I'm actually going to start on the third element in our array. That means that the first two elements are always going to be the same. We know we're never going to change those elements because there's no way that they could have that many duplicates. We only need to start removing from the third element onwards. And then inside of here, we essentially need to completely rewrite this to not use the splice function because that's more performant inacting because it needs to remove an element and then move the elements in your array to fill in the empty space. Instead, what we want to do is essentially just create a new array by overwriting all the values inside of our array that we don't need. So, what we can do is we can do a little bit of a check here and we can essentially check to see if the element two previous to our current element since now we're essentially doing our thing backwards by starting on the third element, we need to check backwards instead of checking forward. So what we want to do is we can say if nums of i is equal to the nums of i minus 2 that allows us to say okay we now have a duplicate inside of our array. So we essentially want to completely ignore this if it's a duplicate. So instead what we're going to do is we're going to check if these are not equal. If they're not equal then that means that what we need to do is actually save this value because this is not a duplicate value. We can keep this value inside of our array. So what we're going to do is we're going to take our nums at the index of K and we're going to replace it with whatever is at the index of I. Then finally what we're going to do is we're just going to increment K by one. There we go. And what we're doing here essentially if I just rename this to let instead of const is we're now creating a brand new array of our values. And we're essentially just taking our current array. We're just looping through it. And as soon as we find something that's not duplicated, we save that in our brand new array which is using this value K. And every time we find a duplicate, we're essentially skipping over that by not incrementing K. So K kind of stays earlier inside of our array, pointing at an earlier element. I'll actually use my diagram to show you. Let's just pull this back over and we'll bring up our diagram. So now instead of starting with the first element, we're actually starting with the third element. So we're starting right here and we're looking two backwards at the element back here. And we also have this value of K, which by default is going to start out at two just like this because we know we're skipping this element and this element. So essentially our k value starts right here at two. So what we're doing is we're looking at this element and we say you know what those are not the same. So what we're going to do is we're just going to skip this completely and we're going to increment this by 1 2 3. Now we're looking here and we're looking here and again they're different. So we're going to increment this up to four. So now essentially it's at this particular point. So now we're looking here and we are looking here and I need to add a few more elements into our array. There we go. You can see again they're not the same. So we're going to increment this again. Move it over. looking here and here and so on. We're going to keep doing that until finally we get to this instance. Our value here is currently six. Just like that. And you're going to see that these two values are actually the same. So now we essentially need to completely get rid of this element and not save it inside of our array. So instead of incrementing K, we're actually not going to be incrementing K in this particular instance. So K will only point to these elements instead of this element as well. It's a little bit easier to see this if we actually have this in the middle of our array. So let's come in here. We're going to change this back to two. And we're going to start right here where we are doing our searching. You can see they're not the same. We increment by one. So this moves here. This moves and this moves. And we'll increment it again because again those are not the same. So this is now going to be equal to four. Just like that. And you'll see that these values are the same. So instead of incrementing K, we leave that at four. And instead we move these pointers one down again. And you'll see that now these two are different. So I take the value in this place and I overwrite my value where K is, which is at four. I now change this to five. again do my exact same check and this is should be checking against here and in this case these numbers are the same but that shouldn't really matter too much I think if we just go ahead and we actually run our code so let's come over to here we want to go back to the page that we were on to be able to run our code I'm just going to take our code copy what we had bring it down to here and hopefully this should work I know my explanation maybe wasn't perfect at understanding exactly what's going on but we should hopefully see this works and if it doesn't we can make some different modifications looks like actually we do have some errors inside of our code and that's most likely probably due to that problem that I was running into here where these two numbers are the same. So there's something in my code that I need to modify slightly. So let's go ahead and look back at our code again. And first of all, we're returning the wrong value down here. This should return K because we're supposed to return the number of values in our array. And since we're not removing values from our array, obviously that fixes that problem, but that wasn't the problem our code was running into. I think I know what the problem was, though. When we looked at that diagram, you noticed essentially when we overwrite the element at K and we pointed at it now again by basing off of I, we're pointing at the wrong number. But instead, I think we should be basing this off of K minus 2 because K is like the new values inside of our array while I is our old array. So essentially, if we go back to our diagram, we'll bring this over and back to our diagram. Instead, we would be looking at whatever this value is minus 2, which would be three right here. So that's a better way of actually looking at what our array should be because essentially the value that we are comparing against is here even though we're looking at the old array at this value in that particular case. So essentially we just need to base it off of K because that'll give us the real value inside of our actual new array that we're creating. And hopefully that'll work. I'm just going to copy over our code that we have. I'm going to paste it down here and see if that small change actually fixes our potential problem. Returning K here. And then obviously making sure we index off the right place. We'll give that a quick submit. We won't even bother running. I'm feeling really confident about this one. That's usually never a great sign, but actually it looks like it worked this time. And if we view the details, hopefully we can see actually now we are ahead of the average on this particular case, which is quite amazing. And if we look over here, you can see our memory performance is not as good. That's perfectly okay. That's not really what we're worried about. I think runtime performance is generally more important unless you're specifically going for a memory based problem that you really need to want to focus on the memory. But overall, I'm actually really proud we were able to go from essentially the very bottom of the barrel all the way to in the very top echelons just by iteratively approaching our code and changing it as we go. Now, there's one more problem that I want to look at. This one is a medium difficulty problem, and again, it's something that you can use built-in tools to do essentially instantaneously, or you could write out your own custom implementation to really test how it works. So, in this one, we have implement randomize set, which is a class that essentially allows us to insert a value, and it'll insert it unless it already exists, just like a set. It only allows non-duplicates. It'll remove a value if it is already in there to remove and then we can just get a random value which returns a completely random value from our array and it should have equal probability of returning any of the elements in our array. And again importantly this must be an 01 time complexity. So that means essentially every time you look up a value from your set or get a value or remove a value from your set, it must happen essentially instantaneously. You can't loop through your array to get the value. It just must be an instantaneous get the value from the array. So let's go grab the starting code for this particular problem. bring it over into our real editor here and we'll get rid of the comments at the bottom. We don't really need these. And the big thing that you could do if you want to really just not care about actually implementing this is again you could use a set. So we could just say this set equals new set just like that. And here we could just say set dot and actually it's this set dot and let's make sure up here we say that we have set is going to be a set and I believe this has numbers being passed in. There we go. So we have a number set. And now what we can do inside of here is we can just add a number. And I believe this actually returns to us. It doesn't return to us a boolean properly. So that would be a little bit of a problem. This is called vow here. So we need to make sure we return our boolean. But we could do this essentially. Let me see. This is going to be delete to remove the particular value. And then for get random we could just say this set dot. We would want to get the values which would essentially give us all the different items in the array. And then we could say this dot set dot size. That'll give us the actual size. and we can create essentially a random value between the size clamp that value and do it that way and that would work fine but that kind of defeats the whole purpose of actually implementing this particular problem. So instead of using a set like this I'm actually going to essentially create our very own set that has that time complexity that we're looking for. So let's get rid of all the code that we have here for the set and instead of creating a set I'm going to create my own set. We'll call it set but we're not going to actually use a set behind the scenes and this set is just going to be a JavaScript object. And this JavaScript object is going to be a record that has a number as a value or as a key and a boolean as the actual value. It doesn't really matter what this is, if it's a boolean or anything. We're just really caring about what the number is inside of this thing. And this boolean is just there to say that that thing actually exists at that particular point. So by default, we have a completely empty set. And when we want to insert a value into our set, all we're going to do is say this set. And whatever that value is, we're just going to set to the value of true. So we're just essentially inserting at that particular value inside of our array. And it's actually not even an array. We're just using an object, which in this case is acting like a dictionary or a map where we're just mapping from one value to another value. And actually, if we wanted, we could use the built-in map type inside of JavaScript, which would probably even be better in this case. So, I'm going to do number and I'm going to come in here with a boolean because this map is just kind of a better way of doing this particular thing because it has all the operations that we want. So, here I can say this set and if we want to add something to this, we should just be able to say set. There we go. value and true. But first of all, this returns a boolean if that thing already exists. Actually, it returns a boolean of true if it does not exist and false if it does exist. So we can say if this set has our val, then we can just go ahead and we can return false because it already has that value. Otherwise, we can return true down here because it does not have that specific value. Now, if we did this not using a map, instead all you would do is just replace this with square brackets here. And you would replace this with square brackets here and set that equal to whatever value you want. That would be how you would do it without a map. But a map is really specifically meant for dictionary types. And since we're doing this as a dictionary, I'm going to do that. So now we can move on to remove, which is going to be very similar. So we can say that if the set already has the value or actually in this case, if it does not have the value, return false. Otherwise, we want to delete it. So we'll say delete that specific value from here. And then we return true. So remove insert that's already done and this should be 01 time complexity because you can see we're not looping or doing any loops. We're just getting a specific value or setting a specific value at an index. Now the final thing is to get a specific random value from here. So we can say this set and we have that size variable again that allows us to just get essentially that random index. So we can say index is equal to and we want to get the size here. We want to do minus one on the size specifically. And then we want to get a random version of that. So we can use math.random. There we go. That's going to give us a value between zero and one. We just want to multiply by essentially this value over here on the right. But this math.random technically returns a value between 0 and one, but it can never return one. It's impossible for it to return one. N99999999 is the largest value we can get. So instead of minusing one here, we actually can just use this set size because it can never return one, which means we can never actually return the set size. It'll always be slightly less than our set size. Now this will be a decimal. So we need to convert this to an actual number. We're going to use floor to make sure we always round down because if we round up then we could accidentally return our set size and it would be impossible to return zero. So by rounding down we essentially get a random value between whatever our smallest number is which is zero all the way up to our maximum element inside of our array. Then what we can do is we can come in here and we can actually get that from our set. So we can say this set and we want to get based on an index. So the best way for us to do that is just come in here with values and we want to get some value at a specific index just like that. And actually we don't want the value we want the keys instead. Now keys returns to us an iterator. So we actually need to convert that to an array. So we can just say that we want a new array of those values. And actually I think an easier way to do that would just be array from. I think that actually will do the exact same thing. Looks like not we'll have to do new array. And then we can use index here specifically. And actually I think yeah array.f from should work in that case. So we'll say array from. There we go. That'll essentially give us that new value and we can just return that specific value. So hopefully that'll actually do what we want it to. I don't actually have hopes that it'll be the most performant. I think actually using a map was a mistake in this particular case just because the fact it returns an iterator which adds some extra array related stuff that we had to do here. So I think doing it with objects may be the better case. But you can see it is actually returning our correct data. Let's make sure we do a submission up here to check our performance stats because like I said, I don't think this is going to be super great and we'll probably have to change over to an object. Let's just make sure we get rid of those warnings. Go over to this view detail here. And you can see here we're actually not doing too bad. We're in the top 25%. And for memory, we're, you know, not doing terrible. We're actually up here in the top 80%. Actually, I was wrong. We're in the bottom 25% for this solution. I was incorrect. I was looking at this chart, not looking at the actual number up here. So, we definitely have some room to improve. I think the first place we can try to improve is instead of using a map, let's just go ahead and use an object and see if that makes a difference for us. So this is going to be a record that is going to be a number and a boolean just like that. And then down here, we can just replace that with that square brackets like I was talking about. And same thing here, we can say square brackets is going to be equal to that value. Return that true down here. Same thing right here. Replace this with square brackets. And same thing here. We want to replace this with square brackets. And technically we can just put delete at the front here and that'll delete that value. That's something that a lot of people don't know about JavaScript. You can use delete to delete things from an actual array or or an object, sorry. Or we could just, you know, set it to undefined as well. But in our case, we'll just use delete. That works fine. Now down here, we can make this a little bit easier because we can say const entries equals object dot. In our case, we just care about the keys. So we're going to get our keys. So we'll say that's our items. And then we can say this items right here. And we can do that exact same. Math.f floor math.random times our items.length or size. Of course, I had to pass my object in here. That's why I was getting some errors there. There we go. So, we can say items.length. Just like that. Return that particular value. We don't need our array. Or anything like that. It's just items. There we go. And actually, there's a small problem that keys only returns the stringbased keys. I don't know. It should actually return our numbers here. We can probably just do like parse int and that should be fine. I don't really like doing that. That'll definitely hurt our time complexity. It'll make it quite a bit slower. Not really our time complexity, but our performance will be hit by that. So, let's see if this works or if I need to make some slight adjustments to it. One immediate thing I see that we can make as an adjustment is actually instead of storing true and false here, we can actually return our number. This does work. So, let's actually just submit this, see what our performance looks like in this particular instance, and then we can go ahead and actually try to make more improvements if we need to. So let's view that analysis and you can now see here we are actually much worse in both memory and we are much worse in runtime. So it's definitely some improvements we can make. One improvement we can make which is not really something I wanted to do because it added extra overhead for space that we're storing is we can actually keep track of two separate things. The first one can be this record right here or it could be a map. It doesn't really matter. We can use a map because it's kind of what maps are meant for. So, we're kind of going back to what we had before and instead of storing a boolean here, we're actually going to store a separate number. And then we're going to have an array, which is going to be all of our different items, which is just going to be a number array. And essentially, our map is going to store the index in the array where we store that particular value. So here, instead of setting this equal to true, we're going to set it to whatever our array inside this items is, whatever that index for that is. So, we can say this items is equal to an empty array and this set is a new map. Just like that. Now down here when we're inserting a value, what I want to do is I want to take this items and I want to push in what that new item is. Just like th