2

I'm working on a leetcode problem where you rotate an array.

"Given an array, rotate the array to the right by k steps, where k is non-negative."

In the solution I'm trying, I slice the array, getting the last k elements and the first n-k elements. This is stored in a tuple, then assigned to the first k elements and last n-k elements, respectively (code shown below).

Is this solution O(1) time and O(1) space, or does the slicing operation and tuple/simultaneous assignment have extra time/space costs that I'm not aware of?

def rotate(self, nums: List[int], k: int) -> None:

    k = k% len(nums)

        if k>0:
    nums[:k],nums[k:] = nums[-k:], nums[:-k]
Joyce Lee
  • 378
  • 3
  • 9

1 Answers1

1

As said here Big-O of list slicing , array slicing in Python is not in O(1) since it's backed by an array behind.

Your algorithm would therefore be in O(k) since you read k elements 2 times and write k elements 2 times to your array.

Sunny Pelletier
  • 329
  • 2
  • 13
  • 1
    That's really helpful, thanks. I think it would actually be O(n) since I would be slicing k elements and n-k elements, and I suppose the space complexity would be O(n) for that reason as well. – Joyce Lee Aug 13 '19 at 20:42