Move Zeroes

🎯

Move Zeroes

easyTWO_POINTERFacebookAmazonMicrosoft

Imagine organizing a shelf where all empty boxes (zeroes) need to be moved to the end without disturbing the order of the other items.

💡 This problem is a classic example of using two pointers moving in the same direction to rearrange elements in-place. Beginners often struggle because they try to remove and append zeroes separately, which is inefficient and can break the order of non-zero elements.

📋

Problem Statement

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. You must do this in-place without making a copy of the array.

1 ≤ nums.length ≤ 10^5-2^31 ≤ nums[i] ≤ 2^31 - 1

💡

Example

Input"[0,1,0,3,12]"

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

All zeroes are moved to the end, and the order of non-zero elements (1,3,12) is preserved.

• All elements are zero → output is the same array
• No zero elements → array remains unchanged
• Single element array with zero → array remains the same
• Single element array with non-zero → array remains the same

⚠️

Common Mistakes

Swapping zero with itself unnecessarily

Unnecessary operations that slow down the algorithm

✅ Only swap when current index is different from lastNonZeroFoundAt

Not maintaining relative order of non-zero elements

Output array has non-zero elements in wrong order, failing correctness

✅ Use two-pointer approach that moves non-zero elements forward in order

Using extra space when problem requires in-place

Interviewer rejects solution due to extra memory usage

✅ Implement in-place two-pointer approach without auxiliary arrays

Forgetting to fill zeroes after moving non-zero elements

Trailing elements remain unchanged, causing incorrect output

✅ After placing all non-zero elements, fill remaining positions with zeroes

Modifying array while iterating in a way that skips elements

Some elements are not processed, leading to incorrect results

✅ Use separate pointers and careful iteration to avoid skipping

🧠

Brute Force (Using Extra Array)

💡 This approach is straightforward and helps beginners understand the problem by separating zero and non-zero elements explicitly, though it uses extra space.

Intuition

Create a new array and first copy all non-zero elements, then fill the rest with zeroes. This clearly separates the problem into two steps.

Algorithm

1. Create a new array of the same size as nums.
2. Traverse nums and copy all non-zero elements to the new array in order.
3. Fill the remaining positions in the new array with zeroes.
4. Copy the new array back to nums.

💡 This algorithm is easy to visualize but uses extra space, which is not optimal but helps build intuition.

</>

Code

def moveZeroes(nums):
    n = len(nums)
    temp = [0]*n
    index = 0
    for num in nums:
        if num != 0:
            temp[index] = num
            index += 1
    for i in range(n):
        nums[i] = temp[i]

# Driver code
if __name__ == "__main__":
    arr = [0,1,0,3,12]
    moveZeroes(arr)
    print(arr)

Line Notes

n = len(nums)Store length to avoid repeated calls and for clarity.

temp = [0]*nInitialize a new array filled with zeroes to hold the result.

for num in nums:Traverse original array to find non-zero elements.

if num != 0:Check to filter out zero elements.

temp[index] = numPlace non-zero elements in order in the new array.

index += 1Move to next position for next non-zero element.

for i in range(n):Copy back all elements from temp to original array.

nums[i] = temp[i]Overwrite original array to meet in-place requirement.

import java.util.Arrays;
public class MoveZeroes {
    public static void moveZeroes(int[] nums) {
        int n = nums.length;
        int[] temp = new int[n];
        int index = 0;
        for (int num : nums) {
            if (num != 0) {
                temp[index++] = num;
            }
        }
        for (int i = 0; i < n; i++) {
            nums[i] = temp[i];
        }
    }
    public static void main(String[] args) {
        int[] arr = {0,1,0,3,12};
        moveZeroes(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Line Notes

int n = nums.length;Store array length for iteration limits.

int[] temp = new int[n];Create auxiliary array initialized with zeroes.

for (int num : nums)Enhanced for loop to iterate over elements.

if (num != 0)Filter non-zero elements to copy first.

temp[index++] = num;Place non-zero elements sequentially in temp.

for (int i = 0; i < n; i++)Copy back to original array to satisfy problem constraints.

nums[i] = temp[i];Overwrite original array elements.

#include <iostream>
#include <vector>
using namespace std;
void moveZeroes(vector<int>& nums) {
    int n = nums.size();
    vector<int> temp(n, 0);
    int index = 0;
    for (int num : nums) {
        if (num != 0) {
            temp[index++] = num;
        }
    }
    for (int i = 0; i < n; i++) {
        nums[i] = temp[i];
    }
}
int main() {
    vector<int> arr = {0,1,0,3,12};
    moveZeroes(arr);
    for (int num : arr) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

int n = nums.size();Get size of vector for iteration.

vector<int> temp(n, 0);Initialize temp vector with zeroes.

for (int num : nums)Range-based for loop to iterate elements.

if (num != 0)Select non-zero elements to copy first.

temp[index++] = num;Assign non-zero elements sequentially.

for (int i = 0; i < n; i++)Copy back to original vector.

nums[i] = temp[i];Overwrite original vector elements.

function moveZeroes(nums) {
    const n = nums.length;
    const temp = new Array(n).fill(0);
    let index = 0;
    for (const num of nums) {
        if (num !== 0) {
            temp[index++] = num;
        }
    }
    for (let i = 0; i < n; i++) {
        nums[i] = temp[i];
    }
}
// Driver code
const arr = [0,1,0,3,12];
moveZeroes(arr);
console.log(arr);

Line Notes

const n = nums.length;Store length for iteration and clarity.

const temp = new Array(n).fill(0);Create new array filled with zeroes.

for (const num of nums)Iterate over original array elements.

if (num !== 0)Filter non-zero elements to copy first.

temp[index++] = num;Place non-zero elements sequentially.

for (let i = 0; i < n; i++)Copy back to original array to meet problem constraints.

nums[i] = temp[i];Overwrite original array elements.

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the array twice: once to copy non-zero elements and once to copy back, each O(n). Extra space of O(n) is used for the temporary array.

💡 For n=100,000 elements, this means about 200,000 operations and extra memory for 100,000 elements, which is inefficient for large inputs.

Interview Verdict: Accepted but not optimal

This approach works but uses extra space, which is not ideal in interviews where in-place solutions are preferred.

🧠

Two Pointers (In-Place, Swap Non-Zero Elements)

💡 This approach introduces the two-pointer technique to solve the problem in-place without extra space, improving efficiency and meeting interview constraints.

Intuition

Use one pointer to track the position to place the next non-zero element, and another to scan through the array. Swap non-zero elements forward.

Algorithm

1. Initialize a pointer 'lastNonZeroFoundAt' to 0.
2. Traverse the array with index 'current'.
3. When nums[current] is non-zero, swap it with nums[lastNonZeroFoundAt] and increment lastNonZeroFoundAt.
4. Continue until the end of the array.

💡 This algorithm maintains the relative order of non-zero elements by swapping them forward as soon as they are found.

</>

Code

def moveZeroes(nums):
    lastNonZeroFoundAt = 0
    for current in range(len(nums)):
        if nums[current] != 0:
            nums[lastNonZeroFoundAt], nums[current] = nums[current], nums[lastNonZeroFoundAt]
            lastNonZeroFoundAt += 1

# Driver code
if __name__ == "__main__":
    arr = [0,1,0,3,12]
    moveZeroes(arr)
    print(arr)

Line Notes

lastNonZeroFoundAt = 0Tracks the position to place the next non-zero element.

for current in range(len(nums))Iterate over all elements to find non-zero values.

if nums[current] != 0Check if current element is non-zero to move forward.

nums[lastNonZeroFoundAt], nums[current] = nums[current], nums[lastNonZeroFoundAt]Swap non-zero element to the front position.

lastNonZeroFoundAt += 1Increment position for next non-zero element.

import java.util.Arrays;
public class MoveZeroes {
    public static void moveZeroes(int[] nums) {
        int lastNonZeroFoundAt = 0;
        for (int current = 0; current < nums.length; current++) {
            if (nums[current] != 0) {
                int temp = nums[lastNonZeroFoundAt];
                nums[lastNonZeroFoundAt] = nums[current];
                nums[current] = temp;
                lastNonZeroFoundAt++;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {0,1,0,3,12};
        moveZeroes(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Line Notes

int lastNonZeroFoundAt = 0;Pointer to place next non-zero element.

for (int current = 0; current < nums.length; current++)Traverse array to find non-zero elements.

if (nums[current] != 0)Check for non-zero elements to move forward.

int temp = nums[lastNonZeroFoundAt];Temporary variable for swapping.

nums[lastNonZeroFoundAt] = nums[current];Place non-zero element at correct position.

nums[current] = temp;Complete the swap.

lastNonZeroFoundAt++;Move pointer forward for next placement.

#include <iostream>
#include <vector>
using namespace std;
void moveZeroes(vector<int>& nums) {
    int lastNonZeroFoundAt = 0;
    for (int current = 0; current < nums.size(); current++) {
        if (nums[current] != 0) {
            swap(nums[lastNonZeroFoundAt], nums[current]);
            lastNonZeroFoundAt++;
        }
    }
}
int main() {
    vector<int> arr = {0,1,0,3,12};
    moveZeroes(arr);
    for (int num : arr) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

int lastNonZeroFoundAt = 0;Tracks where to place next non-zero element.

for (int current = 0; current < nums.size(); current++)Iterate over all elements.

if (nums[current] != 0)Identify non-zero elements to move forward.

swap(nums[lastNonZeroFoundAt], nums[current]);Swap current non-zero with position at lastNonZeroFoundAt.

lastNonZeroFoundAt++;Increment pointer for next non-zero placement.

function moveZeroes(nums) {
    let lastNonZeroFoundAt = 0;
    for (let current = 0; current < nums.length; current++) {
        if (nums[current] !== 0) {
            [nums[lastNonZeroFoundAt], nums[current]] = [nums[current], nums[lastNonZeroFoundAt]];
            lastNonZeroFoundAt++;
        }
    }
}
// Driver code
const arr = [0,1,0,3,12];
moveZeroes(arr);
console.log(arr);

Line Notes

let lastNonZeroFoundAt = 0;Pointer for next non-zero element placement.

for (let current = 0; current < nums.length; current++)Traverse array elements.

if (nums[current] !== 0)Check for non-zero elements.

[nums[lastNonZeroFoundAt], nums[current]] = [nums[current], nums[lastNonZeroFoundAt]];Swap elements using destructuring assignment.

lastNonZeroFoundAt++;Move pointer forward after placing non-zero.

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array with constant extra space. Swapping elements in-place avoids extra memory.

💡 For n=100,000, this means about 100,000 operations and no extra memory, making it efficient and scalable.

Interview Verdict: Accepted and optimal for in-place requirement

This is the preferred approach in interviews because it meets all constraints efficiently.

🧠

Two Pointers (Overwrite Non-Zero, Fill Zeroes After)

💡 This approach separates the process into two phases: first overwrite non-zero elements at the front, then fill the rest with zeroes, which is simpler and avoids unnecessary swaps.

Intuition

Use one pointer to overwrite non-zero elements in order, then fill the remaining positions with zeroes.

Algorithm

1. Initialize a pointer 'lastNonZeroFoundAt' to 0.
2. Traverse the array, and whenever a non-zero element is found, write it at lastNonZeroFoundAt and increment lastNonZeroFoundAt.
3. After traversal, fill all remaining positions from lastNonZeroFoundAt to end with zeroes.

💡 This method avoids swapping by overwriting and then filling zeroes, which can be more intuitive.

</>

Code

def moveZeroes(nums):
    lastNonZeroFoundAt = 0
    for num in nums:
        if num != 0:
            nums[lastNonZeroFoundAt] = num
            lastNonZeroFoundAt += 1
    for i in range(lastNonZeroFoundAt, len(nums)):
        nums[i] = 0

# Driver code
if __name__ == "__main__":
    arr = [0,1,0,3,12]
    moveZeroes(arr)
    print(arr)

Line Notes

lastNonZeroFoundAt = 0Pointer to place next non-zero element.

for num in nums:Traverse all elements to find non-zero values.

if num != 0:Filter non-zero elements to overwrite at front.

nums[lastNonZeroFoundAt] = numOverwrite element at lastNonZeroFoundAt with non-zero.

lastNonZeroFoundAt += 1Increment pointer for next placement.

for i in range(lastNonZeroFoundAt, len(nums))Fill remaining positions with zeroes.

nums[i] = 0Set zero at current position.

import java.util.Arrays;
public class MoveZeroes {
    public static void moveZeroes(int[] nums) {
        int lastNonZeroFoundAt = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[lastNonZeroFoundAt++] = num;
            }
        }
        for (int i = lastNonZeroFoundAt; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
    public static void main(String[] args) {
        int[] arr = {0,1,0,3,12};
        moveZeroes(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Line Notes

int lastNonZeroFoundAt = 0;Pointer for next non-zero element placement.

for (int num : nums)Iterate over all elements.

if (num != 0)Filter non-zero elements to overwrite.

nums[lastNonZeroFoundAt++] = num;Overwrite element and increment pointer.

for (int i = lastNonZeroFoundAt; i < nums.length; i++)Fill remaining positions with zeroes.

nums[i] = 0;Set zero at current index.

#include <iostream>
#include <vector>
using namespace std;
void moveZeroes(vector<int>& nums) {
    int lastNonZeroFoundAt = 0;
    for (int num : nums) {
        if (num != 0) {
            nums[lastNonZeroFoundAt++] = num;
        }
    }
    for (int i = lastNonZeroFoundAt; i < nums.size(); i++) {
        nums[i] = 0;
    }
}
int main() {
    vector<int> arr = {0,1,0,3,12};
    moveZeroes(arr);
    for (int num : arr) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

int lastNonZeroFoundAt = 0;Pointer to place next non-zero element.

for (int num : nums)Traverse all elements.

if (num != 0)Filter non-zero elements.

nums[lastNonZeroFoundAt++] = num;Overwrite element and increment pointer.

for (int i = lastNonZeroFoundAt; i < nums.size(); i++)Fill remaining elements with zeroes.

nums[i] = 0;Set zero at current index.

function moveZeroes(nums) {
    let lastNonZeroFoundAt = 0;
    for (const num of nums) {
        if (num !== 0) {
            nums[lastNonZeroFoundAt++] = num;
        }
    }
    for (let i = lastNonZeroFoundAt; i < nums.length; i++) {
        nums[i] = 0;
    }
}
// Driver code
const arr = [0,1,0,3,12];
moveZeroes(arr);
console.log(arr);

Line Notes

let lastNonZeroFoundAt = 0;Pointer for next non-zero element placement.

for (const num of nums)Iterate over all elements.

if (num !== 0)Filter non-zero elements.

nums[lastNonZeroFoundAt++] = num;Overwrite element and increment pointer.

for (let i = lastNonZeroFoundAt; i < nums.length; i++)Fill remaining positions with zeroes.

nums[i] = 0;Set zero at current index.

⏱

Complexity

TimeO(n)

SpaceO(1)

Two passes over the array: one to overwrite non-zero elements, one to fill zeroes, both O(n). No extra space used.

💡 For n=100,000, this means about 200,000 operations but no extra memory, which is efficient and easy to implement.

Interview Verdict: Accepted and optimal

This approach is often preferred for its simplicity and clarity while maintaining optimal time and space.

📊

All Approaches - One-Glance Tradeoffs

💡 The two-pointer in-place approaches (Approach 2 and 3) are best for interviews due to optimal time and space. The brute force approach is useful for initial understanding but not recommended to code.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Extra Array)	O(n)	O(n)	No	N/A	Mention only - never code
2. Two Pointers (Swap In-Place)	O(n)	O(1)	No	N/A	Preferred approach to code
3. Two Pointers (Overwrite and Fill Zeroes)	O(n)	O(1)	No	N/A	Also preferred; simpler to implement

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then move to optimal in-place solutions. Practice coding and explaining each step clearly.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach using extra space for clarity.Discuss the inefficiency and introduce the two-pointer in-place approach.Code the optimal solution carefully, explaining each step.Test with edge cases and explain the time and space complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer checks your problem understanding, ability to optimize space, and code correctness. They also test if you can handle edge cases and explain your approach clearly.

Common Follow-ups

• What if you need to move all zeroes to the front instead?
• How would you modify the solution if you cannot swap elements?
• Can you solve this problem if the array is immutable?
• What if you want to move all occurrences of a given number to the end?

💡 These follow-ups test your adaptability and understanding of the two-pointer technique beyond the basic problem.

🔍

Pattern Recognition

When to Use

1) Need to rearrange elements in an array in-place; 2) Problem mentions moving or partitioning elements; 3) Maintaining relative order is required; 4) Zero or a special value needs to be moved to one side.

Signature Phrases

move all 0's to the endmaintain relative orderin-place rearrangement

NOT This Pattern When

Problems that require sorting or random access without in-place rearrangement are different patterns.

Similar Problems

Sort Colors - similar partitioning with three categoriesPartition Array - general partitioning based on a pivot

Practice

1. You are given two strings that may contain the backspace character '#'. After processing all backspaces, you need to determine if the resulting strings are equal. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Sort both strings after removing backspaces and then compare them.

B. Use a brute force approach by building the final strings with stacks and then compare them.

C. Use dynamic programming to track the state of each character after backspaces.

D. Use two pointers starting from the end of both strings, simulating backspaces on the fly without extra space.

Solution

1. Step 1: Understand the problem constraints

   The problem requires comparing two strings after applying backspace operations, which can be done efficiently by simulating the effect of backspaces without reconstructing the entire string explicitly.

2. Step 2: Identify the optimal approach

   Using two pointers from the end of both strings allows skipping characters affected by backspaces on the fly, achieving O(n + m) time and O(1) extra space, which is optimal compared to building stacks or using DP.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two pointers from the end simulate backspaces efficiently [OK]

Hint: Two pointers from end simulate backspaces efficiently [OK]

Common Mistakes:

• Assuming DP is needed for backspace processing
• Using sorting which changes character order
• Building full strings with stacks uses extra space

2. You are given two sorted arrays, where the first array has enough space at the end to hold all elements of the second array. You need to merge them into one sorted array in-place without using extra space. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Sort the combined elements after copying both arrays into a new array.

B. Use two pointers starting from the end of both arrays and merge in-place from the back.

C. Use a two-pointer approach starting from the front and merge into a new array.

D. Use a greedy approach by always picking the smaller element from the front of both arrays.

Solution

1. Step 1: Understand the problem constraints

   The first array has extra space at the end to hold all elements of the second array, allowing in-place merging.

2. Step 2: Identify the optimal approach

   Starting from the end with two pointers avoids overwriting unprocessed elements and achieves O(m+n) time with O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers from the back merge without extra space [OK]

Hint: Merge from the back to avoid overwriting [OK]

Common Mistakes:

• Merging from the front overwrites elements
• Sorting combined array wastes time

3. What is the time complexity of the optimal one-pass Dutch National Flag algorithm for sorting colors, and why might some candidates mistakenly think it is higher?

medium

A. O(n log n) because it involves multiple swaps and pointer movements

B. O(n) but with O(n) extra space for auxiliary arrays

C. O(n^2) because swapping elements can cause repeated scanning

D. O(n) because each element is visited at most once with constant-time swaps

Solution

1. Step 1: Analyze loop iterations

   The algorithm uses three pointers and processes each element at most once, moving mid pointer forward or swapping with high pointer.

2. Step 2: Understand why complexity is O(n)

   Each swap or pointer move is O(1), and total operations are proportional to n, so time complexity is O(n). Candidates may confuse swaps causing repeated scans, but high pointer moves backward, ensuring no element is processed twice.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Algorithm is linear time with constant space [OK]

Hint: Each element processed once, swaps don't repeat work [OK]

Common Mistakes:

• Thinking swaps cause O(n^2)
• Confusing with quicksort complexity
• Assuming extra space needed

4. Suppose now the second array nums2 can contain negative numbers and the first array nums1 has no extra space at the end. Which of the following approaches correctly merges nums2 into nums1 while maintaining sorted order?

hard

A. Create a new array of size m+n, merge nums1 and nums2 into it, then copy back to nums1.

B. Use the two-pointer backward in-place merge as before, ignoring extra space constraints.

C. Sort nums1 and nums2 separately, then concatenate and sort the combined array.

D. Use a two-pointer forward approach merging into nums1 in-place without extra space.

Solution

1. Step 1: Understand constraints

   nums1 has no extra space at the end, so in-place backward merge is impossible.

2. Step 2: Identify correct approach

   Using extra space to merge into a new array and then copying back is necessary to maintain sorted order.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Extra space is required when nums1 lacks buffer space [OK]

Hint: No extra space in nums1 means new array needed [OK]

Common Mistakes:

• Trying in-place merge without space
• Sorting combined array wastes time

5. Suppose the array is not sorted and you want to remove duplicates in-place with O(1) extra space. Which modification to the two-pointer approach is correct?

hard

A. Scan the array multiple times with nested loops to remove duplicates.

B. Use two pointers without sorting, comparing elements directly to remove duplicates.

C. Use a hash set to track duplicates and overwrite duplicates in-place.

D. Sort the array first, then apply the two-pointer approach.

Solution

1. Step 1: Understand constraints

   Two-pointer approach relies on sorted array to detect duplicates in one pass.

2. Step 2: Identify correct modification

   Sorting first ensures duplicates are adjacent, enabling two-pointer removal in O(n log n) time and O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting enables two-pointer approach on unsorted input [OK]

Hint: Two-pointer requires sorted array; sort first if unsorted [OK]

Common Mistakes:

• Trying two-pointer without sorting
• Using extra space violating constraints