This code first iterates through a list nums
, updating counts of integers 0, 1, 2, also called red, white, and blue respectively. nums
is guaranteed to only have the integers 0, 1, and/or 2. After finding the counts, the code uses [::]
, a trick to modify a list in-place, to sort nums
.
def sortColors(self, nums: List[int]) -> None:
red = white = blue = 0
for num in nums:
match num:
case 0:
red += 1
case 1:
white += 1
case 2:
blue += 1
# [::] to modify nums in-place - Space O(1)
nums[::] = ([0] * red) + ([1] * white) + ([2] * blue)
return nums
I thought ([0] * red) + ([1] * white) + ([2] * blue)
would be evaluated before modifying nums, meaning that list would have to be created and stored in memory before nums[::] =
can proceed. To me, this makes sense, since in Python the right side of =
is evaluated before variable assignment, which makes things like x = x + 1
work. So, under this understanding, at this point in the code, both the original nums
list and the new list would be stored in memory. Because the new list will be the same length as nums
, O(n) additional space is needed.
However, an analyzer tool said this code was O(1) space. The only thing I can think of is that the moment nums[::] =
is called, the code ignores the original contents of nums and modifies nums in-place to the new list.
How is this O(1) space, and is my understanding of space complexity and variable assignment correct?