CODEWITHSUNDEEP
pythonlist
Albert G Lieu
Albert G Lieu

Reputation: 911

list pop and insert are very slow in python

I am working on a leetcode question 189. Rotate Array.

Problem statement: Given an array, rotate the array to the right by k steps, where k is non-negative. Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4]

Following is my code. My understanding is that the time complexity is O(k), but it ends up being very low. Could you please shine some light on this and educate me?

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

Upvotes: 1

Views: 645

Answers (3)

Corralien
Corralien

Reputation: 120429

FYI, in the case you use numpy

import numpy as np

nums = [1, 2, 3, 4, 5, 6, 7]
k = 3

print(np.roll(nums, k).tolist())

# Output:
[5, 6, 7, 1, 2, 3, 4]

Upvotes: 0

Dani Mesejo
Dani Mesejo

Reputation: 61910

One approach is to use a deque rotate, as below

from collections import deque
from typing import List

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


nums = [1,2,3,4,5,6,7]
Solution().rotate(nums, 3)
print(nums)

Output

[5, 6, 7, 1, 2, 3, 4]

From the documentation (emphasis mine):

Rotate the deque n steps to the right. If n is negative, rotate to the left. When the deque is not empty, rotating one step to the right is equivalent to d.appendleft(d.pop()), and rotating one step to the left is equivalent to d.append(d.popleft()).

The problem with inserting at the beginning of a list is that it is O(n), you have to shift all the elements. In a deque inserting at the beginning (appendleft) is O(1).

For more details about the time complexity of deque and list, see here

Upvotes: 2

Daniel Hao
Daniel Hao

Reputation: 4980

Deque is great DS for this. Alternatively, you can try this: This got accepted and ranked 88% in Python category. (about the same speed as deque)

[Note] the length of list is 10^5. It asks for in-place ops.

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

Upvotes: 2

Related Questions