Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Two pointers

Move the zeros to the end

Easy · Target 10 minutes · Two pointers

Given an integer array nums, move every 0 to the end while keeping the other values in their original relative order. Do it in place with O(1) extra memory, and return the array.

Examples

InputOutputWhy
nums = [0, 1, 0, 3, 12][1, 3, 12, 0, 0]
nums = [4, 2, 7][4, 2, 7]No zeros: nothing moves.

Constraints

  • 1 ≤ n ≤ 10⁴
  • −2³¹ ≤ nums[i] ≤ 2³¹ − 1

Hints

Hint 1

Copying the non-zero values to a new array and padding with zeros is easy. How would you do it in the same array?

Hint 2

Keep a write position w: the next non-zero value goes there. Read the array from left to right.

Hint 3

Swap each non-zero value into position w and advance w. The zeros drift right as values are swapped past them.

Where people lose marks

  • Swapping adjacent zeros with each other repeatedly, which is O(n²) for an input such as many zeros followed by values.
  • Using a partition that does not keep order (swapping with the far end): the non-zero values come out scrambled.
Console⌘/Ctrl + Enter runs

Write a solution and run it against the real test table.


Keep going

Preparing for a real process? Quant interview preparation, or book a free 20-minute call.