Find Maximun area on Array

Question

I am doing exercises from the app Data Structures in Scala, I have coded the second problem on Arrays like this:

/**
   * Given n non-negative integers a1, a2, ..., an, where each represents a
   * point at coordinate (i, ai), n vertical lines are drawn such that
   * the two endpoints of line i is at (i, ai) and (i, 0). 
   * 
   * Find two lines, which together with x-axis forms a container such
   * that the container contains the most water.
   *
   * Efficiency: O(n)
   *
   * @param a Array of line heights
   * @return Maximum area
   */
  def maxArea(a: Array[Int]): Int = {
    @tailrec
    def go(l: Int, r: Int)(max: Int): Int = {
      if (l >= r) max
      else {
        val currArea = math.min(a(l), a(r)) * (r - l)
        val area = math.max(max, currArea)
        log debug s"Current area for $l and $r is $currArea"
        log debug s"Max area till now is $area"
        if (a(l) < a(r)) go(l + 1, r)(area)
        else go(l, r - 1)(area)
      }
    }
    go(0, a.size - 1)(0)
}

I wonder if there is a better alternative to write recursive functions as a way of looping through the Array, as someone once told me calls recursion the GOTO of functional programming.

You can check the complete source code at GitHub

Thank you in advance.

Re recursion/goto, for those interested, [the related paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125) — Lasf, Nov 16 '18 at 20:14

score 1 · Accepted Answer · answered Nov 16 '18 at 20:42

Here's a way to implement your algorithm without recursion (not that I actually think there's anything inherently wrong with recursion).

def maxArea2(a: Array[Int]): Int = {
  Stream.iterate(0 -> a){ case (_, arr) =>
    if (arr.length < 2) -1 -> arr
    else {
      val (lft, rght) = (arr.head, arr.last)
      val area = (lft min rght) * (arr.length - 1)
      if (lft <= rght) area -> arr.dropWhile(_ <= lft)
      else             area -> arr.reverse.dropWhile(_ <= rght)
    }
  }.takeWhile(_._1 >= 0).maxBy(_._1)._1
}

The idea is to iterate lazily and the take (i.e. realize) only those you need.

You'll note that this iterates, and calculates areas, fewer times because it drops values that can't beat the current area calculation.

Thanks!, so it seems this approach would be more efficient? – Alejandro Alcalde Nov 17 '18 at 14:36 — Alejandro Alcalde, Nov 17 '18 at 14:36

Find Maximun area on Array

1 Answers1