give me the best code for the "Container With Most Water" leetcode in python
- User
give me the best code for the "Container With Most Water" leetcode in python
- Assistant
The "Container With Most Water" problem from LeetCode is a classic problem that can be solved efficiently using the two-pointer technique. The idea is to use two pointers, one starting at the beginning of the height array and one at the end. We calculate the area formed between the two pointers and then move the pointer that points to the shorter line inward, hoping to find a taller line that could potentially form a larger area.
Here’s an optimal solution in Python:
def maxArea(height): left = 0 right = len(height) - 1 max_area = 0 while left < right: # Calculate the width width = right - left # Calculate the height (the shorter line) h = min(height[left], height[right]) # Calculate area current_area = width * h # Update maximum area if the current one is greater max_area = max(max_area, current_area) # Move the pointer for the shorter line if height[left] < height[right]: left += 1 else: right -= 1 return max_area # Example usage: height = [1,8,6,2,5,4,8,3,7] print(maxArea(height)) # Output: 49Explanation of the Code:
-
Initialization: We initialize two pointers,
leftandright, denoting the start and end of the list, and a variablemax_areato keep track of the maximum water area found. -
While Loop: The loop continues until the two pointers meet. Inside the loop:
- We calculate the width as the difference between the
rightandleftpointers. - The height is determined by the shorter of the two lines at the
leftandrightpointers. - The area is calculated using the formula
width * height.
- We calculate the width as the difference between the
-
Update Maximum Area: If the calculated area is greater than the
max_area, we updatemax_area. -
Move the Pointer: We then check which of the two heights is shorter:
- If the height at
leftis less than the height atright, we incrementleft. - Otherwise, we decrement
right.
- If the height at
-
Return Result: Finally, we return the
max_areafound.
This solution has a time complexity of O(n) and a space complexity of O(1), which makes it highly efficient for this problem.
-