Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Container with most water challenge

Sharing is caring!

Problem statement

Given n non-negative integers a_1, a_2, \dots, a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

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

Solution
We are going to solve this problem using two pointers l and r. Pointer l starts from the left-most side and r starts from the right-most side. We then keep track of our maximum container:

maximum = max(maximum, min(height[l], height[r]) * (r - l))

and then move one of the pointers based on the following conditions:

if height[l] < height[r]:
    l += 1
else:
    r -= 1

Let us explain the logic behind this algorithm using the illustration below.

For wall A we want to use wall D as its counterpart since D is taller than A and as far on the right as possible. Any wall to the left of D can be ignored because it will only make our container smaller as D is already taller than A. That is why it doesn't make any sense to decrease our index r. With A and D we have a container size of 3.

We then increment our index 'l' because A is shorter than D. That is, move it to wall B in hopes that we can find a taller counterpart for our tall wall D. Now, wall B is taller than its predecessor and actually increases our container size to 4. We can see that since we previously increased the index pointing to the shorter of the two walls (A vs D) we were able to find a counterpart (B) for wall D that increased our container size.

Finally we again increase our index pointing to the shortest wall in hopes that we may find an even taller counterpart for D. Moving l to C we see that this does not increase our container size. Also since l and r meet, we stop the search and return 4.

The full code is listed below.

Full code

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l = 0
        r = len(height) - 1
        maximum = 0
        while l < r:
            maximum = max(maximum, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        
        return maximum