8

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.

Improve this question
4
  • Something like this stackoverflow.com/questions/852439/…. And then take the second item. Commented Feb 11, 2013 at 10:41
  • What do you mean by 'smallest complexity'? Commented Feb 11, 2013 at 10:44
  • 1
    Define "complexity", are we talking clear maintainable code? Or computational efficiency? Commented Feb 11, 2013 at 10:44
  • The fastest and most efficient algorithm Commented Feb 11, 2013 at 10:45

20 Answers 20

Reset to default
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#?

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

I liked that Linq solution, Is it efficient? please explain.
yes efficient and good also.............. Its sorting the numbers in the order "descending" and then skipping first one and getting the Second one.
Yes i tried that working good! and very nice approach, How can I 'measure' the complexity in that?
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)
The first way might output incorrect result if you have duplicates for the maximum values(which is 13 here)
|
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

Improve this answer

Comments

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];
}
Improve this answer

Comments

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();
Improve this answer

Comments

0 
/* 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]))
Improve this answer

Comments

0 
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");
}
Improve this answer

Comments

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
Improve this answer

Comments

0

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];
            }
        }
Improve this answer

Comments

-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.

Improve this answer

1 Comment

You can do with O(n) instead of O(2n) or O(n log n).
-1 
 var result = (from elements in inputElements
    orderby elements descending
    select elements).Distinct().Skip(1).Take(1);
 return result.FirstOrDefault();
Improve this answer

1 Comment

will work for zero element, first will break when array having zero element.
-1

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

Improve this answer

Comments

-1 
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();
        }   
    }
}
Improve this answer

1 Comment

This would be significantly more useful if you included comments or otherwise described what it does rather than just post the code.
-1

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

     }
Improve this answer

1 Comment

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'
-1

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

       }
   }

}
Improve this answer

Comments

-1 
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();
Improve this answer

Comments

-1 
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);
Improve this answer

2 Comments

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!
How is this answer any different than the accepted answer or Dmitry's answer?
-1 
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

Improve this answer

Comments

-2 
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();
        }
    }
}
Improve this answer

2 Comments

This would be significantly more useful if you included comments or otherwise described what it does rather than just post the code.
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.
-3

Sort the array and take the second to last value?

Improve this answer

1 Comment

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.
-3 
public static int F(int[] array)
{
    
    Array.Sort(array);
  
    //Will reverse the array in a Descending format
    Array.Reverse(array);
    
    return array[1];
}
Improve this answer

2 Comments

Thank you for your interest in contributing to the Stack Overflow community. This question already has quite a few answers—including one that has been extensively validated by the community. Are you certain your approach hasn’t been given previously? If so, it would be useful to explain how your approach is different, under what circumstances your approach might be preferred, and/or why you think the previous answers aren’t sufficient. Can you kindly edit your answer to offer an explanation?
This unnecessarily increases complexity by reversing the array. Why not just access the second-last entry of the array?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.