The solution involves scanning the array with two pointers while adjusting their positions based on the water capacity. By optimizing the search, we can achieve linear time complexity. The core of this approach is tracking the maximum water container during the traversal.
Problem Statement
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]). The goal is to find two lines that, together with the x-axis, form a container that holds the most water. Return the maximum amount of water a container can store.
To solve this problem, we need to identify the two lines that form the largest container possible by calculating the area between them. The area is determined by the smaller of the two heights and the distance between the lines. The challenge is to maximize this area while minimizing unnecessary calculations.
Examples
Example 1
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
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 2
Input: height = [1,1]
Output: 1
Example details omitted.
Constraints
- n == height.length
- 2 <= n <= 105
- 0 <= height[i] <= 104
Solution Approach
Two-pointer approach
Start by placing two pointers at the beginning and end of the array. Calculate the area formed by the lines at these pointers and track the maximum area. Move the pointer pointing to the smaller line towards the other pointer, aiming to find a taller line that may increase the area. Repeat this until the pointers meet, adjusting based on the height at each step.
Greedy optimization
The greedy aspect comes into play when choosing which pointer to move. Since the area is limited by the shorter line, we always move the pointer pointing to the shorter line. This ensures that we focus on increasing the height of the container, which can only improve the area calculation.
Time complexity and space complexity
The time complexity of the two-pointer approach is O(n), where n is the length of the array, as we only traverse the array once. The space complexity is O(1), since we only use a constant amount of space to store the pointers and the maximum area.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
The time complexity of the solution is O(n) because we iterate through the array once with two pointers. The space complexity is O(1), as we only use a few extra variables for storing pointers and the maximum area.
What Interviewers Usually Probe
- Do you understand the two-pointer technique and how it helps reduce the time complexity of this problem?
- Can you explain why we always move the pointer pointing to the shorter line in the two-pointer approach?
- Will you be able to implement the solution in linear time instead of simulating all possible pairs?
Common Pitfalls or Variants
Common pitfalls
- Failing to optimize the solution and instead using a brute-force approach that simulates all pairs, leading to O(n^2) time complexity.
- Incorrectly assuming that we need to calculate the area for every possible pair, without leveraging the two-pointer approach for optimization.
- Not updating the maximum area correctly when adjusting the pointers, potentially missing a larger valid container.
Follow-up variants
- What if the problem includes additional constraints, such as a limit on the number of lines that can be considered for the container?
- How would the solution change if the array elements were not restricted to heights, but had varying widths?
- What if you need to find the maximum area of water contained between two specific indices, instead of any two lines?
How GhostInterview Helps
- Capture the user's input array and highlight the two-pointer progression as they adjust the pointers during the process.
- Provide step-by-step visual aids to walk through the two-pointer approach and the iterative process of finding the maximum area.
- Offer workflows for sharing the screen to showcase the iterative steps and help understand the pointer adjustments in real-time.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How does the two-pointer technique work in this problem?
The two-pointer technique involves starting with one pointer at the beginning and another at the end of the array, calculating the container area, and then moving the pointer pointing to the smaller line to potentially find a larger area.
Why do we move the pointer pointing to the smaller line?
We move the pointer pointing to the smaller line because the area is limited by the shorter line. By moving it, we try to find a taller line to increase the area.
What is the time complexity of this solution?
The time complexity is O(n), where n is the number of lines, because we only traverse the array once using two pointers.
Can this problem be solved in O(n^2) time?
Yes, but O(n^2) would be inefficient. A brute-force solution would check all pairs of lines, which is unnecessary when a two-pointer technique can solve it in linear time.
What is the space complexity of this problem?
The space complexity is O(1) because we only need a few variables for tracking the pointers and the maximum area, regardless of the input size.
Need direct help with Container With Most Water instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Container With Most Water from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Create Maximum Number involves merging digits from two arrays while preserving order, maximizing the resulting number.
Open problem page#455 Assign CookiesMaximize content children by assigning at most one cookie per child using two-pointer scanning and greedy sorting techniques.
Open problem page#581 Shortest Unsorted Continuous SubarrayFind the shortest unsorted continuous subarray that, if sorted, would sort the entire array.
Open problem page