189. Rotate Array (Array, Math, Two Pointers)

링크 - https://leetcode.com/problems/rotate-array/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days

난이도 - Medium

Intuition

1) Cyclic Replacements

우리는 계속해서 값을 바꿔주는 식으로 이 문제를 풀 수 있다.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n

        start = count = 0
        while count < n:
            cur, prev = start, nums[start]
            while True:
                next_idx = (cur + k) % n
                nums[next_idx], prev = prev, nums[next_idx]
                cur = next_idx
                count += 1

                if start == cur:
                    break

            start += 1

Time Complexity: O(N) one pass

Space Complexity: O(1)

2) Reverse 3 times

우리는 3번의 reverse로 이 문제를 풀 수 있다. 먼저 전체 list를 뒤집는다. 그리고 앞의 k개의 list를 뒤집는다. 마지막으로 남은 list를 뒤집는다.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(arr, start, end):
            while start < end:
                arr[start], arr[end] = arr[end], arr[start]
                start += 1
                end -= 1

        n = len(nums)
        k %= n

        reverse(nums, 0, n-1)
        reverse(nums, 0, k-1)
        reverse(nums, k, n-1)

Time Complexity: O(N) 2 passes

Space Complexity: O(1)