CODEWITHSUNDEEP
c#algorithmmax
codecompleting
codecompleting

Reputation: 9611

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

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.

Upvotes: 7

Views: 4699

Answers (3)

Skizz
Skizz

Reputation: 71060

Yes, it is. As you traverse the list, keep a record of the largest number found and whenever you find a bigger number, save the largest found into a second largest found before updating the largest found. If the value is bigger than the second largest, then update the second largest value.

Upvotes: 0

svick
svick

Reputation: 244767

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.

Upvotes: 1

Kieren Johnstone
Kieren Johnstone

Reputation: 42003

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

Upvotes: 29

Related Questions