Noob v. Algorithms #22, playing with .pop(), .unshift() and .splice()
Browsing through the top interview questions in LeetCode, one of the harder easy questions is this one:
First solution: while loop using .pop() and .unshift()
Here’s how that works:
In this challenge, we want to perform the operation
k times. We could do it by setting up a while loop:
Let’s unpack that.
On line 2, we’re setting a counter with an initial value of zero. At the end of each loop (on line 5), we increment the counter by one.
On line 3, we’re saying: “while our counter is less than the number of times we’re supposed to perform the loop, go ahead and loop”.
Note: yes, i started the counter at zero, instead of one. If you want to start yours at 1, then in line 3, write
while i <= k instead of
while i < k.
This works, but is not that fast:
How can we speed this up? I decided to try .splice() instead of .pop() …
Second Solution: .splice() instead of .pop()
LeetCode performance times are not very consistent. When I first tried this solution, .splice() ran faster than .pop(); later it seemed the same.
When you remove an item from an array, the items after that have to move forward to take the missing item’s place in memory. Depending on how big the array is, this can slow down run-time. (Since all of an array’s elements must be ‘seated together’ in memory, the elements must be re-indexed every time the array is altered).
If you are always removing the last item in the array, there are no later items, so you can skip the re-indexing. By definition .pop() always removes only the last item. So it’s fast at what it does.
.splice() can target items anywhere in the array; so when it targets anything but the last item, it is slower.
.splice() takes two arguments.
- the index at which you want to start removing items. (Use -1, -2, to indicate last, second-to-last etc . indices of the array.)
- the number of items to remove. If no second argument is provided, slice will remove all elements starting with the provided index until the end of the array.
Here’s how .splice() works:
In our challenge, we can use it like so:
but … (sigh) … it ain’t faster:
Third solution: optimize for different scenarios.
So far, our code approaches by popping off one element at a time and appending it to the front of the array. It works the same way whether we have a short or long array; and whether we are supposed to pop off 1 item or 1 million items.
We can speed things up by optimizing for different scenarios. What if we have an array of 100 elements, and
k is 90? If we pop off last item and append it to the front of the array 90 times, we have to re-index the array …. 90 times. That’s a lot.
How about if we just splice() off the last
k items from the end, and add them to the front of the array as one block?
We could do that like so:
- we are using
-kto .splice() off the last
kitems of the array.
- nums.splice(-k) returns an array. To add the elements of that array to the start of nums (instead of the array itself) we use the spread operator:
Running the code as is:
does not work …
because it misses edge cases where the number of times we need to rotate,
k, is greater than the array’s length.
To handle the edge cases, we can add an if /else statement:
Notice that the else statement uses the code from our second solution!
And now our code runs way faster:
You can see the code execute live here, on PythonTutor.com
and you can play with it here on repl.it:
Copyright © Joan Indiana Lyness 2019