BigBinary Academy

DSA using JavaScript

Lesson

5.5Move zeros to end

Move All Zeroes to the End

Problem Statement

Given an array, move all zeroes to the end while maintaining the relative order of the non-zero elements.

Sample Test Case

Input

Array: [1, 0, 2, 0, 3]

Output

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

Approaches

Brute Force Approach

Idea

We can use an additional array to store non-zero elements and append zeros later.

Steps

Create an empty array.
Traverse the original array and append non-zero elements to the new array.
After traversing the array, count the zeros in the original array.
Append the counted number of zeros to the end of the new array.

Time Complexity

O(n) where n is the number of elements in the array (two passes over the array).

Space Complexity

O(n) due to the use of an additional array of the same size as the input array.

Example Code

Dry Run

Input: [1, 0, 2, 0, 3]
After collecting non-zero elements: [1, 2, 3]
Append zeros: [1, 2, 3, 0, 0]

Efficient Approach

Idea

Use two pointers to move non-zero elements in-place and fill the remaining space with zeros.

Steps

Initialize a pointer pos = 0 to track the position of non-zero elements.
Traverse the array:
- If the current element is non-zero, swap it with the element at index pos and increment pos.
After the loop, set all remaining positions after pos to zero.

Time Complexity

O(n), where n is the number of elements in the array (single pass over the array).

Space Complexity

O(1), since no extra space is used except for a few variables.

Example Code

Dry Run

Input: [1, 0, 2, 0, 3]
Step 1: After the first swap: [1, 0, 2, 0, 3]
Step 2: After second swap: [1, 2, 0, 0, 3]
Step 3: After third swap: [1, 2, 3, 0, 0]

Example Test Case

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

Complexity Analysis

Brute Force Approach

Time Complexity: O(n) (Two passes over the array)
Space Complexity: O(n) (Extra space for the result array)

Efficient Approach

Time Complexity: O(n) (Single pass over the array)
Space Complexity: O(1) (In-place with constant extra space)

Conclusion

The brute force approach is easier to understand and implement but requires extra space.
The efficient approach optimizes space usage and is more suitable for larger arrays.