How do you approach Move Zeroes?

Use two pointers: one for iterating and one for the position of the next non-zero element.

What is the time complexity of Move Zeroes?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Move Zeroes?

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample. Moving both pointers on a match when only one should move, which steps over valid pairs. Choosing left < right where left <= right is meant. The first never examines the middle element.

Sitelet https://gitgood.dev/coding/move-zeroes

gitGood.dev

← Back to problems

Move Zeroes

EasyAlgorithms

Description

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note: You must do this in-place without making a copy of the array.

Example 1

Input: nums = [0,1,0,3,12]

Output: [1,3,12,0,0]

Example 2

Input: nums = [0]

Output: [0]

Constraints

- 1 <= nums.length <= 10^4 - -2^31 <= nums[i] <= 2^31 - 1

Move Zeroes: approach, complexity and pitfalls

An easy two pointers problem, graded against 6 test cases (3 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

If you are stuck

Show the 3-step hint ladder

Use two pointers: one for iterating and one for the position of the next non-zero element.
When you find a non-zero element, swap it with the element at the insertion position.
The key insight is that all elements before the insertion pointer are non-zero.

The optimal approach

Show the approach: Two Pointers

Use a slow pointer to track the position where the next non-zero should go, and a fast pointer to scan through the array.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.