[Python] ✅ In-Place Array Rotation || Fully explained from brute force to optimal space O(1)
Intuition\nWhen I first encountered the problem of rotating an array, my initial thought was to create a new array to store the rotated elements. This seemed li
# Intuition\nWhen I first encountered the problem of rotating an array, my initial thought was to create a new array to store the rotated elements. This seemed like a straightforward approach, where I could directly place each element into its new position. I thought of using an extra array (`output`) where the elements of the original array (`nums`) could be repositioned based on the rotation count `k`. The idea was to calculate the new index for each element and then copy them back to `nums`.\n\n# Approach\nMy initial approach involved using a new array to temporarily hold the rotated values. I calculated the new index for each element in `nums`, taking into account the rotation count `k`. After populating the `output` array with the rotated elements, I copied these values back into the original `nums` array. However, this approach didn\'t modify `nums` in-place as required. I then learned about a more efficient technique, which involved reversing parts of the array. This approach begins by reversing the entire array, then reversing the first `k` elements, and finally reversing the remaining elements. This method cleverly utilizes the properties of reversal to achieve the rotation without needing any extra space.\n\n# Complexity\n- Time complexity:\nThe time complexity is $$O(n)$$, as each element is accessed a constant number of times during the reversal process.\n\n- Space complexity:\nThe space complexity is $$O(1)$$, as the rotation is done in-place without using any additional storage proportional to the input size.\n\n# Code\n```python\nclass Solution:\n    def rotate(self, nums: List[int], k: int) -> None:\n        """\n        Do not return anything, modify nums in-place instead.\n        """\n        \n        def rev(l, r):\n            while l < r:\n                nums[l], nums[r] = nums[r], nums[l]\n                l += 1\n                r -= 1\n        \n        n = len(nums)\n        k %= n  # Handle cases where k > n\n        \n        rev(0, n-1)  # Reverse the entire array\n        rev(0, k-1)  # Reverse the first k elements\n        rev(k, n-1)  # Reverse the remaining elements\n
['Python3']