Another question which is favorite among interviewers is rotating an array by a fixed distance. Before understanding how can we do that, it is important to understand what it means to rotate an array. Given an array of length N, rotation by a fixed distance K means shifting each element to the right by K indices. The indices of course are computed in a rotational manner such that if the new index of the element goes beyond the array boundaries, it can be wrapped to the beginning of the array.
Here is an example of input and output.
The problem seems very easy until someone puts few constraints. So, here is the list of constraints
- Auxiliary space permitted is O(1) – you must not use extra space proportional to the size of the problem.
- You must solve it in linear running time
Approaching the Problem
Before we devise the solution with all fulfilled constraints, let us find a brute force solution.
Rotating an Array using extra space
The first solution which comes to my mind is using auxiliary space proportional to the size minimum(K, A-K). Let us say it array TEMP with size L
The algorithm is fairly simple
- Copy last L elements of the INPUT array to TEMP array
- Shift rest of the elements to the extreme right
- Copy the TEMP array in the first L indices of the INPUT array
This solution runs in linear time but the space requirement is O(N). Now consider an array which has 10 million elements and this rotation is a part of a big functionality. Possibly the amount of program memory available to you at that time is a few megabytes. You certainly won’t prefer allocating a new array which might result in a OutOfMemoryError.
Rotating an Array in non linear time
Here is another simple to code solution which requires constant extra space
- Loop through the array K times
- In each iteration shift elements by one position to the right
This solution is space efficient, but the time required is proportion to K.N. Hence, it is not efficient in terms of running time. We definitely need a better solution.
A recursive solution for Rotating an Array
Here is another clue!
Think about a use case where K is half of N. This is the best scenario, where we can just loop through i = 0 to K and swap the elements INPUT[i] and INPUT[i +K]. This is a good news, but not all Ks will divide the array into two equal parts.
But the idea is still valid, we can probably break down the problem to fit the above scenario.
- Let us represent the array in the form AB, where B starts from the index K. The final output is expected to be of form BA.
- Let us say that the part B is larger than the part A.
- So, we can divide part B into B1 and B2 such that B2 is of same length as A. The array looks like AB1B2
- Now swap A and B2 to get B2B1A. We can see that A is at the right place.
- The problem is now reduced to B2B1 which can be solved in recursive fashion.
The solution satisfies the space constraint, but I doubt its run time efficiency. My argument is that, in one recursion step we are just fixing one chunk smaller chunk of the array. In the subsequent recursive steps, we end up accessing few elements multiple times. Hence, the run time is definitely more than being linear.
A Better Solution
Here is another effective solution
- The output is basically divided into two subsections.
- One of the subsection is of size K, the other is of size N-K
- The relative order and position of the elements in the individual subsections is preserved.
Here is a simple algorithm to achieve this:
- Reverse the first subsection A, which gives an array ArB
- Reverse the second subsection B, which transforms the array to ArBr
- Now reverse ArBr to get BA
The solution is in fact a Linear Time Constant Space solution and it satisfies both the constraint. To achieve this, you need to have a method which can partially reverse an array.
This above solution is good, but I think we can do better. In the above solution, we had two visit each element of the array twice, during partial reversal as well as full reversal.
A much better solution
This solution is the most intuitive one, if done the right way. Imagine you have to rotate the array by K distance to the right. Here are the steps:
- Store the last element of the array in a temporary variable T
- Move element at i = N-K at the last index.
- Move element i = N-2K at the index N-K
- Move element i = N-3K at the index N-2K and so on.
- While calculating the indices, just make sure that the modulo division is considered, so that you don’t overshoot the boundaries of the array.
- There would be two cases
- Either you move all the elements and end up taking an element from index N, in which case just take the element from temporary variable T and stop the process.
- Or you did not move all the elements and still end up taking the element from index N, in which case just take it from the temporary variable T and repeat the process for index N-1.
This solution just visits each element once and requires constant space for the temporary variable.