LeetCode 11. Container With Most Water

LeetCode Problem No.11.

No.10 is here.

modalsoul.hatenablog.com

11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/

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.

Example

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Code1

object Solution {
  import scala.math.{max, min, abs}
  def maxArea(height: Array[Int]): Int = {
    var tmp = 0
    for {
      n1 <- 0 until height.length
      n2 <- 0 until height.length
    } {
      tmp = max(tmp, min(height(n1), height(n2)) * abs(n1 - n2))
    }
    tmp
  }
}

Methods

• Get all pairs of line and calculate the area of all pairs.

Results

Runtime: 1412 ms, faster than 7.89% of Scala online submissions for Container With Most Water. Memory Usage: 53.4 MB, less than 100.00% of Scala online submissions for Container With Most Water.

Code2

object Solution {
  import scala.math.{max, min, abs}
  def maxArea(height: Array[Int]): Int = {
    var tmp = 0
    var left = 0
    var right = height.length - 1
    while (right > left) {
      val rh = height(right)
      val lh = height(left)
      tmp = max(tmp, min(rh, lh) * (right - left))
      if(rh > lh) left = left + 1
      else right = right - 1
    }
    tmp
  }
}

Methods

• left starts with head of array.
• right starts with last of array.
• Calculate area with left and right.
• Shift left or right which is smaller.

Results

Runtime: 708 ms, faster than 30.26% of Scala online submissions for Container With Most Water. Memory Usage: 75.5 MB, less than 100.00% of Scala online submissions for Container With Most Water.