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.

Something like this http://stackoverflow.com/questions/852439/how-to-sort-elements-of-array-list-in-c-sharp. And then take the second item. — Youp Bernoulli, Feb 11 '13 at 10:41
Define "complexity", are we talking clear maintainable code? Or computational efficiency? — Massif, Feb 11 '13 at 10:44

score 32 · Accepted Answer · edited May 23 '17 at 12:10

32

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#?

edited May 23 '17 at 12:10

Community

1
1

answered Feb 11 '13 at 10:41

andy

5,979
2
27
49

I liked that Linq solution, Is it efficient? please explain. – E.Meir Feb 11 '13 at 10:51
yes efficient and good also.............. Its sorting the numbers in the order "descending" and then skipping first one and getting the Second one. – andy Feb 11 '13 at 10:52
Yes i tried that working good! and very nice approach, How can I 'measure' the complexity in that? – E.Meir Feb 11 '13 at 10:58
Minor add, You should add Distinct() before Skipping 1. – E.Meir Feb 11 '13 at 11:05
1

Question : in the LINQ implementation, will it actually sort the whole array ? Indeed, this is not theoretically required (the first solution that you propose doesn't sort it, it just walks through once) – Myobis Jun 12 '13 at 07:50
2

The first way might output incorrect result if you have duplicates for the maximum values(which is 13 here) – Vivekh Nov 28 '18 at 13:00
The loop solution is O(N) but the Linq solution is O(N.Log(N)), so don't use that if you're worried about performance. – Matthew Watson Aug 23 '19 at 07:34

score 3 · Answer 2 · answered Nov 20 '18 at 16:49

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

score 1 · Answer 3 · answered Aug 13 '14 at 00:12

1

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

answered Aug 13 '14 at 00:12

Haithem KAROUI

1,533
4
18
39

score 0 · Answer 4 · answered Feb 11 '13 at 10:44

0

You'd want to sort the numbers, then just take the second largest. Here's a snippet without any consideration of efficiency:

var numbers = new int[] { 3, 5, 1, 5, 4 };
var result=numbers.OrderByDescending(x=>x).Distinct().Skip(1).First();

answered Feb 11 '13 at 10:44

Dmitry Ledentsov

3,620
18
28

score 0 · Answer 5 · answered Mar 14 '18 at 04:49

 static void Main(string[] args)
    {
        int[] myArray = new int[] { 0, 11, 2, 15, 16, 8, 16 ,8,15};
        int Smallest = myArray.Min();
        int Largest = myArray.Max();
        foreach (int i in myArray)
        {
            if(i>Smallest && i<Largest)
            {
                Smallest=i;
            }
        }
        System.Console.WriteLine(Smallest);
        Console.ReadLine();   
    }

This will work even if you have reputation of items in an array

nahid · Answer 6 · 2018-10-29T16:04:28.143

           int[] arr = {-10, -3, -3, -6};
           int h = int.MinValue, m = int.MinValue;

                    foreach (var t in arr)
                    {
                        if (t == h || t == m)
                            continue;
                        if (t > h)
                        {                            
                            m = h;
                            h = t;
                        }
                        else if(t > m )
                        {                            
                            m = t;
                        }

                    }

            Console.WriteLine("High: {0} 2nd High: {1}", h, m);
                   //or,
            m = arr.OrderByDescending(i => i).Distinct().Skip(1).First();

            Console.WriteLine("High: {0} 2nd High: {1}", h, m);

Please note that code only answers are really discouraged. Just dumping the code on somebody isn't very helpful for future readers. Focus on explaining what you are doing, too! — itsmysterybox, Oct 29 '18 at 06:52
How is this answer any different than the accepted answer or Dmitry's answer? — Steven B., Nov 20 '18 at 16:59

score 0 · Answer 7 · answered May 31 '19 at 20:43

/* we can use recursion */
var counter = 0;
     findSecondMax = (arr)=> {

        let max = Math.max(...arr);
        counter++;
        return counter == 1 ? findSecondMax(arr.slice(0,arr.indexOf(max)).concat(arr.slice(arr.indexOf(max)+1))) : max;
    }

    console.log(findSecondMax([1,5,2,3,0]))

score 0 · Answer 8 · edited Aug 23 '19 at 09:01

static void Main(string[] args){
    int[] arr = new int[5];
    int i, j,k;
    Console.WriteLine("Enter Array");

    for (i = 0; i < 5; i++) {
        Console.Write("element - {0} : ", i);
        arr[i] = Convert.ToInt32(Console.ReadLine());
    }

    Console.Write("\nElements in array are: ");
    j=arr[0];
    k=j;

    for (i = 1; i < 5; i++) {
        if (j < arr[i])
        {
            if(j>k)
            {
                k=j;
            }
            j=arr[i];
        }  
    }

    Console.WriteLine("First Greatest element: "+ j);
    Console.WriteLine("Second Greatest element: "+ k);
    Console.Write("\n");
}

score 0 · Answer 9 · edited Jun 03 '21 at 13:53

0

int max = 0;
int secondmax = 0;
int[] arr = { 2, 11, 15, 1, 7, 99, 6, 85, 4 };

for (int r = 0; r < arr.Length; r++)
{
    if (max < arr[r])
    {
        max = arr[r];
    }
}

for (int r = 0; r < arr.Length; r++)
{
    if (secondmax < arr[r] && arr[r] < max)
    {
        secondmax = arr[r];
    }
}

Console.WriteLine(max);
Console.WriteLine(secondmax);
Console.Read();

edited Jun 03 '21 at 13:53

Josef

2,869
2
22
23

answered Jun 03 '21 at 07:49

Shahab Adnan

1
2

score 0 · Answer 10 · answered Jan 16 '22 at 18:16

0

Python 36>=

def sec_max(array: list) -> int:
_max_: int = max(array)
second: int = 0
for element in array:
    if second < element < _max_:
        second = element
    else:
        continue
return second

answered Jan 16 '22 at 18:16

Amine Mohamed

21
1

score 0 · Answer 11 · answered Apr 17 '22 at 11:04

Using below code we can find out second highest number, even array contains multiple max numbers

// int[] myArray = { 25, 25, 5, 20, 50, 23, 10 };
    public static int GetSecondHighestNumberForUniqueNumbers(int[] numbers)
    {
        int highestNumber = 0, Seconhight = 0;
        List<int> numberList = new List<int>();
        for (int i = 0; i < numbers.Length; i++)
        {
            //For loop should move forward only for unique items
            if (numberList.Contains(numbers[i]))
                continue;
            else
                numberList.Add(numbers[i]);

            //find higest number
            if (highestNumber < numbers[i])
            {
                Seconhight = highestNumber;
                highestNumber = numbers[i];
            } //find second highest number
            else if (Seconhight < numbers[i])
            {
                Seconhight = numbers[i];
            }
        }

score -1 · Answer 12 · answered Feb 11 '13 at 10:42

-1

It's not like that your structure is a tree...It's just a simple array, right?

The best solution is to sort the array. And depending on descending or ascending, display the second or the 2nd last element respectively.

The other alternative is to use some inbuilt methods, to get the initial max. Pop that element, and then search for the max again. Don't know C#, so can't give the direct code.

answered Feb 11 '13 at 10:42

Pratik Bothra

2,642
2
30
44

You can do with O(n) instead of O(2n) or O(n log n). – Joey Feb 11 '13 at 10:47

score -1 · Answer 13 · edited Sep 24 '16 at 21:28

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int size;
            Console.WriteLine("Enter the size of array");
            size = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Enter the element of array");
            int[] arr = new int[size];
            for (int i = 0; i < size; i++)
            {
                arr[i] = Convert.ToInt32(Console.ReadLine());
            }
            int length = arr.Length;
            Program program = new Program();
            program.SeconadLargestValue(arr, length);
        }

        private void SeconadLargestValue(int[] arr, int length)
        {
            int maxValue = 0;
            int secondMaxValue = 0;
            for (int i = 0; i < length; i++)
            {
                if (arr[i] > maxValue)
                {
                    secondMaxValue = maxValue;
                    maxValue = arr[i];
                }
                else if(arr[i] > secondMaxValue)
                {
                    secondMaxValue = arr[i];
                }
            }
            Console.WriteLine("First Largest number :"+maxValue);
            Console.WriteLine("Second Largest number :"+secondMaxValue);
            Console.ReadLine();
        }   
    }
}

This would be significantly more useful if you included comments or otherwise described what it does rather than just post the code. — Whit Waldo, Nov 04 '16 at 17:31

score -1 · Answer 14 · edited Sep 11 '15 at 22:22

-1

 var result = (from elements in inputElements
    orderby elements descending
    select elements).Distinct().Skip(1).Take(1);
 return result.FirstOrDefault();

edited Sep 11 '15 at 22:22

QuantumLicht

2,103
3
23
32

answered Sep 11 '15 at 21:25

Gaurav Bhushan

11

will work for zero element, first will break when array having zero element. – Gaurav Bhushan Sep 11 '15 at 21:27

Praveen M P · Answer 15 · 2016-11-28T13:00:13.877

I am giving solution that's in JavaScript, it takes o(n/2) complexity to find the highest and second highest number.
here is the working Fiddler Link

    var num=[1020215,2000,35,2,54546,456,2,2345,24,545,132,5469,25653,0,2315648978523];
var j=num.length-1;
var firstHighest=0,seoncdHighest=0;
num[0] >num[num.length-1]?(firstHighest=num[0],seoncdHighest=num[num.length-1]):(firstHighest=num[num.length-1],   seoncdHighest=num[0]);
j--;
for(var i=1;i<=num.length/2;i++,j--)
{
   if(num[i] < num[j] )
   {
          if(firstHighest < num[j]){
          seoncdHighest=firstHighest;
           firstHighest= num[j];
          }
           else if(seoncdHighest < num[j] ) {
               seoncdHighest= num[j];

           }
   }
   else {
       if(firstHighest < num[i])
       {
           seoncdHighest=firstHighest;
           firstHighest= num[i];

       }
       else if(seoncdHighest < num[i] ) {
            seoncdHighest= num[i];

       }
   }

}

score -1 · Answer 16 · answered Nov 14 '15 at 06:48

This isn't too bad:

int[] myArray = new int[] { 0, 1, 2, 3, 13, 8, 5 };

var secondMax =
    myArray.Skip(2).Aggregate(
            myArray.Take(2).OrderByDescending(x => x).AsEnumerable(),
            (a, x) => a.Concat(new [] { x }).OrderByDescending(y => y).Take(2))
        .Skip(1)
        .First();

It's fairly low on complexity as it only every sorts a maximum of three elements

score -1 · Answer 17 · answered Nov 28 '16 at 07:11

My solution below.

    class Program
    {
      static void Main(string[] args)
        {
        Program pg = new Program();
        Console.WriteLine("*****************************Program to Find 2nd Highest and 2nd lowest from set of values.**************************");
        Console.WriteLine("Please enter the comma seperated numbers : ");
        string[] val = Console.ReadLine().Split(',');
        int[] inval = Array.ConvertAll(val, int.Parse); // Converts Array from one type to other in single line  or Following line
        // val.Select(int.Parse)
        Array.Sort(inval);
        Console.WriteLine("2nd Highest is : {0} \n 2nd Lowest is : {1}", pg.Return2ndHighest(inval), pg.Return2ndLowest(inval));
        Console.ReadLine();

        }


        //Method to get the 2nd lowest and 2nd highest from list of integers ex 1000,20,-10,40,100,200,400

        public  int Return2ndHighest(int[] values)
        {
           if (values.Length >= 2)
              return values[values.Length - 2];
           else
              return values[0];
         }

         public  int Return2ndLowest(int[] values)
         {
              if (values.Length > 2)
                  return values[1];
              else
                  return values[0];
          }

     }

or 'code' int[] val = Array.ConvertAll(Console.ReadLine().Split(','), int.Parse); Array.Sort(val); int min = val.Min(); int max = val.Max(); int length = val.Length; int Secondlowest = val.OrderBy(x => x).Skip(1).First(); int SecondHighest = val.OrderByDescending(x => x).Skip(1).First(); Console.WriteLine("2nd Highest is : {0} \n 2nd Lowest is : {1}", SecondHighest, Secondlowest); Console.ReadLine(); 'code' — Kiran Kumar, Nov 28 '16 at 07:39

score -2 · Answer 18 · answered Feb 11 '13 at 10:41

-2

Sort the array and take the second to last value?

answered Feb 11 '13 at 10:41

Captain Kenpachi

6,960
7
47
68

2

Sorting is not exactly a smaller complexity. He's getting O(n) right now. Sorting will only increase it to O(n lg n), unless RADIX is used. – Achrome Feb 11 '13 at 10:42

score -2 · Answer 19 · edited Nov 04 '16 at 18:43

namespace FindSecondLargestNumber
{
    class Program
    {
        static void Main(string[] args)
        {
            int max=0;
            int smax=0;
            int i;
            int[] a = new int[20];
            Console.WriteLine("enter the size of the array");
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine("elements");
            for (i = 0; i < n; i++)
            {
                a[i] = int.Parse(Console.ReadLine());

            }
            for (i = 0; i < n; i++)
            {
                if ( a[i]>max)
                {
                    smax = max;
                    max= a[i];
                }
                else if(a[i]>smax)
                {
                    smax=a[i];
                }
            }
            Console.WriteLine("max:" + max);

            Console.WriteLine("second max:"+smax);
                Console.ReadLine();
        }
    }
}

This would be significantly more useful if you included comments or otherwise described what it does rather than just post the code. — Whit Waldo, Nov 04 '16 at 17:31
Your code is not formatted correctly (only about half of it) and it's also completely lacking in explanation as to why this is the lowest complexity approach to solving the problem. — silentsod, Nov 04 '16 at 17:41

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

19 Answers19

Linked

Related