CODEWITHSUNDEEP
pythonarraystime-complexity
Joyce Lee
Joyce Lee

Reputation: 386

Time complexity of Array Slicing and Simultaneous Assignment

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]

Upvotes: 2

Views: 2404

Answers (1)

Sunny Pelletier
Sunny Pelletier

Reputation: 379

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.

Upvotes: 1

Related Questions