2
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I don't understand this s %= len(array), your comment isn't helping clarify it for me either. \$\endgroup\$ – Clever Programmer Oct 11 '16 at 14:55
  • \$\begingroup\$ That is the modulus operator (the remainder of the division), so it is saying "what is the remainder of split_amount / the length of the array?" This is the amount to actually shift the "array." \$\endgroup\$ – JakeD Oct 11 '16 at 17:04
  • \$\begingroup\$ Similar to s += 2 which is the same as s = s + 2, s %= 2 is the same as s = s % 2. \$\endgroup\$ – JakeD Oct 11 '16 at 17:20
  • \$\begingroup\$ Oh no, I totally understand the use of the augmented assignment operator. That is not confusing me. I am trying to understand why we are doing it and how it helps us. Also, what does the '11 --> 1' part mean in your comment. \$\endgroup\$ – Clever Programmer Oct 12 '16 at 2:27
  • \$\begingroup\$ @CleverProgramer Oh sorry, I said that if the size of the array is 5, and the shift amount is 11, the array will be the same if shifted 11 times as if shifted 1 time (multiples of 5, or whatever the size of the array is, will leave you with the same exact array). \$\endgroup\$ – JakeD Oct 12 '16 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.