Get the second largest number in a list in linear time

Question

I m learning Python and the simple ways to handle lists is presented as an advantage  Sometimes it is  but look at this    gt  gt  gt  numbers    20 67 3 2 6 7 74 2 8 90 8 52 8 4 3 2 5 7   gt  gt  gt  numbers remove max numbers    gt  gt  gt  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    gt  gt  gt  numbers    20 67 3 2 6 7 74 2 8 90 8 52 8 4 3 2 5 7   gt  gt  gt  if numbers 0  gt numbers 1           m  m2   numbers 0   numbers 1      else         m  m2   numbers 1   numbers 0       gt  gt  gt  for x in numbers 2           if x gt m2            if x gt m               m2  m   m  x           else               m2   x      gt  gt  gt  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

User · Answer

Why to complicate the scenario  Its very simple and straight forward    Convert list to set - removes duplicates 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

User · Answer

def SecondLargest x           largest   max x 0  x 1           largest2   min x 0  x 1           for item in x              if item  gt  largest                 largest2   largest                largest   item             elif largest2  lt  item and item  lt  largest                 largest2   item         return largest2     SecondLargest  20 67 3 2 6 7 74 2 8 90 8 52 8 4 3 2 5 7

User · Answer

Max out the value by comparing each one to the max item  In the first if  every time the value of max item changes it gives its previous value to second max  To tightly couple the two second if ensures the boundary  def secondmax self  list       max item   list 0      second max   list 1      for item in list          if item  gt  max item              second max    max item             max item   item         if max item  lt  second max              max item   second max     return second max

User · Answer

Just to make the accepted answer more general  the following is the extension to get the kth largest value   def kth largest numbers  k       largest ladder    float  -inf      k     count   0     for x in numbers          count    1         ladder pos   1         for v in largest ladder              if x  gt  v                  ladder pos    1             else                  break         if ladder pos  gt  1              largest ladder   largest ladder 1 ladder pos     x    largest ladder ladder pos       return largest ladder 0  if count  gt   k else None

User · Answer

gt  gt  gt  l    19  1  2  3  4  20  20   gt  gt  gt  sorted set l   -2  19

User · Answer

You can also try this    gt  gt  gt  list  20  20  19  4  3  2  1 100 200 100   gt  gt  gt  sorted set list   key int  reverse True  1  100

User · Answer

list nums    1  2  6  6  5  minimum   float  -inf   max  min   minimum  minimum for num in list nums      if num  gt  max          max  min   num  max     elif max  gt  num  gt  min          min   num print min if min    minimum else None       Output   5

User · Answer

If you do not mind using numpy  import numpy as np    np partition numbers  -2  -2    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 kth element is the same it would be in a sorted array  all elements before are smaller  and all behind are larger

User · Answer

Best solution that my friend Dhanush Kumar came up with      def second max loop           glo max   loop 0          sec max   float  quot -inf quot           for i in loop              if i  gt  glo max                  sec max   glo max                 glo max i             elif sec max  lt  i  lt  glo max                  sec max   i         return sec max           print second max  -1 -3 -4 -5 -7             assert second max  -1 -3 -4 -5 -7    -3     assert second max  5 3 5 1 2      3     assert second max  1 2 3 4 5 7     5     assert second max  -3 1 2 5 -2 3 4      4     assert second max  -3 -2 5 -1 0      0     assert second max  0 0 0 1 0      0

User · Answer

A simple way     n int input    arr   set map int  input   split     arr remove max arr   print  max arr

User · Answer

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  gt  m2              if x  gt   m1                  m1  m2   x  m1                         else                  m2   x     return m2 if count  gt   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     gt  74 second largest  1 1 1 1 1 2     gt  1 second largest  2 2 2 2 2 1     gt  2 second largest  10 7 10     gt  10 second largest  1 1 1 1 1 1     gt  1 second largest  1     gt  None second largest       gt  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

User · Answer

You could always use sorted   gt  gt  gt  sorted numbers  -2  74

User · Answer

there are some good answers here for type      in case someone needed the same thing on a type     here it is    def secondLargest D       def second largest L             if len L  lt 2               raise Exception  Second Of One           KFL None  KeyForLargest         KFS None  KeyForSecondLargest         n   0         for k in L              if KFL    None or k gt  L KFL                    KFS   KFL                 KFL   n             elif KFS    None or k gt  L KFS                    KFS   n             n  1         return  KFS      KFL None  KeyForLargest     KFS None  KeyForSecondLargest     if len D  lt 2           raise Exception  Second Of One       if type D   type               if type D   type                   return second largest D           else              raise Exception  TypeError       else          for k in D              if KFL    None or D k  gt  D KFL                    KFS   KFL                                KFL   k             elif KFS    None or D k   gt   D KFS                    KFS   k     return KFS   a     one  1    two   2    thirty  30  b    30 1 2   print a secondLargest a    print b secondLargest b      Just for fun I tried to make it user friendly xD

User · Answer

use defalut  sort   method to get second largest number in the list  sort is in built method you do not need to import module for this   lis    11 52 63 85 14  lis sort   print lis len lis -2

User · Answer

Most of previous answers are correct but here is another way    Our strategy is to create a loop with two variables first highest and second highest  We loop through the numbers and if our current value is greater than the first highest then we set second highest to be the same as first highest and then the second highest to be the current number  If our current number is greater than second highest then we set second highest to the same as current number     usr bin env python3 import sys def find second highest numbers        min integer   -sys maxsize -1     first highest  second highest   min integer     for current number in numbers          if current number    first highest and min integer    second highest              first highest current number         elif current number  gt  first highest              second highest   first highest             first highest   current number         elif current number  gt  second highest              second highest   current number     return second highest  print find second highest  80 90 100    print find second highest  80 80    print find second highest  2 3 6 6 5

User · Answer

def secondlarget passinput       passinputMax   max passinput    find the maximum element from the array     newpassinput    i for i in passinput if i    passinputMax    Find the second largest element in the array      print  newpassinput      if len newpassinput   gt  0          return max newpassinput   return the second largest     return 0 if   name         main         n   int input   strip       lets say 5     passinput   list map int  input   rstrip   split       1 2 2 3 3     result   secondlarget passinput   2     print  result   2

User · Answer

You could use the heapq module    gt  gt  gt  el    20 67 3 2 6 7 74 2 8 90 8 52 8 4 3 2 5 7   gt  gt  gt  import heapq  gt  gt  gt  heapq nlargest 2  el   90 8  74    And go from there

User · Answer

You can find the 2nd largest by any of the following ways   Option 1   numbers   set numbers  numbers remove max numbers   max numbers    Option 2   sorted set numbers   -2

User · Answer

The quickselect algorithm  O n  cousin to quicksort  will do what you want  Quickselect has average performance O n   Worst case performance is O n 2  just like quicksort but that s rare  and modifications to quickselect reduce the worst case performance to O n    The idea of quickselect is to use the same pivot  lower  higher idea of quicksort  but to then ignore the lower part and to further order just the higher part

User · Answer

you have to compare in between new values  that s the trick  think always in the previous  the 2nd largest  should be between the max and the previous max before  that s the one      def secondLargest lista       max number     0     prev number    0      for i in range 0  len lista             if lista i   gt  max number              prev number   max number             max number    lista i          elif lista i   gt  prev number and lista i   lt  max number              prev number   lista i       return prev number

User · Answer

if   name         main         n   int input        arr   list map float  input   split         high   max arr      secondhigh   min arr      for x in arr          if x  lt  high and x  gt  secondhigh              secondhigh   x     print secondhigh    The above code is when we are setting the elements value in the list  as per user requirements  And below code is as per the question asked    list numbers    20  67  3  2 6  7  74  2 8  90 8  52 8  4  3  2  5  7   find the highest element in the list high   max numbers   find the lowest element in the list secondhigh   min numbers  for x in numbers              find the second highest element in the list      it works even when there are duplicates highest element in the list      It runs through the entire list finding the next lowest element     which is less then highest element but greater than lowest element in     the list set initially  And assign that value to secondhigh variable  so      now this variable will have next lowest element in the list  And by end      of loop it will have the second highest element in the list               if  x lt high and x gt secondhigh           secondhigh x print secondhigh

User · Answer

Below code will find the max and the second max numbers without the use of max function  I assume that the input will be numeric and the numbers are separated by single space  myList   input   split   myList   list map eval myList     m1   myList 0  m2   myList 0   for x in myList      if x  gt  m1          m2   m1         m1   x     elif x  gt  m2          m2   x  print   Max Number    m1  print   2nd Max Number    m2

User · Answer

n input  Enter a list    n sort   l len n  n remove n l-1   l len n  print n l-1

User · Answer

O n   Time Complexity of a loop is considered as O n  if the loop variables is incremented   decremented by a constant amount  For example following functions have O n  time complexity       Here c is a positive integer constant       for  int i   1  i  lt   n  i    c                 some O 1  expressions        To find the second largest number i used the below method to find the largest number first and then search the list if thats in there or not   x    1 2 3  A   list map int  x   y   max A  k1   list   for values in range len A    if y   A values       k append A values    z   max k1  print z

User · Answer

Objective  To find the second largest number from input   Input   5         2 3 6 6 5  Output  5    n   int raw input    arr   map int  raw input   split    print sorted list set arr    -2

User · Answer

This can be done in  N   log N  - 2  time  which is slightly better than the loose upper bound of 2N  which can be thought of O N  too     The trick is to use binary recursive calls and  tennis tournament  algorithm  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    The size of this  losers  group is log N   and again  we can revoke the binary recursive calls to find the largest among the losers  which will take  log N  - 1  time  Actually  we can just linearly scan the losers group to get the answer too  the time budget is the same    Below is a sample python code   def largest L       global paris     if len L     1          return L 0      else          left   largest L  len L   2           right   largest L len L   2            pairs append  left  right           return max left  right   def second largest L       global pairs     biggest   largest L      second L    min item  for item in pairs if biggest in item       return biggest  largest second L       if   name         main         pairs            test array     L    2 -2 10 5 4 3 1 2 90 -98 53 45 23 56 432           if len L     0          first  second   None  None     elif len L     1          first  second   L 0   None     else          first  second   second largest L       print  The largest number is      str first       print  The 2nd largest number is      str second

User · Answer

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  gt  first              first  second   n  first         elif first  gt  n  gt  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     gt  74 second largest  1  1  1  1  1  2     gt  1 second largest  2  2  2  2  2  1     gt  1 second largest  10  7  10     gt  7 second largest   1  3  10  16     gt  10 second largest  1  1  1  1  1  1     gt  None second largest  1     gt  None second largest       gt  None

[python] Get the second largest number in a list in linear time

Examples related to python

Examples related to performance