Rotate array by K elements
Problem Statement: Given an array of integers, rotating array of elements by k elements either left or right.
Examples:
Example 1:
Input: N = 7, array[] = {1,2,3,4,5,6,7} , k=2 , right
Output: 6 7 1 2 3 4 5
Explanation: array is rotated to right by 2 position .
Example 2:
Input: N = 6, array[] = {3,7,8,9,10,11} , k=3 , left
Output: 9 10 11 3 7 8
Explanation: Array is rotated to right by 3 position.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution :
Approach 1: Using a temp array
- For Rotating the Elements to right
Step 1: Copy the last k elements into the temp array.
Step 2: Shift n-k elements from the beginning by k position to the right
Step 3: Copy the elements into the main array from the temp array.
Code:
C++ Code
#include <iostream>
using namespace std;
void Rotatetoright(int arr[], int n, int k)
{
if (n == 0)
return;
k = k % n;
if (k > n)
return;
int temp[k];
for (int i = n - k; i < n; i++)
{
temp[i - n + k] = arr[i];
}
for (int i = n - k - 1; i >= 0; i--)
{
arr[i + k] = arr[i];
}
for (int i = 0; i < k; i++)
{
arr[i] = temp[i];
}
}
int main()
{
int n = 7;
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int k = 2;
Rotatetoright(arr, n, k);
cout << "After Rotating the elements to right " << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}
Output:
After Rotating the elements to right
6 7 1 2 3 4 5
Time Complexity: O(n)
Space Complexity: O(k) since k array element needs to be stored in temp array
Java Code
import java.util.*;
public class Main {
public static void Rotatetoright(int[] arr, int n, int k) {
if (n == 0)
return;
k = k % n;
if (k > n)
return;
int[] temp = new int[k];
for (int i = n - k; i < n; i++) {
temp[i - n + k] = arr[i];
}
for (int i = n - k - 1; i >= 0; i--) {
arr[i + k] = arr[i];
}
for (int i = 0; i < k; i++) {
arr[i] = temp[i];
}
}
public static void main(String args[]) {
int n = 7;
int[] arr = {1,2,3,4,5,6,7};
int k = 2;
Rotatetoright(arr, n, k);
System.out.println("After Rotating the elements to right ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
Output:
After Rotating the elements to right
6 7 1 2 3 4 5
Time Complexity: O(n)
Space Complexity: O(k) since k array element needs to be stored in temp array
- For Rotating the Elements to left
Step 1: Copy the first k elements into the temp array.
Step 2: Shift n-k elements from last by k position to the left
Step 3: Copy the elements into the main array from the temp array.
Code:
C++ Code
#include <iostream>
using namespace std;
void Rotatetoleft(int arr[], int n, int k)
{
if (n == 0)
return;
k = k % n;
if (k > n)
return;
int temp[k];
for (int i = 0; i < k; i++)
{
temp[i] = arr[i];
}
for (int i = 0; i < n - k; i++)
{
arr[i] = arr[i + k];
}
for (int i = n - k; i < n; i++)
{
arr[i] = temp[i - n + k];
}
}
int main()
{
int n = 7;
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int k = 2;
Rotatetoleft(arr, n, k);
cout << "After Rotating the elements to left " << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
return 0;
}
Output:
After Rotating the elements to left 3 4 5 6 7 1 2
Time Complexity: O(n)
Space Complexity: O(k) since k array element needs to be stored in temp array
Java Code
import java.util.*;
public class Main {
public static void Rotatetoleft(int[] arr, int n, int k) {
if (n == 0)
return;
k = k % n;
if (k > n)
return;
int[] temp = new int[k];
for (int i = 0; i < k; i++) {
temp[i] = arr[i];
}
for (int i = 0; i < n - k; i++) {
arr[i] = arr[i + k];
}
for (int i = n - k; i < n; i++) {
arr[i] = temp[i - n + k];
}
}
public static void main(String args[]) {
int n = 7;
int[] arr = {1,2,3,4,5,6,7};
int k = 2;
Rotatetoleft(arr, n, k);
System.out.println("After Rotating the elements to left ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
Output:
After Rotating the elements to left 3 4 5 6 7 1 2
Time Complexity: O(n)
Space Complexity: O(k) since k array element needs to be stored in temp array
Approach 2: Using ” Reversal Algorithm “
Approach:
- For Rotating Elements to right
Step 1: Reverse the last k elements of the array
Step 2: Reverse the first n-k elements of the array.
Step 3: Reverse the whole array.
For Eg , arr[]={1,2,3,4,5,6,7} , k=2
Code:
C++ Code
#include <iostream>
using namespace std;
// Function to Reverse the array
void Reverse(int arr[], int start, int end)
{
while (start <= end)
{
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// Function to Rotate k elements to right
void Rotateeletoright(int arr[], int n, int k)
{
// Reverse first n-k elements
Reverse(arr, 0, n - k - 1);
// Reverse last k elements
Reverse(arr, n - k, n - 1);
// Reverse whole array
Reverse(arr, 0, n - 1);
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = 7;
int k = 2;
Rotateeletoright(arr, n, k);
cout << "After Rotating the k elements to right ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
Output:
After Rotating the k elements to right 6 7 1 2 3 4 5
Time Complexity – O(N) where N is the number of elements in an array
Space Complexity – O(1) since no extra space is required
Java Code
import java.util.*;
public class Main {
// Function to Reverse the array
public static void Reverse(int[] arr, int start, int end) {
while (start <= end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// Function to Rotate k elements to right
public static void Rotateeletoright(int[] arr, int n, int k) {
// Reverse first n-k elements
Reverse(arr, 0, n - k - 1);
// Reverse last k elements
Reverse(arr, n - k, n - 1);
// Reverse whole array
Reverse(arr, 0, n - 1);
}
public static void main(String args[]) {
int[] arr = {1,2,3,4,5,6,7};
int n = 7;
int k = 2;
Rotateeletoright(arr, n, k);
System.out.print("After Rotating the k elements to right ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
Output:
After Rotating the k elements to right 6 7 1 2 3 4 5
Time Complexity – O(N) where N is the number of elements in an array
Space Complexity – O(1) since no extra space is required
- For Rotating Elements to left
Step 1: Reverse the first k elements of the array
Step 2: Reverse the last n-k elements of the array.
Step 3: Reverse the whole array.
For Eg , arr[]={1,2,3,4,5,6,7} , k=2
Code:
C++ Code
#include <iostream>
using namespace std;
// Function to Reverse the array
void Reverse(int arr[], int start, int end)
{
while (start <= end)
{
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// Function to Rotate k elements to left
void Rotateeletoleft(int arr[], int n, int k)
{
// Reverse first k elements
Reverse(arr, 0, k - 1);
// Reverse last n-k elements
Reverse(arr, k, n - 1);
// Reverse whole array
Reverse(arr, 0, n - 1);
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = 7;
int k = 2;
Rotateeletoleft(arr, n, k);
cout << "After Rotating the k elements to left ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
Output:
After Rotating the k elements to left 3 4 5 6 7 1 2
Time Complexity – O(N) where N is the number of elements in an array
Space Complexity – O(1) since no extra space is required
Java Code
import java.util.*;
public class Main {
// Function to Reverse the array
public static void Reverse(int[] arr, int start, int end) {
while (start <= end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// Function to Rotate k elements to left
public static void Rotateeletoleft(int[] arr, int n, int k) {
// Reverse first k elements
Reverse(arr, 0, k - 1);
// Reverse last n-k elements
Reverse(arr, k , n - 1);
// Reverse whole array
Reverse(arr, 0, n - 1);
}
public static void main(String args[]) {
int[] arr = {1,2,3,4,5,6,7};
int n = 7;
int k = 2;
Rotateeletoleft(arr, n, k);
System.out.print("After Rotating the k elements to left ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
Output:
After Rotating the k elements to left 3 4 5 6 7 1 2
Time Complexity – O(N) where N is the number of elements in an array
Space Complexity – O(1) since no extra space is required
Special thanks to Gurmeet Singh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article