[Python] O(n) inplace solution, explained
Very nice and interesting problem if we are asked to do it in place in linear time. \nImagine, that we have number [1,2,3,4,5,6,7,8] and we have k = 3, then wha
Very nice and interesting problem if we are asked to do it in place in linear time. \nImagine, 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:\n`[6,7,8,1,2,3,4,5]`\n`[8,7,6,5,4,3,2,1]`\nYou 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.\n\n**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.\n\n```\nclass Solution:\n    def rotate(self, nums: List[int], k: int) -> None:\n        def inverse(i, j):\n            while i < j:\n                nums[i], nums[j] = nums[j], nums[i]\n                i, j = i + 1, j - 1\n        \n        n = len(nums)\n        k = k % n\n        inverse(0, n-1)\n        inverse(0, k-1)\n        inverse(k, n-1)\n        return nums\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]