Finding Second Minimum element in an Array

How would you find minimum element in an array (non-repeating random numbers) ? Well, the solution is obvious, you pick first element and compare with the next and keep the lower of the two. Do this again by comparing result of first comparison with the third element. Repeat this process for the complete array and you got the answer. So, in all for n elements you would need to do n-1 comparisons to find the minimum element (Figure 1).


Ok, the solution for finding smallest element was obvious. What if we need to find the next smallest element in an array? Well, one simple solution would be to compare the first two to select minimum and second minimum. Then pick the next element, compare with the minimum (selected in previous step) and replace it if the next element if lower. If not, compare with the second min and replace if necessary. Repeat this over the array and we have the second minimum. This algorithm would require 2n -3 comparisons (one comparison for first two elements + 2 comparisons for remaining elements of array. So 1 + 2 (n -2) = 2n -3.

What about finding 3rd minimum? The above logic would require 3 + 3(n-3) or 3n -6 comparisons.

The next question is can we do better than 2n -3 for finding second element (likewise for 3rd element and so forth). Can we not just sort the array and then just pick the 2nd value off the sorted array? Well, unfortunately that would not help either as best sorting algorithm will take nlog(n) time which is definitely more than what it would take for finding first log(n) elements using above method anyway. Well, the good news is that, yes there is a way to do better than 2n comparisons, and that is what this article is about - finding 2nd minimum in an array in efficient manner.

To solve problem of this nature we can take clue from a specialized form of problem set that can be best solved by technique called Dynamic Programming. My previous post about finding Critical Path is another example where dynamic programming technique was used.

Tournament Algorithm 

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).

Finding Min Using Tournament Method

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.

Finding 2nd Minimum using optimized back-tracking

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)

Thus this method offers marked improvement over crude method.

Code 

Here is complete program:

/\*\*
 \* Copyright (c) 2010-2020 Malkit S. Bhasin. All rights reserved.
 \* 
 \* All source code and material on this Blog site is the copyright of Malkit S.
 \* Bhasin, 2010 and is protected under copyright laws of the United States. This
 \* source code may not be hosted on any other site without my express, prior,
 \* written permission. Application to host any of the material elsewhere can be
 \* made by contacting me at mbhasin at gmail dot com
 \* 
 \* I have made every effort and taken great care in making sure that the source
 \* code and other content included on my web site is technically accurate, but I
 \* disclaim any and all responsibility for any loss, damage or destruction of
 \* data or any other property which may arise from relying on it. I will in no
 \* case be liable for any monetary damages arising from such loss, damage or
 \* destruction.
 \* 
 \* I further grant you ("Licensee") a non-exclusive, royalty free, license to
 \* use, modify and redistribute this software in source and binary code form,
 \* provided that i) this copyright notice and license appear on all copies of
 \* the software;
 \* 
 \* As with any code, ensure to test this code in a development environment
 \* before attempting to run it in production.
 \* 
 \* @author Malkit S. Bhasin
 \* 
 \*/
public class SecondMinimum {

	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];
	}

	private static void printRow(int[] values) {
		for (int i : values) {
			// System.out.print(i + " ");
		}
		// System.out.println(" ");
	}

	public static void main(String args[]) {
		int[] values = { 2, 4, 5, 3, 1, 8, 7, 10 };
		// Get Second Minimum (Non-Optimized)
		System.out.println("Second Minimum (using unoptimized algorithm): " 
				+ getSecondMinimumNonOptimized(values));

		// Get Tree and obtain the Minimum Element in the array
		int[][] outputTree = getOutputTree(values);
		int min = getRootElement(outputTree);

		// Get Second Minimum (Optimized)
		System.out.println("Second Minimum (Using optimized algorithm): " 
				+ getSecondMinimum(outputTree, min));
	}
}

Finally, this raises few questions.

  • 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?

I might attempt to take a shot at above in one of next blog entries. I would love to hear your feedback about the solution presented and if you can optimize it even more. Also, please provide your suggestions on how best to solve additional questions above.

Comments:

Thanks for sharing this info.i like coding until middle-night.

Posted by Kevin on December 06, 2010 at 02:51 PM PST #

you did a good job.you‘re very professional.

Posted by Polarized 3D glasses on December 06, 2010 at 03:05 PM PST #

This does produce a smaller number of comparisons than the unoptimized algorithm, but... it requires more copy operations (to setup the tree). A full analysis would account for the additional copy operations. Benchmarking would round out the picture.

One possibility might be to recursively look for a minimum using a binary search algorithm on the array, but since the array is not sorted both halves of the input array must be searched, then on the return path you can look for the second minimum. This uses the call stack to implement a tree, and because this approach is does not use tail recursion (there's two recursions, and there's a comparison after the second recursion, thus both recursive calls are not tail recursive), the cost of data copies is replaced with the cost of pushing and popping call frames.

Posted by Nico on December 27, 2010 at 02:53 AM PST #

BTW, I really like your idea of looking for the second minimum on the return path of the recursive search. But do note if any thing follows a recursive call other than returning the result of that call, then that call is no longer in tail position, which means that tail recursion optimization does not apply, which means that you'll be pushing extra stack frames. So... tempting, but not necessarily faster.

Posted by Nico on December 27, 2010 at 02:58 AM PST #

Nico,
You are right. This algorithm does require copy operations to setup the tree which is not accounted for in the analysis. Also, one can easily argue that this may not offer any great value if you were to just find the 2nd minimum (however n+logn+copy cost might win over 2n, for sufficiently large n).

The real value of this algorithm is when you have to find say 50th min over a collection of say 1 billion records. Just posted one more blog entry for finding kth minimum, also for obtaining partially sorted list in n + klogn time. The tournament tree structure can be thought of as one time modeling phase - once constructed can be queried to obtain fast results. This is valid algorithm – see this link http://en.wikipedia.org/wiki/Selection_algorithm

I'm afraid I don't quite get your solution. When you say binary search, I suppose you don't really mean sorting the array first (as binary search implies) as that would require nlogn time just for sorting. Are you suggesting divide and conquer, break the array in two parts find the mins and compare on return path. Unfortunately, that would not work either - what if both the mins are in same half. So, you end up finding two mins from each halves, thus involving 2n comparisons. May be I don't understand your solution. Can you please elaborate?

Regarding you other observation about "second minimum on the return path of the recursive search" - is not quite correct. There is no recursion in my code above. Once you build tournament tree, you just back-track from root all the way up-to the top (passing through logn level), you find the second min in one pass - there is no recursion here. Again, can you please elaborate?
Thanks for your comments.

Malkit

Posted by Malkit Bhasin on December 28, 2010 at 05:37 PM PST #

Extremely nice post you have held on. Logical programming thank you for it.

Posted by Website Designers on January 05, 2011 at 07:08 PM PST #

this really helps in clearing the concept of tournament algorithm.

Posted by Nitish on April 22, 2011 at 11:33 PM PDT #

very nice article really loved it !!! looking forward for more !!

Posted by guest on December 07, 2011 at 02:08 AM PST #

thanks...glad you liked it.

Posted by guest on December 08, 2011 at 03:54 AM PST #

really helped understanding tournament problem. keep posting concepts like these

Posted by guest on July 18, 2012 at 02:09 PM PDT #

glad you liked it.. in future i plan to do blogging on blogspot - http://malkit.blogspot.com/

Posted by Malkit on July 19, 2012 at 10:47 AM PDT #

Post a Comment:
  • HTML Syntax: NOT allowed
About

Malkit works in software development at Oracle, Inc. working in Oracle Business Process Manager, part of Oracle Fusion Middleware. Malkit came to Oracle through Sun Microsystems acquisition, living and working in Los Angeles, California.

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today