Python Algorithm Q8+a

Q8 +α Container With Most Water

---

Q

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 the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Sample Input

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Input: height = [1,1]
Output: 1

Input: height = [4,3,2,1,4]
Output: 16

Input: height = [1,2,1]
Output: 2

Constraints

• n == height.length
• 2 <= n <= 10⁵
• 0 <= height[i] <= 10⁴

1. My Solution <- Referenced Solution

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        max_water = 0

        while(right-left > 0): #until dist != 0
            max_water = max(max_water, (right-left)*min(height[right], height[left])) #return water amount

            if height[right] > height[left]:
                left += 1
            else:
                right -= 1

        return max_water

[Using two-pointer]
With brute force, there’s no doubt that time complexity will be O(n^2). So with the two-pointer, improve its structure. Basis is the distance(between left & right). Until left & right meet, constantly moves inward. Since maximum value is saved at the variable “max_water”, never worry that this process passes through some cases. Keep comparing previous maximum value(=max_water) and current value(dist*height). After deciding which is the max, move the pointer which has smaller height “priorly”. For the higher value, it is more probable to move the shorter column.

Overall Review

Comparing and finding which is the maximum set is really complex… Improving from brute force is out of my ability. Feeling much more need to study various kinds of algo.