Finding the second last greatest element in list of integers C#

Question

I have a

list<int> input = //from db of one million records

of 1 million records .

Although I know that using input.OrderByDescending().Skip(1).Take(1) will solve the problem but if I have 1 million records , it is not a best practice to use OrderBY.

In this scenario which solution is the best one when we have more records?

Answer 1

Scan the list while tracking the max, as well as max2 and you'll get O(N) versus O(N * log(N)) time complexity:

  // Maximum value
  int max  = Math.Max(input[input.Count - 1], input[input.Count - 2]);
  // Second greatest   
  int max2 = Math.Min(input[input.Count - 1], input[input.Count - 2]);

  // i >= 0: Comparing with 0 is slightly faster then with Count
  for (int i = input.Count - 3; i >= 0; --i) {
    int v = input[i];

    if (v >= max) {
      max2 = max;
      max = v; 
    }
    else if (v > max2) 
      max2 = v;
  }

Edit: In case duplicates should be ignored (see comments below) and thus the answer for [1, 2, 3, 4, 4, 4, 4] should be 3, not 4:

  // Maximum value
  int max = int.MinValue;
  // Second greatest   
  int max2 = int.MinValue;

  // i >= 0: Comparing with 0 is slightly faster then with Count
  for (int i = input.Count - 1; i >= 0; --i) {
    int v = input[i];

    if (v > max) {
      max2 = max;
      max = v;
    }
    else if (v > max2 && v != max)
      max2 = v;
  }