Rotate array (list) in linear time and constant memory

Question

How can I be sure that this Python algorithm uses constant memory? A theoretical proof is OK.

A textbook* has this exercise: write an algorithm to "rotate" a list of n integers, in other words to shift the list values by k indices each. The catch is that the algorithm should take linear time (proportional to n) and constant memory (the same amount for any n). The rotation can be done with slicing:

>>> n = 5
>>> k = 3
>>> a = [i for i in range(n)]
>>> a = a[k:] + a[:k]
>>> a
[3, 4, 0, 1, 2]

I've verified that doubling n doubles the time taken, and so this algorithm takes linear time. However, I'm not sure it takes constant memory. I assume Python creates a new array that is the concatenation of the two slices, and then reassigns variable a to that array. If so, then I think the memory used is proportional to n. But how can I verify that?

The exercise also gives a hint that is cryptic to me: "Hint: Reverse three subarrays." Why would there be a need to create three subarrays, and why reverse them? Is that the trick to using constant memory? I get that you could reverse the order of elements 0 through k-1, reverse the order of elements k through n-1, then reverse the order of all elements, but that seems like more operations, not less.

*The book is Introduction to Programming in Python, by Sedgewick, Wayne, and Dondero. I'm teaching myself, not taking a course for credit.

Answer 1

The trick that the hint refers to is this:

To rotate a sequence of N elements left by M:

• reverse the whole sequence
• reverse the last M elements
• reverse the first N-M elements

done

e.g. left by 2: 1234567 -> 7654321 -> 7654312 -> 3456712

Yes, this is the trick to using constant memory, because reversing a section of the array is easy to do in place. I don't think there's a built in method for reversing subarrays, so you'd have to do something like:

i=0
j=n-m-1
while i<j:
    temp = a[i]
    a[i] = a[j]
    a[j] = temp
    i+=1
    j-=1

In python, this will probably be slower than the way you wrote it originally, but it is still linear time.

Answer 2

Rather than performing swaps, you could carry a single element around and shift it into the next position:

def rotate(array,offset): # positive offset rotates left to right
    if not array or not offset: return
    index,value = 0,array[0]
    for _ in array:
        index = (index+offset)%len(array)
        value,array[index] = array[index],value
    
A = [1,2,3,4,5,6,7]
rotate(A,3)
print(A)

# [5, 6, 7, 1, 2, 3, 4]

Because of Python's ability to use negatives to index from the end of the array, the function will also work to rotate right to left by giving it a negative offset:

A = [1,2,3,4,5,6,7]
rotate(A,-3)
print(A)

# [4, 5, 6, 7, 1, 2, 3]