Sort a linked list containing 3 different types of elements

Question 46. Given a linked list where the nodes can have the values 0 or 1 or 2, sort it in a single pass. For instance 2->1->0->0->2->0>1 should be sorted as 0->0->0->1->1->2->2


To sort the linked list in a single pass, we make use of the fact that there are only 3 possible values for the nodes in the linked list. So as we traverse the linked list, we can remove the nodes from the original linked list and append them into 3 separate linked lists based on the value of the nodes. At the end we can merge the 3 linked lists. The procedure we can use to solve the problem is as follows

1. Maintain the head and tail pointers for linked list-0 (will contain nodes with value 0), linked list-1 (will contain nodes with value 1) and linked list-2 (will contain nodes with value 2)

2. As we traverse through the original linked list, remove each node from the original linked list and add it to linked list-0 or linked list-1 or linked list-2 based on the value of the node.

3. At the end connect the tail of linked list-0 to the head of linked list-1 and the tail of linked list-1 to the head of linked list-2

C/C++


/*
head: array of head pointers of the separated lists
tail: array of tail pointers of the separated lists
cur_node: current node being processed
i: data value of the node
*/
void add_node(struct node *head[], struct node *tail[], 
		struct node *cur_node, int i)
{
	cur_node->next = head[i];
	head[i] = cur_node;
	if (!tail[i])
		tail[i] = cur_node;

}


/*first_node: first node in list to be sorted 
num_distinct_values: number of distinct values in the nodes
Return value: head of the sorted list
*/
struct node * sort_list(struct node *first_node, int num_distinct_values)
{
	struct node **head, **tail; 
	struct node *result = NULL, *cur_node, *next_node, *last_element;
	int i;

	if (!first_node)
		return NULL;

	head = (struct node**) calloc(num_distinct_values, sizeof(struct node*));
	tail = (struct node**) calloc(num_distinct_values, sizeof(struct node*)); 

	for (i = 0; i < num_distinct_values; ++i) {
		head[i] = NULL;
		tail[i] = NULL;
	}

	/*Partition the list into separate lists, (0-list, 1-list, 2-list)
	based on the data in the node*/
	cur_node = first_node;
	while (cur_node) {
		next_node = cur_node->next;
		add_node(head, tail, cur_node, cur_node->data);
		cur_node = next_node;
	}

	/*Connect the tail of first linked list with head of second linked list
	and so on*/
	result = head[0];
	last_element = tail[0];
	for (i = 1; i < num_distinct_values; ++i) {
		if (!result)
			result = head[i];

		/*Link last element of previous list with head of current list*/
		if (last_element)
			last_element->next = head[i];

		/*update the last element to the tail of current list*/
		if (tail[i])
			last_element = tail[i];
	}

	free(head);
	free(tail);

	return result;
}



Java


/*
head: array of heads of the separated lists
tail: array of tails of the separated lists
curNode: current node being processed
i: data value of the node
*/
public static void addNode(LinkedListNode[] head, LinkedListNode[] tail, 
			LinkedListNode curNode, int i) {
	curNode.next = head[i];
	head[i] = curNode;
	if (tail[i] == null)
		tail[i] = curNode;

}

/*firstNode: first node in the list to be sorted 
numDistinctValues: number of distinct values 
Return value: head of the sorted list
*/
public static LinkedListNode sortList(LinkedListNode firstNode, 
				int numDistinctValues) {
	LinkedListNode[] head = new LinkedListNode[numDistinctValues]; 
	LinkedListNode[] tail = new LinkedListNode[numDistinctValues];
	LinkedListNode result = null;

	if (firstNode == null)
		return null;

	int i;
	for (i = 0; i < numDistinctValues; ++i) {
		head[i] = null;
		tail[i] = null;
	}

	/*Partition the list into separate lists (0-list, 1-list and 2-list)
	based on the data in the node*/
	LinkedListNode curNode = firstNode;
	while (curNode != null) {
		LinkedListNode nextNode = curNode.next;
		addNode(head, tail, curNode, curNode.data);
		curNode = nextNode;
	}

	/*Connect the tail of first linked list with head of second linked list
	and so on*/
	result = head[0];
	LinkedListNode lastElement = tail[0];
	for (i = 1; i < numDistinctValues; ++i) {
		if (result == null)
			result = head[i];

		/*Link last element of previous list with head of current list*/
		if (lastElement != null)
			lastElement.next = head[i];

		/*update the last element to the tail of current list*/
		if (tail[i] != null)
			lastElement = tail[i];
	}

	return result;
}


Python


#head: list having head nodes of all the separated linked lists
#tail: list having tail nodes of all the separated linked lists
#cur_node: current node being processed
#i: data value of the node
@staticmethod
def add_node(head, tail, cur_node, i) :
	cur_node.next = head[i]
	head[i] = cur_node
	if (tail[i] == None):
		tail[i] = cur_node


#first_node:  first node in the linked list to be sorted
#num_distinct_values: number of distinct values 
#Return value: head of the sorted linked list
@staticmethod
def sort_linked_list(first_node, num_distinct_values) :
	head = [None] * num_distinct_values 
	tail = [None] * num_distinct_values
	result = None

	if (not first_node):
		return None

	#Partition the input linked list into separate linked lists 
	#(0-list, 1-list and 2-list) based on the data in the node
	cur_node = first_node
	while (cur_node) :
		next_node = cur_node.next
		LinkedListNode.add_node(head, tail, cur_node, cur_node.data)
		cur_node = next_node
	
	#Connect the tail of first linked list with head of second linked list
	#and so on
	result = head[0]
	last_element = tail[0]
	for  i in range(1, num_distinct_values):
		if (not result):
			result = head[i]

		#Link last element of previous linked list with head of 
		#current linked list
		if (last_element):
			last_element.next = head[i]

		#update the last element to the tail of current linked list
		if (tail[i] != None):
			last_element = tail[i]
	

	return result


Merge M sorted arrays

Question 45. Given m sorted arrays each of which has a size n, merge the arrays in sorted order into a single array of size m*n


To efficiently solve the problem we use a heap which has a maximum size of m (number of sorted arrays). If the arrays are sorted in non-decreasing order, then we maintain a min heap otherwise we maintain a max heap. The algorithm is as follows

1. Pick the first element from each array, add it to the heap and construct the heap using the heapify function

2. Add the topmost element in the heap to the result array. Then replace the topmost element of the heap with the next element from the same array as the topmost element. Re-adjust the heap using the heapify function. Suppose all elements in the same array are over, then add a MAX_INT for non-decreasing order (MIN_INT for non-increasing order) into the root of the heap and re-adjust the heap using heapify. Repeat this step until all elements in all the arrays are processed.

Inserting an element into a heap of size m takes O(logm). Since we have n*m elements, the time complexity of this approach is O(nm * logm).

The code for merging k sorted lists is given below.

C/C++


/*
arrays: the arrays to be merged. arrays[0] has the first array, arrays[1] has 
		the second array and so on
n: number of elements in each array
k: number of arrays
result: the merged results are passed back in this array
*/
void merge_k_sorted_arrays(int arrays[][MAX_NUM_ELEMENTS], int n, int k, 
			int *result)
{
	struct node *heap = (struct node*) calloc(k, sizeof(struct node));
	int *arr_pos = (int*) calloc(k, sizeof(int));
	int i, pos, res_index, array_no;

	/*Store the first element in each array into the heap*/
	for (i = 0; i < k; ++i) {
		heap[i].value = arrays[i][0];
		heap[i].array_no = i;
		arr_pos[i] = 1;
	}

	/*Construct the initial heap using the heapify procedure*/
	for (i = k - 1; i >= 0; --i)
		heapify(heap, i, k);
	
	/*
	Process the remaining elements in the arrays. When all elements in the 
	arrays have been processed, MAX_INT will be present at root of heap
	*/
	res_index = 0;
	while (heap[0].value != MAX_INT) {
		/*
		root of the heap will have the lowest value. So store
		it into the result
		*/
		result[res_index++] = heap[0].value;

		array_no = heap[0].array_no;
		pos = arr_pos[array_no];

		/*
		If the root belongs to array x, then replace the root with
		the next element in array x
		*/
		if (pos >= n) {
			/*If we have exhausted all elements in the array, 
			then insert MAX_INT into the heap*/
			heap[0].value = MAX_INT;
			heap[0].array_no = array_no;
		} else {
			heap[0].value = arrays[array_no][pos];
			heap[0].array_no = array_no;
		}

		/*Re-adjust the heap after replacing the root*/
		heapify(heap, 0, k);

		arr_pos[array_no]++;
	}

	free(arr_pos);
	free(heap);
}


/* Helper function to perform heapify
heap: min heap.  Maximum number of elements in heap is k
pos: position of the heap that may need to be fixed
heap_size: current number of nodes in the heap
*/
void heapify(int heap[], int pos, int heap_size)
{
	int left = 2 * pos;
	int right = (2 * pos) + 1;
	int ix_of_smallest = pos;

	/*Find which of the three are the smallest: heap[pos] OR left child
	OR right child*/
	if (left < heap_size && heap[pos] > heap[left])
		ix_of_smallest = left;
	if (right < heap_size && heap[ix_of_smallest] > heap[right])
		ix_of_smallest = right;

	if (ix_of_smallest != pos) {
		/*
		If pos doesn't contain the smallest value,
		then swap the smallest value into pos 
		*/
		int temp = heap[pos];
		heap[pos] = heap[ix_of_smallest];
		heap[ix_of_smallest] = temp;

		/*Recursively re-adjust the heap*/
		heapify(heap, ix_of_smallest, heap_size);
	}
}



Java


/*
arrays: the arrays to be merged. arrays[0] has the first array, arrays[1] has
		the second array and so on
Return value: the merged results are passed back in this array
*/
public static int[] mergeKSortedArrays(int[][] arrays) {
	int k = arrays.length;	/*number of arrays*/
	int n = arrays[0].length; /*number of elements in each array*/
	Node[] heap = new Node[k];
	int[] arrPos = new int[k];
	int[] result = new int[k * n];

	/*Store the first element in each array into the heap*/
	int i;
	for (i = 0; i < k; ++i) {
		heap[i] = new Node();
		heap[i].value = arrays[i][0];
		heap[i].arrayNo = i;
		arrPos[i] = 1;
	}

	/*Construct the initial heap using the heapify procedure*/
	for (i = k - 1; i >= 0; --i)
		heapify(heap, i, k);

	
	/*
	Process the remaining elements in the arrays. When all elements in the
	arrays have been processed, MAX_INT will be present at root of heap
	*/
	int resIndex = 0;
	while (heap[0].value != MAX_INT) {
		/*
		root of the heap will have the lowest value. So store
		it into the result
		*/
		result[resIndex++] = heap[0].value;

		int arrayNo = heap[0].arrayNo;
		int pos = arrPos[arrayNo];

		/*
		If the root belongs to array x, then replace the root with
		the next element in array x
		*/
		if (pos >= n) {
			/*If we have exhausted all elements in the array, 
			then insert MAX_INT into the heap*/
			heap[0].value = MAX_INT;
			heap[0].arrayNo = arrayNo;
		} else {
			heap[0].value = arrays[arrayNo][pos];
			heap[0].arrayNo = arrayNo;
		}

		/*Re-adjust the heap after replacing the root*/
		heapify(heap, 0, k);

		arrPos[arrayNo]++;
	}

	return result;
}

/* Helper function to perform heapify
heap: min heap.  Maximum number of elements in heap is k
pos: position of the heap that may need to be fixed
heapSize: current number of nodes in the heap
*/
public static void heapify(int[] heap, int pos, int heapSize) {
	int left = 2 * pos;
	int right = (2 * pos) + 1;
	int ixOfSmallest = pos;

	/*Find which of the three are the smallest - heap[pos] OR left child
	OR right child*/
	if (left < heapSize && heap[pos] > heap[left])
		ixOfSmallest = left;
	if (right < heapSize && heap[ixOfSmallest] > heap[right])
		ixOfSmallest = right;


	if (ixOfSmallest != pos) {
		/*
		If pos doesn't contain the smallest value,
		then swap the smallest value into pos 
		*/
		int temp = heap[pos];
		heap[pos] = heap[ixOfSmallest];
		heap[ixOfSmallest] = temp;

		/*Recursively re-adjust the heap*/
		heapify(heap, ixOfSmallest, heapSize);
	}
}




Python


#lists:  the lists to be merged. lists[0] has the first list, lists[1] has 
#		the second list and so on
#Return value:  the merged results are passed back in this list
def merge_k_sorted_lists(lists) :
	k = len(lists)	#number of lists
	n = len(lists[0]) #number of elements in each list
	heap = []
	arr_pos = []

	#Store the first element in each list into the heap
	for  i in range(0, k):
		new_node = Node()
		new_node.value = lists[i][0]
		new_node.list_no = i
		heap.append(new_node)
		arr_pos.append(1)
	
	#Construct the initial heap using the heapify procedure
	for  i in range(k - 1, -1,-1):
		heapify(heap, i, k)

	#Process the remaining elements in the lists. When all elements in  
	#the lists have been processed, MAX_INT will be present at root of heap
	result = [] 
	while (heap[0].value != MAX_INT) :
		#root of the heap will have the lowest value. So store
		#it into the result
		result.append(heap[0].value)

		list_no = heap[0].list_no
		pos = arr_pos[list_no]

		#If the root belongs to list x, then replace the root with
		#the next element in list x
		if (pos >= n) :
			#If we have exhausted all elements in the list, 
			#then insert MAX_INT into the heap
			heap[0].value = MAX_INT
			heap[0].list_no = list_no
		else :
			heap[0].value = lists[list_no][pos]
			heap[0].list_no = list_no
		

		#Re-adjust the heap after replacing the root
		heapify(heap, 0, k)

		arr_pos[list_no] += 1
	
	return result

#Helper function to perform heapify
#heap: min heap.  Maximum number of elements in heap is k
#pos: position of the heap that may need to be fixed
#heap_size: current number of nodes in the heap
def heapify(heap, pos, heap_size) :
	left = 2 * pos
	right = (2 * pos) + 1
	ix_of_smallest = pos

	#Find which of the three are the smallest - value at pos OR left child
	#OR right child
	if (left < heap_size and heap[pos] > heap[left]):
		ix_of_smallest = left
	if (right < heap_size and heap[ix_of_smallest] > heap[right]):
		ix_of_smallest = right
 
	if (ix_of_smallest != pos) :
		#If pos doesn't contain the smallest value,
		#then swap the smallest value into pos 
		heap[pos], heap[ix_of_smallest] = heap[ix_of_smallest], heap[pos]

		#Recursively readjust the heap
		heapify(heap, ix_of_smallest, heap_size)




Merge a small sorted array into a larger sorted array

Question 44. Given a small array of size n having n sorted elements and a big array of size m+n having m sorted elements at the beginning of the big array, merge the two arrays and store them in the big array


There is just enough free space in the big array to accommodate the elements of the small array. The two sorted arrays can be merged in O(m+n). The trick is to start filling up the big array from the end where the free space is present. The code for this is given below

C/C++


/*
a: array of size m+n which has m elements at beginning and n spaces at end
b: array of size n with n elements
m: number of elements in array a
n: number of elements in array b
*/
void merge_arrays(int a[], int b[], int m, int n)
{
	int i, j, fill_pos;

	i = m - 1;
	j = n - 1;
	fill_pos = m + n - 1; /*Start filling from the rear of the array*/

	while (i >= 0 && j >= 0) {
		if (a[i] > b[j]) {
			a[fill_pos--] = a[i--];
		} else {
			a[fill_pos--] = b[j--];
		}
	}

	/*Fill up the remaining elements of array a if any*/
	while (i >= 0)
		a[fill_pos--] = a[i--];

	/*Fill up the remaining elements of array b if any*/
	while (j >= 0)
		a[fill_pos--] = b[j--];

} 



Java


/*
a: array of size m+n which has m elements at beginning and n spaces at end
b: array of size n with n elements
m: number of elements in array a
n: number of elements in array b
*/
public static void mergeArrays(int[] a, int[] b, int m, int n) 	{
	int i = m - 1;
	int j = n - 1;
	int fillPos = m + n - 1; /*Start filling from the rear of the array*/

	while (i >= 0 && j >= 0) {
		if (a[i] > b[j]) {
			a[fillPos--] = a[i--];
		} else {
			a[fillPos--] = b[j--];
		}
	}

	/*Fill up the remaining elements of array a if any*/
	while (i >= 0)
		a[fillPos--] = a[i--];

	/*Fill up the remaining elements of array b if any*/
	while (j >= 0)
		a[fillPos--] = b[j--];
}  



Python


#a: list of size m+n which has m elements at beginning 
#b: list of size n with n elements
#m: number of elements in list a
#n: number of elements in list b
def merge_lists(a, b, m, n) :
	i = m - 1
	j = n - 1
	fill_pos = m + n - 1 #Start filling from the rear of list a

	while (i >= 0 and j >= 0) :
		if (a[i] > b[j]) :
			a[fill_pos] = a[i]
			fill_pos -= 1
			i -= 1
		else :
			a[fill_pos] = b[j]
			fill_pos -= 1
			j -= 1
		
	#Fill up the remaining elements of list a if any
	while (i >= 0):
		a[fill_pos] = a[i]
		fill_pos -= 1
		i -= 1

	#Fill up the remaining elements of list b if any
	while (j >= 0):
		a[fill_pos] = b[j]
		fill_pos -= 1
		j -= 1



Wave sort

Question 43. Re-arrange the elements in an array like a wave so that the values of the array alternately increase and decrease. The elements in the array are unique. For instance, if A = {50, 10, 20, 30, 40}, after re-arranging A can be {10, 30, 20, 50, 40} where in the value of consecutive elements alternately increases and decreases


This problem can be solved in O(nlogn) without additional memory as follows:

1. First sort the entire array in ascending order. So {50, 10, 20, 30, 40} becomes {10, 20, 30, 40, 50}

2. Then starting from index 1 in the array, swap the neighboring elements. So {10, 20, 30, 40, 50} becomes {10, 30, 20, 50, 40}

C/C++


/*
a: array that has to be sorted so that the values in it alternatively increase
	and decrease. The elements should be unique
length: number of elements in the array. should be >= 1
*/
void wave_sort(int a[], int length)
{
	int i, temp;

	/*Sort the elements in ascending order*/
	qsort(a, length, sizeof(int), cmp_function);

	/*Swap the alternate elements*/
	for (i = 1; i < length - 1; i += 2) {
		temp = a[i];
		a[i] = a[i+1];
		a[i+1] = temp;
	}
}



Java


/*
a: non-empty array that has to be sorted so that the values in it 
	alternatively increase and decrease. The elements should be unique
*/
public static void waveSort(int[] a) {
	/*Sort the elements in ascending order*/
	Arrays.sort(a);

	/*Swap the alternate elements*/
	for (int i = 1; i < a.length - 1; i += 2) {
		int temp = a[i];
		a[i] = a[i+1];
		a[i+1] = temp;
	}
}



Python


#a: non-empty list that has to be sorted so that the values in it 
#	alternatively increase and decrease. The elements should be unique
def wave_sort(a) :
	#Sort the elements in ascending order
	a.sort()

	#Swap the neighboring elements
	for  i in range(1, len(a) - 1, 2):
		a[i], a[i+1] = a[i+1], a[i]



Search a sorted list with interspersed empty slots

Question 42. Consider the sorted array of strings A= {“”, “apple”, “”, “”, “ball”, “cat”, “”, “dog”, “”, “”, “”, “egg”, “”}. The array has empty strings interspersed in it. How will you efficiently search for strings in such an array?


We can use binary search to search the array of sorted strings. However since the array has empty strings in it, suppose we hit an empty string during binary search, we won’t know how to continue the search. To solve this problem we slightly modify the binary search and use the following strategy:

1. Binary search will occur between indexes low and high. If A[high] is an empty string, then we go on decrementing high till A[high] is a non-empty string. (Suppose we don’t find a non-empty string and we reach A[low], then all elements between low and high are empty strings. So we simply return indicating the search string was not found.)

2. We then find the mid element between low and high. If A[mid] is a non-empty string, then we proceed with the usual binary search. If A[mid] however is an empty string, then we go on incrementing mid till A[mid] is a non-empty string. Since A[high] already has a non-empty string, we will surely find a non-empty string when we keep incrementing mid.

C/C++


/*
strings: sorted array of strings in which some of the strings can be empty ("")
num_strings: number of strings present (including empty strings)
x: string to be searched
Returns: index of x in the array strings if found, -1 otherwise
*/
int search(char *strings[], int num_strings, char *x)
{
	int mid, result;
	int low = 0;
	int high = num_strings - 1;
	
	while (low <= high) {
		/*If we hit an empty string at position high, then keep decreasing
		high till we get a non-empty string*/
		while (low <= high && strcmp(strings[high], "") == 0) {
			--high;
		}

		/*If we have only empty strings between low and high, then return
		not found*/
		if (low > high)
			return -1;
		mid = (low + high) / 2;

		/*If we get an empty element at mid, then keep incrementing mid. 
		We are guaranteed to find a non-empty string since strings[high]
		is non-empty*/
		while (strcmp(strings[mid], "") == 0)
			mid = mid + 1; 

		/*Compare the mid element with the element being searched*/
		result = strcmp(strings[mid], x);

		if (result == 0) {
			return mid;
		} else if (result < 0) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	return -1;
}



Java


/*
strings: sorted array of strings in which some of the strings can be empty ("")
x: string to be searched
Returns: index of x in the array strings if found, -1 otherwise
*/
public static int search(String[] strings, String x) {
	int low = 0;
	int high = strings.length - 1;

	while (low <= high) {
		/*If we hit an empty string at position high, then keep 
		decreasing high till we get a non-empty string*/
		while (low <= high && strings[high] == "") 
			--high;

		/*If we have only empty strings between low and high, then return
		 not found*/
		if (low > high)
			return -1;

		int mid = (low + high) / 2;
 
		/*If we get an empty element at mid, then keep incrementing mid. 
		We are guaranteed to find a non-empty string since strings[high]
		is non-empty*/ 
		while (strings[mid] == "")
			mid = mid + 1; 

		/*Compare the mid element with the element being searched*/
		int result = strings[mid].compareTo(x);

		if (result == 0) {
			return mid;
		} else if (result < 0) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	return -1;
}



Python


#strings: sorted list of strings in which some of the strings can be empty ('')
#x: string to be searched
#Returns: index of x in the strings list if found, -1 otherwise
def search(strings, x) :
	low = 0
	high = len(strings) - 1

	while (low <= high) :
		#If we hit an empty string at position high, then keep decreasing
		#high until we get a non-empty string
		while (low <= high and strings[high] == '') :
			high = high - 1
		
		#If we have only empty strings between low and high, then return
		#not found
		if (low > high):
			return -1

		mid = (low + high) // 2

		#If we get an empty element at mid, then keep incrementing mid.
		#We are guaranteed to find a non-empty string since strings[high]
		#is non-empty
		while (strings[mid] == ''):
			mid += 1

		#Compare the mid element with the element being searched
		if (strings[mid] == x) :
			return mid
		elif (strings[mid] < x) :
			low = mid + 1
		else :
			high = mid - 1
		
	return -1



Find the first element larger than k in a sorted array

Question 41. Find the first element larger than k in a sorted array


Consider the sorted array A = {10, 20, 20, 30, 40, 50}. The first element larger than 25 is 30. In normal binary search, we search for a particular element and stop when we find the element. When we are trying to find the first element larger than k, k may not even exist in the array. So we instead use a modified form of binary search where we keep track of the first element larger than k as we search the array. The time complexity is O(logn). The code is given below

C/C++


/*
a: sorted array containing elements in non-decreasing order
length: number of elements in the array
k: we are searching for the number immediately above k
Returns: the number immediately greater than k in the array if it exists,
		MAX_INT otherwise
*/
int find_next_higher(int a[], int length, int k)
{
	int low, high, mid, result;

	low = 0; 
	high = length - 1;

	result = MAX_INT;
	while (low <= high) {
		mid = (low + high) / 2;

		if (a[mid] > k) {
			result = a[mid]; /*update the result and continue*/
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	} 

	return result;
}



Java


/*
a: sorted array containing elements in non-decreasing order
k: we are searching for the number immediately above k
Returns: the number immediately greater than k in the array if it exists,
	MAX_INT otherwise
*/
public static int findNextHigher(int[] a, int k) {
	int low = 0; 
	int high = a.length - 1;

	int result = MAX_INT;
	while (low <= high) {
		int mid = (low + high) / 2;

		if (a[mid] > k) {
			result = a[mid]; /*update the result and continue*/
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	} 

	return result;
}



Python


#a: sorted list containing elements in non-decreasing order
#k: we are searching for the number immediately above k
#Returns: the number immediately greater than k in the list if it exists,
#		MAX_INT otherwise
def find_next_higher(a, k) :
	low = 0 
	high = len(a) - 1

	result = MAX_INT
	while (low <= high) :
		mid = (low + high) // 2

		if (a[mid] > k) :
			result = a[mid] #update the result and continue
			high = mid - 1
		else :
			low = mid + 1

	return result 



Find the first occurrence of an element in a sorted array

Question 40. Find the first occurrence of a number in a sorted array


Consider the sorted array A = {10, 10, 20, 20, 30, 30, 30}. If we are asked to return the first occurrence of 30, then we return the index 4. If we are asked to return the first occurrence of a number not present in the array such as 15, then we return -1.

We can do this using modified binary search in O(logn). In normal binary search, we stop as soon as we find the element being searched. In the modified binary search, we continue the binary search if the found element is not the first occurrence of the element in the array. The code is given below

C/C++


/*
a: array being searched
n: number of elements in array
x: element being searched
Return value: first position of x in a, if x is absent -1 is returned
*/
int find_first(int a[], int n, int x)
{
	int start, end, mid;

	start = 0;
	end = n - 1;

	while (start <= end) {
		mid = (start + end) / 2;

		if (a[mid] == x) {
			if (mid == 0 || a[mid - 1] != x)
			     return mid;
			else
			     end = mid - 1;

		} else if (a[mid] > x) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	return -1;
}



Java


/*
a: array being searched
x: element being searched
Return value: first position of x in a, if x is absent -1 is returned
*/
public static int findFirst(int[] a, int x) {
	int n = a.length;
	int start = 0;
	int end = n - 1;

	while (start <= end) {
		int mid = (start + end) / 2;

		if (a[mid] == x) {
			if (mid == 0 || a[mid - 1] != x)
			     return mid;
			else
			     end = mid - 1;

		} else if (a[mid] > x) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	return -1;
}



Python


#a: list being searched
#x: element being searched
#Return value: first position of x in a, if x is absent -1 is returned
def find_first(a, x) :
	n = len(a)
	start = 0
	end = n - 1

	while (start <= end) :
		mid = (start + end) // 2

		if (a[mid] == x) :
			if (mid == 0 or a[mid - 1] != x):
			     return mid
			else:
			     end = mid - 1

		elif (a[mid] > x) :
			end = mid - 1
		else :
			start = mid + 1
		
	return -1



Find max and min using least operations

Question 39. Find the maximum and minimum elements in an array using the least number of comparisons


In the simple approach, we will compare each element of the array with the maximum value and minimum value obtained so far. So for every element, we need 2 comparisons.

In the efficient approach, we pick all pairs of consecutive numbers in the array and first compare the numbers within each pair. Then we compare the highest in the pair with the maximum value and the lowest in the pair with the minimum value. So we need 3 comparisons for 2 elements instead of 4 comparisons needed by the simple approach.

Since we will be picking pairs of consecutive numbers, if we have odd number of elements in the array, the last element will be left unpaired. To avoid this problem, if we have odd elements, we will initialize the max value and the min value to the first element in the array and then go on picking pairs of numbers from the second element onwards.

C/C++


/*a:input array 
length: number of elements in array a
min_value: the minimum value is returned here
max_value: the maximum value is returned here*/
void find_min_max(int a[], int length, int *min_value, int *max_value) {
	int i = 0;
	*max_value = MIN_INT;
	*min_value = MAX_INT;
	if (length % 2 == 1) {
		/*If there are odd number of elements, then initialize 
		max_value and min_value with a[0]*/
		*max_value = *min_value = a[0];
		i = 1;
	}

	for (; i < length; i += 2) {
		if (a[i] > a[i+1]) {
			if (a[i] > *max_value) 
				*max_value = a[i];
			if (a[i+1] < *min_value)
				*min_value = a[i+1];
		} else {
			if (a[i] < *min_value)
				*min_value = a[i];
			if (a[i+1] > *max_value)
				*max_value = a[i+1];
		}
	}
}



Java


/*a:input array 
result: the minimum value is returned in result[0] and 
	the maximum value is returned in result[1]*/
public static void findMinMax(int[] a, int[] result) {
	int length = a.length;
	int maxValue = MIN_INT;
	int minValue = MAX_INT;
	int i = 0;
	if (length % 2 == 1) {
		/*If there are odd number of elements, then initialize 
		maxValue and minValue with a[0]*/
		maxValue = minValue = a[0];
		i = 1;
	}

	for (; i < length; i += 2) {
		if (a[i] > a[i+1]) {
			if (a[i] > maxValue) 
				maxValue = a[i];
			if (a[i+1] < minValue)
				minValue = a[i+1];
		} else {
			if (a[i] < minValue)
				minValue = a[i];
			if (a[i+1] > maxValue)
				maxValue = a[i+1];
		}
	}
	result[0] = minValue;
	result[1] = maxValue;
}




Python


#a: input list 
#Returns: the minimum value and maximum value in list are returned
def find_min_max(a) :
	length = len(a)
	max_value = MIN_INT
	min_value = MAX_INT

	i = 0
	if (length % 2 == 1) :
		#If there are odd number of elements, then initialize 
		#max_value and min_value with a[0]
		max_value = min_value = a[0]
		i = 1
	
	while ( i < length ) :
		if (a[i] > a[i+1]) :
			if (a[i] > max_value) :
				max_value = a[i]
			if (a[i+1] < min_value):
				min_value = a[i+1]
		else :
			if (a[i] < min_value):
				min_value = a[i]
			if (a[i+1] > max_value):
				max_value = a[i+1]
		
		i += 2

	return min_value, max_value




Find the smallest and second smallest

Question 38. Find the smallest and second smallest numbers in an array


We can find the smallest and second smallest numbers in a single scan of the array. We will maintain another array called min_values for storing the 2 smallest numbers. min_values[0] will store the smallest value and min_values[1] will store the second smallest value. min_values[0] and min_values[1] are initialized to MAX_INT. As we traverse the main array, we do the following

– If the current element is smaller than min_values[0], then we move min_values[0] to min_values[1] and store the current element in min_values[0]

– If the current element is larger than min_values[0] but smaller than min_values[1], then we store the current element in min_values[1]

The code is given below:

C/C++


/*
a:input array 
length: number of elements in array a
min_value: the two smallest values will be returned here
*/
void find_two_smallest(int a[], int length, int min_value[])
{
	int i;

	min_value[0] = min_value[1] = MAX_INT;

	for (i = 0; i < length; ++i) {
		if (a[i] < min_value[0]) {
			min_value[1] = min_value[0];
			min_value[0] = a[i];
		} else if (a[i] < min_value[1]) {
			min_value[1] = a[i];
		}
	}
}



Java


/*
a:input array 
minValue: the two smallest values will be returned here
*/
public static void findTwoSmallest(int[] a, int[] minValue) {
	minValue[0] = minValue[1] = MAX_INT;

	for (int curVal : a) {
		if (curVal < minValue[0]) {
			minValue[1] = minValue[0];
			minValue[0] = curVal;
		} else if (curVal < minValue[1]) {
			minValue[1] = curVal;
		}
	}
}



Python


#a:input list 
#Return value: the two smallest values will be returned 
def find_two_smallest(a) :
	length = len(a)

	min_value = [MAX_INT, MAX_INT]

	for  cur_val in a:
		if (cur_val < min_value[0]) :
			min_value[1] = min_value[0]
			min_value[0] = cur_val 
		elif (cur_val  < min_value[1]) :
			min_value[1] = cur_val 
		
	
	return min_value[0], min_value[1]