How to find students with the best grades in a list?

Question

Suppose, I have a list of Students. Students have fields like name, birth date, grade, etc. How would you find Students with the best grade in Scala?

For example:

List(Student("Mike", "A"), Student("Pete", "B"), Student("Paul", A))"

I want to get

List(Student("Mike", "A"), Student("Paul", A))

Obviously, I can find the max grade ("A" in the list above) and then filter the list

students.filter(_.grade == max_grade)

This solution is O(N) but runs over the list twice. Can you suggest a better solution?

Answer 1

Running over the list twice is probably the best way to do it, but if you insist on a solution that only runs over once, you can use a fold (here works on empty lists):

(List[Student]() /: list){ (best,next) => best match {
  case Nil => next :: Nil
  case x :: rest =>
    if (betterGrade(x,next)) best
    else if (betterGrade(next,x)) next :: Nil
    else next :: best
}}

If you are unfamiliar with folds, they are described in an answer here. They're a general way of accumulating something as you pass over a collection (e.g. list). If you're unfamiliar with matching, you can do the same thing with isEmpty and head. If you want the students in the same order as they appeared in the original list, run .reverse at the end.

Answer 2

Using foldLeft you traverse the list of students only once :

scala> students.foldLeft(List.empty[Student]) {
     | case (Nil, student) => student::Nil
     | case (list, student) if (list.head.grade == student.grade) => student::list
     | case (list, student) if (list.head.grade > student.grade) => student::Nil
     | case (list, _) => list
     | }
res17: List[Student] = List(Student(Paul,A), Student(Mike,A))

Answer 3

There are already 6 answers, but I still feel compelled to add my take:

case class Lifted(grade: String, students: List[Student]) {
  def mergeBest(other: Lifted) = grade compare other.grade match {
    case  0 => copy(students = other.students ::: students)
    case  1 => other
    case -1 => this
  }
}

This little case class will lift a Student into an object that keeps track of the best grade and a list cell containing the student. It also factors out the logic of the merge: if the new student has

• the same grade => merge the new student into the result list, with the shorter one at the front for efficiency - otherwise result won't be O(n)
• higher grade => replace current best with the new student
• lower grade => keep the current best

The result can then be easily constructed with a reduceLeft:

val result = { 
  list.view.map(s => Lifted(s.grade, List(s)))
    .reduceLeft((l1, l2) => l1.mergeBest(l2))
    .students
}
// result: List[Student] = List(Student(Paul,A), Student(Mike,A))

PS. I'm upvoting your question - based on the sheer number of generated response

Answer 4

You can use filter on the students list.

case class Student(grade: Int)
val students = ...
val minGrade = 5
students filter ( _.grade < minGrade)

Works just fine also for type String

Answer 5

After sorting, you can use takeWhile to avoid iterating a second time.

case class Student(grade: Int)
val list = List(Student(1), Student(3), Student(2), Student(1), Student(25), Student(0), Student (25))

val sorted = list.sortWith (_.grade > _.grade)
sorted.takeWhile (_.grade == sorted(0).grade)

It still sorts the whole thing, even grades 1, 3, 0 and -1, which we aren't interested in, before taking the whipped cream, but it is short code.

update:

A second approach, which can be performed in parallel, is, to split the list, and take the max of each side, and then only the higher one, if there is - else both:

def takeMax (l: List[Student]) : List [Student] = l.size match {
    case 0 => Nil
    case 1 => l 
    case 2 => if (l(0).grade > l(1).grade) List (l(0)) else 
      if (l(0).grade < l(1).grade) List (l(1)) else List (l(0), l(1))
    case _ => {
      val left = takeMax (l.take (l.size / 2))
      val right= takeMax (l.drop (l.size / 2))
     if (left (0).grade > right(0).grade) left else 
     if (left (0).grade < right(0).grade) right else left ::: right }
}

Of course we like to factor out the student, and the method to compare two of them.

def takeMax [A] (l: List[A], cmp: ((A, A) => Int)) : List [A] = l.size match {
    case 0 | 1 => l 
    case 2     => cmp (l(0), l(1)) match {
      case 0 => l 
      case x => if (x > 0) List (l(0)) else List (l(1))
    }
    case _ => {
      val left = takeMax (l.take (l.size / 2), cmp)
      val right= takeMax (l.drop (l.size / 2), cmp)
      cmp (left (0), right (0)) match {
        case 0 => left ::: right
        case x => if (x > 0) left else right }
     }
}

def cmp (s1: Student, s2: Student) = s1.grade - s2.grade 
takeMax (list, cmp)