Thursday Dec 16, 2010

Finding Second Minimum with REPEATING elements in array

I posed few questions at the end of my earlier blog entry about finding 2nd minimum element. Let’s tackle the first question – how to efficiently find second minimum when we have repeating elements in the array. 

Let’s say we have following scenario. Notice that the minimum element, 1 appears twice in the list.

As before, we will use tournament method to first find the minimum value. Also note that while progressing through successive levels, the root elements, if repeating, will be compared against each other at some point. 

Using tournament method we obtain the minimum as below. 

Design Details

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.

Implementation Details

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.


Here is updated code for the method getSecondMinimum (no change in rest of methods in previous post). Click here to download complete class - (remove the .txt extension).

	 \* The logic for finding second minimum is as follows:
	 \* elements) as second minimum.
	 \* second lowest with this value.
	 \* @param tree
	 \* @param rootElement
	 \* @param level
	 \*            The depth from where to start back-tracking
	 \* @param rootIndex
	 \*            Index of the root element at that depth level
	 \* @return
	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
			// one row above
			rowAbove = tree[i - 1];
			adjacentleftIndex = rootIndex \* 2;
			adjacentleftElement = rowAbove[adjacentleftIndex];

			// following
				adjacentRightIndex = adjacentleftIndex + 1;
				adjacentRightElement = rowAbove[adjacentRightIndex];
			} else {
				adjacentRightElement = -1;

			// root continue the loop.
			if (adjacentRightElement == -1) {
				// just checking for error condition
				if (adjacentleftElement != rootElement) {
					throw new RuntimeException(
							"This is error condition. Since there "
									+ " it must be root element");
				} else {
					rootIndex = rootIndex \* 2;

			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,
				int minRightSubTree = getSecondMinimum(tree, rootElement, i,
				return getMin(minLeftSubTree, minRightSubTree);

			} else {
				throw new RuntimeException(
						"This is error condition. One of the adjacent "
								+ "elements must be root element");

		return secondLeast;

Running Time

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. 




« March 2014