Left rotate array by d elements

Question

I have code to rotate an array of size n by d elements, but the complexity of my code is O(nd).

I want to know if there is any way to reduce the complexity.

Here is my code:

def leftRotate(arr, d, n): 
    for i in range(d): 
        leftRotatebyOne(arr, n) 

# Function to left Rotate arr[] of size n by 1*/  
def leftRotatebyOne(arr, n): 
    temp = arr[0] 
    for i in range(n-1): 
        arr[i] = arr[i + 1] 
    arr[n-1] = temp 


# utility function to print an array */ 
def printArray(arr, size): 
    for i in range(size): 
        print ("% d"% arr[i], end =" ") 


# Driver program to test above functions */ 
arr = [1, 2, 3, 4, 5, 6, 7] 
leftRotate(arr, 2, 7) 
printArray(arr, 7)

You can print array in a single `print` function call: `' '.join(map(str, [1, 2, 3]))`. There is no need to execute dedicated function — Pavel Botsman, Jun 05 '20 at 12:19

score 1 · Answer 1 · answered Jun 05 '20 at 12:24

1

It is as simple as that

arr.append(arr.pop(0))

Python offers a lot of ways to avoid using indexed access.

arr.pop(0)

removes the first element of the list - and returns it

answered Jun 05 '20 at 12:24

volcano

3,578
21
28

This or a `deque` should be the only accepted answers. Anything else is needlessly complex. – Axe319 Jun 05 '20 at 13:11

score 1 · Accepted Answer · edited Jun 20 '20 at 09:12

Yes there is a Better solution for your code and time complexity will be O(n)

code:

def leftRotate(arr, d, n):
    temp=[]
    for i in range(d):
        temp.append(arr[i])
    for i in range(d,n):
        arr[i-d]=arr[i]
    for i in range(0,d):
        arr[n-d+i]=temp[i]

# utility function to print an array */ 
def printArray(arr, size): 
    for i in range(size): 
        print ("% d"% arr[i], end =" ") 


# Driver program to test above functions */ 
arr = [1, 2, 3, 4, 5, 6, 7] 
leftRotate(arr, 2, 7) 
printArray(arr, 7)

score -1 · Answer 3 · answered Jun 05 '20 at 12:17

I don't know if you are using lists numpy arrays or arrays but you can use array slicing without an loop like this:

temp = arr[0]
arr[0:-2] = arr[1:-1]
arr[-1] = temp

If you are using numpy arrays there is a numpy function to shift the array either in left or right direction and it's np.roll

You can also avoid passing the array size in every function. You can get it with array.size

score -1 · Answer 4 · answered Jun 05 '20 at 12:18

instead of iterating through all of the items, store the last item of the list to a var the remove it from the list after that insert it to the start

def left_rotate_by_one(arr):
    temp = arr[len(arr)-1] #get last item
    arr.remove(len(arr)-1) # remove it
    arr.insert(0,temp)

Left rotate array by d elements

4 Answers4

code: