Is it possible to get the 2 largest numbers in a list using one pass?

Question

Is it possible to find the 2 largest numbers in an array and only loop through the collection once?

I had this as a question for an interview, and I really did not have time.

Answer 1

It seems pretty simple.

int[] nums = { 3, 1, 4, 1, 5, 9, 2, 6 }; int max1 = -1; int max2 = -1; foreach (int num in nums) { if (num > max1) { max2 = max1; max1 = num; } else if (num > max2) { max2 = num; } } 

For example:

 // 3: max2 = -1; max1 = 3; // 1: max2 = 1; // 4: max2 = 3; max1 = 4; 

Short description:

• Define -1 as a placeholder, use int.MinValue or, even better, a separate bool to indicate no match
• If the test value is greater than the current maximum (max1), assign the current maximum max2, the new value max1
• Otherwise, if it should be less, but if it is more than the second maximum, assign a new value max2

Answer 2

In general, you can find the K largest (or smallest) numbers in the array using one pass for any K. The total time complexity will be O (NK), where N is the size of the array:

Keep a sorted list of numbers that contains no more than K elements. Go through the array and for each element:

• If the list is not already filled, insert an element
• otherwise, if the item is larger than the smallest item in the list, insert that item and delete the smallest.

At the end, the list will contain the K largest elements that we wanted.

This solution is rather slow. Using a self-balancing binary search tree or a skip list, you can go to O (N log K). (Since it is generally impossible to sort faster than O (N log N), and this method can be used to sort the entire array, if we set K = N, it looks like the best we can get.)

In the case of K = 2, you do not need all this heavy equipment. Two variables are enough, representing two positions in the list.

Answer 3

Yes it is. As you go through the list, keep a record of the largest number found and whenever you find a larger number, save the largest found in the second largest found before updating the largest found. If the value is greater than the second largest, update the second largest.