Program to right rotate an array by 'k' elements

Posted by N.K. Chauhan on Jan 04, 2022

An array A is given, the task is to "right" rotate A by k places.

Example 1: Right rotate by 3 : {1, 2, 3, 4, 5, 6, 7}

Input: {1, 2, 3, 4, 5, 6, 7}
Output: {5, 6, 7, 1, 2, 3, 4}

Example 2: Right rotate by 2 : {10, 20, 43, 12, 7, 123}

Input: {10, 20, 43, 12, 7, 123}
Output: {7, 123, 10, 20, 43, 12}


Solutions

Method 1: Using extra space

We can solve this problem in O(n) time, using O(k) extra space.

Create an auxiliary array 'aux' of size k and copy A[n-k to n-1] elements to 'Aux'. Now traverse array A from n-k to 0; and right shift every element by (i+k).

0,0,0,0,1,1,1,2,2
0,0,1

Complexity

If k < n, the time complexity of this solution is (k + (n-k)+ k) or (n+k) or O(n); we have also used an auxiliary array 'aux' of size 'k', so space complexity is O(k).

Method 2: Reversal Algorithm

We can solve this problem in O(n) time and O(1) space, with the help of reversal algorithm.

In reversal algorithm - we first reverse A[0 to n-k-1] and A[n-k to n-1] and than reverse the whole array A[0 to n-1].

5,6,7,1,2,3,4
7,123,10,20,43,12

Complexity

The time complexity of this solution is O(n) and space complexity is O(1).

Method 3: In Place (No auxiliary array)

We can solve this problem in-place, without using any auxiliary array.

In this approach we need to right rotate the array by 1, k times; if value of k is n - we will be traversing it n times, so time complexity is O(n^2).

5,6,7,1,2,3,4
7,123,10,20,43,12

Complexity

Here the array is rotated by 1, k times; if value of k is n - it will be traversed n times, so time complexity is O(n^2).

Here no auxiliary array is used, yet the space complexity is O(k) only, because for every rotation a 'tmp' variable is used to store last element.

Related


Longest substring without repeating characters

Program to print Intersection of two sorted arrays

Count the number of inversions in an array - in O(n log n) time

Find a triplet in an array that sums to a given number

Merge two sorted arrays in O(1) space

Program to print Union of two sorted arrays

Print all possible permutations of an Array in O(1) space

Two Sum - return index of a pair of array elements with a given sum

Print all Subsets (Power Set) of a given array

Rain water trapping problem - O(n) time & O(n) space

Word Break Problem (Using HashMap and DP)