move-zeroes

Difficulty: Easy  ·  Topic: Two Pointers  ·  Practice it on parikshan: /practice/move-zeroes/start

The story

Tesla's Autopilot perception pipeline produces a fixed-size buffer of detected obstacles each frame. Some slots are real obstacles (positive distance readings); others are zero, the slot was reserved but the detector found nothing. Downstream planners only care about real obstacles in their detection order; zeros are noise. The buffer is reused frame-to-frame so it cannot be reallocated, and the order of real readings carries time-of-arrival semantics. The task: push the zeros to the end in place, keeping the non-zero values in their original relative order.

That is move-zeroes. It is the un-sorted cousin of remove-duplicates-from-sorted-array, same write-pointer trick, different predicate.

What's actually being asked

Given an integer array nums, move every 0 to the end while keeping the relative order of the non-zero elements unchanged. The output is the transformed array printed on a single line.

The naive approach

Build a new array of non-zeros, then pad with zeros: nums = [x for x in nums if x != 0] + [0] * nums.count(0). O(n) time, O(n) space. Correct, but trashes the in-place hint.

Another wrong approach: scan, and on every zero shift the rest of the array left. O(n²). Times out at n = 10^5 if zeros are dense.

The key insight

Keep a write pointer that points at the next slot a non-zero value should land in. Sweep a read pointer left to right. Whenever the read pointer finds a non-zero, swap it with the write slot and advance the write pointer.

Because the write pointer never overtakes the read pointer (write <= read always), the swap always exchanges a non-zero value at read with a zero (or an earlier non-zero that has already been placed) at write. After the full sweep, the first write slots hold the non-zero values in original order, and the rest hold the zeros that got swapped to the tail.

This is the same slow/fast skeleton as remove-duplicates, but the predicate is "is this value non-zero?" instead of "is this value different from the last accepted?".

Step-by-step approach

1. Initialise write = 0.
2. For read from 0 to n - 1:
   • If nums[read] != 0:
     • Swap nums[read] with nums[write].
     • Increment write.
3. Print nums as space-separated values.

A micro-optimisation: skip the swap when read == write (which happens during a run of non-zeros at the start). It avoids redundant self-swaps but is not necessary for correctness.

Worked example

nums = [0, 1, 0, 3, 12]
n = 5

Output: 1 3 12 0 0.

Notice that the non-zero values appear in their original order (1, 3, 12), and the zeros end up at the tail.

Complexity

• Time: O(n). One pass, with one swap per non-zero value.
• Space: O(1).

For n = 10^5 this is a few microseconds in Python. Comfortable under the 2-second budget.

Common pitfalls

• Advancing write even when nums[read] is zero. Then the invariant breaks; you copy zeros into the prefix.
• Writing instead of swapping. A bare nums[write] = nums[read] keeps the array's multiset but drops a value if you forget to zero the slot at read afterwards. Use swap.
• Two-pass version: pull all non-zeros forward, then pad with zeros. Works but does double the work and stops being in place in spirit (it's still in place by language pedantry).
• Sorting the array. Throws away the relative order of non-zero values; that order is the whole point.
• Treating negatives as zero. Read the spec: the predicate is nums[read] != 0, not nums[read] > 0.

Where this shows up in the enterprise

• Tesla Autopilot / Waymo perception: in-place compaction of obstacle buffers per frame.
• NVIDIA Triton inference: collapsing skipped batch slots before the next kernel launch.
• Stripe Radar: a sorted run of risk events where some slots are placeholder; compact the real ones forward.
• Spotify recommendations: per-user candidate lists where some positions are vetoed by policy; collapse the survivors.
• AWS Lambda batch invocation: pre-allocated buffer of S3 event records, some are duplicates that get masked to zero (sentinel) by an earlier filter and need to be moved out.
• Google Maps directions API: a route polyline buffer where some waypoints are removed by simplification; compact remaining points forward to keep the buffer dense.
• Datadog log filtering: in a fixed-size shipping buffer, drop sentinel-marked lines while preserving order of survivors.

The pattern is: in-place compaction of a buffer by a predicate, preserving order. The write-pointer trick is the standard answer in any system where the buffer is reused frame-to-frame.

Variants you'll see elsewhere

• remove-duplicates-from-sorted-array: predicate is "different from last accepted", input is sorted.
• remove-element: same shape, predicate is "not equal to target value".
• partition-array-into-disjoint-intervals: harder partition predicate.
• sort-array-by-parity: partition into even and odd; same write-pointer with a swap.
• sort-colors: three-way version using Dutch National Flag.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

1. The editor runs your code against public tests for instant feedback and against per-session dynamic private tests (generated freshly per session). Synthetic cases include all-zero arrays, no-zero arrays, single-element arrays, and arrays where the zeros are clustered at the start, end, or both.
2. Hints are graduated. Level 1 nudges to "next slot for a non-zero". Level 4 gives you the full swap recipe.
3. The AI training assistant in exam mode offers Explain, Review, Find Bugs, Add Comments, Optimise, each at an integrity cost. In practice mode AI chat is free.
4. The dispute flow runs after the verdict. The most common dispute here: "my output is right but in a different order". The order is the answer, non-zeros must appear in original relative order. Read the spec.

Read this concept, attempt in practice mode, take a hint only when stuck, then redo in exam mode. When the slow/fast write-pointer is muscle memory, every in-place compaction problem feels the same.

In the AI-integrated workspace

In your future job, the agent writes the code. Your job is to:

1. Recognise the write-pointer pattern any time you see "in place" plus "preserve order" plus "filter or move". The recognition is the skill.
2. Tell the agent precisely: "two pointers, write trails read, swap on non-zero, advance write". Not "move zeros to the end", that gets you a wasteful two-pass version.
3. Read the generated code and verify: order is preserved (no sort), the operation is a swap (not an overwrite), and the buffer is mutated in place.
4. Push the edge cases the agent will miss: empty input (n=0 if allowed), single-element, all zeros, all non-zeros, and arrays that already have all zeros at the tail (the algorithm should still produce the right output, possibly with redundant swaps).

Candidates who recognise the write-pointer pattern in five seconds turn agents into leverage. Candidates who can't end up approving an allocation-heavy two-pass that ignores the spec's in-place hint. parikshan is built to train the first kind.