Second Largest Item

June 2, 2017

Any solution based on sorting will require O(n log n) comparisons, which is too many. Any solution based on heaps will require O(n log n) comparisons to build the heap plus O(2 log n) comparisons to extract the second largest, which is better but still not good enough. Selection sort uses O(2n – 3) comparisons regardless of the initial order of the data. Our solution uses O(2n – 3) comparisons in the worst case, just as selection sort, but only O(n + log n) in the expected case; I don’t know of a better algorithm:

(define (second-max lt? xs)
  (if (or (null? xs) (null? (cdr xs)))
      (error 'second-max "not enough data")
      (begin
        (when (lt? (car xs) (cadr xs))
          (set! xs (cons (cadr xs) (cons (car xs) (cddr xs)))))
        (let loop ((first (car xs)) (second (cadr xs)) (xs (cddr xs)))
          (cond ((null? xs) second)
                ((lt? second (car xs))
                  (if (lt? first (car xs))
                      (loop (car xs) first (cdr xs))
                      (loop first (car xs) (cdr xs))))
                (else (loop first second (cdr xs))))))))

The outer loop makes n – 1 comparisons. The trick is to make the primary comparison on the second largest item found so far, so only when you know that you have a new second largest item do you have to compare to the largest item, which happens O(log n) times in the expected case. Here’s an example:

> (second-max < '(4 1 9 2 3 8 5 7 6))
8

You can run the program at http://ideone.com/2bNnhJ.


					
Advertisements

Pages: 1 2

19 Responses to “Second Largest Item”

  1. Milbrae said

    According to the QuickSelect algorithm, here’s some modified code from the RosettaCode example in D

    import std.stdio, std.algorithm;
    
    void main()
    {
        uint[] a = [13, 11, 9, 7, 5, 3, 1, 0, 2, 4, 6, 8, 10, 12];
        a.topN(a.length - 2);
        a[a.length-2].writeln;
    }
    

    Output: 12

  2. Ernie said

    Can you check the result by changing the last number in the array to 13. Do you get 13 or 11 as the result?

  3. Milbrae said

    You’re right, Ernie. My code works only for arrays with distinct items. My bad.

  4. Jussi Piitulainen said

    Same algorithm, different expression.

    (define (second < us)
      (define (fold m n us) ; m ≤ n are least so far
        (if (pair? us)
            (call-with-values
                (lambda () (step m n (car us)))
              (lambda (m n) (fold m n (cdr us))))
            n))
      (define (step m n u) ; m ≤ n are least so far, consider u
        (if (< u n)
            (if (< u m)
                (values u m)
                (values m u))
            (values m n)))
      (if (and (pair? us) (pair? (cdr us)))
          (if (< (cadr us) (car us))
              (fold (cadr us) (car us) (cddr us))
              (fold (car us) (cadr us) (cddr us)))
          (error "list must contain at least two elements")))
    
    (write (second < '(3 1 4 1 5 9 2 6)))
    (write (second > '(3 1 4 1 5 9 2 6)))
    (newline) ; writes: 16
    
  5. Jussi Piitulainen said

    By the way, isn’t there something like a heap or a priority queue with a specified capacity, which simply drops values that don’t fit there any more? Then this algorithm essentially implements that data structure, with room for just two elements, in the two variables where it keeps the two best elements.

  6. programmingpraxis said

    @Jussi: Yes, there is a size-limited priority queue; we studied in a previous exercise.

  7. Steve said
    SECLAR    ; Second largest number
             N ARR,I
             F I=1:1:10 S ARR($R(100))=""
             W !!,"Numbers in order:"
             S I="" F  S I=$O(ARR(I)) Q:'I  W !?5,I
             W !!,"Second largest number: ",$O(ARR($O(ARR(""),-1)),-1)
             Q
    

    MCL> D ^SECLAR

    Numbers in order:
    11
    21
    29
    42
    56
    58
    67
    69
    73
    93

    Second largest number: 73

  8. The above language is MUMPS

  9. Klong

    
            L::[1 9 2 7]
    [1 9 2 7]
            L@((>L)@1)
    7
    
    
  10. kernelbob said

    Second largest is the second smallest if you order elements backwards. The C++ standard library can do that.

    #include <algorithm>
    #include <functional>
    #include <array>
    #include <iostream>
     
    template <class RandomIterator>
    RandomIterator second_largest(RandomIterator first, RandomIterator last)
    {
        typedef
            typename std::iterator_traits<RandomIterator>::value_type
            value_type;
        std::nth_element(first, first + 1, last, std::greater<value_type>());
        return first + 1;
    }
    
    int main()
    {
        std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
     
        std::cout << *second_largest(s.begin(), s.end()) << std::endl;
        return 0;
    }
    
  11. Globules said

    Here’s a Haskell version. It uses radix sort, so it requires no comparisons. (Does this make me a bad person?)

    import Control.Monad.ST (runST)
    import Data.Vector.Algorithms.Radix (Radix, sort)
    import qualified Data.Vector.Unboxed as U
    import qualified Data.Vector.Unboxed.Mutable as M
    
    penultimate :: (M.Unbox a, Radix a) => U.Vector a -> Maybe a
    penultimate xs | U.length xs < 2 = Nothing
                   | otherwise = Just $ runST $ do v <- U.thaw xs
                                                   sort v
                                                   M.read v (M.length v - 2)
    
    main :: IO ()
    main = do
      -- There is no second largest element in a one element vector.
      print $ penultimate $ U.fromList [1 :: Int]
      
      let xs = U.fromList [1, 2, 2, 3, 4, 4, 5 :: Int]
      print $ penultimate xs
      print $ penultimate $ U.reverse xs
    
    $ ./sndlrg 
    Nothing
    Just 4
    Just 4
    
  12. Milbrae said

    @kernelbob: Try this….

    [sourceode lang=”cpp”]
    #include
    #include
    #include
    #include

    template
    RandomIterator second_largest(RandomIterator first, RandomIterator last)
    {
    typedef
    typename std::iterator_traits::value_type
    value_type;
    std::nth_element(first, first + 1, last, std::greater());
    return first + 1;
    }

    int main()
    {
    std::array s = {5, 9, 4, 2, 8, 6, 1, 9, 0, 3};

    std::cout << *second_largest(s.begin(), s.end()) << std::endl;
    return 0;
    }
    [/sourcecode]

    As you can see I've changed one item (from 7 to 9) and the output will be 9 instead of 8. Just like my solution above this one works for arrays iff the largest item appears only once.

    Can't tell about the solutions of bookofgraham and Steve, though.

  13. Paul said

    Using a heap and heapreplace in Python, the heap never grows larger than 2 elements.

    def second_largest(seq):
        heap = list(seq[:2])
        heapify(heap)
        for i in seq[2:]:
            if i > heap[0]:
                heapreplace(heap, i)
        return heap[0]
    
  14. kernelbob said

    @Milbrae, thanks.

    I misread the problem statement.

  15. @Milbrae:

    In MUMPS, I put the numbers as the subscripts and so they can only appear once. In KLONG I believe my solution will only work if the numbers appear only once.

  16. ardnew said

    I have a slight problem with the discussion preceding your solution example. You state sorting will be O(n log n), using a heap will be O(n log n) + O(2 log n), and that the latter is more efficient — because O(n log n) > O(2 log n), i assume.

    However, this is an inaccurate comparison because sorting will require O(n log n) to build the structure, yet you get constant time for retrieving the element (or O(n) maybe). Whereas the heap has O(n log n) for building the structure and O(2 log n) for retrieval. The inequality then should really be O(n log n) + C C < O(2 log n).

    So for the one-time task of finding the second largest item, the sorting approach has constant time and would always be more efficient. Do you agree?

  17. ardnew said

    Oops something weird with formatting, end of second paragraph: O(n log n) + C < O(n log n) + O(2 log n), and simplified: C < O(2 log n)

  18. Steve said

    This Klong solution permits multiple numbers of the same value

            l::[9 12 19 18 19]  # list of numbers assigned to l
    [9 12 19 18 19]
            =l                         # get locations of each unique number
    [[0] [1] [2 4] [3]]
            {*x}'=l                  # get 1st location of each unique number
    [0 1 2 3]
            l2::{l@x}'{*x}'=l    # get value for each 1st location
    [9 12 19 18]
            >l2                      # get locations of numbers sorted from greatest to least
    [2 3 1 0]
            (>l2)@1              # get location of 2nd (largest) number
    3
            l2@(>l2)@1       # get value of 2nd (largest) number
    18
    

    or

            l::[9 12 19 18 19]; l2::{l@x}'{*x}'=l;l2@(>l2)@1
    18
    
  19. programmingpraxis said

    @Ardnew: On reflection, the hash methods are O(n log k), which makes them competitive (within a constant factor) with the O(n method of this exercise. That’s only true because k = 2.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: