Category: Arrays

Rotate an array

admin / / Arrays, Data Structures

© Parineeth M R

Question 22. Rotate an array by k times

Consider the array {10, 20, 30, 40, 50}. Suppose we rotate the array once, we have to move the elements 10, 20, 30, 40 right by 1 position and move the last element 50 to the beginning to get {50, 10, 20, 30, 40}. So if we have an array of size n, then for 1 rotate operation we will need n moves. If we rotate the array k times then there will be k*n moves. There is a faster method for rotating an array. Let the array be A = {10, 20, 30, 40, 50} and the number of rotations k = 2. The procedure is:

1. Reverse the entire array. So we get {50, 40, 30, 20, 10}

2. Reverse the array in the region 0 to k -1. If k = 2, we reverse the region A[0] to A[1]. So we get the array {40, 50, 30, 20, 10}

3. Finally reverse the array in the region k to n-1 where n is the length of the array. If k=2, we reverse the region A[2] to A[4]. So we get the required result {40, 50, 10, 20, 30}.

With this technique, we always need 2*n moves irrespective of the value of k.

C/C++


/*Main function to rotate a 1 dimensional array
a: array which should be rotated. 
length: number of elements in the array. Should be > 0
num_rotations: how many times to rotate the array. Should be >= 0
*/
void rotate_array(int a[], int length, int num_rotations)
{
	/*Suppose an array has a length of 5, every time we rotate by 5 
	locations, we end up with the same array. So obtain num_rotations 
	value from 0 to length - 1*/
	num_rotations = num_rotations % length;

	if (num_rotations == 0)
		return;

	reverse_array(a, 0, length - 1);

	reverse_array(a, 0, num_rotations - 1);

	reverse_array(a, num_rotations, length - 1);
}

Java


/*Main function to rotate a 1 dimensional array
a: array which should be rotated. 
numRotations: how many times to rotate the array. Should be >= 0
*/
public static void rotateArray(int[] a, int numRotations) {
	int length = a.length;
	if (length == 0)
		return;

	/*Suppose an array has a length of 5, every time we rotate by 
	5 locations, we end up with the same array. So obtain numRotations 
	value from 0 to length - 1*/
	numRotations = numRotations % length;

	if (numRotations == 0)
		return;

	reverseArray(a, 0, length - 1);

	reverseArray(a, 0, numRotations - 1);

	reverseArray(a, numRotations, length - 1);
}

Python


#Main function to rotate a 1 dimensional list
#a: list which should be rotated. 
#num_rotations: how many times to rotate the list. Should be >= 0
def rotate_list(a, num_rotations) :
	length = len(a)
	if (length == 0):
		return

	#Suppose a list has a length of 5, every time we rotate by 
	#5 locations, we end up with the same list. So obtain num_rotations 
	#value from 0 to length - 1
	num_rotations = num_rotations % length

	if (num_rotations == 0):
		return

	reverse_list(a, 0, length - 1)

	reverse_list(a, 0, num_rotations - 1)

	reverse_list(a, num_rotations, length - 1)


#Helper function which reverses a list in region (low, high)
#a: list which needs to be reversed
#low: lower index of region to be reversed
#high: higher index of region to be reversed
def reverse_list(a, low, high) :
	while (low < high) :
		a[low], a[high] = a[high], a[low]
		low += 1
		high = high - 1

Move all zeroes to one end

admin / / Arrays, Data Structures

© 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]

Remove all duplicates from an array

admin / / Arrays, Data Structures

© Parineeth M R

Question 20. Given an array, remove all the duplicates from the array

Suppose the given array is A = {1, 4, 2, 1, 5, 2} and we have to remove all duplicates from it, then the result array is {1, 4, 2, 5}. All duplicates in an array A can be removed using the following approaches

1. Brute force approach. Pick every element in A and remove all the duplicates of that element. Removing all duplicates of one element can be done in O(n). Since we have to do this for n elements, the time complexity will be O(n2) and no extra space is needed

2. Hash table approach. Traverse the elements in A and add the elements to a hash table. If we encounter an element which is already in the hash table, then we exclude it from the result. The time complexity is O(n) but we will need extra space for the hash table.

3. Sorting. Sort the array A. After sorting, the duplicates will be arranged next to each other. Then iterate through the sorted array and retain an element in A only if it is different from the previous element. We will be using this approach in the code below. The time complexity is O(nlog(n)) and we don’t need additional space.

C/C++


/*
a: non-empty array from which duplicates should be removed. 
	this array will be modified in-place
length: number of elements in array a 
Returns: number of elements in array a after removing duplicates 
*/
int remove_duplicates(int a[], int length)
{
	int i, fill_pos;

	/*Sort the array*/
	sort(a, length);

	fill_pos = 1;
	for (i = 1; i < length; ++i) {
		if (a[i] != a[i - 1]) {
			a[fill_pos] = a[i];
			fill_pos++;
		}
	}

	return fill_pos;
}

Java


/*
a: non-empty input array from which duplicates should be removed. 
	this array will be modified
Returns: new output array which doesn't have duplicates 
*/
public static int[] removeDuplicates(int[] a) {
	int length = a.length;

	/*Sort the array*/
	Arrays.sort(a);

	int fillPos = 1;
	for (int i = 1; i < length; ++i) {
		if (a[i] != a[i - 1]) {
			a[fillPos] = a[i];
			fillPos++;
		}
	}

	int[] result = Arrays.copyOf(a, fillPos);
	return result;
}

Python


#a: non-empty input list from which duplicates should be removed. 
#	this list will be modified in-place
def remove_duplicates(a) :
	length = len(a)

	#Sort the list
	a.sort()

	fill_pos = 1
	for  i in range(1, length):
		if (a[i] != a[i - 1]) :
			a[fill_pos] = a[i]
			fill_pos += 1

	#remove the remaining items in the list from fill_pos onwards
	if (fill_pos < length):		
		del a[fill_pos:]

Remove all occurrences of an element from an array

admin / / Arrays, Data Structures

© Parineeth M R

Question 19. Given an array, remove all occurrences of an element from the array

Suppose the given array is A = {1, 4, 2, 1, 5, 2} and we have to remove all occurences of 1 from it, then the result array is {4, 2, 5, 2}. The element to be removed from the array can be present in multiple locations. We can efficiently remove all occurrences of the element in O(1) space and O(n) time in a single pass through the array by doing the following:

1. Maintain a variable called fill_pos to keep track of where we should store the next element of the array that should not be deleted. Initialize fill_pos to 0.

2. Traverse through the array. If the current element in the array should be deleted then skip it. If current element in the array should not be deleted, then store the current element at fill_pos in the array and increment fill_pos

C/C++


/*
a: input array from which all occurrences of an element should be removed
length: number of elements in array a 
x: element to be removed
Return value: number of elements in a after removing x 
*/
int remove_element(int a[], int length, int x)
{
	int i, fill_pos;

	fill_pos = 0;
	for (i = 0; i < length; ++i) {
		if (a[i] != x) {
			a[fill_pos] = a[i];
			fill_pos++;
		}
	}

	return fill_pos;
}

Java


/*
a: input array from which all occurrences of an element should be removed
x: element to be removed
Return value: output array after removing x 
*/
public static int[] removeElement(int[] a, int x) {
	int fillPos = 0;
	for (int i = 0; i < a.length; ++i) {
		if (a[i] != x) {
			a[fillPos] = a[i];
			fillPos++;
		}
	}

	int[] result = Arrays.copyOf(a, fillPos);
	return result;
}

Python


#a: input list from which all occurrences of an element should be removed
#x: element to be removed
def remove_element(a, x) :
	length = len(a)
	fill_pos = 0
	for  i in range(0, length):
		if (a[i] != x) :
			a[fill_pos] = a[i]
			fill_pos += 1
	
	#delete all the elements from fill_pos onwards	
	if (fill_pos < length) :
		del a[fill_pos:]

Replace each element with next greatest

admin / / Arrays, Data Structures

© Parineeth M R

Question 18. Replace each element in an array with the next greatest

Consider the array A = {0, 2, 8, 1, 3, 5, 4}.

The greatest number after 0 in A is maximum of {2, 8, 1, 3, 5, 4} = 8. So 0 is replaced by 8.

The greatest number after 8 in A is maximum of {1, 3, 5, 4} = 5. So 8 is replaced with 5.

4 is the last number in A. There are no more elements to its right. So 4 is replaced by an invalid number or the smallest possible number.

So the resulting array is = {8, 8, 5, 5, 5, 4, INVALID_NUMBER}.

The brute force approach will try to compute the next greatest of an element by scanning all the elements to its right. This will have a time complexity of O(n2).

However we can achieve the same in O(n) by traversing from the end of the array to the beginning and maintaining the maximum element seen so far. The code is given below

C/C++


/*
a: array in which each element should be replaced with next greatest
n: number of elements in the array. n >= 1
*/
void replace_with_next_greatest(int a[], int n) {
	int i, next_greatest, temp;

	next_greatest = a[n-1];
	a[n-1] = INVALID_NUMBER;  

	/*Process the array from backwards*/
	for (i = n-2; i >= 0; --i) {
		temp = a[i];

		a[i] = next_greatest;

		if (temp > next_greatest)
			next_greatest = temp;
	}
}

Java


/*
a: non-empty array in which each element should be replaced with next greatest
*/
public static void replaceWithNextGreatest(int[] a) {
	int n = a.length;
	int nextGreatest = a[n-1];
	a[n-1] = INVALID_NUMBER;  

	/*Process the array backwards*/
	for (int i = n-2; i >= 0; --i) {
		int temp = a[i];

		a[i] = nextGreatest;

		if (temp > nextGreatest)
			nextGreatest = temp;
	}
}

Python


#a: non-empty list in which each element should be replaced with next greatest
def replace_with_next_greatest(a) :
	n = len(a)

	next_greatest = a[n-1]
	a[n-1] = INVALID_NUMBER  

	#Process the list from the back
	for i in range(n-2, -1, -1) :
		temp = a[i]

		a[i] = next_greatest

		if (temp > next_greatest):
			next_greatest = temp