<jupyter_start><jupyter_text>Rotate Array<jupyter_code>import sys; sys.path.append('../..')
from puzzles import leet_puzzle
leet_puzzle('rotate-array')
n, k = 7, 4
example_array = list(range(n))
example_array<jupyter_output><empty_output><jupyter_text>Simple SolutionThe simplest solution splits the array at the point to rotate, and constructs a new array using the two parts.<jupyter_code>def rotate_simple(input_array, order):
    order %= len(input_array)
    return input_array[order:] + input_array[:order]

rotate_simple(example_array, k)
%%timeit
rotate_simple(example_array, k)<jupyter_output>The slowest run took 6.15 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 621 ns per loop<jupyter_text>This solution has both time and space complexity of O(n).  Bubble RotateHowever if we want to rotate a large array in place (without creating a new array), the solution above is inefficient. The time complexity is O(n), dependant only on the size of the input array, but the space complexity is also O(n) since we need to create a new array with the rotated elements. By applying a similar algorithm to bubble sort we can perform the rotation in place.<jupyter_code>def rotate_bubble_inplace(input_array, order):
    order %= len(input_array)
    for i in range(order):
        for j in range(len(input_array)):
            input_array[j], input_array[j - 1] = input_array[j - 1], input_array[j]
    return input_array
            
example_array2 = list(example_array)
rotate_bubble_inplace(example_array2, k)
%%timeit
rotate_bubble_inplace(example_array, k)<jupyter_output>100000 loops, best of 3: 8.46 µs per loop<jupyter_text>However, although the space complexity is now O(1), the time complexity is O(n * k). It would be good to find a solution that has O(1) space complexity and O(n) time complexity.  Reverse RotateAnother way of rotating the array is to split the array into two sub arrays at the point of rotation. Each subarray is reversed, before rotating the entire array. This solution achieves O(1) space complexity and O(n).<jupyter_code>def rotate_reverse_inplace(input_array, order):
    length = len(input_array)
    order = -order % length
    split_location = length - order
    input_array[:split_location] = reversed(input_array[:split_location])
    input_array[split_location:] = reversed(input_array[split_location:])
    input_array.reverse()
    return input_array

example_array2 = list(example_array)
rotate_reverse_inplace(example_array2, k)
%%timeit
rotate_reverse_inplace(example_array, k)<jupyter_output>The slowest run took 5.80 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 2.1 µs per loop
{'fraction_non_alphanumeric': 0.07581227436823104, 'fraction_numerical': 0.01696750902527076, 'mean_word_length': 5.240990990990991, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '506838', 'license': 'MIT', 'n_tokens_mistral': 876, 'n_tokens_neox': 817, 'n_words': 310, 'path': 'Array/Rotate Array.ipynb', 'repo_name': 'moagstar/puzzles', 'size': '2770'}