[leetcode] 189. Rotate Array

Question

One array that contains the only integer, and one integer named "k" are given. you should rotate the array by the point of k and return it.

• 189. Rotate Array

Solution

I came up with two ideas. One is to get the last element by using the "pop" function and insert it from the left of the array. And repeat this operation by k times.

Second is to divide the given array by the number that subtracts k from the length of the given array. And swap those divided arrays and return it.

Submission

Here is the result of my idea.

Runtime: 64 ms, faster than 56.95% of Python3 online submissions for Rotate Array.
Memory Usage: 15.4 MB, less than 5.09% of Python3 online submissions for Rotate Array.

Time complexity: O(n)
Space complexity: O(n)

Some people might think it seems like that time complexity and space complexity are gonna be O(1). However, Insert is O(n) in time because when inserting the element at first index, the rest of the elements are shifted to the right each. Besides, it is necessary to store a previous array list to shift before insertion. So, both are O(n).

I think array[:i] is the same logic.

• Python Time complexity

Here is my python code

def rotate(self, nums: List[int], k: int) -> None:
    # # first solution - O(n) in time, O(n) in space
    # insert is not O(1). https://wiki.python.org/moin/TimeComplexity
    # for _ in range(k):
    #     nums.insert(0, nums.pop())

    # second solution - O(n) in time, O(n) in space
    i = len(nums) - k
    nums[:] = nums[i:] + nums[:i]

https://github.com/nk18chi/leetcode/blob/master/solutions/rotate_array/index.py