Given a list and an integer n, write a Python program to right-rotate the list by n position.
Examples :
Input : n = 2, List_1 = [1, 2, 3, 4, 5, 6]
Output : List_1 = [5, 6, 1, 2, 3, 4]
Explanation: We get output list after right rotating (clockwise) given list by 2.Input : n = 3, List_1 = [3, 0, 1, 4, 2, 3]
Output : List_1 = [4, 2, 3, 3, 0, 1]
Approach #1 : Traverse the first list one by one and then put the elements at required places in a second list. zzz
Python3
# Python program to right rotate a list by n# Returns the rotated listdef rightRotate(lists, num): output_list = [] # Will add values from n to the new list for item in range(len(lists) - num, len(lists)): output_list.append(lists[item]) # Will add the values before # n to the end of new list for item in range(0, len(lists) - num): output_list.append(lists[item]) return output_list# Driver Coderotate_num = 3list_1 = [1, 2, 3, 4, 5, 6]print(rightRotate(list_1, rotate_num)) |
[4, 5, 6, 1, 2, 3]
Time complexity : O(n)
Approach #2 : Another approach to solve this problem by using slicing technique. One way of slicing list is by using len() method.
Python3
# Python program to right rotate# a list by n using list slicingn = 3list_1 = [1, 2, 3, 4, 5, 6]list_1 = (list_1[len(list_1) - n:len(list_1)] + list_1[0:len(list_1) - n])print(list_1) |
[4, 5, 6, 1, 2, 3]
Approach #3 : In the above method, last n elements of list_1 was taken and then remaining elements of list_1. Another way is without using len() method.
Python
# Right Rotating a list to n positionsn = 3list_1 = [1, 2, 3, 4, 5, 6]if n>len(list_1): n = int(n%len(list_1))list_1 = (list_1[-n:] + list_1[:-n])print(list_1) |
[4, 5, 6, 1, 2, 3]
Time complexity : O(n)
Note : list_1[:] will return the whole list as the blank space on left of slicing operator refers to start of list i.e 0 and blank space on right refers to ending position of list.
Approach 4: One additional approach that could be used to right rotate a list by n positions is to use the collections.deque module. This module provides a doubly-linked list that supports fast insertion and deletion at both ends of the list, as well as fast rotating operations.
To right rotate a list by n positions, you can use the rotate() method of the deque object. This method rotates the elements of the list by the specified number of positions to the right. For example:
Python3
from collections import deque# Create a deque object from the listlist_1 = [1, 2, 3, 4, 5, 6]deque_1 = deque(list_1)# Rotate the deque by 3 positions to the rightdeque_1.rotate(3)# Convert the deque back to a listlist_1 = list(deque_1)print(list_1) # Output: [4, 5, 6, 1, 2, 3] |
[4, 5, 6, 1, 2, 3]
The time complexity of the deque.rotate() method is O(n), because it involves shifting all the elements in the deque by a certain number of positions. The time complexity of the list() and deque() constructors is also O(n), because they involve iterating through all the elements in the input list or deque and creating a new list or deque with those elements.
Auxiliary space: O(n), because it involves creating a new deque and a new list, both of which have the same size as the input list.
Approach 5: Using recursion
- The function right_rotate takes two parameters, lst which is the list to be rotated, and n which is the number of positions to rotate.
- In the base case, if n is 0, the list is returned as it is.
- In the recursive case, the list is rotated by 1 position by concatenating the last element of the list to the front and then calling the function again with n-1.
Python3
def right_rotate(lst, n): if n == 0: return lst else: return right_rotate(lst[-1:] + lst[:-1], n-1)list_1 = [1, 2, 3, 4, 5, 6]n = 2print(right_rotate(list_1, n))list_1 = [3, 0, 1, 4, 2, 3]n = 3print(right_rotate(list_1, n)) |
[5, 6, 1, 2, 3, 4] [4, 2, 3, 3, 0, 1]
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach 6: Using extend() method and slicing:
Step-by-step algorithm for implementing the approach
- Take the input list lst and the number of positions to rotate n.
- Compute the actual number of positions to rotate by taking n modulo the length of lst.
- Extend lst with a slice of itself consisting of the first n elements of lst.
- Delete the first n elements of lst.
- Return the modified lst.
Python3
def right_rotate(lst, n): n = n % len(lst) lst.extend(lst[:n]) del lst[:n] return lstlst = [1, 2, 3, 4, 5, 6]n = 3print(right_rotate(lst, n)) |
[4, 5, 6, 1, 2, 3]
Time Complexity: O(N)
This is because the function first calculates the number of positions to rotate by taking the modulus of n with the length of the list lst, which takes constant time. The function then extends the list by concatenating a slice of the first n elements of the list with the original list, which takes O(n) time.
Auxiliary Space: O(N)
This is because the function concatenate a slice of the first N members of the original list with the new list object, which requires O(N) space.
Approach 7: Using numpy.roll() method
- Take the input list lst and the number of positions to rotate n.
- Convert the list to a numpy array using np.array(lst).
- Use np.roll(arr, n) to shift the elements of the numpy array arr by n positions to the right.
- Converting the numpy array back to list.
- Return the list
Python3
import numpy as npdef right_rotate(lst, n): # Convert the list to a numpy array arr = np.array(lst) # Use np.roll to shift the elements to the right arr = np.roll(arr, n) # Convert the numpy array back to a list arr = arr.tolist() # Return the rotated list return arr.tolist() list_1 = [1, 2, 3, 4, 5, 6]n1 = 2print(right_rotate(list_1, n1))list_2 = [3, 0, 1, 4, 2, 3]n2 = 3print(right_rotate(list_2, n2)) |
Output
[5, 6, 1, 2, 3, 4] [4, 2, 3, 3, 0, 1]
Time Complexity: O(N) where N is the length of the array as we have to traverse the whole list.
Auxiliary Space: O(N) as we have to convert the list to a numpy array that operation requires O(n) space. Therefore space complexity is O(N).
