Grokking #209

// Scala code
object Solution {
  import scala.collection.mutable._
  import scala.util.Sorting._

  def smallestDistancePair(nums: Array[Int], k: Int): Int = {
    var n = nums.length
    quickSort(nums)

    var lo = 0
    var hi = nums(n - 1) - nums(0)

    while (lo < hi) {
      var mid = lo + (hi - lo) / 2

      // count number of pairs which distance <= mid
      var count = 0
      var j = 0
      for (i <- 0 until n) {
        j = math.max(i + 1, j)
        while (j < n && nums(i) + mid >= nums(j)) {
          j += 1
        }
        count += j - i - 1
      }

      // if number of pairs with distance up to mid >= k,
      // continue searching until found minimum "mid" value (minimum distance)
      if (count >= k) {
        hi = mid
      } else {
        lo = mid + 1
      }
    }

    return lo
  }
}