Today, while going through my regular routine of reading up on what’s new in Swift, I stumbled upon the problem of rotating an array by a given number of positions. This is something I haven’t done in Swift before, and it seemed like a good problem to brush up on my coding skills. Let’s have a look at how things played out.
Our goal is to write a function, which will rotate the contents of an array by the number of positions given as a parameter. On top of that, we would like to meet the following criteria:
- The running time of the algorithm should be linear (O(n)).
- The algorithm should use a constant amount of extra space, not counting the space used by the input array.
Let’s take a look at a simple example, that will better illustrate the problem we’re trying to solve. We will assume that the following array is our input and we want to rotate it by three positions:
[1, 2, 3, 4, 5]
The array we get, when the algorithm is finished, should look like this:
[3, 4, 5, 1, 2]
It is important to note, that the parameter representing the length of the rotation, can be larger than the size of the array and it can be lower than 0 (this indicates rotation in the opposite direction).
Before we get to coding
When solving algorithmic problems, it is always a good idea to do a few examples by hand and go through the whole algorithm in your head, instead of jumping straight into coding. This will help you find rules and dependencies that are easy to miss at first sight, as well as get the details of the algorithm right.
In the case of the array rotation problem, three things are worth noticing:
- Rotating the array by a number m, which is larger than the size of the array, is the same as rotating by m % arraySize
- Rotating the array by a negative number -m, is the same as rotating by arraySize – (m % arraySize)
- We should make sure that our algorithm works correctly for arrays with a even and odd number of elements.
Since we’re developing our algorithm in Swift and we’re dealing with arrays, it makes total sense write all the code as an extension on the Array type. Here is what it would look like:
The basic idea is to move each element in the array by the necessary number of positions (which is smaller than the size of the array), while avoiding indexing out of bounds with the help of the % operator. This leads to an algorithm that performs array rotation in place, while accomplishing the time and space complexity goals. Let’s discuss the most important lines:
- Line 5: Here we encode the rules that were discussed in the previous paragraph. They ensure that we never have to rotate the contents of the array by more than arraySize – 1.
- Line 7: It is necessary to check whether the array contains an even or odd number of elements. In case of arrays with an even number of elements, we use two smaller rotations starting from indexes 0 and 1 to avoid looping over the same elements twice.
- Line 15: The rotateFrom() method rotates a given number of elements, starting from position, and moving each element by stride positions.
The resulting algorithm performs at most arraySize rotations so its running time is O(n). It uses only a few extra variables to keep track of the elements that need to be moved, which means that the extra space required is constant – O(1).