Lets Code Everyday - Day 23

Question - 23:

Move Zeroes

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [0]

First approach:

class Solution {
    public void moveZeroes(int[] nums) {
        List<Integer> nonZerosList = new ArrayList<>();
        List<Integer> zerosList = new ArrayList<>();
         for(int i=0;i<nums.length;i++){
            if(nums[i]!=0) nonZerosList.add(nums[i]);
            else zerosList.add(nums[i]);
         }

         nonZerosList.addAll(zerosList);

         for(int i=0;i<nonZerosList.size();i++){
             nums[i] = nonZerosList.get(i);
         } 
    }
}

Step-by-step implementation:

1. Create two new lists, nonZerosList and zerosList, to hold the non-zero and zero elements of the input array, respectively.

2. Traverse the input array nums using a for-loop, and add the non-zero elements to nonZerosList and the zero elements to zerosList.

3. Concatenate zerosList to the end of nonZerosList.

4. Traverse the concatenated list nonZerosList using a for-loop, and copy each element to the corresponding position in the input array nums.

5. The method moveZeroes() does not return anything, it only modifies the input array nums in place.

This code has an O(n) time complexity, where n is the size of the input array nums. This is because the input array is divided into two lists in a single pass by the code, and the concatenated list is then passed again to copy the contents back into nums.

The space complexity of this code is also O(n), because it creates two new lists of size at most n to hold the non-zero and zero elements of nums, respectively. Therefore, this implementation uses extra space proportional to the size of the input array.

Second approach:

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

Step-by-step implementation:

1. Initialize a variable index to 0, which will be used to keep track of the position where non-zero elements should be placed in the input array.

2. Traverse the input array nums using a for-loop, and for each element nums[i]:

   a. If nums[i] is not zero, copy it to the index position of nums, and increment index by 1. This ensures that all non-zero elements are moved to the beginning of the array, in their original order.

   b. If nums[i] is zero, do nothing.

   c. If index is not equal to i, this means that the current element nums[i] is a zero that was skipped in the previous step, so it should be replaced with a 0 at the current position i in the input array. This ensures that all zero elements are moved to the end of the array, in their original order.

3. The method moveZeroes() does not return anything, it only modifies the input array nums in place.

• Time complexity: O(n), where n is the length of the input array nums. The code performs a single pass over the input array, and each element is visited at most twice. Therefore, the time complexity is linear in the size of the input array.

• Space complexity: O(1), because the code only uses a constant amount of extra space to store the index variable. The input array is modified in place, so no additional space is used. Therefore, the space complexity is constant, regardless of the size of the input array.

Conclusion:

The Second approach to the problem is more efficient than the first one, because it only requires a single pass over the input array, and does not use any extra space to store the zero and non-zero elements separately.

Thanks for reading....Happy Learning 😁