Find min and max elements of array

Question

I want to find the min and max elements of an array using for comprehension. Is it possible to do that with one iteration of array to find both min element and max element?

I am looking for a solution without using scala provided array.min or max.

Answer 1

You can get min and max values of an Array[Int] with reduceLeft function.

scala> val a = Array(20, 12, 6, 15, 2, 9)

a: Array[Int] = Array(20, 12, 6, 15, 2, 9)

scala> a.reduceLeft(_ min _)

res: Int = 2

scala> a.reduceLeft(_ max _)

res: Int = 20

See this link for more information and examples of reduceLeft method: http://alvinalexander.com/scala/scala-reduceleft-examples

Answer 2

Here is a concise and readable solution, that avoids the ugly if statements :

def minMax(a: Array[Int]) : (Int, Int) = {
  if (a.isEmpty) throw new java.lang.UnsupportedOperationException("array is empty")
  a.foldLeft((a(0), a(0)))
  { case ((min, max), e) => (math.min(min, e), math.max(max, e))}
}

Explanation : foldLeft is a standard method in Scala on many collections. It allows to pass an accumulator to a callback function that will be called for each element of the array.

Take a look at scaladoc for further details

Answer 3

def findMinAndMax(array: Array[Int]) = { // a non-empty array

    val initial = (array.head, array.head)  // a tuple representing min-max


    // foldLeft takes an initial value of type of result, in this case a tuple
    // foldLeft also takes a function of 2 parameters.
    // the 'left' parameter is an accumulator (foldLeft -> accum is left)
    // the other parameter is a value from the collection.

    // the function2 should return a value which replaces accumulator (in next iteration)
    // when the next value from collection will be picked.

    // so on till all values are iterated, in the end accum is returned.

    array.foldLeft(initial) { ((min, max), x) => 
          if (x < min) (x, max) 
          else if (x > max) (min, x) 
          else acc 
    }
}

Answer 4

Following on from the other answers - a more general solution is possible, that works for other collections as well as Array, and other contents as well as Int:

def minmax[B >: A, A](xs: Iterable[A])(implicit cmp: Ordering[B]): (A, A) = {
  if (xs.isEmpty) throw new UnsupportedOperationException("empty.minmax")

  val initial = (xs.head, xs.head)

  xs.foldLeft(initial) { case ((min, max), x) => 
    (if (cmp.lt(x, min)) x else min, if (cmp.gt(x, max)) x else max) }
}                                               

For example:

minmax(List(4, 3, 1, 2, 5))              //> res0: (Int, Int) = (1,5)

minmax(Vector('Z', 'K', 'B', 'A'))       //> res1: (Char, Char) = (A,Z)

minmax(Array(3.0, 2.0, 1.0))             //> res2: (Double, Double) = (1.0,3.0)

(It's also possible to write this a bit more concisely using cmp.min() and cmp.max(), but only if you remove the B >: A type bound, which makes the function less general).

Answer 5

Consider this (for non-empty orderable arrays),

val ys = xs.sorted
val (min,max) = (ys.head, ys.last)

Answer 6

val xs: Array[Int] = ???

var min: Int = Int.MaxValue
var max: Int = Int.MinValue

for (x <- xs) {
  if (x < min) min = x
  if (x > max) max = x
}

Answer 7

I'm super late to the party on this one, but I'm new to Scala and thought I'd contribute anyway. Here is a solution using tail recursion:

@tailrec
def max(list: List[Int], currentMax: Int = Int.MinValue): Int = {
    if(list.isEmpty) currentMax
    else if ( list.head > currentMax) max(list.tail, list.head)
    else max(list.tail,currentMax)
}

Answer 8

Of all of the answers I reviewed to this questions, DNA's solution was the closest to "Scala idiomatic" I could find. However, it can be slightly improved by...:

1. Performing as few comparisons as needed (important for very large collections)
2. Provide ideal ordering consistency by only using the Ordering.lt method
3. Avoiding throwing an Exception
4. Making the code more readable for those new to and learning Scala

The comments should help clarify the changes.

def minAndMax[B>: A, A](iterable: Iterable[A])(implicit ordering: Ordering[B]): Option[(A, A)] =
  if (iterable.nonEmpty)
    Some(
      iterable.foldLeft((iterable.head, iterable.head)) {
        case (minAndMaxTuple, element) =>
          val (min, max) =
            minAndMaxTuple //decode reference to tuple
          if (ordering.lt(element, min))
            (element, max) //if replacing min, it isn't possible max will change so no need for the max comparison
          else
            if (ordering.lt(max, element))
              (min, element)
            else
              minAndMaxTuple //use original reference to avoid instantiating a new tuple
      }
    )
  else
    None

And here's the solution expanded to return the lower and upper bounds of a 2d space in a single pass, again using the above optimizations:

def minAndMax2d[B >: A, A](iterable: Iterable[(A, A)])(implicit ordering: Ordering[B]): Option[((A, A), (A, A))] =
  if (iterable.nonEmpty)
    Some(
      iterable.foldLeft(((iterable.head._1, iterable.head._1), (iterable.head._2, iterable.head._2))) {
        case ((minAndMaxTupleX, minAndMaxTupleY), (elementX, elementY)) =>
          val ((minX, maxX), (minY, maxY)) =
            (minAndMaxTupleX, minAndMaxTupleY) //decode reference to tuple
          (
              if (ordering.lt(elementX, minX))
                (elementX, maxX) //if replacing minX, it isn't possible maxX will change so no need for the maxX comparison
              else
                if (ordering.lt(maxX, elementX))
                  (minX, elementX)
                else
                  minAndMaxTupleX //use original reference to avoid instantiating a new tuple
            , if (ordering.lt(elementY, minY))
                (elementY, maxY) //if replacing minY, it isn't possible maxY will change so no need for the maxY comparison
              else
                if (ordering.lt(maxY, elementY))
                  (minY, elementY)
                else
                  minAndMaxTupleY //use original reference to avoid instantiating a new tuple
          )
      }
    )
  else
    None

Answer 9

You could always write your own foldLeft function - that will guarantee one iteration and known performance.

val array = Array(3,4,62,8,9,2,1)
if(array.isEmpty) throw new IllegalArgumentException // Just so we can safely call array.head

val (minimum, maximum) = array.foldLeft((array.head, array.head)) {  // We start of with the first element as min and max
  case ((min, max), next) =>
    if(next > max) (min, next)
    else if(next < min) (next, max)
    else (min, max)
}

println(minimum, maximum) //1, 62

Answer 10

scala> val v = Vector(1,2)
scala> v.max
res0: Int = 2
scala> v.min
res1: Int = 2

You could use the min and max methods of Vector