container_with_most_water
1# @leet start 2class Solution: 3 def maxArea(self, height: list[int]) -> int: 4 """ 5 This problem involves calculating the max area of a set of bars. 6 The distance betwee each bar is 1, and the height of each bar is given. 7 The naive solution involves testing each $n * (n - 1)$ combination of bars 8 to find the highest area. This predictably takes $O(n^2)$ time, and takes 9 the most amount of time possible (there are $n^2$ pairs, so testing all of them 10 is the brute force approach. 11 12 There's an $O(n)$ solution by removing checking $n - 1$ positions for each pair. 13 The way to do that is by knowing that it's only possible to increase the area 14 by either starting at the center or the ends. 15 16 If we start at the center, every pair is possibly bigger, on both the left 17 and right hand side. We'd still end up with an $O(n^2)$ solution, because 18 we have to check both sides and we want to avoid that. 19 20 If we start at the ends, however, we know that there's no possible way to increase 21 the area unless we move the smaller bar in. If we move the larger bar in, 22 then we always decrease the total area. However, if we move the smaller bar in, 23 there is a chance there is a larger bar in between that can produce a larger area. 24 25 We do this up to $O(n)$ times, and calculate the largest area in the array. 26 """ 27 i, j = 0, len(height) - 1 28 max_area_so_far = 0 29 30 while i < j: 31 left_height, right_height = height[i], height[j] 32 area = (j - i) * min(left_height, right_height) 33 max_area_so_far = max(area, max_area_so_far) 34 if left_height < right_height: 35 i += 1 36 else: 37 j -= 1 38 39 return max_area_so_far 40 41 42# @leet end 43sol = Solution() 44 45 46def test(): 47 assert sol.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49 48 assert sol.maxArea([1, 1]) == 1
class
Solution:
3class Solution: 4 def maxArea(self, height: list[int]) -> int: 5 """ 6 This problem involves calculating the max area of a set of bars. 7 The distance betwee each bar is 1, and the height of each bar is given. 8 The naive solution involves testing each $n * (n - 1)$ combination of bars 9 to find the highest area. This predictably takes $O(n^2)$ time, and takes 10 the most amount of time possible (there are $n^2$ pairs, so testing all of them 11 is the brute force approach. 12 13 There's an $O(n)$ solution by removing checking $n - 1$ positions for each pair. 14 The way to do that is by knowing that it's only possible to increase the area 15 by either starting at the center or the ends. 16 17 If we start at the center, every pair is possibly bigger, on both the left 18 and right hand side. We'd still end up with an $O(n^2)$ solution, because 19 we have to check both sides and we want to avoid that. 20 21 If we start at the ends, however, we know that there's no possible way to increase 22 the area unless we move the smaller bar in. If we move the larger bar in, 23 then we always decrease the total area. However, if we move the smaller bar in, 24 there is a chance there is a larger bar in between that can produce a larger area. 25 26 We do this up to $O(n)$ times, and calculate the largest area in the array. 27 """ 28 i, j = 0, len(height) - 1 29 max_area_so_far = 0 30 31 while i < j: 32 left_height, right_height = height[i], height[j] 33 area = (j - i) * min(left_height, right_height) 34 max_area_so_far = max(area, max_area_so_far) 35 if left_height < right_height: 36 i += 1 37 else: 38 j -= 1 39 40 return max_area_so_far
def
maxArea(self, height: list[int]) -> int:
4 def maxArea(self, height: list[int]) -> int: 5 """ 6 This problem involves calculating the max area of a set of bars. 7 The distance betwee each bar is 1, and the height of each bar is given. 8 The naive solution involves testing each $n * (n - 1)$ combination of bars 9 to find the highest area. This predictably takes $O(n^2)$ time, and takes 10 the most amount of time possible (there are $n^2$ pairs, so testing all of them 11 is the brute force approach. 12 13 There's an $O(n)$ solution by removing checking $n - 1$ positions for each pair. 14 The way to do that is by knowing that it's only possible to increase the area 15 by either starting at the center or the ends. 16 17 If we start at the center, every pair is possibly bigger, on both the left 18 and right hand side. We'd still end up with an $O(n^2)$ solution, because 19 we have to check both sides and we want to avoid that. 20 21 If we start at the ends, however, we know that there's no possible way to increase 22 the area unless we move the smaller bar in. If we move the larger bar in, 23 then we always decrease the total area. However, if we move the smaller bar in, 24 there is a chance there is a larger bar in between that can produce a larger area. 25 26 We do this up to $O(n)$ times, and calculate the largest area in the array. 27 """ 28 i, j = 0, len(height) - 1 29 max_area_so_far = 0 30 31 while i < j: 32 left_height, right_height = height[i], height[j] 33 area = (j - i) * min(left_height, right_height) 34 max_area_so_far = max(area, max_area_so_far) 35 if left_height < right_height: 36 i += 1 37 else: 38 j -= 1 39 40 return max_area_so_far
This problem involves calculating the max area of a set of bars. The distance betwee each bar is 1, and the height of each bar is given. The naive solution involves testing each $n * (n - 1)$ combination of bars to find the highest area. This predictably takes $O(n^2)$ time, and takes the most amount of time possible (there are $n^2$ pairs, so testing all of them is the brute force approach.
There's an $O(n)$ solution by removing checking $n - 1$ positions for each pair. The way to do that is by knowing that it's only possible to increase the area by either starting at the center or the ends.
If we start at the center, every pair is possibly bigger, on both the left and right hand side. We'd still end up with an $O(n^2)$ solution, because we have to check both sides and we want to avoid that.
If we start at the ends, however, we know that there's no possible way to increase the area unless we move the smaller bar in. If we move the larger bar in, then we always decrease the total area. However, if we move the smaller bar in, there is a chance there is a larger bar in between that can produce a larger area.
We do this up to $O(n)$ times, and calculate the largest area in the array.
sol =
<Solution object>
def
test():