How to solve HackerRank’s “Left rotation” array challenge (Javascript)
Step by step explanation of how you can use the greedy algorithm to solve this challenge. I would recommend to go and check the details of this problem and try to solve it yourself in any programing language or just pseudocode.
It states that if you have an array of x length e.g. a [1, 2, 3, 4, 5] and the number of rotations d is 2, you need to write a function to perform a left rotation d on the array a. Imagine this array as a queue of people and you want 2 persons 1, 2 from the front of the row and move them to the end to get the resultant array [3, 4, 5, 1, 2]. Simple!
It looks quite straight forward so let's list the steps involved in solving this problem.
- Loop through array d times and in the first iteration, the value of d is 1.
- Pull out the first element from the array, which is 1, and append it to the array a
- The new array becomes [2, 3, 4, 5, 1]
- The value of d in the next iteration is 2
- Pull out the first element from the array, which is 2, and append it to the array a
- The new array becomes [3, 4, 5, 1, 2]
- The iteration finishes and we have the final result [3, 4, 5, 1, 2] to return
By the look of it, we have described this solution in the big O notation as O of d or O(d)
Let’s write a simple function to implement this algorithm:
Or you can use the simpler version with a while loop:
The push function is used to append a value to the array and shift to pull out the first item from the copy array.
Ran all the tests on hackerrank.com and all tests passed.
Great! but I was thinking of different test cases. Let’s say we have this same array with a length of 5 and this time the value of d is 5 so with O(d) we will loop through 5 times and at the end the result will be exactly the same as the original array [1, 2, 3, 4, 5]. That’s a waste of 5 iterations and we could just return the original array which would have been super fast. Great! To achieve this let's add a single line at the top of our function:
Ok moving on, what if the value of d is 10? Iterate 5 times to get the same result and then 5 times again to get the same result again as the original array. Same stands for 10, 15, 20… if you notice the pattern is that if the length of the array a is a multiple of d, we don’t need to do anything and just return the original array a. With JavaScript remainder operator % we can improve our code with this check.
With this code even if the value of d is 100000… as long as the remainder is 0, our big O notation expression will be O(1).
Next, let's take another big value of d for which the remainder is not 0 e.g. 12
This means that we can avoid 5 +5 = 10 iterations and just pull out first 2 people and place them at the end of the queue to get [3, 4, 5, 1, 2]
We need to find a way to remove all unnecessary iterations and just find the minimum number of moves to get the result. In this case only 2.
How did we get this number 2?
2 is a remainder of 12 % 5 therefore with this formula, we will never iterate one person/number twice. In this case, the new value of d becomes 2. Let’s update our previous code to achieve this:
On line #2 above, our value of d will always be less than the length of an array a. On line #4 we check the value of d, which will be the value of the remainder. Now let’s go through some examples in our mind
if array.length is 5
- and value of d is 0, the remainder will be 0 so 0 iterations
- and value of d is 4, the remainder will be 4 so 4 iterations
- and value of d is 5, the remainder will be 0 so 0 iterations
- and value of d is 6, the remainder will be 1 so 1 iteration
- and value of d is 12, the remainder will be 2 so 2 iterations
- and value of d is 3888886, the remainder will be 1 so only 1 iteration
That's a big improvement. Instead of 3888886 iterations, we iterated just once.
So now we have learned that the value of d will always be less than the length of the array a
Following the concept of the greedy algorithm, how can we improve this algorithm a bit more?
Keeping the same short and easy to understand example, the value of array a is [1, 2, 3, 4, 5] and this time the value of d is 3.
Based on our previous optimized algorithm we need to iterate 3 times. Let's draw this.
We moved person 1, then 2 and finally 3 to get the result [4, 5, 1, 2, 3]
If you compare it with the original array [1, 2, 3, 4, 5] it looks like we have moved 4 and 5 to the front of the queue/array. We could just iterate 2 times from the back of the array/queue to the front.
Here the difference is of just 1 iteration, however, this difference will increase with the increase in the value of d. Even for such a small array if the value of d is 4, we can move 5 from the back to the front of the array/queue which will reduce it by 2 iterations.
Hence, we can divide the length of the array into 2 halves e.g. 5/2=2.5 and check it against the value of d, e.g. 3. If the value of d is greater, then move the elements from the end of the array to the front, otherwise move elements from the front to the back of the array.
In this case, 3 (and 4) is bigger than 2.5 so we can start pulling out from the end and push/prepend to the front of queue/array. Updated sketches:
Ok so let's update our previous code to achieve this
unshift is used to prepend an item to the front of an array in Javascript and pop removes the last item from an array (it mutates the original array). Therefore in the above code, copy.pop() removes the element from the original array and pass it to unshift, which then adds it back to the original array but at the front.
Looks good. Excellent. Just 2 iterations instead of 3. Awesome (a little pat on my own shoulder)
Still feeling greedy? Me too! I don’t like these 2 iterations. What else can we do to improve this algorithm? Let’s say we have an array of 10 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and the value of d is 5.
Hmm… I can see that I don’t need to iterate at all in this case. I know that the value of d is exactly half of the length of the array which means that I can just move the first half of the array to the end or move the second half to the front of the array without iterating d times and will get the same result.
Therefore, we need to check if array.length/2 is equal to d. If it is, then pull out half of the array and append it to the end and return the new array.
splice is a function used to take the starting and end index/position of an array and return that slice of the array, in this case, it will slice [1, 2, 3, 4, 5]
Importantly it mutates the original array (unlike slice) and removes these sliced values from the original array. So it removes 1, 2, 3, 4, 5 from the array a and original array became [6, 7, 8, 9, 10]
concat as the name indicates, concat one array to another. So the original array was [6, 7, 8, 9, 10] and [1, 2, 3, 4, 5] was the concatenation of these 2 arrays returned [6, 7, 8, 9, 10, 1, 2, 3, 4, 5].
So our algorithm now is a bit more improved but we can move half of items/people from the queue and move them to the end in just one go
Now, what? can we improve this algorithm a bit more? Absolutely!
We noticed 2 things. First, we have improved the value of d to become always less than the length of the array and second that we can pull out x items from the original array and append all at once with splice/concat functions and that's totally safe because as I mentioned, the value of d is less than the length of the original array. So why just use splice/concat when we can move half of the array? Why not for any number of d?
e.g. if the value of d is 3 with the previous array of 10 items. We can simply pull out the first 3 items and append it to the end. What if the value of d is 11? well it will never happen. with d = d % a.length 11 will become 1 and of course, if d is 10 we have converted that with this condition if (d % a.length === 0) return a; so we are good and can we turn our algorithm from O(d) to just O(1).
Let's do this:
All tests still passing with a variety of different combinations of array a and a number d
I would love to know if you can find a way to optimize this algorism to run even faster or if you have an entirely different solution.
Thanks for reading!
