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:
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: 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
Constraints:
n == height.length2 <= n <= 1050 <= height[i] <= 104The key idea behind solving Container With Most Water is understanding how the area between two vertical lines is calculated: area = min(height[left], height[right]) * width. A brute-force approach would check every pair of lines to compute the maximum area, but this leads to inefficient performance.
A more optimal strategy uses the Two Pointers technique. Start with one pointer at the beginning of the array and the other at the end, forming the widest possible container. At each step, compute the area and update the maximum found so far. To potentially increase the area, move the pointer that points to the shorter line, since the container height is limited by the smaller boundary.
This greedy insight reduces unnecessary checks while still exploring promising candidates. The optimized method processes the array in a single pass, achieving O(n) time complexity with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (check all pairs) | O(n^2) | O(1) |
| Two Pointers (Optimal) | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
If you simulate the problem, it will be O(n^2) which is not efficient.
Try to use two-pointers. Set one pointer to the left and one to the right of the array. Always move the pointer that points to the lower line.
How can you calculate the amount of water at each step?
The two pointers approach efficiently searches for the maximum area by starting with the widest possible container and gradually narrowing it:
This approach works due to the observation that the area is limited by the shorter line, so the only way to get a larger area is to find a taller line.
Time Complexity: O(n), where n is the number of elements in the height array, due to the single traversal of the array.
Space Complexity: O(1) as only a few extra variables are used.
1#include <stdio.h>
2
3int maxArea(int* height, int heightSize) {
4 int left = 0,
This C implementation defines a function maxArea which takes an array of heights and iteratively calculates the maximum water that can be contained using a two-pointer approach. The output is printed after calling the function.
Although not optimal for large inputs, the brute force approach explores every possible pair of lines to find the maximum container area:
However, the complexity of this approach makes it unsuitable for large datasets due to its quadratic time complexity.
Time Complexity: O(n^2), where n is the number of elements as each pair is checked.
Space Complexity: O(1) due to a linear amount of extra space.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is commonly asked in coding interviews at companies like Google, Amazon, Meta, and other tech firms. It tests understanding of greedy thinking, two-pointer techniques, and optimization from brute-force solutions.
The problem mainly relies on arrays and pointer manipulation. The two-pointer technique works directly on the input array without requiring additional data structures, which keeps the space complexity constant.
The optimal approach uses the two pointers technique. Start with pointers at both ends of the array and move the pointer with the smaller height inward while tracking the maximum area. This greedy strategy ensures all useful candidates are explored in linear time.
The container's height is limited by the shorter line. Moving the taller line would only reduce the width without increasing the limiting height. By moving the shorter pointer, we give a chance to find a taller boundary that could increase the area.
This brute force C implementation explores every pair of lines to find the maximum container area by calculating the area for all possible pairs.