Coding Interview Questions

Rotate Array Coding Interview Solution

by

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)

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview-related questions? Check Top Interview Questions category.

Leave a Comment