How to find max in a list of tuples?

Question

I have the following list of tuples:

val arr = List(('a',10),('b',2),('c',3))

How to find the tuple with the max key or max value?

The proper answer should be (c, 3) for max key lexicographically or ('a', 10) for max value.

Solution 1

Easy-peasy:

scala> val list = List(('a',10),('b',2),('c',3))
list: List[(Char, Int)] = List((a,10), (b,2), (c,3))

scala> val maxByKey = list.maxBy(_._1)
maxByKey: (Char, Int) = (c,3)

scala> val maxByVal = list.maxBy(_._2)
maxByVal: (Char, Int) = (a,10)

So basically you can provide to List[T] any function T => B (where B can be any ordered type, such as Int or String by example) that will be used to find the maximum.

Solution 2

Starting in Scala 2.13, a slightly safer solution (which handles empty lists) would consist in using maxByOption/minByOption which returns None if the sequence is empty:

List(('a', 10),('b', 2),('c', 3)).maxByOption(_._1)
// Option[(Char, Int)] = Some((c,3))
List[(Char, Int)]().maxByOption(_._1)
// Option[(Char, Int)] = None

This way you could also decide to fallback on a default value when the list is empty:

List[(Char, Int)]().maxByOption(_._1).getOrElse(('a', 1))
// (Char, Int) = (a,1)

Solution 3

No doubt @om-nom-nom provided a concise, correct answer. However, it will throw an exception for an empty list.

EDIT #2 Given my first edit, it's worthwhile to re-write my original, flawed answer:

def max[A](list: List[(A, Int)]): Option[Int] = list match  {
    case Nil => None
    case x :: xs => { val result = xs.foldLeft(x._2) { // acc = first item in list                                        
                              (acc, elem) => if(elem._2 > acc) elem._2 else acc 
                      }
                      Some(result)
                    }
} 

Note: I'm guessing that scalaz would let you use a more generic Num-like type instead of Int, but I haven't worked with it at all.

Testing

scala> val list = List(('a',10),('b',2),('c',3))
list: List[(Char, Int)] = List((a,10), (b,2), (c,3))

scala> max(list)
res5: Option[Int] = Some(10)

scala> val list: List[(String, Int)] = Nil
list: List[(String, Int)] = List()

scala> max(list)
res6: Option[Int] = None

EDIT For picking a start value, I decided to edit my answer after talking with @DustinGetz.

Picking Int.MinValue might not be a good choice as it's dependent on the particular OS/system on which the app is running.

I would argue that the first element in the list should be the start value. However, there's a potential run-time exception if the list is empty.

Please take a look at this post for more discussion - https://stackoverflow.com/a/23184020/409976.

Comments

[Kevin Meredith]

+1, but it's important to note, I believe, that it'll fail for an empty list. scala> val list: List[(String, Int)] = Nil list: List[(String, Int)] = List() | scala> list.maxBy(_._2) | **java.lang.UnsupportedOperationException: empty.maxBy**

[yAsH]

@om-nom-nom if the above list has an extra tuple ('d',10) how do we get both ('a',10),('d',10) as output?