Container With Most Water
Problem Description
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Example 2:
Constraints:
- n == height.length
- 2 <= n <= 105
- 0 <= height[i] <= 104
Solve it on LeetCode
Approaches
1. Brute Force
In the brute force approach, we'll iterate over all possible pairs of lines and calculate the area of water that it can contain. This involves a nested loop where the outer loop picks the first line and the inner loop tries all possible second lines. For each pair of lines, we calculate the minimum of these two heights (as water can only be stored up to the shorter line) and multiply it by the distance between them (their indices difference) to get the area. We keep track of the maximum area we've found so far.
Intuition:
- Check all pairs of lines (i, j), compute the container area they define.
- The area is determined by
H[i]andH[j], taking the smaller one, and the distance between walls(j - i).
Code:
- Time Complexity: O(n^2) due to the nested loop through the list.
- Space Complexity: O(1) as we're only using a few extra variables.
2. Two-Pointer
In this more optimal approach, we use two pointers, one at the beginning and one at the end of the array. In every step, we calculate the area formed by the lines at these two pointers. Then, we move the pointer pointing to the shorter line inward because moving the taller one wouldn't possibly increase the area.
Intuition:
- Start with the widest container possible. Move the shorter line inwards step by step.
- By closing in the pointers, we seek better maximum areas because even though the width reduces, we might have taller lines.
Code:
- Time Complexity: O(n) since we go through the list at most twice in a single pass.
- Space Complexity: O(1) as no additional space is used apart from some variables for storage.