0

the question on leetcode says "Given an array, rotate the array to the right by k steps, where k is non-negative." for example "Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4]"

My solution in python was:

def rotate(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: None Do not return anything, modify nums in-place instead.
    """
    i = 0
    while (i < k):
        nums.insert(0, nums.pop())
        i+=1

This does not seem to match any of the given solutions. I am curious what the time/space complexity of this would be? Is that why this is not a given solution? OR is it best to not use array functions in tech interviews?

Thanks

Sabrina White
  • 11

2 Answers2

0

Heres on example of cut list in python, not sure if this is the solution you are looking for. Where you take the list at index k to the length of the list. So in this case its 3 to 6 and you take beginning of list 0 to 2 and you take the first part of the list and you add it to the end of the list by amount of k.

nums[k:length] = [4,5,6,7]
nums[0:k] = [1,2,3]`

def rotate(nums, k):
    
    length = len(nums)
    nums[:] = nums[k:length] + nums[0:k]
    print(nums)
        
number = [1,2,3,4,5,6,7]
rotate(number,3)

Here is a link to some other explantions.

https://www.geeksforgeeks.org/python-program-for-program-for-array-rotation-2/

ruthless
  • 309
  • 3
  • 13
0

insert will internally copy all the consequent n-1 elements by 1 for each iteration. Hence, your code is of time complexity O(nk) as Paul said. Thus, even though it answers the question, it is too inefficient for a large array. Instead, you could use array slicing, which is of time complexity O(N).

def rotate_to_right(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: None Do not return anything, modify nums in-place instead.
    """
    d = len(nums) - k
    nums[:]=nums[d:]+nums[:d]

if __name__ == '__main__':
    nums = [1,2,3,4,5,6,7]
    k = 3
    rotate_to_right(nums, k)
    print(nums)

Result:

[5, 6, 7, 1, 2, 3, 4]
abysslover
  • 683
  • 5
  • 14