Container With Most Water - Problem 11

Problem:

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.

Note: You may not slant the container.

Naive O(n2) Loop(TLE):

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        mArea = 0
        i = 0
        while i < len(height):
            j = i + 1
            while j < len(height):
                area = (j - i) * min(height[i], height[j])
                mArea = area if area > mArea else mArea
                j += 1
            i += 1
        return mArea

We define the maximum area between point i and j is S(i, j). So what we need is S(1, n).

Assuming ai > aj, S(i, j) = max(A(i, j), S(i, j-1)). Because with the ascending of the i, the width is descending, and the height is equal or smaller then aj. So the area is smaller than A(i, j). So it could't be the max area. So the max area only could be A(i, j) or S(i, j-1).

So, we can get the equation.

\begin{eqnarray}S(i, j)=
\begin{cases}
max(A(i, j), S(i, j-1), & a_i > a_j \cr
max(A(i, j), S(i+1, j), & a_j > a_i
\end{cases}
\end{eqnarray}

So, use this equation:

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        mArea = 0
        i, j = 0, len(height) - 1
        while i < j:
            area = min(height[i], height[j]) * (j - i)
            mArea = area if area > mArea else mArea
            if height[i] > height[j]:
                j -= 1
            else:
                i += 1
        return mArea

Trapping Rain Water - Problem 42

Problem:

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

rainwatertrap

The volume it can contains is decided by the leftMax height and rightMax height. So first calc the position i's leftMax and rightMax, and loop again to find out position i's volume.

min(leftMax - rightMax) - height[i]

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        area, maxHeight = 0, 0
        left, right = [], []
        for h in height:
            maxHeight = h if h > maxHeight else maxHeight
            left.append(maxHeight)
        maxHeight = 0
        for h in height[::-1]:
            maxHeight = h if h > maxHeight else maxHeight
            right.append(maxHeight)
        right = right[::-1]
        for i in xrange(len(height)):
            area += min(left[i], right[i]) - height[i]
        return area

We don't need to find the max Height. Use a variable to record the second height, i.e. the maximum height it passes, because the pointer will stop at the maximum height. And the volume is decided by the left and right. If left is smaller, the left side could contain. And the volume is decided by the left nearest maximum height, i.e. second Height.

secHeight - height

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        area, secHight = 0, 0
        left, right = 0, len(height) - 1
        while left < right:
            if height[left] < height[right]:
                secHight = max(height[left], secHight)
                area += secHight - height[left]
                left += 1
            else:
                secHight = max(height[right], secHight)
                area += secHight - height[right]
                right -= 1
        return area

Also, we can add the 'V' area to total from left to right once a loop. Find the begin, nearest lowest, and nearest highest, and calc the area. Move the begin to the highest, until move to the end.

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        area, begin = 0, 0
        while begin < len(height) - 1 and height[begin] <= height[begin + 1]:
            begin += 1
        while begin < len(height):
            lowest = -1
            highest = -1
            for i in xrange(begin, len(height) - 1):
                if height[i] < height[i + 1]:
                    lowest = i
                    break
            if lowest == -1:
                begin = len(height)
                continue
            tmpPos, tmpValue = 0, 0
            for i in xrange(lowest + 1, len(height)):
                if height[i] > height[begin]:
                    highest = i
                    break
                if height[i] >= tmpValue:
                    tmpPos = i
                    tmpValue = height[i]
            if highest == -1:
                highest = tmpPos
            w = highest - begin - 1
            h = min(height[begin], height[highest])
            area += w * h - sum([min(_h, h) for _h in height[begin + 1:highest]])
            begin = highest
        return area