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.

Brute-force Approach

Iterate through all possible pairs of lines and calculate the area. Find the maximum area.

Time: O(n^2)

Space: O(1)

Optimal Approach

Use two pointers, one at the start and one at the end of the array. This will maximize the width of the container. Now, try to maximize the height by moving the pointer with the smaller height inwards.

Time: O(n)

Space: O(1)