Push Target Values Back
Problem
A playlist editor wants every copy of one song id moved to the end of the queue without shuffling anything else. Given a list nums and a value v, rearrange the list in place so that the elements different from v keep their original relative order at the front and every copy of v sits at the back. Return the same list object, and use only a constant amount of extra memory.
Examples
Input: nums = [4, 0, 7, 0, 2], v = 0
Output: [4, 7, 2, 0, 0]
Why: 4, 7 and 2 stay in the order they arrivedInput: nums = [3, 1, 3, 3, 5], v = 3
Output: [1, 5, 3, 3, 3]
Why: three copies of 3 collect at the backInput: nums = [], v = 9
Output: []
Why: edge case, there is nothing to moveHints
0 / 3
Building a second list of keepers and a second list of copies works, but the task asks for constant extra memory. Think about where the next keeper should land.
Use two indexes into the same list: one that reads every element, and one that marks the slot the next keeper will be written to.
Read left to right and copy each element that differs from v into the write slot, advancing the write index each time. Once the reader is done, fill every slot from the write index to the end with v.
Solution
The write index only moves when a keeper is copied, so it never overtakes the reader and no keeper is overwritten before it has been read. Copying in reading order preserves the relative order of the keepers for free. Every slot after the last keeper must hold a copy of v, because the number of copies equals the number of slots left over. Time is O(n) with one pass plus the fill, and space is O(1).
def push_back(nums, v):
write = 0 # slot for the next value we keep in front
for x in nums:
if x != v:
nums[write] = x # copy forward, order is preserved
write += 1
for i in range(write, len(nums)):
nums[i] = v # the leftover slots belong to v
return nums
print(push_back([4, 0, 7, 0, 2], 0)) # -> [4, 7, 2, 0, 0]
print(push_back([3, 1, 3, 3, 5], 3)) # -> [1, 5, 3, 3, 3]
print(push_back([], 9)) # -> []Stuck on the idea rather than the code? Move Zeroes covers it.