3
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks much, I thought there must be something like this destructuring concept. \$\endgroup\$ – Eric Wilson Sep 30 '12 at 18:48
2
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ :) Well, yes, sorting makes such an exercise trivial -- and significantly slower. \$\endgroup\$ – Eric Wilson Dec 15 '14 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.