How To Find A Second Largest Element in an Array?

Gaurav B Sinha

Rate me:

4.71/5 (4 votes)

11 Sep 2015CPOL

14.6K

Finding the second largest element in an array using Linq

Introduction

The code snippet below will show you how to find a second largest element in an array:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MSMUTest
{
    class Program
    {
        /*
         * Write a function that accepts an array of non-negative integers and 
         * returns the second largest integer in the array. Return -1 if there is no second largest.
         */

        public int [] AcceptArrayElements(int count)
        {
            int[] inputElement = new int[count];
            for (int cnt = 0; cnt < count; cnt++)
            {
                inputElement[cnt] = Convert.ToInt32(Console.ReadLine());
            }
            return inputElement;
        }
        

 public int FindSecondLargestElement(int[] inputElements)
        {

            var result = (from elements in inputElements
                          orderby elements descending
                          select elements).Distinct().Skip(1).Take(1);
#region ForBeginners
            // May use below code block if not much versed in linq.
            //var result = (from elements in inputElements
            //              orderby elements descending
            //              select elements
          //  int scndLargestNumber = -1;
            //int [] finalArray = result.ToArray();
            //for (int cnt = 0; cnt < finalArray.Length; cnt++)
            //{
               
            //    if ( finalArray[cnt] < finalArray[0])
            //    {
            //        scndLargestNumber = finalArray[cnt];
            //        break;
            //    }
               
            //}
#endregion

            return result.FirstOrDefault();
        }

        static void Main(string[] args)
        {
            Console.WriteLine("Please Enter Count");
            int count =Convert.ToInt32( Console.ReadLine());
            Program test = new Program();
            Console.WriteLine("Enter Your Number");
            int[] inputElements = test.AcceptArrayElements(count);
            for (int cnt = 0; cnt < inputElements.Length; cnt++)
            {
                Console.WriteLine("Your Input Element At Position {0} is {1}.", 
					cnt, inputElements[cnt]);
            }
            Console.WriteLine("Second Largest Element In Your Provided Input Is {0} ", 
				test.FindSecondLargestElement(inputElements));

        }
    }
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By

Gaurav B Sinha

Technical Lead

India

This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

Good

irneb14-Sep-15 1:06

irneb

14-Sep-15 1:06

Just a question - what about duplicate values? Would 2nd largest be the 2nd in the list if 2 or more duplicates are at the start of the ordered list? Or should the 2nd largest unique value be returned?

That may mean you get rid of the Distinct call or not. Which actually brings up another issue - are you sure this is most optimal approach? I can think of at least one O(N) approach, while this is an O(N log N) at best (the Destinct call adds some possible further complexity).

As an example:

namespace SecondLargest
{
    class Program
    {
        static Random rnd = new Random();
        static int count = 1000;

        public static void Main(string[] args)
        {
            int[] inputElements = new int[count];
            for (int cnt = 0; cnt < count; cnt++)
            {
                inputElements[cnt] = rnd.Next();
            }
            Stopwatch sw = new Stopwatch();
            sw.Restart();
            int Second = FindSecondLargestElement_Linq(inputElements);
            sw.Stop();          
            Console.WriteLine("Second largest {0}, found using O(N log N) LINQ-SQL, {1}", Second, sw.Elapsed);

            sw.Restart();
            Second = FindSecondLargestElement_Linq2(inputElements);
            sw.Stop();          
            Console.WriteLine("Second largest {0}, found using O(N log N) LINQ, {1}", Second, sw.Elapsed);

            sw.Restart();
            Second = FindSecondLargestElement_Imperative(inputElements);
            sw.Stop();          
            Console.WriteLine("Second largest {0}, found using O(N) imperative, {1}", Second, sw.Elapsed);

            Console.ReadKey(true);
        }

        public static int FindSecondLargestElement_Linq(int[] inputElements)
        {
            return (from elements in inputElements
                    orderby elements descending
                    select elements).Distinct().Skip(1).FirstOrDefault();       }

        public static int FindSecondLargestElement_Linq2(int[] inputElements)
        {
            return inputElements.OrderByDescending(k => k).Distinct().Skip(1).FirstOrDefault();
        }

        public static int FindSecondLargestElement_Imperative(int[] inputElements)
        {
            int L = int.MinValue;
            int S = int.MinValue;
            for (int i = 0; i < inputElements.Length; i++) {
                int V = inputElements[i];
                if (V > L) {
                    S = L;
                    L = V;
                } else if ((L > V) && (V > S)) {
                    S = V;
                }
            }
            return S;
        }
    }
}

Then the resulting time taken:

Second largest 2137772579, found using O(N log N) LINQ-SQL, 00:00:00.0061404
Second largest 2137772579, found using O(N log N) LINQ, 00:00:00.0003753
Second largest 2137772579, found using O(N) imperative, 00:00:00.0001044

Ouch ... that shows 2 things: (1) Using the SQL variant of LINQ actually adds a whole lot extra overhead to the already enumeration instantiation of Linq. And (2) the Linq method is at best 3 times slower than the imperative on a sample of 1000.

And just to be more comprehensive, I've done the same by repeating each call 3 times - to allow for pre-compilation & optimization:

Second largest 2140265055, found using O(N log N) LINQ-SQL, 00:00:00.0052420
Second largest 2140265055, found using O(N log N) LINQ-SQL, 00:00:00.0001626
Second largest 2140265055, found using O(N log N) LINQ-SQL, 00:00:00.0001410
Second largest 2140265055, found using O(N log N) LINQ, 00:00:00.0003709
Second largest 2140265055, found using O(N log N) LINQ, 00:00:00.0001407
Second largest 2140265055, found using O(N log N) LINQ, 00:00:00.0001401
Second largest 2140265055, found using O(N) imperative, 00:00:00.0001035
Second largest 2140265055, found using O(N) imperative, 00:00:00.0000011
Second largest 2140265055, found using O(N) imperative, 00:00:00.0000008

Much better results, yet still the imperative approach is orders of magnitude faster.

modified 14-Sep-15 7:22am.

Isn't the default value zero?

George Swan11-Sep-15 20:23

George Swan

11-Sep-15 20:23

Thanks for the tip. My understanding is that the default value of an int is zero not -1, so your method will return 0 if nothing is found. Also, I don't think you need to use Take(1)

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

Best wishes, George

modified 12-Sep-15 3:02am.

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.