[Google Question] Second Maximum number in an array

Problem: Get the second maximum number in an array of unique integers. You need to minimize the number of comparisons.

Example:

Input: arr = [1,2,3,4]
Output: 3

Approach: We can use two variables approach to solve this problem easily but it will take 2*n comparisons to identify the second maximum. Let's see how we can reduce the number of comparisons. Let's use divide and conquer approach:

We can get the maximum of every pair of elements (arr[i], arr[i + 1]) in the array and store it in temp array. If we find that number of elements in the temp array is one that means we get the maximum number otherwise we will assign temp array to original array and repeat the process.

Using the above approach, we can get the maximum number but how to get the second maximum. If you see we really care about the numbers which were being compared to maximum number, right! As one of them should be the second maximum so what we will do while comparing arr[i] and arr[i + 1], we will also store the Min(arr[i], arr[i + 1]) in an hash where key is Max(arr[i], arr[i + 1)) and value is Min(arr[i], arr[i + 1]). Here are hash will have key as number and value is a list of numbers that were less than the key number which we found while comparing. If you see we are creating a tree here. For example say our input array is [1, 2, 3, 4, 5, 6, 7, 8]

                8

           /         \

       4                8

   /       \          /     \

  2        4       6        8

 /  \    /   \      /  \      /  \

1   2  3    4  5    6  7    8

If you see in the above tree, we just care about the children of 8 (max number) to get the second maximum. Instead of maintaining a tree, we are storing the children of max number in a hash table. Hopefully the approach is clear now.

Implementation in C#:

        public int FindSecondMaxUsingMinimumComparisons(int[] arr)

        {

            if (arr?.Length <= 1)

            {

                throw new ArgumentException();

            }

            List<int> nums = new List<int>(arr);

            Dictionary<int, List<int>> lesserNumbers = new Dictionary<int, List<int>>();

            while (nums.Count != 1)

            {

                List<int> tempStorage = new List<int>();

                for (int i = 0; i < nums.Count; i += 2)

                {

                    if (i + 1 == nums.Count)

                    {

                        tempStorage.Add(nums[i]);

                    }

                    else

                    {

                        if (nums[i] > nums[i + 1])

                        {

                            tempStorage.Add(nums[i]);

                            if (!lesserNumbers.ContainsKey(nums[i]))

                            {

                                lesserNumbers.Add(nums[i], new List<int>());

                            }

                            lesserNumbers[nums[i]].Add(nums[i + 1]);

                        }

                        else

                        {

                            tempStorage.Add(nums[i + 1]);

                            if (!lesserNumbers.ContainsKey(nums[i + 1]))

                            {

                                lesserNumbers.Add(nums[i + 1], new List<int>());

                            }

                            lesserNumbers[nums[i + 1]].Add(nums[i]);

                        }

                    }

                }

                nums = tempStorage;

            }

            return Enumerable.Max(lesserNumbers[nums[0]]);

        }

Complexity: Total comparisons: n + logn