Move Zeroes (opens in a new tab) Easy

Problem

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

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

Output: [1,3,12,0,0]

Summary

To solve this problem, we can iterate through the input array and use a pointer to keep track of the position for the next non-zero element to be placed. Whenever we encounter a non-zero element, we swap it with the element at the pointer's position and increment the pointer. This will effectively move all non-zero elements to the beginning while maintaining their relative order and pushing zeroes to the end.

Solution

In TypeScript

function moveZeroes(nums: number[]): void {
	let position = 0;
 
	for (let i = 0; i < nums.length; i++) {
		if (nums[i] !== 0) {
			[nums[position], nums[i]] = [nums[i], nums[position]];
			position++;
		}
	}
}

In Python

def moveZeroes(nums: List[int]) -> None:
		position = 0
 
		for i in range(len(nums)):
				if nums[i] != 0:
						nums[position], nums[i] = nums[i], nums[position]
						position += 1

Step-by-step explanation

1. We create a variable position and initialize it to 0. This variable represents the index at which the next non-zero element will be placed in the array.

let position = 0;

2. We use a for loop to iterate through the input array nums. For each element in the array, we do the following:

for (let i = 0; i < nums.length; i++) {
	// ...
}

3. We check if the current element nums[i] is not equal to 0. If it is not 0, it means we've encountered a non-zero element.

if (nums[i] !== 0) {
	// ...
}

4. We swap the current element nums[i] with the element at the position index. By doing this, we move the non-zero element towards the beginning of the array, while maintaining the relative order of the non-zero elements. We then increment the position variable, as the next non-zero element should be placed at the next index.

[nums[position], nums[i]] = [nums[i], nums[position]];
position++;

5. At this point, all non-zero elements have been moved to the beginning of the array, and all 0's have been moved to the end of the array while maintaining the relative order of the non-zero elements.

After executing this code, the input array nums will have been modified in-place, with all non-zero elements at the beginning and all 0's at the end while maintaining their relative order.

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array. We iterate through the input array once, swapping non-zero elements with elements at the pointer's position.

Space Complexity

The space complexity of this solution is O(1), as we are not using any additional data structures to store elements. We are only using a pointer to keep track of the position for the next non-zero element.