Rotate Array

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• Trick: Reverse array, then:
  • Reverse first k elements
  • Reverse last remaining elements
• This amounts to the same thing as rotating k times.

Todo

Explain this rotation business to someone else.

Complexity

Runtime

$O(N)$

Space

$O(1)$

Code

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        
        i = 0
        j = len(nums) - 1
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
        
        i = 0
        j = k - 1
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
        
        i = k
        j = len(nums) - 1
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

Notes

Cards

START Basic Front: Rotate Array Back: Reverse, reverse first k, reverse remaining

END

---

References

• Rotate Array