Question

You are a given an array of n elements, design an algorithm to find the minimum element and the 2nd minimum element in the array using as few comparisons as possible.

For example, A[] can be [5, 6, 7, 3, 2, 1]. You should output 1 as minimum, 2 as 2nd minimum element in the array, and at the same time, minimize the number of comparisons used.


(i) describe the idea behind your algorithm in English
(ii) provide java code
(iii) How many comparisons does your algorithm make?

Answer 1

Here are the solution to above problem:

1. We are iterating over the complete array and then comparing the values to find the smallest.

2. /**
   * The Class SecondSmallest.
   */
   class FindSmallest {

      /**
      * Prints the smallest.
      *
      * @param arr the arr
      */
      static void printSmallest(int arr[]) {
          int first = arr.length;
          int second = arr.length;
          int arraySize = arr.length;

          if (arraySize < 2) {
              System.out.println("Invalid");
              return;
          }
          first = second = Integer.MAX_VALUE;
          for (int i = 0; i < arraySize; i++) {
              if (arr[i] < first) {
                  second = first;
                  first = arr[i];
              } else if (arr[i] < second && arr[i] != first) {
                  second = arr[i];
              }
          }
          if (second == Integer.MAX_VALUE)
              System.out.println("There is no second" + "smallest element");
          else
              System.out.println("The smallest element is " + first + " and second Smallest" + " element is " + second);
      }

      /**
      * The main method.
      *
      * @param args the arguments
      */
      public static void main(String[] args) {
          int arr[] = { 5, 6, 7, 3, 2, 1 };
          printSmallest(arr);
      }
   }

3. it will be O(n).