Start learning free

LESSON 232 OF 347 · TWO POINTERS

Container With Most Water in C#: Two Pointers in O(n)

Practice O(n) Read the full explanation

You are given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i are (i, ai) and (i, 0). Find two lines, which together with the x-axis form a container, such that this container contains the most water.

Note: You may not slant the container and n is at least 2.

 

The above vertical lines are represented by the array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) one container can contain is 49.

 

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49
STEP 1 OF 7
    Ctrl + Enter to check

    C# · TWO POINTERS

    Container With Most Water in C#, explained

    Problem overview

    The method MaxArea receives an int[] height. Entry height[k] is a vertical line at position k reaching up to that height. Any two lines, together with the x-axis, form a container. Its water area is the distance between the lines times the height of the shorter line. The method returns the largest area any pair can hold.

    For [1, 8, 6, 2, 5, 4, 8, 3, 7] the answer is 49. The lines at indices 1 and 8 have heights 8 and 7, so the water level is 7 and the width is 8 - 1 = 7, giving 7 * 7 = 49. The container cannot be tilted, and there are at least two lines.

    Approach: start wide, move the shorter line

    The direct way is to try all pairs, which is O(n²). The two-pointer solution reaches O(n).

    Start with the widest container: left at index 0 and right at the last index. Its area is min(height[left], height[right]) * (right - left). Now one pointer must move inward, because the width shrinks by one with every step. The question is which one.

    • The water level is capped by the shorter line. If you move the taller line inward, the width gets smaller and the height is still at most the shorter line's, so the new container cannot be larger. Moving the taller line is pointless.
    • If you move the shorter line, the next line may be taller and might make up for the lost width.

    So after measuring a container, discard the shorter line. Every container that uses that line with a narrower partner is no better than the one just measured, so nothing is lost. The pointers meet after n - 1 moves.

    On the example, the first container uses indices 0 and 8 (heights 1 and 7): area 1 * 8 = 8. Line 0 is shorter, so left moves to index 1. Now the heights are 8 and 7 and the width is 7, giving 49. Line 8 is the shorter one, so right moves to index 7, and later containers are narrower and, on this input, never exceed 49.

    Step by step

    1. Set up the state. result starts at 0, left at 0 and right at height.Length - 1, the last valid index.
    2. Loop while left < right. When the pointers meet there is no pair left to form a container.
    3. Compute the area. Take Math.Min of the two heights, since water above the shorter line would spill, and multiply by right - left.
    4. Keep the best. Math.Max compares the new area with result so the stored value never decreases.
    5. Move the shorter side. If height[left] < height[right], increment left.
    6. Otherwise decrement right. This branch runs when the right line is the shorter one or when the two are equal. With equal heights, moving either pointer is safe.
    7. Return result.

    The solution in C#

    class Solution {
    public int MaxArea(int[] height) {
        int result = 0, left = 0, right = height.Length - 1;
        while (left < right) {
            int area = Math.Min(height[left], height[right]) * (right - left);
            result = Math.Max(result, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return result;
    }
}

    C# notes on this code:

    • Length is a property. For an array, write height.Length with no parentheses. The last index is one less than the length, because indexing starts at 0.
    • Math.Min and Math.Max are static methods on the Math class, with capital letters. Each takes two numbers and returns one of them.
    • The product is an int. If heights and widths could be large enough that the area exceeds about 2.1 billion, the multiplication would wrap around silently instead of throwing. Declaring area and result as long and casting one factor would be the fix in that case.
    • Declaring several variables. int result = 0, left = 0, right = height.Length - 1; declares three int variables in one statement. The third initializer can use height, since it is a parameter.

    Complexity

    Time: O(n). Each iteration moves one pointer one step inward, so the loop runs exactly n - 1 times. Each iteration does a constant amount of work.

    Space: O(1). The method keeps only a handful of integer variables, whatever the size of the input.

    Edge cases and common mistakes

    • Exactly two lines. For [1, 1] the loop runs once: area 1 * 1 = 1. Then the pointers meet and the loop ends.
    • Zero heights. For [0, 0] the area is 0, so the method returns 0. Starting result at 0 is correct because areas are never negative.
    • Using the taller line's height. The water level is the minimum of the two heights. Using Math.Max there overstates the area.
    • Using left <= right. When the pointers are equal, the "container" has width 0 and one line. The loop must stop before that.
    • Moving the taller line. It looks natural to keep the shorter line and move the taller one, but this is exactly the move that cannot help.
    • Width off by one. The width is right - left, the difference of the indices, not the count of lines between them.

    Testing

    • [1, 8, 6, 2, 5, 4, 8, 3, 7] gives 49.
    • [1, 1] gives 1.
    • [4, 3, 2, 1, 4] gives 16: the two outer lines of height 4, four apart.
    • [0, 0] gives 0.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free