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

• finnw: I would have upvoted this if you hadn't posted that "I am in a hurry" comment in response to Josh's answer.
• bevacqua: -1 for "being in a hurry" what is that, even?

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

• crazyTechie: Hi Josh Leitzel, I agree with you. But I am in little hurry. Thanks.
• Carl Smotricz: We dish out information. We're not here to compensate for your poor planning.
• Jon Skeet: @abishek: That's no excuse really. Josh has given you a high level description of what to do - it shouldn't take you very long to convert that into code.
• Josh Leitzel: Sorry, but I won't post the code for you. I've basically described the algorithm for you in words, which should make it very easy for you to write the corresponding Java. If you're interested in just grabbing the code and turning it in, then I'm sure you can find something with a quick Google search as this is a common elementary programming algorithm. But I think it's important that you try to grasp the concepts, as this kind of problem-solving thinking is incredibly important.
• crazyTechie: @Tony - To be frank I am in parallel working on it. And I got the solution myself. Thanks

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

• Carl Smotricz: Objects don't have "<" and ">", those only work for numbers. But you can use compareTo(). Here's the API for Comparable: <java.sun.com/j2se/1.4.2/docs/api/java/lang/Comparable.html>
• crazyTechie: but obj.getvalue returns integer
• Carl Smotricz: Oh, you have a certain kind of object. OK then. What will your algorithm do if there is a 0 in the list?
• crazyTechie: :) there wont be a zero in the list..this is list of time taken by students to solve a problem. I dont think anyone would solve it in zero sec's. :)
• Troubadour: @abhishek: You never know, they might be in a hurry too.

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

• Andrew Thompson: Given the OP was asking for a hurried solution in Java, back in 2009, I think your answer missed the mark on two counts.

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

• Carl Smotricz: That would work, but it doesn't sound like it would meet the requirements of the assignment. For one thing, the loops would be implicit. And there would in effect be two loops running in sequence.
• Jonik: Heh, I don't know about any assignments. This meets the spec of finding two smallest (even with duplicates), and no-one said it wouldn't be ok to use the libraries ;-) (stackoverflow.com/questions/822768/…)
• Jonik: The question does mention single loop though, so we could argue about that part of course. :) This solution itself uses zero loops, obviously, although under the hood probably 3 are involved (one for making the copy). In any case, I think this approach should be mentioned too.
• Jonik: Well, right, perhaps this is a bit silly answer to that q. Still, in the real world, you should start optimising this kind of stuff only after your profiler shows that there's a real performance bottleneck there (assuming you're not writing a library or something).
• Jonik: More downvotes please! :P If I'm going to delete this, I might just as well get the Peer Pressure tag for it. ;)