Java Algo to Find smallest and second smallest Number in List

Question

I need to find smallest and second smallest number in a list.

Can I do this using single loop? Also, we need to consider the case of two multiple occurences of a number.

Ex: 1. from list [20,30,90,50] output 20 ,30 2. from list [30,30,90,50] output 30 ,30

plz help

Answer 1

I want to encourage you to do your homework on your own and understand the concepts behind it, so I won't post any code for you, but here are some things to guide you:

• It is possible to do this with only one loop.
• Make one pass through the list, all the time saving the current smallest and second-smallest number. These are the smallest and second-smallest up until this point in the list.
• At the end, you'll notice (if you've done it correctly) that you have the smallest and second-smallest numbers.
• In the case of a duplicate number, just be sure to include an equals check in the condition you use; i.e., you'll be checking for smaller values, so use i <= smallest and i <= secondSmallest as your two conditions (as opposed to a strict smaller than comparison).

Answer 2

I am sorry, Actually I dont have list of Integers. But I ahve list of objects.

Anyways, thanks for the help. I hope the following code works

if (minimum==0 || obj.getValue() < minimum) {
    second = minimum;
    minimum= obj.getValue();
} else if (obj.getValue() < second || second==0) {
    second = obj.getValue();
}

Answer 3

Pseudocode only since it's homework, to be turned into your language of choice. Assuming the list has two or more numbers in it (indexes 0 and 1):

set lowest to value at index 0.
set second_lowest to value at index 1.
if lowest is greater than second_lowest:
    swap lowest and second_lowest.
vary idx from 3 to last element:
    if value at index idx is less than lowest:
        set second_lowest to lowest
        set lowest to value at index idx
    else
        if value at index idx is less than second_lowest:
            set second_lowest to value at index idx

This works by basically checking every number to see if it should be the new lowest or new second lowest number. It can be done in one loop.

What you want to do is to run this program in your head, writing down on paper what the variables get changed to. That's a good way to understand how a computer works. Consider the list [30,20,90,10,50,12,7], following the following steps:

lowest   second   description
------   ------   -----------
    30       20   store first two elements.
    20       30   swap them if in wrong order (they are).
    20       30   90 is not less than either so ignore.
    10       20   10 is less than lowest (20) so move
                  lowest to second, store 10 to lowest.
    10       20   50 is not less than either so ignore.
    10       12   12 is less than second (20) so
                  store 12 to second.
     7       10   7 is less than lowest (10) so move
                  lowest to second, store 7 to lowest.

Answer 4

This can be done in recursive way using BinarySearch. Below is a BinarySearch to find the smallest. It can be extended to find smallest and second smallest (Tournament like method).

public int findSmallest(int[] A, int start, int end){
    if(end == start){
        return A[start];
    }else if(start == end-1){
        return Math.min(A[start], A[end]);
    }else{
            int mid = start + (end-start)/2;
            int min1 = findSmallest(A, start, mid);
            int min2 = findSmallest(A, mid+1, end);

            return Math.min(min1, min2);    
    }
}

Here is the method to find Second smallest. Basic idea is to return the max when search size is <=2. For rest of the search return min.

public static int findSecondSmallest(int[] A, int start, int end){
    if(end == start){
        return A[start];
    }else if(start == end-1){
        return Math.max(A[start], A[end]);
    }else{
            int mid = start + (end-start)/2;
            int min1 = findSecondSmallest(A, start, mid);
            int min2 = findSecondSmallest(A, mid+1, end);

            return Math.min(min1, min2);    
    }
} 

Answer 5

#include <stdio.h>
#include <limits.h> /* For INT_MAX */

/* Function to print first smallest and second smallest elements */
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)
    {
      second = arr[i];
    }
  }
  printf("The smallest element is %d and second Smallest element is %d",
         first, second);
}

/* Driver program to test above function */
int main()
{
  int arr[] = {12, 13, 15, 10, 35, 1};
  print2Smallest(arr, 6);
  getchar();
  return 0;
}

Answer 6

Call Collections.min(), then remove the element you got from the List, and call it again?

    List<Integer> list = Arrays.asList(20, 30, 90, 50);
    List<Integer> copy = new ArrayList<Integer>(list);
    Integer smallest = Collections.min(copy); // 20
    copy.remove(smallest);
    Integer secondSmallest = Collections.min(copy); // 30

(Making a copy not to mess with the original.)

This is probably far from the most performant solution (From Collections.min() Javadoc: "This method iterates over the entire collection, hence it requires time proportional to the size of the collection."), but it's very simple to write and maintain. :)