Find the second maximum number in an array with the smallest complexity

Question

Tried to googled it but with no luck. How can I find the second maximum number in an array with the smallest complexity?

code OR idea will be much help.

I can loop through an array and look for the maximum number after that, I have the maximum number and then loop the array again to find the second the same way.

But for sure it is not efficient.

Answer 1

You could sort the array and choose the item at the second index, but the following O(n) loop will be much faster.

int[] myArray = new int[] { 0, 1, 2, 3, 13, 8, 5 };
int largest = int.MinValue;
int second = int.MinValue;
foreach (int i in myArray)
{
 if (i > largest)
 {
  second = largest;
  largest = i;
 }
else if (i > second)
    second = i;
}

System.Console.WriteLine(second);

OR

Try this (using LINQ):

int secondHighest = (from number in test
                             orderby number descending
                             select number).Distinct().Skip(1).First()

How to get the second highest number in an array in Visual C#?

Answer 2

public static int F(int[] array)
{
    array = array.OrderByDescending(c => c).Distinct().ToArray();
    switch (array.Count())
    {
        case 0:
            return -1;
        case 1:
            return array[0];
    }
    return array[1];
}

Answer 3

Answer in C# :

static void Main(string[] args)
        {
            //let us define array and vars
            var arr = new int[]{ 100, -3, 95,100,95, 177,-5,-4,177,101 };

            int biggest =0, secondBiggest=0;
            for (int i = 0; i < arr.Length; ++i)
                {
                int arrItem = arr[i];
                if(arrItem > biggest)
                {
                    secondBiggest = biggest; //always store the prev value of biggest 
                                             //to second biggest...
                    biggest = arrItem;
                 }
                else if (arrItem > secondBiggest && arrItem < biggest) //if in our 
                 //iteration we will find a number that is bigger than secondBiggest and smaller than biggest 
                   secondBiggest = arrItem;
            }

            Console.WriteLine($"Biggest Number:{biggest}, SecondBiggestNumber: 
                              {secondBiggest}");
            Console.ReadLine(); //make program wait
        }

Output : Biggest Number:177, SecondBiggestNumber:101