Move all zeroes to one end

© Parineeth M R

Question 21. Move all the zeroes in an array to the right end of the array


We can move all the zeroes to one end of the array (in this case, the right end) in O(n) using the following technique:

1. Scan for the first zero from the left side of the array.

2. Scan for the first non-zero from the right side of the array.

3. Swap the zero and non-zero provided that the zero appears to the left of the non-zero

C/C++


/*
a: input array in which the zeroes should be moved to one end
length: number of elements in array a 
*/
void move_zeroes(int a[], int length)
{
	int left, right;

	left = 0;
	right = length - 1;

	while (left < right) {
		/*Locate the first zero from the left*/
		while (left < length && a[left] != 0)
			left++;

		/*Locate first non-zero from the right*/
		while (right >= 0 && a[right] == 0)
			right--;

		if (left < right) {
			/*Swap a[left] and a[right]*/
			int temp = a[left];
			a[left] = a[right];
			a[right] = temp;
		}
	}
} 



Java


/*
a: input array in which the zeroes should be moved to one end
*/
public static void moveZeroes(int[] a) {
	int length = a.length;

	int left = 0;
	int right = length - 1;

	while (left < right) {
		/*Locate the first zero from the left*/
		while (left < length && a[left] != 0)
			left++;

		/*Locate first non-zero from the right*/
		while (right >= 0 && a[right] == 0)
			right--;

		if (left < right) {
			/*Swap a[left] and a[right]*/
			int temp = a[left];
			a[left] = a[right];
			a[right] = temp;
		}
	}
}



Python


#a: input list in which the zeroes should be moved to one end
def move_zeroes(a) :
	length = len(a)

	left = 0
	right = length - 1

	while (left < right) :
		#Locate the first zero from the left
		while (left < length and a[left] != 0):
			left += 1

		#Locate first non-zero from the right
		while (right >= 0 and a[right] == 0):
			right = right - 1

		if (left < right) :
			#Swap a[left] and a[right]
			a[left], a[right] = a[right], a[left]