Find largest two numbers from list using clojure

Question

I'm trying to write a function that finds the largest two numbers from a list of positive integers in Clojure.

I've toyed around with Scheme in the past, but I'm very new to Clojure. This is what I came up with:

; Accumulator function for reduce later
(defn top-two [acc x]
  (let [big1 (first acc) big2 (second acc)]
    (cond
      (> x big1) [x big1]
      (> x big2) [big1 x]
      :else acc)))

(defn top-two-list [coll]
  (reduce top-two [0 0] coll))

This works, but I'm wondering if there is a way to simplify the top-two function, or to make this more readable or idiomatic.

This could be done much simpler if I was willing to sort the entire list, but I'm looking for an O(n) solution.

Any thoughts?

Answer 1

This looks like a clean way to find the max two elements. It can be shortened a little bit with destructuring:

; Accumulator function for reduce later
(defn top-two [[big1 big2 :as acc] x]
  (cond
    (> x big1) [x big1]
    (> x big2) [big1 x]
    :else acc))

(defn top-two-list [coll]
  (reduce top-two [0 0] coll))

You could also write something like so:

(defn top-two [coll]
  (let [big1 (apply max coll)
        big2 (apply max (remove #(= big1 %) coll))]
    [big1 big2]))

But I think it is programmer preference which you prefer. Both solutions are O(n), however the second ends up scanning the list twice.

Answer 2

An alternative way of finding the largest two numbers in a list would be:

(take 2 (sort > coll))

Sort the collection using the > function as a comparator then take the first 2 values.

For example:

user=> (take 2 (sort > [6 5 3 1 7 4 9 2 0 8]))
(9 8)