[LeetCode Solution] 189. Rotate Array

Problem Description

Rotate Array

Rotate the elements of a list by k.

Solution

Approach

For the input list [1,2,3,4,5,6,7] and k=3, a simple approach is to iterate through the list and shift each element i by k positions. However, a problem arises in cases like:

123456   k=2

In this case, if we shift by k positions, we end up with:

123456
  1
    3
5
  1 
    3    

Here, we jump k positions and cycle through the same elements. To address this, I introduced a variable init to record the starting point of the cycle and incremented i when it returns to the initial point. This helps prevent cycling through the same elements.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        # If the length of the array is equal to k, return nums
        # If the length of the array is 1, return the array as it is
        if len(nums) == k or len(nums) == 1:
            return nums
        
        i = 0
        init = i
        before = nums[i-(k%len(nums))]
        cnt = 1
        while cnt <= len(nums):
            # If a full cycle is completed and there are remaining elements, increment i by 1
            if i == init and cnt != 1: 
                i += 1
                init += 1
                before = nums[i-(k%len(nums))]
            temp = nums[i]
            nums[i] = before
            before = temp
            i = (i+k)%len(nums)
            cnt += 1

The time complexity and space complexity of this solution are as follows:

• Time Complexity: O(N)
  • As the loop iterates through nums, the time complexity is O(N).
• Space Complexity: O(1)
  • No additional space is used.