Question: This code (a solution to this LeetCode challenge) 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(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)  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, LeetCode's analyzer 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?

Answer: Your assessment that the code you've shown takes O(n) extra space to temporarily build a new list with the sorted values is correct. It's possible to do a counting sort like this in O(1) space, but the code to implement it in Python is just a little more complicated: def sortColors(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 assert len(nums) == red+white+blue for i in range(len(nums)): nums[i] = (i >= red) + (i >= red+white) # note: bool+bool->int  This will use only O(1) extra memory, since only the red, white and blue counters take up space beyond the starting nums list. Note that a lot of other, more Pythonic styles of programming are likely to allocate O(n) temporary memory in the background, at least in some situations. For example, if you assign an itertools.repeat iterator to a slice (e.g. nums[:red] = itertools.repeat(0, red)), you won't consume O(n) memory directly in the same way as the original code (since the iterator takes only constant memory), but the slice assignment will dump the iterator into a temporary list in the background so that it can know if it needs to resize the list (it doesn't, but it can't know that in advance). Similarly, if you clear() the list and then extend() it with itertools.repeat iterators, the resizing logic of the list might temporarily consume O(n) extra memory as it copies the list items into a larger section of memory (thanks to user no comment who pointed this out in the comments). I'd also note that list.sort is probably faster for most reasonable lengths of list, even though its asymptotic complexity is worse than your code's counting sort! Having a very well written implementation in C is a big advantage! Of course, it probably does allocate at least some extra memory (probably O(n) space in the worst case, but I haven't checked).