Question: Write an efficient C program to find smallest and second smallest element in an array.
O(2n)
http://stackoverflow.com/questions/3715935/algorithm-find-index-of-2nd-smallest-element-from-an-unknown-array
http://traceformula.blogspot.com/2015/07/order-statistics-minimum-maximum-median.html
There are cases that we need to find both minimum and maximum of an unsorted array. We can easily find them by using the above algorithm. However, it requires 2 * (n-1) comparisons. We can do better in terms of number of comparisons! Pause yourself for a few seconds to think about it.
In order to solve this, we pick 2 elements at a time. We compare the smaller element with the current min, and the bigger element with the current max, and update min and max accordingly. The number of comparisons is around 3/2 * n.
public int[] findMinAndMax(int[] a){ //we assume that the array has at least 2 elements
int min = a[0]>a[1]?a[1]:a[0];
int max = a[0]>a[1]?a[0]:a[1];
int l = a.length % 2 == 0? a.length:a.length-1;
int smaller, bigger;
for(int i = 2; i<l;i+= 2){
if(a[i] > a[i+1]){
smaller = a[i+1]; bigger = a[i];
}else{
smaller = a[i]; bigger = a[i+1];
}
if (min > smaller) min = smaller;
if (max < bigger) max = bigger;
}
if(a.length % 2 == 1){ //\\
if(a[a.length-1] > max) max = a[a.length-1];
else if (a[a.length-1] < min) min = a[a.length-1] ;
}
int result[] = new int[]{min, max};
return result;
}
we can do better with only (roughly) n + lgn comparisons.
We solve this using divide and conquer approach. First, we find the smallest and second smallest of the first half of the array, then find the smallest of second smallest of the second half of the array. Then we can combine the results of the 2 halves.
http://www.sanfoundry.com/java-program-find-second-smallest-n-elements-with-given-complexity-constraint/
Not efficient:
http://www.cprogrambank.com/cprogar9
http://www.geeksforgeeks.org/second-minimum-element-using-minimum-comparisons/
https://blogs.oracle.com/malkit/entry/finding_2nd_minimum_element_in
https://blogs.oracle.com/malkit/entry/finding_kth_minimum_partial_ordering
https://blogs.oracle.com/malkit/entry/kth_order_statistics_partial_ordering
http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/
Read full article from Find the smallest and second smallest element in an array | GeeksforGeeks
O(2n)
1) Initialize both first and second smallest as INT_MAX
first = second = INT_MAX
2) Loop through all the elements.
a) If the current element is smaller than first, then update first
and second.
b) Else if the current element is smaller than second then update
second
void print2Smallest(int arr[], int arr_size){ int i, first, second; /* There should be atleast two elements */ if (arr_size < 2) { printf(" Invalid Input "); return; } first = second = INT_MAX; for (i = 0; i < arr_size ; i ++) { /* If current element is smaller than first then update both first and second */ if (arr[i] < first) { second = first; first = arr[i]; } /* If arr[i] is in between first and second then update second */ else if (arr[i] < second && arr[i] != first) second = arr[i]; } if (second == INT_MAX) printf("There is no second smallest element\n"); else printf("The smallest element is %d and second Smallest element is %d\n", first, second);}http://traceformula.blogspot.com/2015/07/order-statistics-minimum-maximum-median.html
There are cases that we need to find both minimum and maximum of an unsorted array. We can easily find them by using the above algorithm. However, it requires 2 * (n-1) comparisons. We can do better in terms of number of comparisons! Pause yourself for a few seconds to think about it.
In order to solve this, we pick 2 elements at a time. We compare the smaller element with the current min, and the bigger element with the current max, and update min and max accordingly. The number of comparisons is around 3/2 * n.
public int[] findMinAndMax(int[] a){
we can do better with only (roughly) n + lgn comparisons.
We solve this using divide and conquer approach. First, we find the smallest and second smallest of the first half of the array, then find the smallest of second smallest of the second half of the array. Then we can combine the results of the 2 halves.
- public int findSecondSmallest(int[] a){
- //We assume that the array has at least 2 elements
- return findMinAnd2ndSmallest(a, 0, a.length-1)[1];
- }
- //find min & second smallest
- private int[] findMinAnd2ndSmallest(int[] a, int start, int end){
- if(start == end) return new int[]{a[start], Integer.MAX_VALUE};
- int[] left = findMinAnd2ndSmallest(a, start, (start+end) / 2);
- int[] right = findMinAnd2ndSmallest(a,(start+end) / 2+1, end);
- int smallest = 0, secondSmallest = 0;
- if(left[0] < right[0]) {
- smallest = left[0]; secondSmallest = right[0];
- if(right[0] > left[1]) secondSmallest = left[1];
- }else {
- smallest = right[0]; secondSmallest = left[0];
- if(left[0] > right[1]) secondSmallest = right[1];
- }
- return new int[]{smallest, secondSmallest};
- }
http://www.sanfoundry.com/java-program-find-second-smallest-n-elements-with-given-complexity-constraint/
Not efficient:
http://www.cprogrambank.com/cprogar9
for(i=1;i<n;i++)
{
if(min>a[i])
{
min=a[i];
j=i;
}
}
smin=a[n-j-1];
for(i=1;i<n;i++)
{
if(smin>a[i] && j!=i)
smin=a[i];
}
http://www.geeksforgeeks.org/second-minimum-element-using-minimum-comparisons/
First, we find the minimum element as explained by building a tournament tee. To build the tree, we compare all adjacent pairs of elements (leaf nodes) with each other. Now we have n/2 elements which are smaller than their counterparts (from each pair, the smaller element forms the level above that of the leaves). Again, find the smaller elements in each of the n/4 pairs. Continue this process until the root of the tree is created. The root is the minimum.
Next, we traverse the tree and while doing so, we discard the sub trees whose root is greater than the smallest element. Before discarding, we update the second smallest element, which will hold our result. The point to understand here is that the tree is height balanced and we have to spend only logn time to traverse all the elements that were ever compared to the minimum in step 1. Thus, the overall time complexity is n + logn. Auxiliary space needed is O(2n), as the number of leaf nodes will be approximately equal to the number of internal nodes.
Next, we traverse the tree and while doing so, we discard the sub trees whose root is greater than the smallest element. Before discarding, we update the second smallest element, which will hold our result. The point to understand here is that the tree is height balanced and we have to spend only logn time to traverse all the elements that were ever compared to the minimum in step 1. Thus, the overall time complexity is n + logn. Auxiliary space needed is O(2n), as the number of leaf nodes will be approximately equal to the number of internal nodes.
struct Node{ int idx; Node *left, *right;};// Utility function to create a tournament tree nodeNode *createNode(int idx){ Node *t = new Node; t->left = t->right = NULL; t->idx = idx; return t;}// This function traverses tree across height to// find second smallest element in tournament tree.// Note that root is smallest element of tournament// tree.void traverseHeight(Node *root, int arr[], int &res){ // Base case if (root == NULL || (root->left == NULL && root->right == NULL)) return; // If left child is smaller than current result, // update result and recur for left subarray. if (res > arr[root->left->idx] && root->left->idx != root->idx) { res = arr[root->left->idx]; traverseHeight(root->right, arr, res); } // If right child is smaller than current result, // update result and recur for left subarray. else if (res > arr[root->right->idx] && root->right->idx != root->idx) { res = arr[root->right->idx]; traverseHeight(root->left, arr, res); }}// Prints minimum and second minimum in arr[0..n-1]void findSecondMin(int arr[], int n){ // Create a list to store nodes of current // level list<Node *> li; Node *root = NULL; for (int i = 0; i < n; i += 2) { Node *t1 = createNode(i); Node *t2 = NULL; if (i + 1 < n) { // Make a node for next element t2 = createNode(i + 1); // Make smaller of two as root root = (arr[i] < arr[i + 1])? createNode(i) : createNode(i + 1); // Make two nodes as children of smaller root->left = t1; root->right = t2; // Add root li.push_back(root); } else li.push_back(t1); } int lsize = li.size(); // Construct the complete tournament tree from above // prepared list of winners in first round. while (lsize != 1) { // Find index of last pair int last = (lsize & 1)? (lsize - 2) : (lsize - 1); // Process current list items in pair for (int i = 0; i < last; i += 2) { // Extract two nodes from list, make a new // node for winner of two Node *f1 = li.front(); li.pop_front(); Node *f2 = li.front(); li.pop_front(); root = (arr[f1->idx] < arr[f2->idx])? createNode(f1->idx) : createNode(f2->idx); // Make winner as parent of two root->left = f1; root->right = f2; // Add winner to list of next level li.push_back(root); } if (lsize & 1) { li.push_back(li.front()); li.pop_front(); } lsize = li.size(); } // Traverse tree from root to find second minimum // Note that minimum is already known and root of // tournament tree. int res = INT_MAX; traverseHeight(root, arr, res); cout << "Minimum: " << arr[root->idx] << ", Second minimum: " << res << endl;}https://blogs.oracle.com/malkit/entry/finding_2nd_minimum_element_in
For solving problem of finding minimum element in an array, we will use what can be termed tournament method. Imagine a tennis tournament with 'n' players. Each player is paired with another player and the winner advance to next round and loser goes home. So, after first round the field is reduced to half. So, to find the winner of the tournament a total log(n) rounds will be played, where n is the field size (Figure 2).
For our problem, in the first iteration we compare adjacent elements of the array and the lower of two values are selected to form another array half the size (half + 1 for odd number of elements). The process is repeated till we find the minimum value. The number of comparisons needed to find the minimum is still the same, as calculated below:
Total comparisons: n (1/2 + 1/4 + … ) = n
(This above is convergent geometric series which has generalized solution of form (a/1 – r), or for our case it would be ½ (1 – ½); which equates to value 1)
During the process of finding minimum value, the generated arrays (during successive) iterations are saved to form a two-dimensional array (recursion tree) with first row being the input array and subsequent rows as generated from above iterations to form reverse tree (top row with input array and the minimum element at the bottom – root element).
The reason why we went the tournament way (as opposed to serial comparison) is that we can leverage the reverse tree to find the second minimum value with log(n) comparisons (asymptotic), hence the solution represents marked improvements over 2n (ignoring constant) comparisons as required by trivial method.
Here is the logic to find second minimum value.
The logic is that at some point the minimum element (root element) must have knocked out the second minimum element. So, by backtracking from the root element (minimum) all the way to the top and checking all the adjacent elements to the root element (for each row) we can find the second minimum. The key point to note is that at any level (above root level), the adjacent elements can be obtained by the index of root element at this level. Therefore, you don't need to scan complete sub-array (of recursion tree at any level). The adjacent elements for n-1 level is obtained as follows:
Adjacent Left (n-1 level) : 2 \* (root index for nth level)
Adjacent Right(n-1 level): 2 \* (root index for nth level) + 1
Therefore, for each row of the recursion tree, you just need to perform two comparisons to find the root element index to obtain the adjacent elements of row above. Refer to Figure 3 below. One of the elements marked in green box must be second minimum.
Adjacent Left (n-1 level) : 2 \* (root index for nth level)
Adjacent Right(n-1 level): 2 \* (root index for nth level) + 1
Therefore, for each row of the recursion tree, you just need to perform two comparisons to find the root element index to obtain the adjacent elements of row above. Refer to Figure 3 below. One of the elements marked in green box must be second minimum.
So, how many comparisons we make using this method. Let’s calculate (ignoring constants):
Comparisons for finding minimum: n
Comparisons for finding 2nd minimum: log(n)
Total: n + log(n)
Comparisons for finding 2nd minimum: log(n)
Total: n + log(n)
- The above solution assumed that there are no repeating elements in the array. What needs to be done to handle repeating elements?
- How to find 3rd, 4th… Kth minimum element in the array? Hint: The solution leverages the solution (uses already generated reverse tree) for finding second minimum.
- What if we are limited by memory and cannot load the whole array (or the generated tree) in memory?
public static int getSecondMinimumNonOptimized(int[] values) {
int min = -1, secondMin = -1;
int firstValue = values[0];
int secondValue = values[1];
if (firstValue < secondValue) {
min = firstValue;
secondMin = secondValue;
} else {
min = secondValue;
secondMin = firstValue;
}
int nextElement = -1;
for (int i = 2; i < values.length; i++) {
nextElement = values[i];
if (nextElement < min) {
secondMin = min;
min = nextElement;
} else if (nextElement < secondMin) {
secondMin = nextElement;
}
}
return secondMin;
}
/\*\*
\* Takes an input array and generated a two-dimensional array whose rows are
\* generated by comparing adjacent elements and selecting minimum of two
\* elements. Thus the output is inverse triangle (root at bottom)
\*
\* @param values
\* @return
\*/
public static int[][] getOutputTree(int[] values) {
Integer size = new Integer(values.length);
double treeDepth = Math.log(size.doubleValue()) / Math.log(2);
int intTreeDepth = getIntValue(Math.ceil(treeDepth)) + 1;
int[][] outputTree = new int[intTreeDepth][];
// first row is the input
outputTree[0] = values;
printRow(outputTree[0]);
int[] currentRow = values;
int[] nextRow = null;
for (int i = 1; i < intTreeDepth; i++) {
nextRow = getNextRow(currentRow);
outputTree[i] = nextRow;
currentRow = nextRow;
printRow(outputTree[i]);
}
return outputTree;
}
/\*\*
\* Compares adjacent elements (starting from index 0), and construct a new
\* array with elements that are smaller of the adjacent elements.
\*
\* For even sized input, the resulting array is half the size, for odd size
\* array, it is half + 1.
\*
\* @param values
\* @return
\*/
private static int[] getNextRow(int[] values) {
int rowSize = getNextRowSize(values);
int[] row = new int[rowSize];
int i = 0;
for (int j = 0; j < values.length; j++) {
if (j == (values.length - 1)) {
// this is the case where there are odd number of elements
// in the array. Hence the last loop will have only one element.
row[i++] = values[j];
} else {
row[i++] = getMin(values[j], values[++j]);
}
}
return row;
}
/\*\*
\* The logic for finding second minimum is as follows:
\*
\* Starting from root element (which is minimum element), find the lower of
\* two adjacent element one row above. One of the two element must be root
\* element. If the root element is left adjacent, the root index (for one
\* row above) is two times the root index of any row. For right-adjacent, it
\* is two times plus one. Select the other element (of two adjacent
\* elements) as second minimum.
\*
\* Then move to one row further up and find elements adjacent to lowest
\* element, again, one of the element must be root element (again, depending
\* upon the fact that it is left or right adjacent, you can derive the root
\* index for this row). Compare the other element with the second least
\* selected in previous step, select the lower of the two and update the
\* second lowest with this value.
\*
\* Continue this till you exhaust all the rows of the tree.
\*
\* @param values
\* @return
\*/
public static int getSecondMinimum(int[][] tree, int rootElement) {
int adjacentleft = -1, adjacentRight = -1;
int secondLeast = Integer.MAX_VALUE;
int rootIndex = 0;
int[] rowAbove = null;
// we have to scan in reverse order
for (int i = tree.length - 1; i > 0; i--) {
// one row above
rowAbove = tree[i - 1];
adjacentleft = rowAbove[rootIndex \* 2];
// the root element could be the last element carried from row above
// because of odd number of elements in array, you need to do
// following
// check. if you don't, this case will blow {8, 4, 5, 6, 1, 2}
if (rowAbove.length >= ((rootIndex \* 2 + 1) + 1)) {
adjacentRight = rowAbove[rootIndex \* 2 + 1];
} else {
adjacentRight = -1;
}
// if there is no right adjacent value, then adjacent left must be
// root
// continue the loop.
if (adjacentRight == -1) {
// just checking for error condition
if (adjacentleft != rootElement) {
throw new RuntimeException("This is error condition. Since there "
+ " is only one adjacent element (last element), "
+ " it must be root element");
} else {
rootIndex = rootIndex \* 2;
continue;
}
}
// one of the adjacent number must be root (min value).
// Get the other number and compared with second min so far
if (adjacentleft == rootElement && adjacentRight != rootElement) {
secondLeast = getMin(secondLeast, adjacentRight);
rootIndex = rootIndex \* 2;
} else if (adjacentleft != rootElement && adjacentRight == rootElement) {
secondLeast = getMin(secondLeast, adjacentleft);
rootIndex = rootIndex \* 2 + 1;
} else {
throw new RuntimeException("This is error condition. One of the adjacent "
+ "elements must be root element");
}
}
return secondLeast;
}
/\*\*
\* Returns minimum of two passed in values.
\*
\* @param num1
\* @param num2
\* @return
\*/
private static int getMin(int num1, int num2) {
return Math.min(num1, num2);
}
/\*\*
\* following uses Math.ceil(double) to round to upper integer value..since
\* this function takes double value, diving an int by double results in
\* double.
\*
\* Another way of achieving this is for number x divided by n would be -
\* (x+n-1)/n
\*
\* @param values
\* @return
\*/
private static int getNextRowSize(int[] values) {
double size = Math.ceil(values.length / 2.0);
return getIntValue(size);
}
private static int getIntValue(double value) {
return new Double(value).intValue();
}
/\*\*
\* Returns the root element of the two-dimensional array.
\*
\* @param tree
\* @return
\*/
public static int getRootElement(int[][] tree) {
int depth = tree.length;
return tree[depth - 1][0];
}
https://blogs.oracle.com/malkit/entry/finding_second_minimum_with_repeating
For single root, the depth of tree will be log(n), for second repeating element (for worst case) will be log(n) – 1 and so on. For m repeating root elements, there will be m backtrackings, one for each repeating root. Thus for m repeating roots, the running time:
n + log(n) + (log(n) -1) + … + (log(n) – m)
Or, O(n + mlog(n)), ignoring constants.
Also, note that the for repeating elements other than root element, the running time remains same as previously calculated (for non-repeating elements - O(n + log(n)); can also be obtained by substituting m=1 above) and that the previous code will work fine without any changes.
We can use similar logic as to find the second minimum, but we need to make slight changes to our logic. Our earlier code allowed only one of the adjacent elements of the row above to be root but now it is a valid condition and the of course the result of comparison will be a root element for such cases.
As noted above, if the root element is repeating, it must meet other root element(s) in the back path. So at the point where the two root elements meet, the tree would be divided into two sub-trees and we need to backtrack along the root element in each sub-tree till we reach the top level and select the minimum for each sub-tree. As before, since the second minimum must meet the root element at some point; by comparing the minimum for each path, we can obtain second minimum for repeating root.
We can use similar logic as used for finding second minimum, but we will have to make few changes:
1. The api getSecondMinimum will be extended to take additional parameters. In addition to the tree, it will also take the level to backtrack from and the root index. Same api can then be recursively used for back traversal of the tree from any point – root or from any level above root.
2. Whenever we hit a level where both the adjacent elements of row above are root elements, obtain the minimum from each sub-tree for both the root elements (left adjacent and right adjacent). Comparing the result of two would give us the second minimum.
3. To back track from root, just pass the total depth of the tree for the level argument and root index as value of 0.
public static int getSecondMinimum(int[][] tree, int rootElement,
int level, int rootIndex) {
int adjacentleftElement = -1, adjacentRightElement = -1;
int adjacentleftIndex = -1, adjacentRightIndex = -1;
int secondLeast = Integer.MAX_VALUE;
int[] rowAbove = null;
// we have to scan in reverse order
for (int i = level - 1; i > 0; i--) {
// one row above
rowAbove = tree[i - 1];
adjacentleftIndex = rootIndex \* 2;
adjacentleftElement = rowAbove[adjacentleftIndex];
// the root element could be the last element carried from row above
// because of odd number of elements in array, you need to do
// following
// check. if you don't, this case will blow {8, 4, 5, 6, 1, 2}
if (rowAbove.length >= ((adjacentleftIndex + 1) + 1)) {
adjacentRightIndex = adjacentleftIndex + 1;
adjacentRightElement = rowAbove[adjacentRightIndex];
} else {
adjacentRightElement = -1;
}
// if there is no right adjacent value, then adjacent left must be
// root continue the loop.
if (adjacentRightElement == -1) {
// just checking for error condition
if (adjacentleftElement != rootElement) {
throw new RuntimeException(
"This is error condition. Since there "
+ " is only one adjacent element (last element), "
+ " it must be root element");
} else {
rootIndex = rootIndex \* 2;
continue;
}
}
// one of the adjacent number must be root (min value).
// Get the other number and compared with second min so far
if (adjacentleftElement == rootElement
&& adjacentRightElement != rootElement) {
secondLeast = getMin(secondLeast, adjacentRightElement);
rootIndex = rootIndex \* 2;
} else if (adjacentleftElement != rootElement
&& adjacentRightElement == rootElement) {
secondLeast = getMin(secondLeast, adjacentleftElement);
rootIndex = rootIndex \* 2 + 1;
} else if (adjacentleftElement == rootElement
&& adjacentRightElement == rootElement) {
// This is case where the root element is repeating
// The tree is now divided into two sub-trees and we need to
// back-track both the sub-trees and select the minimum for
// each. Then lower of the two is second minimum
int minLeftSubTree = getSecondMinimum(tree, rootElement, i,
adjacentleftIndex);
int minRightSubTree = getSecondMinimum(tree, rootElement, i,
adjacentRightIndex);
return getMin(minLeftSubTree, minRightSubTree);
} else {
throw new RuntimeException(
"This is error condition. One of the adjacent "
+ "elements must be root element");
}
}
return secondLeast;
}
- Is the implementation too complex? In addition to Tournament method there are other mechanisms to find Kth minimum efficiently. This wiki page enumerates some of those methods - Selection Algorithm. I will try to solve using some of the methods listed on wiki resource. As always, feedback welcome.
Avoiding pure mathematics and using approximations, the worst case running time of this algorithm can be calculated as follows:
For finding second min –> O(n + log(n))
For Kth min (or partial k sort) –> O(n + klog(n)), ignoring constants (actually, the algorithm should perform much better than this as not all the k elements can be at log(n) depth).
For Kth min (or partial k sort) –> O(n + klog(n)), ignoring constants (actually, the algorithm should perform much better than this as not all the k elements can be at log(n) depth).
private static int[] findKthMinimum(int[] inputArray, int k) {
int[] partiallySorted = new int[k];
int[][] outputTree = getOutputTree(inputArray);
int root = getRootElement(outputTree);
partiallySorted[0] = root;
int rootIndex = 0;
int level = outputTree.length;
int[][][] fullAdjacencyList = new int[k - 1][][];
int[] kthMinIdx = null;
for (int i = 1; i < k; i++) {
fullAdjacencyList[i - 1] = getAdjacencyList(outputTree, root,
level, rootIndex);
kthMinIdx = getKthMinimum(fullAdjacencyList, i, root);
int row = kthMinIdx[0];
int column = kthMinIdx[1];
root = fullAdjacencyList[row][column][0];
partiallySorted[i] = root;
level = column + 1;
rootIndex = fullAdjacencyList[row][column][1];
}
return partiallySorted;
}
http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/
Read full article from Find the smallest and second smallest element in an array | GeeksforGeeks
