How can we find second maximum from array efficiently?

Question

Is it possible to find the second maximum number from an array of integers by traversing the array only once?

As an example, I have a array of five integers from which I want to find second maximum number. Here is an attempt I gave in the interview:

#define MIN -1
int main()
{
    int max=MIN,second_max=MIN;
    int arr[6]={0,1,2,3,4,5};
    for(int i=0;i<5;i++){
        cout<<"::"<<arr[i];
    }
    for(int i=0;i<5;i++){
        if(arr[i]>max){
            second_max=max;
            max=arr[i];          
        }
    }
    cout<<endl<<"Second Max:"<<second_max;
    int i;
    cin>>i;
    return 0;
}

The interviewer, however, came up with the test case int arr[6]={5,4,3,2,1,0};, which prevents it from going to the if condition the second time. I said to the interviewer that the only way would be to parse the array two times (two for loops). Does anybody have a better solution?

Answer 1

The easiest solution would be to use std::nth_element.

Answer 2

for(int i = 0; i < 5; i++){
    if(arr[i] > max){
        second_max = max;
        max = arr[i];          
    }else if(arr[i] > second_max && arr[i] != max){
        second_max = arr[i];
    }
}

This works.

Answer 3

You need a second test:

 for(int i=0;i<5;i++){  
   if(arr[i]>max){  
     second_max=max;  
     max=arr[i];            
   }
   else if (arr[i] > second_max && arr[i] != max){
     second_max = arr[i];
   }
 }

Answer 4

Here you are:

std::pair<int, int> GetTwoBiggestNumbers(const std::vector<int>& array)
{
    std::pair<int, int> biggest;
    biggest.first = std::max(array[0], array[1]);  // Biggest of the first two.
    biggest.second = std::min(array[0], array[1]); // Smallest of the first two.

    // Continue with the third.
    for(std::vector<int>::const_iterator it = array.begin() + 2;
        it != array.end();
        ++it)
    {
        if(*it > biggest.first)
        {
            biggest.second = biggest.first;
            biggest.first = *it;
        }
        else if(*it > biggest.second)
        {
            biggest.second = *it;
        }
    }

    return biggest;
}

Answer 5

Your initialization of max and second_max to -1 is flawed. What if the array has values like {-2,-3,-4}?

What you can do instead is to take the first 2 elements of the array (assuming the array has at least 2 elements), compare them, assign the smaller one to second_max and the larger one to max:

if(arr[0] > arr[1]) {
 second_max = arr[1];
 max = arr[0];
} else {
 second_max = arr[0];
 max = arr[1];
}

Then start comparing from the 3rd element and update max and/or second_max as needed:

for(int i = 2; i < arr_len; i++){
    // use >= n not just > as max and second_max can hav same value. Ex:{1,2,3,3}   
    if(arr[i] >= max){  
        second_max=max;
        max=arr[i];          
    }
    else if(arr[i] > second_max){
        second_max=arr[i];
    }
}

Answer 6

Your original code is okay, you just have to initialize the max and second_max variables. Use the first two elements in the array.

Answer 7

Quickselect is the way to go with this one. Pseudo code is available at that link so I shall just explain the overall algorithm:

QuickSelect for kth largest number:
    Select a pivot element
    Split array around pivot
    If (k < new pivot index)
       perform quickselect on left hand sub array
     else if (k > new pivot index)
       perform quickselect on right hand sub array (make sure to offset k by size of lefthand array + 1)
     else
       return pivot

This is quite obviously based on the good old quicksort algorithm.

Following this algorithm through, always selecting element zero as the pivot every time:

select 4th largest number:
1) array = {1, 3, 2, 7, 11, 0, -4}
partition with 1 as pivot
{0, -4, _1_, 3, 2, 7, 11}
4 > 2 (new pivot index) so...

2) Select 1st (4 - 3) largest number from right sub array
array = {3, 2, 7, 11}
partition with 3 as pivot
{2, _3_, 7, 11}
1 < 2 (new pivot index) so...

3) select 1st largest number from left sub array
array = {2}

4) Done, 4th largest number is 2

This will leave your array in an undefined order afterwards, it's up to you if that's a problem.

Answer 8

Step 1. Decide on first two numbers.
Step 2. Loop through remaining numbers.
Step 3. Maintain latest maximum and second maximum.
Step 4. When updating second maximum, be aware that you are not making maximum and second maximum equal.

Tested for sorted input (ascending and descending), random input, input having duplicates, works fine.

#include <iostream>
#define MAX 50
int GetSecondMaximum(int* data, unsigned int size)
{
    int max, secmax;
    // Decide on first two numbers
    if (data[0] > data[1])
    {
        max = data[0];
        secmax = data[1];
    }
    else
    {
        secmax = data[0];
        max = data[1];
    }
    // Loop through remaining numbers
    for (unsigned int i = 2; i < size; ++i)
    {
        if (data[i] > max)
        {
            secmax = max;
            max = data[i];
        }
        else if (data[i] > secmax && data[i] != max/*removes duplicate problem*/)
            secmax = data[i];
    }
    return secmax;
}
int main()
{
    int data[MAX];
    // Fill with random integers
    for (unsigned int i = 0; i < MAX; ++i)
    {
        data[i] = rand() % MAX;
        std::cout << "[" << data[i] << "] "; // Display input
    }
    std::cout << std::endl << std::endl;
    // Find second maximum
    int nSecondMax = GetSecondMaximum(data, MAX);
    // Display output
    std::cout << "Second Maximum = " << nSecondMax << std::endl;
    // Wait for user input
    std::cin.get();
    return 0;
}

Answer 9

Other way to solve this problem, is to use comparisons among the elements. Like for example,

a[10] = {1,2,3,4,5,6,7,8,9,10}

Compare 1,2 and say max = 2 and second max = 1

Now compare 3 and 4 and compare the greatest of them with max.

if element > max
     second max = max
     element = max
else if element > second max
     second max = element

The advantage with this is, you are eliminating two numbers in just two comparisons.

Let me know, if you have any problem understanding this.