Is it possible to get the 2 largest numbers in a list using a single 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 an interview question and didn't really get it in time.

Answer 1

It seems pretty straightforward..

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;

Quick explanation:

• Define -1 as a placeholder, could use int.MinValue, or better yet a separate bool to indicate no-match
• If the value tested is bigger than the current maximum (max1), assign current maximum to max2, new value to max1
• Else if must be smaller, but if it's bigger than second-maximum, assign new value to max2

Answer 2

In general, you can find the K largest (or smallest) numbers in an array using a single 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 has at most K elements. Walk though the array and for each item:

1. if there list is not yet full, insert the item
2. otherwise, if the item is bigger than the smallest item in the list, insert this item and remove the smallest one.

In the end, the list will contain K largest items, which is what we wanted.

This solution is quite slow, though. Using a self-balancing binary search tree or a skip list, you could get to O(N log K). (Since it's impossible to sort faster than O(N log N) in general case, and this method can be used for sorting the whole array if we set K = N, this looks like the best we can get.)

In the case of K = 2, you don't need all this heavy machinery. Just two variables representing the two positions in the list are enough.