Get the second largest number in a list in linear time

find second largest number in array c++
find second largest number in array python
c program to find largest and second largest number in an array
find second largest number in array java
find second largest number in array javascript
c program to find second largest and smallest number in an array
how do you find second highest number in an integer array in python
python program to find the largest number in a list

I'm learning Python and the simple ways to handle lists is presented as an advantage. Sometimes it is, but look at this:

>>> numbers = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> numbers.remove(max(numbers))
>>> max(numbers)
74

A very easy, quick way of obtaining the second largest number from a list. Except that the easy list processing helps write a program that runs through the list twice over, to find the largest and then the 2nd largest. It's also destructive - I need two copies of the data if I wanted to keep the original. We need:

>>> numbers = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> if numbers[0]>numbers[1]):
...    m, m2 = numbers[0], numbers[1]
... else:
...    m, m2 = numbers[1], numbers[0]
...
>>> for x in numbers[2:]:
...    if x>m2:
...       if x>m:
...          m2, m = m, x
...       else:
...          m2 = x
...
>>> m2
74

Which runs through the list just once, but isn't terse and clear like the previous solution.

So: is there a way, in cases like this, to have both? The clarity of the first version, but the single run through of the second?

Since @OscarLopez and I have different opinions on what the second largest means, I'll post the code according to my interpretation and in line with the first algorithm provided by the questioner.

def second_largest(numbers):
    count = 0
    m1 = m2 = float('-inf')
    for x in numbers:
        count += 1
        if x > m2:
            if x >= m1:
                m1, m2 = x, m1            
            else:
                m2 = x
    return m2 if count >= 2 else None

(Note: Negative infinity is used here instead of None since None has different sorting behavior in Python 2 and 3 – see Python - Find second smallest number; a check for the number of elements in numbers makes sure that negative infinity won't be returned when the actual answer is undefined.)

If the maximum occurs multiple times, it may be the second largest as well. Another thing about this approach is that it works correctly if there are less than two elements; then there is no second largest.

Running the same tests:

second_largest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])
=> 74
second_largest([1,1,1,1,1,2])
=> 1
second_largest([2,2,2,2,2,1])
=> 2
second_largest([10,7,10])
=> 10
second_largest([1,1,1,1,1,1])
=> 1
second_largest([1])
=> None
second_largest([])
=> None

Update

I restructured the conditionals to drastically improve performance; almost by a 100% in my testing on random numbers. The reason for this is that in the original version, the elif was always evaluated in the likely event that the next number is not the largest in the list. In other words, for practically every number in the list, two comparisons were made, whereas one comparison mostly suffices – if the number is not larger than the second largest, it's not larger than the largest either.

C program to find second largest number in array, How do I find the second highest number in a list? C Program To Find Largest and Second Largest Number in An Array Explained in Hindi - Duration: 14:46. Hindi Life 4,745 views

You could use the heapq module:

>>> el = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> import heapq
>>> heapq.nlargest(2, el)
[90.8, 74]

And go from there...

Find Second largest element in an array, How do you find the second largest number in C? Largest element is: 45 Smallest element is: 2 Second Largest element is: 41 Second Smallest element is: 4 Below is another and traditional method to do the following calculation. The algorithm is simple, we take a number and compare it with all other numbers present in the list and get the largest, smallest, second largest and second smallest element.

You could always use sorted

>>> sorted(numbers)[-2]
74

Get the second largest number in a list in linear time, in both i.e. max1 = max2 = INT_MIN . Iterate though all array elements, run a loop from 0 to size - 1 . Given a list of numbers, the task is to write a Python program to find the largest number in given list. Examples: Input : list1 = [10, 20, 4] Output : 20 Input : list2 = [20, 10, 20, 4, 100] Output : 100. Method 1 : Sort the list in ascending order and print the last element in the list.

Try the solution below, it's O(n) and it will store and return the second greatest number in the second variable. UPDATE: I've adjusted the code to work with Python 3, because now arithmetic comparisons against None are invalid.

Notice that if all elements in numbers are equal, or if numbers is empty or if it contains a single element, the variable second will end up with a value of None - this is correct, as in those cases there isn't a "second greatest" element.

Beware: this finds the "second maximum" value, if there's more than one value that is "first maximum", they will all be treated as the same maximum - in my definition, in a list such as this: [10, 7, 10] the correct answer is 7.

def second_largest(numbers):
    minimum = float('-inf')
    first, second = minimum, minimum
    for n in numbers:
        if n > first:
            first, second = n, first
        elif first > n > second:
            second = n
    return second if second != minimum else None

Here are some tests:

second_largest([20, 67, 3, 2.6, 7, 74, 2.8, 90.8, 52.8, 4, 3, 2, 5, 7])
=> 74
second_largest([1, 1, 1, 1, 1, 2])
=> 1
second_largest([2, 2, 2, 2, 2, 1])
=> 1
second_largest([10, 7, 10])
=> 7
second_largest( [1, 3, 10, 16])
=> 10
second_largest([1, 1, 1, 1, 1, 1])
=> None
second_largest([1])
=> None
second_largest([])
=> None

python - Get the second largest number in a list in linear time, How do you find the largest number in a list? The winner (the largest number) will emerge after all the 'matches' (takes N-1 time), but if we record the 'players' of all the matches, and among them, group all the players that the winner has beaten, the second largest number will be the largest number in this group, i.e. the 'losers' group.

Why to complicate the scenario? Its very simple and straight forward

  1. Convert list to set - removes duplicates
  2. Convert set to list again - which gives list in ascending order

Here is a code

mlist = [2, 3, 6, 6, 5]
mlist = list(set(mlist))
print mlist[-2]

Find Second Largest Number in an Array (Multiple Approaches , How do I find the second largest number in Java? Following is the O(n) time and O(1) extra space approach. Let us understand the approach with a simple example where arr[] = {2, 3, 3, 5, 3, 4, 1, 7}, k = 8, n = 8 (number of elements in arr[]). 1) Iterate though input array arr[] , for every element arr[i] , increment arr[arr[i]%k] by k ( arr[] becomes {2, 11, 11, 29, 11, 12, 1, 15 })

What is the algorithm to find the second largest number in an array , The time complexity of this solution is O(nlogn). A Better Solution is to traverse the array twice. In the first traversal find the maximum element. In the second  try it for 4,8,2 and it will give u "8" as the second largest number . 10/8/17, 11:43 PM

Find the Second Largest Number in an Array, Brent D. gives you the 2nd largest element of the list with a guaranteed worst-case O(n) running time. The partition(a, kth) methods returns an array where the k th element is the same it would be in a sorted array, all elements before are smaller, and all behind are larger. 3) Finally, MH has k largest elements and root of the MH is the kth largest element. Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk) All of the above methods can also be used to find the kth largest (or smallest) element.

Find the Second Largest Element in an Array, Since @OscarLopez and I have different opinions on what the second largest means, I'll post the code according to my vision and in line with the first algorithm​ 

Comments
  • I think your second method (O(N)) is the best, because for large lists using a one-liner just because it is shorter is not a good idea.
  • Is running through the list twice really a problem? It's still O(N), and when you're dealing with cases where the algorithmic complexity is already good enough (or N is small), guesses about performance are almost useless. You need to write it multiple ways and timeit each one (and do so on all platforms/implementations you care about). And, unless this is a bottleneck, that isn't worth the effort.
  • @abarnert, running twice through the list isn't a problem, but I'm trying to understand idiosyncracies of python before letting my students loose on it. I can see lots of cases where a student would take a list, run a transformation, another, another, and where the simple solution is the bad one.
  • Now m2 will just be the largest if the first element is the largest. It also (I believe) fails to replace m2 when m2<x<m
  • @boisvert: But the answer that's right for this toy example may not be—probably won't be—the answer that's right for a similar real-life case. For example, if you need to repeatedly get the top 2 as you continue to add to the list, you probably want to keep track of the top 2 as you go along and check each time you add, or keep the list continuously sorted (e.g., by using a tree-based collection like blist.sortedlist instead of a list).
  • That is the functionality identical to finding max, removing, and finding max of the rest.
  • @boisvert In other worths, the way you wanted it?
  • @OscarLopez list.remove() removes only the first matching element found.
  • You should not rely on Python 2 implementation details; the sort order of None is an arbitrary choice. Use float('inf') instead.
  • @MartijnPieters The function should not return negative infinity (a number that could've been present) when the answer is actually undefined, though. Updated the answer to take that into account.
  • It is equivalent to : sorted(iterable,reverse=True)[:n], still NlogN
  • @AshwiniChaudhary functionally equivalent to that, yes; however because of the implementation it performs fewer comparisons so is more efficient than sorting and slicing
  • @JonClements: But O(NlogN) is still nowhere near as good as O(N) for large N, and the OP already has an O(N) solution, which is what (I think) Ashwini is pointing out.