# Rotate an array by K positions

Nov. 16, 2020 173 ## Problem Statement

We are given an array of size N and a value K. We have to rotate the array by K positions.

Let’s understand by example.

#### Input :

A[ ] = { 1, 2, 3, 4, 5, 6, 7 }
K = 3

#### Output :

5, 6, 7, 1, 2, 3, 4

## Solution

### Rotation using an extra array

A simple solution is to use an extra array and store the elements in the order they are required in the result. We will run two loops, one for storing the last K elements and the other for storing the rest of the elements. In the first loop, store the last K elements in the same order (as that in the old array) filling the starting positions of the new array. Then fill the rest of the elements in the new array in the exact order.

#### Complexity analysis

The time complexity for the above solution is $O(N)$ as we are traversing the array only once, but we are also using extra space, so we also have space complexity of $O(N)$.

Pseudocode for the above approach:

Extra array : arr[ ]
Original array : a[ ]

For i = 0 to K-1
arr[i] = a[N-K+i]

For i = K to N-1
arr[i] = a[i-K]

For i = 0 to N-1
a[i]= arr[i]


#### Implementation of the above approach

• C/C++
• Python
// Program to rotate the given
// array by K positions

#include <bits/stdc++.h>

using namespace std;

// Function to rotate the given
// array by K positions

void rotate_array(int a[], int N, int K)
{

int arr[N];

fill(arr, arr + N, 0);

for (int i = 0; i < K; i++)
arr[i] = a[N - K + i];

for (int i = K; i < N; i++)
arr[i] = a[i - K];

// assign new values to the
// array
for (int i = 0; i < N; i++)
a[i] = arr[i];
}

// Driver code

int main()
{
int a = {1, 2, 3, 4, 5, 6, 7};

int K = 3;

int N = sizeof(a) / sizeof(int);

// Function Call

rotate_array(a, N, K);

for (int i = 0; i < N; i++)
cout << a[i] << " ";
}

# Program to rotate the given
# array by K positions

# Function to rotate the given
# array by K positions

def rotate_array(a, N, K):
arr = []
for i in range(N):
arr.append(0)

for i in range(K):
arr[i] = a[N - K + i]

for i in range(K, N):
arr[i] = a[i - K]

# assign new values to the
# array
for i in range(N):
a[i] = arr[i]

# Driver code
a = [1, 2, 3, 4, 5, 6, 7]
K = 3
N = len(a)

# Function Call

rotate_array(a, N, K)

for i in range(N):
print(a[i], end=" ")


### By rotating the array K times

We can rotate the array K times by one position resulting in the final array rotated by K positions. Save the last element and shift the rest of the elements by one position to the right and then overwrite the first element with the saved last element.

#### Complexity analysis

The time complexity for the above approach is $O(N* K)$. Shifting all the elements by one position takes linear time and this process is repeated for K times.

#### The Pseudocode for the above approach

 for count = 0 to count = K-1
end = a[N-1]
for i = N-1 to i = 1
a[i] = a[i-1]
a = end


#### Implementation of the above approach

• C/C++
• Python
// Program to rotate the given
// array by K positions

#include <bits/stdc++.h>

using namespace std;

// Function to rotate the given
// array by K positions

void rotate_array(int a[], int N, int K)
{
// Rotating the array K times by one
//position

for (int count = 0; count < K; count++)
{
// saving last element

int end = a[N - 1];

for (int i = N - 1; i > 0; i--)
a[i] = a[i - 1];
a = end;
}
}

// Driver code

int main()
{
int a = {1, 2, 3, 4, 5, 6, 7};

int K = 3;

int N = sizeof(a) / sizeof(int);

// Function Call

rotate_array(a, N, K);

for (int i = 0; i < N; i++)
cout << a[i] << " ";
}

# Program to rotate the given
# array by K positions

# Function to rotate the given
# array by K positions

def rotate_array(a, N, K):
# Rotating the array K times by one
# position

for count in range(K):

# saving the last element

end = a[N - 1]

for i in range(N - 1, 0, -1):
a[i] = a[i - 1]

a = end

# Driver code

a = [1, 2, 3, 4, 5, 6, 7]
K = 3
N = len(a)

# Function Call

rotate_array(a, N, K)

for i in range(N):
print(a[i], end=" ")


### Most efficient approach

There is an observation in the problem that we are shifting the last K elements in the starting of the array by pushing the elements in the starting to the end of the array in the exact order. We can achieve this by reversing the last K elements, then reversing the remaining elements, and then finally reversing the whole array.

This is pure observation and can be well understood by a diagram.

For a = { 1, 2, 3, 4, 5, 6, 7 }
K = 3

Initial array:

 1 2 3 4 5 6 7

Array after reversing last K elements:

 1 2 3 4 7 6 5

Array after reversing first N-K elements:

 4 3 2 1 7 6 5

After reversing the modified array:

 5 6 7 1 2 3 4

#### Complexity analysis

The time complexity for the above approach is $O(N)$ because we will use a linear reversing algorithm and we are just calling the reverse function three times.

#### Pseudocode for the above approach

For reversing :
start, end
while start < end :
swap( a[start ], a[end] )
start++
end--

Reverse last K elements
Reverse first N-K elements
Reverse the whole array


#### Implementation of the above approach

• C/C++
• Python
// Program to rotate the given
// array by K positions

#include <bits/stdc++.h>
using namespace std;

//Function for reversing the
// array

void reverse(int a[], int start, int end)
{
while (start < end)
{
swap(a[start], a[end]);
start++;
end--;
}
}

// Function to rotate the given
// array by K positions

void rotate_array(int a[], int N, int K)
{
// reverse last K elements
reverse(a, N - K, N - 1);

// reverse first N-K elements
reverse(a, 0, N - K - 1);

// reverse the whole array
reverse(a, 0, N - 1);
}

// Driver code

int main()
{
int a = {1, 2, 3, 4, 5, 6, 7};

int K = 3;

int N = sizeof(a) / sizeof(int);

// Function Call

rotate_array(a, N, K);

for (int i = 0; i < N; i++)
cout << a[i] << " ";
}

# Program to rotate the given
# array by K positions

# Function for reversing the
# array

def reverse(a, start, end):
while start < end:
a[start], a[end] = a[end], a[start]
start += 1
end -= 1

# Function to rotate the given
# array by K positions

def rotate_array(a, N, K):
# reverse last K elements
reverse(a, N - K, N - 1)

# reverse first N-K elements
reverse(a, 0, N - K - 1)

# reverse the whole array
reverse(a, 0, N - 1)

# Driver code

a = [1, 2, 3, 4, 5, 6, 7]
K = 3
N = len(a)

# Function Call

rotate_array(a, N, K)

for i in range(N):
print(a[i], end=" ")


Liked the post?
0 COMMENT