Rotate an Array in place

The interesting things that you would face during Interviews are mostly in the form of puzzles and challenges. These are meant to not tickle your brain but instead it can stump you. On top of that, if you really give it a thought, some of these questions or scenarios are based off bad architecture and structures. There are possibilities that you would never ever get the change to use any of these but then again, you might just…who knows. In this article we shall look at the simple way to rotate an array in place. So if you had an array of numbers like so, [1, 2, 3, 4, 5, 6, 7] and you wanted to rotate 3 elements, you would be left with [4, 5, 6, 7, 1, 2, 3].
The first thing that comes to mind with Swift is to simply use swift functions to achieve the outcome.

First Go

The first go is to use inbuilt swift function and methodologies. Swift has some amazing functions to get array slices and ranges. You can access the arrays with passing a range, which returns a slice. So arr[iStart..<iEnd] returns a slice from the array that has a range from iStart upto iEnd

Swift has quite a few functions in-built that help you in reversing arrays, they are the simple methods called reverse() and reversed() . Where reverse() does an in-place reverse and reversed() returns a new reversed array.

I recollect this person that was discussing this with me have his jaw fall open and say, “NO!!, that is too easy, can it be done without using any functions”. Well there can be but the question is why would you want to be McGyver and do everything from scratch if you already have it provided to you.

Second Attempt

Ok, point taken, the array might be a large array and working with the slices creates a new array, so while the complexity might be low, it is creating a non-memory efficient solution. The person went on to explain, what if the array was a large array with like 4MB worth of data. I looked at him straight, first for dissing the functionality that was already available in a language, next for even suggesting such an absurd situation. I can understand that it is memory inefficient, but if it was a large array of 4MB, this is definitely not the way I would approach this problem. I would architect a more efficient way to deal with things. Worse case, say it was not possible because it was image data or something like that, why would I want to rotate an array. It didn’t make sense, however, the problem remained to be solved.

The way to solve that is by reversing, and it is quite simple because at the end it achieves what you were after.

Look at the graphic, it outlines the whole article in an image form.
First, let us write the reverse function, and also note that we need to get it to work with in-memory swap, which means we cannot allocate new memory for the array.

a side note on that first.
When we want to swap two numbers, we can do that by using a third temporary variable like so

and done, we have swapped the values of a and b

With Swift and using tuples, we can use a slightly different way such as

and done, we don’t need a third variable.

lastly, swift has an in-built function called swap that takes two inout parameters and swaps their values in memory.

and done, swapped.

Now back to reversing our array, the idea is to have two pointers, one that is at the start of the array and one at the end. swapping the elements and moving in till the middle of the array.

Since we shall reverse the array in-place, we need to send it by reference so we use the inout to do so.

note: using the swapfunction is the fastest way to swap two variables as compared to the other methods listed above.

In the above code, since swift passes parameters by value, the variables are immutable so to be able to change that, we created temporary variables _st and _nd.

This works, however since we are working with trying to optimize a solution, we can further reduce that by using a single variable as

Now let us call it as

Finding a solution

Solutions are generally not as straight forward, however can be simple. Well, if you are in an interview situation, you would now know how to solve this issue.As for the person that brought this problem to me, well here is a pure swift solution with an in-place rotation. However you must also understand that languages evolve to provide more features. Everything can be done in Machine Language, however that developed into Assembly, C, Pascal, C++, Objective-C, Java, C#, Swift and the list goes on. Each new language was created to resolve issues with an earlier one or introduce features that are important. It would be worth considering the features in the newer languages and moving out of the Java mind-set.

Views All Time
Views All Time
248
Views Today
Views Today
1
Posted in Algorithm, puzzle, Tip, Tutorial.