Array Rotation — Programming Interview Problem (II.)

(this article was originally written for my blog vojtastavik.com)

Today, we’re going to focus on another famous programming interview problem — Array rotation. We start with a simple “obvious” solution and move to a more optimized and interesting one afterward.

The problem: Rotate an array of n elements to the right by k steps. For example, with n = 6 and k = 3, the array [1,2,3,4,5,6] is rotated to [4,5,6,1,2,3].

Edge cases

Let’s start by thinking about possible edge cases that can happen:

n == 1 - The array has only one element. Any number of the array rotations will always result to the identical array.

n == 0 - Similar situation as above. When the array is empty, rotations don’t affect it.

k == 0 - Rotate an array by “0” steps to the right does nothing to the array. The resulting array is identical to the input array.

k < 0 - What if k is negative? To rotate an array by -1 steps to the right means to rotate it by 1 step to the left. Let’s say we have an array with 3 elements [1,2,3]. When we rotate it by one step to the left we get [2,3,1]. You can notice that we get the same result if we rotate the array by 2 steps to the right. We can easily transform left rotation to right rotation using stepsToRight = arrayLength - stepsToLeft. Because we know k is already negative we should rather use stepsToRight = arrayLength + stepsToLeft.

abs(k) > n - Imagine we should rotate an array of 2 elements by 3 steps to the right. After two steps, the array will be identical to the original array. It means that when the array is rotated by 3 steps, it’s effectively rotated just by 1 step. What if we were to rotate the array by 5 steps? After 2 rotations, we would get the identical array and 3 rotations to go. Again, we would rotate the array effectively just by 1 step. It means that:

effectiveRotations = rotations % numberOfElementsInTheArray
                 1 = 5         % 2
 
// We can generalize this into:
effectiveRotations = k % n

We transform these edge cases to code:

The “obvious” solution

Let’s try to make the problem a little bit simpler. What does it really mean to rotate an array by one step to the right? It means to remove the last element of the array and insert it at the beginning.

original:
    [ 1 , 2 , 3 , 4 , 5 , 6 ]

remove last:
    [ 1 , 2 , 3 , 4 , 5 ] 6

insert it as the first element:
    [ 6 , 1 , 2 , 3 , 4 , 5 ]

Converted into code:

At this moment, we know how to rotate the array to the right by one step. If we want to rotate the array by more than one step, we simply run the similar algorithm multiple times and we’re done:

What is the time complexity of this solution? For every step, we need to move all elements in the array. The worst case time complexity is O(n*k).

The “better” solution

When k is small, the O(n*k) time complexity of the previous solution isn’t that bad. However, when k is getting close to n, O(n*k) is almost becoming O(n2). Let’s see if we can do better.

Swift Array offers the reverse() function which can reverse the order of the elements in the array. The algorithm we’re going to use can rotate the array by any number of steps only using this function. All we need are these 3 steps:

Original array                1 2 3 4 5 6
n = 6, k = 3

1. Reverse the whole array    6 5 4 3 2 1
2. Reverse first k numbers    4 5 6 3 2 1
3. Reverse last n-k numbers   4 5 6 1 2 3

Converting these steps to Swift is pretty straightforward:

Let’s find the time complexity of this algorithm. The func reversed() -> Arrayfunction has complexity O(n). We use the function three times so the complexity is O(3n). Constants can be omitted so the final time complexity is O(n) 🎉.

Next time, we will invert some binary trees. Stay tuned.