-2

So I know popping an element from an an array is O(n) since you have to shift all the elements over by one. BUT, what if you popped an element AND appended that same element to the back of the array, all in one line. Would this be constant operation O(1) since you don't have to shift anything? Please see my code below with the comment.

def moveZeroes(self, nums: List[int]) -> None:
        index = 0
        zeroes = nums.count(0)
        counter = 0
        while True:
            if counter == zeroes:
                break
            if nums[index] == 0:
                nums.append(nums.pop(index))  # THIS LINE RIGHT HERE
                counter += 1
            else:
                index += 1
SamuelP
  • 175
  • 2
  • 2
  • 8
  • 3
    "since you don't have to shift anything" - why do you think you don't have to shift anything? – user2357112 Mar 16 '21 at 04:46
  • 2
    list.pop() pops from the end and is O(1) because you don't have to shift anything. You just change the length. list.pop(anything-but-the-end) is O(n). Remember, however, that a list only contains references. You're not moving huge objects. – Tim Roberts Mar 16 '21 at 04:50
  • 2
    Even though it's in the same line, the element will be popped first and then will be appended. So the time complexity will be the same. – soumith Mar 16 '21 at 04:51
  • It seems an old question: https://stackoverflow.com/questions/195625/what-is-the-time-complexity-of-popping-elements-from-list-in-python/46136638 – Glauco Mar 16 '21 at 07:41

1 Answers1

1

  1. When you pop any element using its index, you make at most len(array) shifts to reduce the length by 1.

  2. You can append an element into an array in O(1) time complexity.

However, when you call nums.append(nums.pop(index)). It will first do step 1 and then do step 2. So overall, you still do O(n) operations.

vinni3000
  • 46
  • 3