11. Container With Most Water[M]

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

Description

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 and n is at least 2.

img

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.

Example:

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

Solution

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

1
2
3
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.index(needle) if needle in haystack else -1

42. Trapping Rain Water[H]

https://leetcode.com/problems/trapping-rain-water/

Description

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.

img
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

1
2
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Solution

img

https://leetcode.com/problems/trapping-rain-water/solution/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0
        n = len(height)
        left, right = [0] * n, [0] * n
        
        temp = 0
        for i in range(n):     
            temp= max(temp,height[i])
            left[i] = temp
        
        temp = 0
        for i in range(n-1,-1,-1):
            temp = max(temp,height[i])
            right[i] = temp

        res = 0
        for i in range(n):             
            res+=min(left[i],right[i])-height[i]
        return res