How to get the minimum gap between list items?

Question

For example, suppose I have a sorted list

val sorted = List (1, 5, 15, 37, 39, 42, 50)

The smallest clearance is (39-37) = 2. How do I get this result? I am looking at foldLeft. I feel that it looks like what I need, but not quite right.

Answer 1

val sorted = List(1, 5, 15, 37, 39, 42, 50) (sorted.tail,sorted).zipped.map(_-_).min //res2: Int = 2 

[change]

You can also use the fold:

 sorted.tail.foldLeft((sorted.head,Int.MaxValue))((x,y) => (y, math.min(yx._1,x._2)))._2 

Answer 2

 val sorted = List(1, 5, 15, 37, 39, 42, 50) sorted match { case Nil => None case List(a) => None case l => Some(l.sliding(2).map{case Seq(a, b) => math.abs(a - b)}.min) } // res1: Option[Int] = Some(2) 

sliding returns an iterator, so it should go only once.

If you're interested in finding which two elements have the least space, you can also use minBy. So, here is another variation, just for fun.

 sorted.view.zip(sorted.tail).minBy(t => math.abs(t._1 - t._2)) // res4: (Int, Int) = (37,39) 

Answer 3

Here is what I will do:

• write a function that converts a list of n numbers to a list of (n - 1) spaces

• write / use a function that selects the smallest number from a list

Remember to process the empty list for part 1! (By the way, part 2 can be written as a fold).

Answer 4

Using foldLeft:

  sorted match { case Nil | List(_) => None case x :: xs => Some( (xs.foldLeft((Integer.MAX_VALUE, x)) { case ((min, prev), next) => (math.min(min, next - prev), next) })._1 ) } 

Answer 5

Imperative (and possibly faster) version:

  if (sorted.isEmpty) { None } else { var sortedTail = sorted.tail if (sortedTail.isEmpty) { None } else { var minDiff = Int.MaxValue var prev = sorted.head do { val curr = sortedTail.head minDiff = minDiff min math.abs(curr - prev) sortedTail = sortedTail.tail prev = curr } while (!sortedTail.isEmpty) Some(minDiff) } }