To the right, to the left, now rotate

Question

I was working on HackerRank: Circular Array Rotation which is about coming up with an efficient algorithm for array rotations in right-ward manner.

John Watson performs an operation called a right circular rotation on an array of integers. After performing one right circular rotation operation, the array is transformed from [a(0), a(1), ..., a(n-1)] to [a(n-1), a(0), ..., a(n-2)].

Watson performs this operation \$k\$ times. To test Sherlock's ability to identify the current element at a particular position in the rotated array, Watson asks \$q\$ queries, where each query consists of a single integer, \$m\$, for which you must print the element at index \$m\$ in the rotated array.

The first line contains 3 space-separated integers, \$n\$, \$k\$, and \$q\$, respectively. The second line contains \$n\$ space-separated integers, where each integer \$i\$ describes array element \$a(i)\$. Each of the \$q\$ subsequent lines contains a single integer denoting \$m\$.

After vainly attempting to brute-force it (and the inevitable "time limit expired"), I came up with an algorithm that seems quite fast, as well as offering the flexibility of rotating by an arbitrary number of positions (which is, incidentally, why it is a lot faster than brute force).

I then decided to implement a complementary left-rotation function which works similarly (though I didn't manage to use list comprehensions for that one). As you can see from the code, they are coupled in that if a negative number is input as the number of positions to rotate, they call the other with its positive version. I did this for the sake of code reuse, but could it bite me back?

Here is a working demo on repl.it that demonstrates the results. Note I have tested it with small and large numbers, as well as negative numbers, and all appears to be working well.

def rotate_right(array:list, rotate_by:int = 1) -> list:
    '''
    Default behavior: 
        Given input [1,2,3] return [3,1,2]
    Supplying a rotate_by value other than 1 will increase the number
    of positions the values are moved towards the right by.
    '''
    if rotate_by < 0:
        return rotate_left(array, - rotate_by)
    array_length = len(array)
    while rotate_by >= array_length:
        rotate_by -= array_length
    return [array[i - rotate_by] for i in range(array_length)]


def rotate_left(array:list, rotate_by:int = 1) -> list:
    '''
    Default behavior: 
        Given input [1,2,3] return [2,3,1]
    Supplying a rotate_by value other than 1 will increase the number
    of positions the values are moved towards the left by.
    '''
    if rotate_by < 0:
        return rotate_right(array, - rotate_by)
    array_length = len(array)
    while rotate_by >= array_length:
        rotate_by -= array_length
    rotated = []
    for i in range(array_length):
        val_index = i + rotate_by
        if val_index >= array_length:
            val_index -= array_length
        rotated.append(array[val_index])
    return rotated


def main() -> None:
    # Testing code
    arr = [1,2,3,4,5,6,7,8]
    rotate_by = 1
    print('Input array:', arr)
    print('Rotate by:', rotate_by)
    arr_L = arr_R = arr
    print('Rotate left:')
    for _ in range(len(arr)):
        arr_L = rotate_left(arr_L, rotate_by)
        print(arr_L)
    print('Rotate right:')
    for _ in range(len(arr)):
        arr_R = rotate_right(arr_R, rotate_by)
        print(arr_R)

Which will print the following to the output console:

Input array: [1, 2, 3, 4, 5, 6, 7, 8]
Rotate by: 1
Rotate left:
[2, 3, 4, 5, 6, 7, 8, 1]
[3, 4, 5, 6, 7, 8, 1, 2]
[4, 5, 6, 7, 8, 1, 2, 3]
[5, 6, 7, 8, 1, 2, 3, 4]
[6, 7, 8, 1, 2, 3, 4, 5]
[7, 8, 1, 2, 3, 4, 5, 6]
[8, 1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
Rotate right:
[8, 1, 2, 3, 4, 5, 6, 7]
[7, 8, 1, 2, 3, 4, 5, 6]
[6, 7, 8, 1, 2, 3, 4, 5]
[5, 6, 7, 8, 1, 2, 3, 4]
[4, 5, 6, 7, 8, 1, 2, 3]
[3, 4, 5, 6, 7, 8, 1, 2]
[2, 3, 4, 5, 6, 7, 8, 1]
[1, 2, 3, 4, 5, 6, 7, 8]

With the above rotate_right function, the solution to the HackerRank challenge is very straightforward. It passes all test cases with no time-outs.

def main() -> None:
    values, rotations, queries = input().strip().split(' ')
    values, rotations, queries = [int(values), int(rotations), int(queries)]
    array = [int(n) for n in input().strip().split(' ')]
    array = rotate_right(array, rotations)
    # Final step, query the resulting array's indexes
    for _ in range(queries):
        index = int(input().strip())
        print(array[index])

Answer 1

Since you do not modify the list after it is created, one approach to efficient rotations is a simple wrapper class that holds the actual list and an offset denoting the position of the element that is considered to be the first element of a rotation. Now, "rotating" simply increases/decreases that offset value, which is done, of course, in constant time. Conversely, in order to get an \$i\$th element from the rotation, only a constant time overhead is present.

All in all, I had this in mind:

#!/bin/python3

import sys


class ListRotationWrapper:
    def __init__(self, the_list):
        self.the_list = the_list
        self.offset = 0

    def rotate(self, num):
        self.offset = ((self.offset - num) % len(self.the_list))

    def __getitem__(self, index):
        return self.the_list[(index + self.offset) % len(self.the_list)]


def main() -> None:
    values, rotations, queries = input().strip().split(' ')
    values, rotations, queries = [int(values), int(rotations), int(queries)]
    tmp_list = [int(n) for n in input().strip().split(' ')]
    rotable_list = ListRotationWrapper(tmp_list)
    rotable_list.rotate(rotations)
    # Final step, query the resulting array's indexes
    for _ in range(queries):
        index = int(input().strip())
        print(rotable_list[index])


if __name__ == "__main__":
    main()

Hope that helps.

Answer 2

I'd recommend that you try to find a way to make rotate_left a list comprehension. This is as it'll be simpler than you have now, and removes an if. So I'd assume it to be faster too.

To do this you invert rotate_right, in both the indexing and the range. To get:

return [array[rotate_by - i] for i in range(len(array), 0, -1)]

But other than that your code seems pretty good. I personally would merge both rotate_right and rotate_left into one function rotate.

The biggest downside is it's \$O(n)\$ not \$O(k)\$, where \$n\$ is the size of the array, and \$k\$ is how much you want to rotate by. Which is OK in this challenge, as you mostly want \$O(1)\$ indexing.

I'd also change how you change values to numbers, currently you're manually doing it, when you can use map. And by using unpacking as you are with split.

values, rotations, queries = map(int, input().strip().split(' '))

---

As this is a programming challange I'd assume you don't want to use collections.deque. (Gotta love batteries included!) But going forward it would be better than your algorithm in other situations, performance wise. This is as it's an efficient double ended queue. And so you can get queue.rotate(1) to be \$O(1)\$ and queue.rotate(k) to be \$O(k)\$. Rather than it being based on the size of queue.

This can make your testing main:

from collections import deque

def main() -> None:
    # Testing code
    arr = deque([1,2,3,4,5,6,7,8])
    rotate_by = 1
    print('Input array:', arr)
    print('Rotate by:', rotate_by)
    arr_L = arr_R = arr
    print('Rotate left:')
    for _ in range(len(arr)):
        arr_L.rotate(-rotate_by)
        print(arr_L)
    print('Rotate right:')
    for _ in range(len(arr)):
        arr_R.rotate(rotate_by)
        print(arr_R)