# Rotate Array Coding Interview Solution

Rotate Array is a very famous coding interview question asked in the interview. We will discuss the solution in Python, C++, and JavaScript which you can solve in LeetCode if you want.

## Rotate Array LeetCode and InterviewBit Question.

Given an array, rotate the array to the right by n steps, where n is nonnegative.

Example 1:

```Input: nums = [1,2,3,4,5,6,7], n = 4
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [4,5,6,7,1,2,3]```

### Follow up for this question

• Provide at least more than one solution to this problem.
• Can it be done in-place with O(1) extra space?

## Algorithm for Rotate Array Problem

### Brute Force Solution:

It’s the simplest solution, all you need to do is to rotate all the elements of the array in n steps one by one.

### Python Solution for Rotate Array.

```class Solution:
def rotate(self, number: List[int], n: int) -> None:
# speed up the rotation
n %= len(number)

for i in range(n):
previous = number[-1]
for j in range(len(number)):
number[j], previous = previous, number[j]```

### Complexity Analysis:

Time Complexity is O(n x n) another n is the number of iteration or rotations. Space Complexity is O(1). No extra space is used.

### Using Cyclic Replacements:

We can directly place every number of the array at its required correct position. But if we do that, we will destroy the original element. Thus, we need to store the number being replaced in a temp variable.

Then, we can place the replaced number temp at its correct position and so on, `numlen` times, where `numlen` is the length of the array. We have chosen `numlen` to be the number of replacements since we have to shift all the elements of the array(which is `numlen`).

But, there could be a problem with this method, if `numlen % n = 0` where `n=n%numlen`. In this case, while picking up numbers to be placed at the correct position, we will eventually reach the number from which we originally started.

Thus, in such a case, when we hit the original number’s index again, we start the same process with the number following it.

### Python Solution:

```class Solution:
def rotate(self, number: List[int], n: int) -> None:
numlen = len(number)
n %= numlen

start = count = 0
while count < numlen:
current, prev = start, number[start]
while True:
next_idx = (current + n) % numlen
number[next_idx], prev = prev, number[next_idx]
current = next_idx
count += 1

if start == current:
break
start += 1

## Time Complexity: O(n)
## Space Complexity: O(1)```

### C++ Solution

```//Another solution where we are using an extra Array for this answer.
class Solution {
public:
void rotate(vector<int>& nums, int k) {
vector<int> temp(nums.size(),0);
int sze = nums.size();
for(int i=0;i<nums.size();i++){
temp[(i+k)%sze] = nums[i];
}
for(int i=0;i<sze;i++)
nums[i] = temp[i];
};
};

// Time Complexity: O(n)
// Space Complexity: O(n)```