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, 4Solution
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
# Function to rotate the given
# array by K positions
def rotate_array(a, N, K):
arr = []
for i in range(N):
arr.append(0)
# add last K elements
for i in range(K):
arr[i] = a[N - K + i]
# add remaining elements
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[0] = end
Implementation of the above approach
- C/C++
- Python
# 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[0] = 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[7] = { 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
# 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=" ")