HackerRank: Left Array Rotation in Python

Question

Here is the problem on HackerRank. I want to know how I can improve this code. I am mainly trying to improve the following skills: Documentation, functional programming (top-down approach), accurately estimating Big O Complexity, Space Complexity, doc-testing, and readable code.

Sometimes I feel that my code is simply too clustered with documentation, so I am not sure how much or how little to add. Should I write param in my documentation how I have it written? Can I improve my space/time complexity for this algorithm? I tried to focus on changing the list in place so as not to increase the space complexity. Is my estimate of O(2N) correct for my main array_left_rotation() function?

If I want to write about the worst case complexity, is how I wrote it the correct way to write it and is that where I am supposed to write it?

The mysterious no return functions and other funky stuff under the main function are the courtesy of HackerRank. Just in case you want to view it on Github

I wish to improve code style, space/time complexity analysis, and readability.

"""
Author: Rafeh Qazi
Program: Array Left Rotation (Hackerrank Challenge)
Modified: October 2016
Submit this code at: https://www.hackerrank.com/challenges/ctci-array-left-rotation
"""


def array_left_rotation(int_list, shift):
    """
    Given an array of n integers and a number, d, perform d left rotations on the array.
    Then print the updated array as a single line of space-separated integers.
    :param int_list: list
    :param shift: int

    Worst Case Time Complexity: O(2N)

    Worse Case Space Complexity: O(N)

    >>> array_left_rotation([1, 2, 3, 4, 5], 1)
    2 3 4 5 1

    >>> array_left_rotation([2, 3, 4, 5, 1], 3)
    5 1 2 3 4
    """
    pairs = new_index_value_pairs(int_list, shift)
    replace_int_list(int_list, pairs)
    print(*int_list, sep=' ')


def new_index_value_pairs(int_list, shift):
    """
    Create a list of shifted index and value tuples.
    :param int_list: list
    :param shift: int
    :return: list

    Worst Case Complexity: O(N)

    >>> new_index_value_pairs([10, 20, 30], 1)
    [(2, 10), (0, 20), (1, 30)]
    """
    return [((index - shift) % len(int_list), value) for index, value in enumerate(int_list)]


def replace_int_list(int_list, pairs):
    """
    Map the the shifted index value pairs onto the original int_list.
    :param int_list: list
    :param pairs: list

    Worst Case Complexity: O(N)

    >>> int_list = [10, 20, 30]
    >>> replace_int_list(int_list, [(0, 20), (1, 30), (2, 10)])
    >>> int_list
    [20, 30, 10]
    """
    for index, value in pairs:
        int_list[index] = value


if __name__ == '__main__':
    import doctest

    doctest.testmod()
    _, shift = map(int, input().strip().split())
    int_list = list(map(int, input().strip().split()))
    array_left_rotation(int_list, shift)

Update: I am aware of the deque data structure from collections module in Python. However, I wanted to challenge myself.

Answer 1

This is the easiest way I can think of to do a "shift" on a list in Python:

def shift_list(array, s):
    """Shifts the elements of a list to the left or right.

    Args:
        array - the list to shift
        s - the amount to shift the list ('+': left-shift, '-': right-shift)

    Returns:
        shifted_array - the shifted list
    """
    # calculate actual shift amount (e.g., 11 --> 1 if length of the array is 5)
    s %= len(array)

    # uncomment this line to reverse the shift direction
    # s *= -1

    # shift array with list slicing
    shifted_array = array[s:] + array[:s]

    return shifted_array

my_array = [1, 2, 3, 4, 5]

# negative numbers
shift_list(my_array, -7)
>>> [4, 5, 1, 2, 3]

# no shift on numbers equal to the size of the array
shift_list(my_array, 5)
>>> [1, 2, 3, 4, 5]

# works on positive numbers
shift_list(my_array, 3)
>>> [4, 5, 1, 2, 3]

If you need this to shift backwards (to the left) with negative numbers, add the following to the beginning of the shift list function:

s *= -1

I think the above documentation is sufficient to describe everything without being too wordy.

I have added this to the Stack Overflow Python docs.