class Solution(object): def sortColors(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ i = 0 length = len(nums) while (i < length): if nums[i] == 0: nums.insert(0, nums[i]) del nums[i + 1] i = i + 1 elif nums[i] == 2: nums.append(nums[i]) del nums[i] length = length - 1 else: i = i + 1
Is this really o(N) in time? I think
del nums[i] is an o(N) operation, which would make sense as list does not allow random access of elements. Also, though
append is o(1), is
insert(i, sth) o(N) due to the same reason?