array-rotation.py

'''
extracted from leetcode: https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/646/
Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]


Constraints:

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105


Follow up:

Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with O(1) extra space?
'''


# I aimed directly for the fastest and most memory efficient solution by modifiying the array in place

'''Complexity O[1]'''


class Solution:
    def rotate(nums, k):
        """
        Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        nums[:] = nums[-k:]+nums[:-k]


def test():
    nums = [1, 2, 3, 4, 5, 6, 7]
    k = 3
    sol = [5, 6, 7, 1, 2, 3, 4]
    Solution.rotate(nums, k)
    print("expected " + str(sol))
    print("obtained " + str(nums))


if __name__ == "__main__":
    test()