second highest number in array with O(n) complexity

Question

Given an array how can we find the second highest number with O(n) complexity , best complexity i can get is O(nlogn) using sorting techniques. How can I get O(n) time complexity ?

possible duplicate of [Finding the second highest number in array](http://stackoverflow.com/questions/2615712/finding-the-second-highest-number-in-array) — Juan Lopes, Jan 20 '15 at 17:30
You say you have a list of arrays. What is **n** referring to here? Is it the total number of elements in the arrays combined? If so you can treat the list of arrays as one big array and use jaho's solution. — eigenchris, Jan 20 '15 at 17:31
is it a list of arrays or one array with n elements in it? make up your mind dude. — mrk, Jan 29 '15 at 00:15
Does this include duplicates? In which case is the second highest the n-1th element, or the largest number < max. — mksteve, Jan 03 '16 at 08:28

score 3 · Accepted Answer · edited Jan 29 '15 at 00:07

3

Here is a simple linear solution:

firstMax = max(a[0], a[1])
secondMax = min(a[0], a[1])
for elem in a:
    if elem >= firstMax:
        secondMax = firstMax
        firstMax = elem
    else if elem > secondMax:
        secondMax = elem
print(secondMax)

edited Jan 29 '15 at 00:07

Juan Lopes

10,143
2
25
44

answered Jan 20 '15 at 17:47

kraskevich

18,368
4
33
45

1

It's slightly more efficient to do the tests in the other order, since the vast majority of the elements in the array will be less than `secondMax`. If you compare with `secondMax` first, then a typical element will incur one test; as written, almost every element incurs two. (Not my downvote, though.) – rici Jan 20 '15 at 18:10
@rici The question was about an algorithm with a specific time complexity. It was not about the fastest one in practice, so I didn't try to optimize it. – kraskevich Jan 20 '15 at 18:14
Sorry, a misclick in my phone voted down and I didn't see. Now I can't vote up unless the answer is edited. :( – Juan Lopes Jan 20 '15 at 18:20
@ILoveCoding: I understand, but then you complained about QuickSelect being overkill, even though it also has the correct time complexity :) It was just a comment along the same lines. – rici Jan 20 '15 at 18:20
Op is concerned with a list of arrays, you are using one array! – mrk Jan 29 '15 at 00:14
@saadtaame It is very easy to merge all arrays from the list into one, isn't it? – kraskevich Jan 29 '15 at 00:28

score 2 · Answer 2 · edited Jan 03 '16 at 08:25

2

#Here is a simple solution in o(n) complexity


array =[]

puts "enter the size of array"

sizeOfArray  = gets.chomp.to_i

sizeOfArray.times do
        array << gets.chomp.to_i
end

if array[0] > array[1]
        highest = array[0]
        second_highest = array[1]
else
        highest = array[1]
        second_highest = array[0]
end


for i in 2..array.size - 1
        if array[i] > highest
                second_highest = highest
                highest = array[i]
        end

        if (array[i]< highest) && (array[i] > second_highest)
                second_highest = array[i]
        end
end

puts highest
puts second_highest

edited Jan 03 '16 at 08:25

greybeard

2,249
8
30
66

answered Dec 09 '15 at 19:05

ashwintastic

2,262
3
22
49

How is this different from kraskevich's answer? – greybeard Jan 03 '16 at 07:50
@greybeard: approach is same with slight modification, like loop is getting started from 3rd index,plus it is taking input from the users and it prints second highest and also highest :) – ashwintastic Jan 03 '16 at 11:57

score 0 · Answer 3 · answered Jan 20 '15 at 17:31

0

Walk through all the "n" elements across all the arrays and keep the top two highest nos.

Assume a[], b[] and c[] are the arrays.


first_highest = a[0];
second_highest = a[1];

for (all elements in a[], b[] and c[]) {
    if (element > first_highest) {
        first_highest = element;
    } else if (element > second_highest) {
        second_highest = element;
    }
}

answered Jan 20 '15 at 17:31

lsk

532
4
5

Your code seems wrong. a[] = [1, 2, 3] would yield 1 as second largest number – Juan Lopes Jan 20 '15 at 17:33
Are you sure about this? – lsk Jan 20 '15 at 17:46
There might be a problem with [1, 2] and [1, 3, 2]. – greybeard Jan 03 '16 at 07:55

score 0 · Answer 4 · edited May 23 '17 at 10:29

You can do it easily in O(n) with QuickSelect.

QuickSortSelection(numbers, currentLength, k) {
    if (currentLength == 1)
      return numbers[0];
    int pivot = random number from numbers array;

int newPivotIndex = partitionAroundPivot(numbers) // check quicksort algorithm for more details - less elements go left to the pivot, bigger elements go right

if ( k == newPivotIndex )
    return pivot;
else if ( k < newPivotIndex )
    return QuickSortSelection(numbers[0..newPivotIndex-1], newPivotIndex, k)
else
   return QuickSortSelection(numbers[newPivotIndex+1..end], currentLength-newPivotIndex+1, k-newPivotIndex);
}

Look at my answer: Partial selection sort vs Mergesort to find "k largest in array"

It is correct, but it is an overkill for the second maximum. — kraskevich, Jan 20 '15 at 17:49

score 0 · Answer 5 · answered Jan 29 '15 at 00:17

I'm not sure what you are asking here: you say you are given a LIST of arrays. If what you mean is that you have an array and you want to find the second largest element, then you can simply find the highest number in the first pass and find the second highest in a second pass. This takes O(n).

second highest number in array with O(n) complexity

5 Answers5