Move Zeroes

Problem Source: LeetCode
Companies: Facebook, Amazon, Apple, Google, Oracle, eBay, Walmart Labs

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,5,0,8,0,24]

Output: [5,8,24,0,0,0]

Note:

• You must do this in-place without making a copy of the array.
• Minimize the total number of operations.

Solution:

In this problem we have to move the non-zero elements to the front and all the zeroes to the end of the array. We also need to maintain the order of the non-zero elements.

We can solve this problem by taking two indexes and maintaining one according to our required condition and the other index will be used to interate the loop.

Let’s call this indexes as i and j. Starting with i = 0 and j = 0, iterate the loop with condition j < size of the array. Hence, j will be incremented everytime to traverse through the whole array. Now if the current element at index j is non-zero, we will perform swapping between elements at i and j and only then we increment the value of i by one and so on. This solution is an optimal solution for this problem.

Implementation:

Java:

class Solution {
    public void moveZeroes(int[] nums) {
         for (int i = 0, j = 0; j < nums.length; j++) {
                if (nums[j] != 0) {
                    int temp = nums[i];
                    nums[i++] = nums[j];
                    nums[j] = temp;
                }
            }
    }
}

You can implement this solution using other languages also with the same approach!

Complexity Analysis:

• Time Complexity: O(n).
• Space Complexity: O(1).