Left Rotation on an Array

Question

I have a question where I need to rotate an array left k times.

i.e. if k = 2, [1, 2, 3, 4, 5] . -> [3, 4, 5, 1, 2]

So, my code is:

def array_left_rotation(a, n, k):
    for i in range(n):
        t = a[i]
        a[i] = a[(i+n-1+k)%n]
        a[(i+n-1+k)%n] = t

    return a

where n = length of the array.

I think the problem is a mapping problem, a[0] -> a[n-1] if k = 1.

What is wrong with my solution?

Sisyphus

This problem almost surely can be easier solved with slicing. – Forerunner

Consider the case when i==0 and k==1 (the shift of the first element by one position to the right). a[i] = a[(i+n-1+k)%n] becomes a[0] = a[(0+n-1+1)%n]=a[n%n]=a[0]. Is this right? – Forerunner

Have you tried printing the value of (i+n-1+k)%n so as to verify that the elements that get swapped are the ones you expect to get swapped? Have you tried simulating the process with physical objects, to verify that swapping things in this manner produces the desired result? – Topdress

Answer 1

Another way to do this with the help of indexing is shown below..

def rotate(l, n):
    return l[n:] + l[:n]

print(rotate([1, 2, 3, 4, 5], 2))

#output : [3, 4, 5, 1, 2]

This will only return the original list if n is outside the range [-len(l), len(l)]. To make it work for all values of n, use:

def rotate(l, n):
  return l[-n % len(l):] + l[:-n % len(l)]

Westberry

Nice solution! Why is the minus sign (-n...) necessary, though? – Voyage

In python, to index a list back wards you can use negative indices – Westberry

Answer 2

def leftRotation(a, d, n):
    i=0
    while i < n:
        print(a[(i+d)%n], end = ' ')
        i+=1
    return i

if __name__ == '__main__':
    a =[1, 2, 3, 4, 5, 6, 7]
    d = 4
    n = 7 or len(a)
    leftRotation(a, d, n)

Rudiment

Answer 3

A simple way rotate an array n times would be to use slicing,

def left_rotate(arr, n):
    # arr - array to rotate
    # n - n number of rotations
    # For number of rotations greater than length of array
    n = n % len(arr)
    return arr[n:] + arr[:n]

Sejm

Answer 4

One way you can do is by using collections.deque

from collections import deque
k = 2
l = [1, 2, 3, 4, 5]
dl = deque(l)
dl.rotate(k+1)
list(dl)
#[3, 4, 5, 1, 2]

Homothallic

Just a side note: Although your solution returns the specific result required in the question, according to the python doc deque.rotate() has to be called with a negative argument in order to rotate the items to left. The Left rotation was also part of the required behavior in the question. – Havstad

btw. rotating [1,2,3,4] with your code returns [2, 3, 4, 1] which is not the behavior asked for in the question. changing dl.rotate(k+1) into dl.rotate(-1*k) should fix your code – Havstad

Answer 5

def rotate_left(array, shift):
 length = len(array)
 overflow = length * (shift//length + 1)
 return [array[i+shift - overflow] for i in range(length)]

This works if you put in negative numbers, as well, so you can rotate right if you want.

The downside is that it's not in place rotation, so you get a new array, but since your solution returns an array, it makes more sense to leave the original array untouched.

The new index for items in the array is the current index, plus how far left you want to move (although this would actually move them right) minus how many times around the array this would take you plus one. The plus one forces the resulting index to be negative, so we go through the original array from the back.

Singer

Answer 6

**Given an array Arr[ ] of N integers and a positive integer K. The task 
is to cyclically rotate the array clockwise by K. keep the first 
position of array unaltered. PYTHON**

def Rotate(arr, k, output):
    
    if not output: output.append(arr.pop(0))
    if len(arr)==k:
        for _ in range(k):
            if arr: output.append(arr.pop(-1))
    for i in range(k):
        if arr: output.append(arr.pop(0))
    if arr: Rotate(arr, k, output)
    return(output)

arr = [10,20,30]
k = 4
output = []
Rotate(arr, k, output)

Trichromat

Answer 7

I use GO to answer it. But you can take the logic from the code :

for i := d; i > 0; i-- {
    x := a[0]
    a = a[1:]
    a = append(a, x)
 }
 return a

First, x := a[0] take the value first value of array a[0]. Then, delete the array a[0] and push the first array x that you copied to last line in array a (in golang we use : append(arr,element)). And repeat it until d length.

if you using i in loop, it will make the code distracted. Because we only focus in array [0] (first array) and move it to last array while looping.

Hyacinth

Answer 8

Please try this :

import math
import os
import random
import re
import sys



if __name__ == '__main__':

    n = 5  #number of elements

    d = 4  #number of times left operation needs to be performed

    a = [1,2,3,4,5] #array to be rotated

    def leftRotate(a, n, d): 
        # To get the starting point of rotated array 
        mod = d % n 
        print(mod)


    # Prints the rotated array from start position 
        for i in range(n): 
            print (str(a[(mod + i) % n]), end = ' ')

(leftRotate(a, n, d))

Maccabean

Answer 9

def rotateLeft(rotation, arr):
    res = [None] * len(arr)
    rotation = rotation % len(arr)
    
    for i in range(0, len(arr)):
        index = i - rotation
        if index < 0:
            index = index + len(arr)
            
        res[index] = arr[i]
    
    return res

or

def rotateLeft(rotation, arr):
   return arr[rotation:] + arr[:rotation

Creamer

Answer 10

I try to left rotate array via recursion in golang:

func rotLeft(a []int32, d int32) []int32 {  
    if d==0{return a}
    newArr := make([]int32, len(a)-1)  
    copy (newArr, a[1:])
    newArr = append(newArr,a[0])
    return rotLeft(newArr, d-1)
}

Ravishment

Answer 11

JAVA CODE:

public class Solution {

public static void rotate(int[] arr, int d) {
    //eg) n=6, d=4
    int n = arr.length;
    int k=0;
    
    //storing elements from index 0 to d-1
    //in temp array of size d
    
    int temp[] = new int [d];
    
    for(int i=0; i<d; i++)
    {
        temp[i] = arr[i];
        //1,3,6,11
    }
    
    //left rotating elements
    //storing from index 0 to n-d-1
    for(int i=0; i<n-d; i++)
    {
        
        //index: 0 and 1
        arr[i]=arr[d+i];
        //arr[0] = arr[4]
        //arr[1] = arr[5]
        
        //12, 17, 6,11,12,17
    }
    
    //copying temp array elements
    //in arr from index n-d to n-1
    
    for(int i=n-d; i<n; i++)
    {
        //index: 2, 3, 4,5
        arr[i] = temp[k];
        k++;
        //arr[2] = temp[0]
        //arr[3]=temp[1]
        //arr[4]=temp[2]
        //arr[5]=temp[3]
        
        //12, 17, 1,3,6,11
    }
    
    
}

}

Explanation:

1. First we copy the elements from 0 to d-1 in temp array
2. from index 0 to n-d-1, we move elements to the left
3. we replace the elements from index n-d to n-1, by copies stored in temp array

Campaign

Answer 12

Another solution using pop method

a = [1,2,3,4,5] # The list
d = 3 # Number of rotations

# Pop the first element and append it at the end
for i in range(0, d):
    b = a.pop(0)
    a.append(b)

print(' '.join(map(str, a))) # print as space separated string

Sauropod

Answer 13

def rotateLeft(d, arr):
    for i in range(d):
        arr.append(arr[0])
        arr.pop(0)
        
    return arr

Elaterite

Not wrong, but terribly inefficient! – Bookmobile

Answer 14

This solution requires constant extra memory, and runs in O(nk).

If the array has zero length, or there are zero rotations, skip the loop and return arr.

For every rotation we store the first element, then shift every other element to the left, finally placing the first element at the back of the list. We save some work for large values of k by recognizing that every rotation after the nth is a repeat solution -> k % n.

def array_left_rotation(arr, n, k):
    for _ in range(0 if 0 in [n, k] else k % n):
        temp = arr[0]
        for idx in range(n - 1):
            arr[idx] = arr[idx + 1]
        arr[-1] = temp
    return arr

Buyers

generally in Python you try to use the tools provided by the standard lib. This looks like an attempt to write low-level code in Python. It's rarely a good idea: It is hard to guess the memory requirement of an algorithm in Python (much harder than C), and I am not sure OP cares that much about "constant extra memory". Also, a consequence is that readability is low, which is considered important in Python. – Lateritious

This question is tagged data structures and algorithms, so I provided time and space complexity. If asked this question in an interview, space and runtime trade offs need to be addressed. This algorithm is O(1) time and runs in O(nk). The question was not “give me the most pythonic”. If you can’t read this, you need more practice. – Buyers

Answer 15

N, d = map(int, input().split())     #taking length N and no. of rotations d
a = list(input().split())            #taking input array as list
r = a[d % N : N] + a[0 : d % N]      #rotating the array(list)
print(r)  

5 2                            #giving N,D as input
1 2 3 4 5                      #giving input array
['3', '4', '5', '1', '2']      #output

Targum

Answer 16

def rotate_left3(nums):
temp=[]
for i in range(len(nums)-1):
  temp=nums[i]
  nums[i]=nums[i+1]
  nums[i+1]=temp

return nums

Future

An ingenious solution! Please fix your indentation. Why is the function called rotate_left3? How would you deal with OP wanting to rotate the list k times? – Tragus

Could you give an explanation of why the code works? – Both

Answer 17

This is how I did it:

def rotate_left3(nums):
    return [ nums[1] , nums[2] , nums[0] ]

It worked perfect 100%, but if you add more sums, you'd have to add its just set for the 3 that the problem specified.

Adolphadolphe