Time complexity of Array Slicing and Simultaneous Assignment

Question

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]

Sunny Pelletier · Accepted Answer · 2019-08-13 00:14:40Z

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.

answered Aug 13, 2019 at 0:14

Sunny Pelletier

3893 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Joyce Lee Over a year ago

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.

Collectives™ on Stack Overflow

Time complexity of Array Slicing and Simultaneous Assignment

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related