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,1,0,3,12]
Output: [1,3,12,0,0]

Note:

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

Approach

  1. For simple solution, we can do by introducing one variable zeroCount which traverse the nums array and counts how many zero’s are present in the array.
public class Solution {
    public void MoveZeroes(int[] nums) {
        int len = nums.Length;
        int zeroCount = 0;
        foreach(int num in nums) 
            zeroCount = (num == 0) ? zeroCount+1 : zeroCount;
        int index = 0;
        for(int i=0;i<len;i++){
            if(nums[i] != 0)
            {
                nums[index++] = nums[i];
            }
        }
        for(int i=0;i<zeroCount;i++)
            nums[index++] = 0;
    }
}

In the above solution, even though it looks efficient, it took two O(n) operations. So how can we reduce into one O(n) operation.

Look at the below solution to understand the Single traversal solution.

public class Solution {
    public void MoveZeroes(int[] nums) {
        int index = 0;
        int temp;
        
        for(int i=0;i<nums.Length;i++)
        {
            if(nums[i] != 0)
            {
                temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                index++;
            }
        }
    }
}

Time Complexity: O(n)

Space Complexity: O(1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s