CODEWITHSUNDEEP
c#.net
user1400915
user1400915

Reputation: 1943

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

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?

Upvotes: 2

Views: 90

Answers (4)

w.b
w.b

Reputation: 11238

This is a solution iterating just once and using LINQ and C# 7 tuples:

var input = Enumerable.Range(0, 101);

var topTwo = input.Aggregate((Biggest: Int32.MinValue, SecondBiggest: Int32.MinValue),
                             (acc, next) =>
                             {
                                 if (next > acc.Biggest)
                                 {
                                     acc.SecondBiggest = acc.Biggest;
                                     acc.Biggest = next;
                                 }

                                 if (next < acc.Biggest && next > acc.SecondBiggest)   
                                     acc.SecondBiggest = next;

                                 return acc;
                             });

WriteLine(topTwo.SecondBiggest);  // 99

Upvotes: 0

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186833

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

Upvotes: 4

Carra
Carra

Reputation: 17964

You can do it by keeping track of the next max and iterating once through the list.

int max = Int32.MinValue;
int nextMax = Int32.MinValue;

for(int i=0; i<list.Count(); i++)
{
  if(list[i] > max)
  {
    nextMax = max;
    max = list[i]; 
  }
  else if(list[i] > nextMax)
  {
    nextMax = list[i];
  }
}

Upvotes: 2

w.b
w.b

Reputation: 11238

If your list contains only distinct values, you can also do:

var max = input.Max();
input.Remove(max);
var result = input.Max();

Upvotes: 2

Related Questions