Finding Second Minimum with REPEATING elements in array

Originally published on Dec 16, 2010

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.

Code 

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

 
/**
 * 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 SecondMinRepeatingElements {

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

 /**
  * 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, 1, 3, 1, 8, 7, 10 };
  int[][] outputTree = getOutputTree(values);
  int min = getRootElement(outputTree);
  System.out.println("Minimum (Using optimized algorithm): " + min);
  System.out.println("Second Minimum (Using optimized algorithm): "
    + getSecondMinimum(outputTree, min, outputTree.length, 0));
 }
}