Reverse segments of the array, followed by the entire array
    T(n)- O(n)
    :type array: List[int]
    :type k: int
    :rtype: void Do not return anything, modify nums in-place instead.

def rotate_v2(array, k):
    """
    Reverse segments of the array, followed by the entire array
    T(n)- O(n)
    :type array: List[int]
    :type k: int
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    array = array[:]

    def reverse(arr, a, b):
        while a < b:
            arr[a], arr[b] = arr[b], arr[a]
            a += 1
            b -= 1

    n = len(array)
    k = k % n
    reverse(array, 0, n - k - 1)
    reverse(array, n - k, n - 1)
    reverse(array, 0, n - 1)
    return array