283. Move Zeroes

• Link: https://leetcode.com/problems/move-zeroes/description/

Question

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

Note that you must do this in-place without making a copy of the array.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

Follow up: Could you minimize the total number of operations done?

Approach 1: Brute Force

Algorithm

1. Create a new vector for non zero value nonZero
2. Iterate through each element in nums using for loop & push non zero elements in nonZero
3. for loop till nonZero.size() replay all the elements of nums with nonZero
4. Loop through rest of the nums and replace with zeros

Code

class Solution {
public:
	void moveZeroes(vector<int>& nums) {
		vector<int> nonZeros;
		int n = nums.size();
		
		for (int i = 0 ; i < n ; i++) {
			if (nums[i] != 0) nonZeros.push_back(nums[i]);
		}
		
		int n2 = nonZeros.size();
		
		for (int i = 0 ; i < n2 ; i++) {
			nums[i] = nonZeros[i];
		}
		
		for (int i = n2 ; i < n ; i++) {
			nums[i] = 0;
		}
		
		return;
	}
};

Complexity Analysis

• Time Complexity: $O(3n)=O(n)$
  • 3 loops for worst case n elements
• Space Complexity: $O(n)$
  • new array (vector) for non-zeros worst case n elements

Approach 2: Better

Two Pointers DSA

Algorithm

1. Iterate through each element in the list (nums) except for the last one.
2. Check if the current element is zero:
   • If it is, start looking ahead (from the next position) to find the first non-zero element.
3. Find the nearest non-zero element:
   • Start at the next position (j = i + 1) and move forward until either:
     • You find a non-zero element.
     • You reach the end of the list.
4. Swap the zero with the non-zero element:
   • Once a non-zero element is found, swap it with the zero found at index i.
5. Repeat this process for each element in the list until all zeros are moved to the end, maintaining the order of the non-zero elements.

Code

class Solution {
public:
	void moveZeroes(vector<int>& nums) {
		for (int i = 0; i < nums.size() - 1; i++) {

			if (nums[i] == 0) {
				int j = i + 1;

				while (j < nums.size() && nums[j] == 0) {
					j++;
				}
				
				if (j < nums.size()) {
					swap(nums[i], nums[j]);
				}
			}
		}
	}
};

Complexity Analysis

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

Approach 3: Optimal

Algorithm

1. Initialize a lastNonZeroFountAt int with 0
2. Loop through the nums
   1. Replace the nums[nonZeroIndex] with non-zero elements
   2. Increment the nonZeroIndex after every replacement only
3. From the last nonZeroIndex to the end of the nums vector replace the elements with 0

Code

class Solution {
public:
	void moveZeroes(vector<int>& nums) {
		int nonZeroIndex = 0;

		// Move all non-zero elements to the front
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] != 0) {
				nums[nonZeroIndex++] = nums[i];
			}
		}

		// Fill the remaining elements with zeroes
		for (int i = nonZeroIndex; i < nums.size(); i++) {
			nums[i] = 0;
		}
	}

Complexity Analysis

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