Move Zeros to End

Intuition

To ideate a solution for the problem, store the non-zero numbers separately and then place those elements back into the original array. This ensures that all the non-zero numbers are kept at the front of the array. Lastly, fill the remaining positions in the array with zeros.

Approach

Declare a temporary array to store all the non-zero elements. Traverse the original array and copy all non-zero elements to the temporary array.

Overwrite the original array's starting positions with the elements from the temporary array.

Fill the remaining positions in the original array with zeros.

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to move zeroes to the end
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();

        /*Create a temporary array to 
         store non-zero elements*/
        vector<int> temp;

        for (int i = 0; i < n; i++) {
            // Copy non-zero elements to temp
            if (nums[i] != 0) {
                temp.push_back(nums[i]);
            }
        }

        // Number of non-zero elements
        int nz = temp.size();

        for (int i = 0; i < nz; i++) {
            // Copy non-zero elements back to nums
            nums[i] = temp[i];
        }

        for (int i = nz; i < n; i++) {
            // Fill the rest with zeroes
            nums[i] = 0;
        }

    }
};

int main() {
    vector<int> nums = {1, 0, 2, 3, 2, 0, 0, 4, 5, 1};

    //Create an instance of Solution class
    Solution sol;

    sol.moveZeroes(nums);

    cout << "Array after moving zeroes: ";
    // Print the modified array
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }

    return 0;
}
import java.util.*;

class Solution {
    // Function to move zeroes to the end
    public void moveZeroes(int[] nums) {
        int n = nums.length;

        // Create a temporary array to store non-zero elements
        int[] temp = new int[n];
        int count = 0;

        // Copy non-zero elements to temp
        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                temp[count++] = nums[i];
            }
        }

        // Copy non-zero elements back to nums
        for (int i = 0; i < count; i++) {
            nums[i] = temp[i];
        }

        // Fill the rest with zeroes
        for (int i = count; i < n; i++) {
            nums[i] = 0;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, 2, 3, 2, 0, 0, 4, 5, 1};

        // Create an instance of Solution class
        Solution sol = new Solution();
        sol.moveZeroes(nums);

        System.out.print("Array after moving zeroes: ");
        // Print the modified array
        System.out.println(Arrays.toString(nums));
    }
}
from typing import List

class Solution:
    # Function to move zeroes to the end
    def moveZeroes(self, nums: List[int]) -> None:
        n = len(nums)

        """Create a temporary array 
        to store non-zero elements"""
        temp = [0] * n
        count = 0

        # Copy non-zero elements to temp
        for i in range(n):
            if nums[i] != 0:
                temp[count] = nums[i]
                count += 1

        # Copy non-zero elements back to nums
        for i in range(count):
            nums[i] = temp[i]

        # Fill the rest with zeroes
        for i in range(count, n):
            nums[i] = 0

if __name__ == "__main__":
    nums = [1, 0, 2, 3, 2, 0, 0, 4, 5, 1]

    # Create an instance of Solution class
    sol = Solution()
    sol.moveZeroes(nums)

    print("Array after moving zeroes:", nums)
class Solution {
    // Function to move zeroes to the end
    moveZeroes(nums) {
        const n = nums.length;

        /* Create a temporary array
        to store non-zero elements*/
        const temp = new Array(n).fill(0);
        let count = 0;

        // Copy non-zero elements to temp
        for (let i = 0; i < n; i++) {
            if (nums[i] !== 0) {
                temp[count++] = nums[i];
            }
        }

        // Copy non-zero elements back to nums
        for (let i = 0; i < count; i++) {
            nums[i] = temp[i];
        }

        // Fill the rest with zeroes
        for (let i = count; i < n; i++) {
            nums[i] = 0;
        }
    }
}

// Test the code
const nums = [1, 0, 2, 3, 2, 0, 0, 4, 5, 1];

// Create an instance of Solution class
const sol = new Solution();
sol.moveZeroes(nums);

console.log("Array after moving zeroes:", nums);

Complexity Analysis

Time Complexity: O(2*N), O(N) for copying non-zero elements from the original to the temporary array. O(X) for again copying it back from the temporary to the original array. O(N-X) for filling zeros in the original array. Here N is the size of the array and X is the number of non-zero elements. Space Complexity: O(N), for using a temporary array to solve this problem and the maximum size of the array can be N in the worst case.

Intuition

Imagine having a row of empty(represented by 0) and non empty(espresented by non zero number) boxes on a conveyor belt. Given a task to move all the empty boxes to the end of the conveyor belt while keeping the order of the boxes with items intact.

To achieve this efficiently, you decide to use two workers (pointers) who will work together to sort the boxes. Here's how they do it:

Worker 1 starts at the beginning of the conveyor belt and is responsible for finding the empty boxes.
Worker 2 also starts at the beginning and will be used to keep track of where the next non-empty box should go. The process goes like this :

Worker 1 moves along the conveyor belt, checking each box. When Worker 1 finds a non-empty box, they swap it with the box at Worker 2's position.
After the swap, Worker 2 moves to the next position, ready to receive the next non-empty box.
Worker 1 continues to move down the conveyor belt, repeating the process until they have checked all the boxes.

By the end of this process, all the non-empty boxes will have been moved to the front of the conveyor belt in their original order, and all the empty boxes will have been moved to the end.

Approach

Start by taking two pointers, i and j & initialize j to -1. The pointer j will be used to track the position of the first zero in the array that we encounter.
Use a loop to move through the array and place the pointer j at the index of the first zero. If the array does not contain any zeros, exit early as no further steps are needed.
Set the pointer i to j + 1. This positions i right after the first zero found by j. From here, i will start moving through the rest of the array to find non-zero elements.
Now move non zero elements:

Continue looping through the array with i.
Whenever i encounters a non-zero element, swap the elements at positions i and j. This effectively moves the non-zero element to the position of the first zero.
After the swap, update j to point to the next zero in the array. This is done by incrementing j by 1.

Repeat the process until i has traversed the entire array. By the end of the loop, all non-zero elements will have been moved to the front of the array in their original order, and all zeros will be moved to the end.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j = -1; // Initialize j to -1
        int n = nums.size();

        // Find the first zero element's index
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                j = i;
                break;
            }
        }

        // If no zeros are found, return
        if (j == -1) return;

        // Move non-zero elements to the position of the first zero
        for (int i = j + 1; i < n; i++) {
            if (nums[i] != 0) {
                swap(nums[i], nums[j]);
                j++;
            }
        }
    }
};

int main() {
    vector<int> arr = {1, 0, 2, 3, 2, 0, 0, 4, 5, 1};

    // Create an instance of the Solution class
    Solution solution;

    // Call the moveZeroes function
    solution.moveZeroes(arr);

    // Print the elements
    for (auto &it : arr) {
        cout << it << " ";
    }
    cout << '\n';

    return 0;
}
class Solution {
    public void moveZeroes(int[] nums) {
        int j = 0; // Initialize j to 0

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }

        // Fill the remaining elements with zeros
        while (j < nums.length) {
            nums[j++] = 0;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 0, 2, 3, 2, 0, 0, 4, 5, 1};
        
        // Create an instance of the Solution class
        Solution solution = new Solution();
        
        // Modify the array in place
        solution.moveZeroes(arr);
        
        // Print the elements
        for (int it : arr) {
            System.out.print(it + " ");
        }
        System.out.println();
    }
}
from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        j = -1

       # length of nums
        n = len(nums)   
       
        # place the pointer j:
        for i in range(n):
            if nums[i] == 0:
                j = i
                break
        
        # no non-zero elements:
        if j == -1:
            return
        
        """Move the pointers i and 
              j and swap accordingly"""
        for i in range(j + 1, n):
            if nums[i] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                j += 1

# Example usage:
if __name__ == "__main__":
    arr = [1, 0, 2, 3, 2, 0, 0, 4, 5, 1]
    
    #Create an instance of Solution class
    solution = Solution()
    
    solution.moveZeroes(arr)
    
    # Print the modified array
    print(arr)
class Solution {
    moveZeroes(nums) {
        let j = -1;
       // length of nums
        const n = nums.length; 
        
        // place the pointer j:
        for (let i = 0; i < n; i++) {
            if (nums[i] === 0) {
                j = i;
                break;
            }
        }
        
        // no non-zero elements:
        if (j === -1) {
            return nums;
        }
        
        /* Move the pointers i and 
        j and swap accordingly*/
        for (let i = j + 1; i < n; i++) {
            if (nums[i] !== 0) {
                [nums[i], nums[j]] = [nums[j], nums[i]];
                j++;
            }
        }
        
        return nums;
    }
}

// Example usage:
const arr = [1, 0, 2, 3, 2, 0, 0, 4, 5, 1];

//Create an instance of the class
const solution = new Solution();

solution.moveZeroes(arr);

// Print the modified array
console.log(arr);

Complexity Analysis

Time Complexity: O(N), where N is size of the array, as we are traversing the array once. Space Complexity: O(1) , as no use of any extra space is done to solve this problem.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code