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?

Does it matter is the array is reordered in the process of finding the second maximum? — Martin, Mar 06 '10 at 21:39
use `Heap` structure instead `array` or use `sorted array` structure — gaussblurinc, Aug 28 '13 at 09:40

codaddict · Accepted Answer · 2010-03-06T16:50:16.893

30

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

edited Mar 06 '10 at 16:50

answered Mar 06 '10 at 14:15

codaddict

445,704
82
492
529

3

You're right about the negative numbers. However your code will give second_max == max if there are two occurences of the max number. Whether that is correct or not is not clearly stated in the question. – Anders Abel Mar 06 '10 at 14:28
I like the test for the first two elements prior to the for loop. There could even be a guard for the degenerate case of a two element array...and avoid the loop entirely. – Stan Graves Mar 06 '10 at 14:31
@Anders: Exactly. For input like {1,2,3,3}. The def of second_max can vary. It can be just second_max or a second_max different from max. I've gone with the 1st one, as it makes sense (at least to me) and that is what even the library std::nth_element would do. – codaddict Mar 06 '10 at 14:33
A small optimization, you can compare the current array element in the loop with second_max first and then if that passes, then compare with max. So it would be like : if (arr[i] > second_max) { if (arr[i] > max) { second_max = max; max = arr[i]; } else if (arr[i] != max) { second_max = arr[i]; } } This will always give different values for max and second_max, if the array does not contain a single number throughout. – abhinav Mar 06 '10 at 15:14

score 16 · Answer 2 · edited Aug 28 '13 at 09:37

16

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

edited Aug 28 '13 at 09:37

answered Mar 06 '10 at 14:06

avakar

32,009
9
68
103

18

OK, explain how std::nth_element is implemented. – Svante Mar 06 '10 at 15:13
1

See http://en.wikipedia.org/wiki/Selection_algorithm and http://stackoverflow.com/questions/2392485/algorithm-for-nth-element – avakar Mar 06 '10 at 15:26
1

Deleted my answer since it was pretty much a dupe. – Robert Davis Mar 06 '10 at 16:53
4

Depending on how pivot is selected, it may be `O(N^2)` in the worst-case. The `O(N)`-guaranteed one pass algorithm, while not extensible, is better for this specific problem. – polygenelubricants Mar 06 '10 at 18:57
@polygenelubricants, can you elaborate? The problem is `O(n)` in worst-case. The page I linked to provides an `O(n)` worst-case algorithm. – avakar Mar 06 '10 at 20:43
Like I said, it depends on how the pivot is selected. The partition-based selection algorithm, just like the partition-based quick sort algorithm, can exhibit `O(N^2)` worst-case behavior unless you choose the pivot very carefully (wikipedia: "Like quicksort, the performance of the algorithm is sensitive to the pivot that is chosen. If bad pivots are consistently chosen, this degrades to the minimum-based selection described previously, and so can require as much as O(n^2) time"). On average in practice, though, even the potentially bad pivot selection algorithm is good enough. – polygenelubricants Mar 06 '10 at 20:57
The point I was missing is that the standard guarantees expected linear complexity for `std::nth_element`, not worst-case. As such, the implementation may indeed exhibit super-linear runtime. – avakar Mar 06 '10 at 21:24
Does it work when there are duplicates in the array? – Brahim Jun 04 '15 at 08:16
avatar: The problem is O(N) worst case if Intraselect is used. But if just QuickSelect is used, that can go bad and can be O(N * N) . The other thing is the ISO C++ standard only says on average the algorithm has to be O(N). That means QuickSelect is fine and it does not mandate IntraSelect – SJHowe Nov 18 '22 at 11:23

Anders Abel · Answer 3 · 2010-03-06T14:18:41.173

7

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

edited Mar 06 '10 at 14:18

answered Mar 06 '10 at 14:08

Anders Abel

67,989
17
150
217

1

In the second test, make sure arr[i] != max; otherwise your max and second_max could wind up the same, which could be a problem depending on how you'd like things to work. – ty. Mar 06 '10 at 14:12
1

@TopCoder: What is the correct behaviour in case of two occurences of the max value? I don't think it is clearly stated in the question. – Anders Abel Mar 06 '10 at 14:34
1

You could change the first test to "arr[i]>=max" and remove the "arr[i] != max" from the second test. That would allow max and second_max to equal the same value, but only if that value is duplicated in the array. Depending on the particulars of the question, that may be a valid answer. – Stan Graves Mar 06 '10 at 14:37

Johann Gerell · Answer 4 · 2010-03-06T15:46:58.500

2

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

edited Mar 06 '10 at 15:46

answered Mar 06 '10 at 14:14

Johann Gerell

24,991
10
72
122

This never pushes the first down to second place. Consider {5, 1, 7}. – John Marshall Mar 06 '10 at 14:41
Strange use of std::for_each. – pmr Mar 06 '10 at 14:46
@pmr: "Strange use" - in what way? – Johann Gerell Mar 06 '10 at 15:10
1

@Johann: `std::for_each()` can't be used as a loop-statement - its a function. Try to compile your code and watch all those errors fly by. You probably meant to write `for` instead. *(side-note: even if there was a `for_each` statement, `++it` would contradict the intention)* – Georg Fritzsche Mar 06 '10 at 15:15
@gf: Ouch, the C++ days were too long ago... - fixed. – Johann Gerell Mar 06 '10 at 15:46
@Johann: As gf said, your use of std::for_each is simply wrong. You couldn't even define the block inside your for statement as a functor as it depends on values outside of it. It's just a minor flaw however. Just change std::for_each to for. – pmr Mar 06 '10 at 15:48
@Johann: I wrote the commented while you edited it. Didn't mean to keep on bashing onto that minor flaw :) – pmr Mar 06 '10 at 21:51

score 2 · Answer 5 · answered Mar 06 '10 at 14:34

2

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

answered Mar 06 '10 at 14:34

Hans Passant

922,412
146
1,693
2,536

score 1 · Answer 6 · answered Mar 06 '10 at 18:09

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.

score 1 · Answer 7 · answered Mar 06 '10 at 18:39

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

score 1 · Answer 8 · answered Mar 07 '10 at 06:19

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.

typo.. you need max = element. – Karoly Horvath Nov 05 '11 at 00:17 — Karoly Horvath, Nov 05 '11 at 00:17

score 1 · Answer 9 · edited Nov 09 '12 at 08:24

1

Check this solution.

max1 = a[0];
max2 = a[1];

for (i = 1; i < n; i++)
{
    if (max1 < a[i])
    {
        max2 = max1;
        max1 = a[i];
    }

    if (max2 == max1) max2 = a[i + 1];

    if (max2 == a[n])
    {
        printf("All numbers are the same no second max.\n");
        return 0;
    }

    if (max2 < a[i] && max1 != a[i]) max2 = a[i];
}

edited Nov 09 '12 at 08:24

Mario S

11,715
24
39
47

answered Oct 16 '11 at 20:11

mitta

11
1

What happens if a[0]=a[1] = max? I think there's a problem then – Origin Nov 09 '12 at 08:29

score 0 · Answer 10 · answered Apr 05 '12 at 11:47

The upper bound should have be n+log2⁡n−2, but it bigger than O(n) in case of random selection algorithm, but in worst case it much smaller. The solution might be

build a tree like to find the MAX element with n - 1 comparisons

max(N) / \ max(N/2) max(N/2)
remove the MAX and find the MAX again log2n - 1 comparison

PS. It uses additional memory, but it faster than random selection algorithm in worst case.

score 0 · Answer 11 · answered Oct 05 '12 at 00:16

0

Can't we just sort this in decreasing order and take the 2nd element from the sorted array?

answered Oct 05 '12 at 00:16

jhon

87
2
10

score 0 · Answer 12 · answered Jan 07 '13 at 17:39

How about the following below. make_heap is O(n) so this is efficient and this is 1-pass We find the second max by taking advantage that it must be one of the heap children of the parent, which had the maximum.

#include <algorithm>
#include <iostream>

int main()
{
    int arr[6]={0,1,2,3,4,5};

    std::make_heap(arr, arr+6);
    std::cout << "First Max: " << arr[0] << '\n';
    std::cout << "Second Max: " << std::max(arr[1], arr[2]) << '\n';
    return 0;
}

score 0 · Answer 13 · answered Apr 22 '13 at 09:48

int max,secondMax;
max=secondMax=array[0];
                                                for(int i=0;i<array.length;i++)
    {                                                   if(array[i]>max)                                                    {                                           max=array[i];                                                   }
                                                        if(array[i]>secondMax && array[i]<max)                                                  {
    secondMax=array[i];                                                 }
    }

score 0 · Answer 14 · edited Jun 05 '16 at 11:25

0

#include <iostream>
using namespace std;

int main() {

   int  max = 0;
    int sec_Max = 0;

    int array[] = {81,70,6,78,54,77,7,78};

    int loopcount = sizeof(array)/sizeof(int);

    for(int i = 0 ; i < loopcount ; ++i)
    {

        if(array[i]>max)
        {
            sec_Max = max;
            max = array[i];
        }

        if(array[i] > sec_Max && array[i] < max)
        {
            sec_Max = array[i];
        }
    }

    cout<<"Max:" << max << " Second Max: "<<sec_Max<<endl;

    return 0;
}

edited Jun 05 '16 at 11:25

coyotte508

9,175
6
44
63

answered Jun 05 '16 at 11:18

Bunny

1
1

1

This question from years ago is already extensively answered and your question does not add anything new. Moreover there's no comment besides your code on what you did that OP didn't. – coyotte508 Jun 05 '16 at 11:30

score 0 · Answer 15 · edited Nov 26 '11 at 18:26

Here is something which may work ,

public static int secondLargest(int[] a){
    int max=0;
    int secondMax=0;

    for(int i=0;i<a.length;i++){
        if(a[i]<max){
            if(a[i]>secondMax){
                secondMax=a[i];
            }
            continue;
        }

        if(a[i]>max){
            secondMax=max;
            max=a[i];
        }

    }
    return secondMax;
}

score -1 · Answer 16 · edited Oct 16 '11 at 20:16

-1

// Set the first two different numbers as the maximum and second maximum numbers

 int max = array[0];
 int i = 1;
//n is the amount of numbers

 while (array[i] == max && i < n) i++;
 int sec_max = array[i];
 if( max < sec_max ) {
    tmp = sec_max;
    sec_max = max;
    max = tmp;
 }

//find the second maximum number

 for( ; i < n; ++i ) {
   if( array[i] > max ) {
     sec_max = max;
     max = array[i];
   } else if( array[i] > sec_max && array[i] != max ) {
     sec_max = array[i];
   }
 }
 printf("The second maximum number is %d\n", sec_max);

edited Oct 16 '11 at 20:16

Flexo

87,323
22
191
272

answered Sep 24 '11 at 12:13

tianya

93
1
4

Welcome on SO, here, it is a good practice to explain why to use your solution and not just how. That will make your answer more valuable and help further reader to have a better understanding of how you do it. I also suggest that you have a look on our FAQ : http://stackoverflow.com/faq. – ForceMagic Nov 11 '12 at 05:04

How can we find second maximum from array efficiently?

16 Answers16

Linked