https://leetcode.com/problems/rotate-array

Very nice and interesting problem if we are asked to do it in place in linear time. Imagine, that we have number [1,2,3,4,5,6,7,8] and we have k = 3, then what is expected from us is [6,7,8,1,2,3,4,5]. Let us note, that a lot of structure in our list kept the same. Let us reverse list and try to find some patterns: [6,7,8,1,2,3,4,5] [8,7,6,5,4,3,2,1] You see it? What we need to do know is reverse first 3 elements and to reverst last 5 elements and this is all! It seems very easy, but in fact if you never used similar trick, it is very difficult to think, why we need to inverse arrays in the first place.

Complexity: time complexity is O(n), because in whole we change elements 2n times. Space complexity is O(1), because we do it in place.

class Solution:
    def rotate(self, nums, k):
        def inverse(i, j):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i + 1, j - 1
        
        n = len(nums)
        k = k % n
        inverse(0, n-1)
        inverse(0, k-1)
        inverse(k, n-1)
        return nums

If you like the solution, you can upvote it on leetcode discussion section: Problem 0189