Rotate Arrays in Swift
Looking through common interview questions rotating arrays is very common.
There are multiple ways of doing so, no matter if the algorithm is in place or not which potentially adds another layer of complexity.
The problem — moving left by one position
We want to rotate an array
Ideas
Avoid using .remove as this is a O(n) operation.
Avoid using .append as Apple’s documentation states, this is O(1) average but can actually be as much as O(n).
We basically just want to change the location of each of the elements in the array in turn, and then put the (formerly) first element to the end of the array.
Implementation of left shift
As we move each element in the array backwards, we will of course wipe over the initial element.
To preserve this, we will store the first element in a temporary variable.
We then walk through the array (i from 0 to the number of elements — 1), replacing the current element arr[i] with the subsequent element arr[i + 1].
In Swift:
We can then call this rotate left function as many times as we want to (to move 2 to the left, we can call the function twice for example):
for i in 0..1{
rotateSingleLeft([“a”,”b”,”c”,”d”]
}
The problem here is that in the code, we are duplicating the whole array. Why? Can’t we do this in place
In place left shift
We will need to pass in an array of characters to the function that can actually be changed:
var inputArr : [Character] = [“a”,”b”,”c”,”d”]
rotateSingleLeft(&inputArr)
giving us the same results as before
The problem — moving right by one position
Which would give the implementation
We start at the first element, and replace it with the one previous to it (replace i with i-1)
Do you see the problem yet?
We need to be smarter. In order to pursue this strategy we need to move from the end of the array, in order to not wipe over the values that we want to keep.
Implementation of right shift (using reversed)
We can implement our algorithm, but back to front!
One again we can call this as many times as we wish.
Shift left using Array Slices
The logic here is a left shift of k moves the first k characters to the end of the array, and we can use Array Slice to do just that.
Implementation of left shift (using array slices)
It would be possible to write this in a single line, but at the expense of readability. In any case, this is still an in-place function.
Shift right using Array Slices
To rotate right, the only change we are making is to how many initialDigits there are at the beginning of the array. In fact we can make one change
Let initialDigits = chars.count-(k % chars.count)
A more general function
If we want to let negative integers suggest a left shift, and positive integers suggest a right shift we can do this simply (excuse the use of the ternary operator):
Can we make this work for other types rather than just characters?
Seems like a use for generics!
Since we are using arrays, there should be no difficulties here.
In any case, that is quite a large article on how to rotate arrays!
