Design a Dynamic Array (Resizable Array)

Key Takeaways

okay so let's design a dynamic array it feels weird coding this up on my own website so hopefully there aren't any bugs but let's get started a quick refresher is that a dynamic array is also known as a resizable array AKA like an array list in Java or a vector in C++ now Python and JavaScript already have resizable arrays by like default so we'll kind of be working around that and I also want to mention that this is a follow-up from the dynamic array lesson in the algorithms and data structures for beginners course so that's like the prerequisite to this now our Constructor is given some capacity it's our job to initialize an array and I'm just going to call it this for short with that much capacity and that means creating an array of that length even if we don't populate it so in Python we can do that like this with the uh capacity that is provided to us so if this value was four for example we'd have an array of four zeros now we're also actually going to save that capacity as well because it could be changing that's kind of the whole point of a resizable array and once we have that we've pretty much solved this function below down here the one called get capacity because if we're saving it as a variable all we have to do to get it is just return that member variable itself I keep misspelling this and right above that you can see we have another method to get the size getting size is the actual number of values inserted into the like array just because we have this much capacity doesn't mean we actually inserted anything yet so the length aka the size of the array is going to be zero initially so we should probably save that as a member variable as well and initially it's always going to be zero because we're not passing any values into the Constructor we're only passing in the capacity so now we've also kind of finished the get size method down here we'll just go ahead and return the size now for actually retrieving an element this is pretty much equivalent to like having an array and fetching the value at like the I index and for Simplicity in this problem we're going to assume that this index I is always going to be valid so this is actually going to be easy as well even though so far we haven't inserted anything yet we know this is only going to be called with a valid index so we can always just return self. array at indexi now right now if we were to call this when the size is this should actually throw an exception and we could theoretically have an if statement for that we could say if I is greater than or equal to self. size then maybe return Nega 1 or maybe throw some exception but we're not going to be doing that right now for inserting it's also going to be similar in that the index I is always going to be valid but this is the first time we're actually adding a value into the array if we were to try to do this again when the size is zero in theory it should throw an exception but right now we're going to assume index I is always valid and we would insert a value just like this at index I we're inserting the value n that's provided so so far so good now things are going to get a bit more tricky because when we push to the end of the array how do we know where that value is going you're probably used to using a method like this like push back or push to the end or whatever it's called in like your language of choice but where would that value actually go in our representation that we're doing well probably it would go at the array at the index of self. size because for example if we had an array that looks like this we only have one value inserted and the others are just zeroed out like this we would say the size of this array is one because we only have a single value so the next value is going to be inserted at index one that's the idea here and as soon as we add a value like that we're going to say our size is going to be incremented by one the reason we don't increment in the insert method is because in that case we're overwriting an existing value here we're actually adding to the length of the array but there's a catch what if we don't have enough capacity this would actually give us an index out of bounds error like what if like our capacity was four for example but now our size is also four this is going to give us an outof bounds error so we should check for that we should check that if the size is equal to the capacity in theory you could also say greater than or equal but that's never going to be the case it'll never be greater than the capacity that wouldn't really make sense so we check that if it's equal to the capacity before we do this operation we want to resize the array in this problem that means doubling the capacity of the array and here for some like we can keep it simple right now we can just say resize and call that a method but we know know that we do actually have to implement that below so let's go ahead and actually do that right now so initially up above you can see we had like this much capacity for the array so now we want to double it how can we do that well let's allocate a new array and I'll just call it exactly that new array is going to be zero times double the capacity and before I even do this let's just double the capacity we know that's what we're going to be doing that's the constraint of this problem that's the requirement of this problem so take this 2 * the capacity and now we can multiply the new array by this capacity in Python this just means we're creating an array of length this much I know the syntax is very different in other languages so once we create that array we don't want to get rid of the previous values so we should copy those values into this array so I'm going to do that now it's not super crazy we're just going to iterate through uh the index of our current length so self. size we want to go through every single value in the current array so self. array at indexi and we want to copy this value into the new array at index I so just like that and once we're done with that then we can probably uh just reassign self. array that's the whole point of the resize method to double the capacity of this array we've already doubled the capacity variable now let's update this so this is now going to be set to new array so what this function does is it doubles the space that we have to insert values so before in our push back we didn't have enough space to insert a new value after we resize it we will have that space so we can do that you can see that under the hood a dynamic array there's nothing super crazy going on just some like fundamentals like if statements and for Loops so it really pays off to really get a good understanding of the basics and now we only have a single method to Implement and that's pop back this one's not going to be super crazy because once again we're going to assume that pop back is always called in a valid way if that wasn't the case I mean I'll also show you how to code that up but this is an easy problem so I wanted to avoid too many edge cases but let's keep it simple so when we pop back we know that we're going to uh we're assuming it's always valid so we're going to decrement the length by one we called it the size so let's do that and we're going to return the element that we popped back so here we're going to return self. array at index of size you might be wondering why are we returning that one shouldn't we return size + one because we just decremented it no that's not the case because remember arrays start at index zero like if we had an array that looks like this 1 2 3 we know that the indexes are actually 0 1 2 and this array has a length of three so if we took 3 minus 1 we get to two and two is the value at the index that we just popped that's what we would return notice how this is actually not removing the element from the array so I guess this is sort of like a soft deletion there's no reason to delete the element there's no reason to overwrite it because that's kind of just being maintained by our size if we were to pop back and our size is already zero then theoretically we would do something like this say self. size if it's uh equal to zero already then maybe let's raise or throw an exception but in our case we're not going to be doing that so that's pretty much the entire code I'm going to quickly go over the time complexity for each one of these and I just noticed a typo over here I'm really really sorry about that so here we made a bonee head move and did not uh insert the actual value at that index so now the code is entirely correct so this is the entire code but I'm sure you can see it in the solution tab I'm going to go ahead and run it to make sure that it works and as you can see it does pass all of the test cases so let me quickly run through the time complexity for each approach I think it's pretty self-explanatory that get is going to be a constant time operation insert also is going to be a constant time operation we know that inserting and reading from an array is always constant time the Constructor I guess I'll go back to is actually going to be Big O of n where n is the capacity because we are allocating that much memory for our array we're only doing it once so that when we actually call get and insert they will be done efficiently but I'll make a comment so this is going to be Big O of n where n equals the capacity this one is going to be Big O of one this one is also Big O of one push back here you can see this part is definitely Big O of one but what about resizing we know that resizing we're going to have to double the capacity so we're pretty much calling the Constructor again we're doubling that and we know that within resize we have like a loop going over the size of the array and we're initializing an array with double the capacity so theoretically this is going to be Big O of n but how often do you think resize is going to execute well we talked about it in the dynamic arrays lesson and in the worst case yes this is going to be Big O of n but on average and that's the important part here average case is going to be Big O of one aka the am ized time complexity and that's exactly why we double the length of the array every time like maybe when we have to push back we only increase the array by one we only increase the capacity by one and we still have to run this for Loop that would not be big of one average time complexity going to pop back since we're doing a soft deletion this is pretty efficient as well this is a big O of one and resize is always going to be Big O of n but we're not going to be running this very often where n is going to be like the capacity of the array or the size of the array because they're always going to be proportional and get size here is going to be Big O of one and get capacity as well is always going to be Big O of one as well so I'll close things there