Problem Statement in English

You’re given a list of wall heights, heights. Your task is to return the maximum area between 2 walls.

Approach

We use the 2 Pointer Technique. We initialise the left pointer to point at the $0\text{th}$ index, and the right pointer to point at the last index.

The height of water that can be filled in the container depends upon the smaller wall. So we always want to move the smaller wall - in search of a larger wall!

At every step we must move one of the 2 pointers. If we’re moving the left pointer, then we must move it towards the right, and if we’re moving the right pointer then we must move it towards the left.

That’s pretty much it. Take a look at the code to solidify your understanding.

Solution in Python


class Solution:
    def maxArea(self, heights: List[int]) -> int:
        # init `l` and `r` pointer
        l, r = 0, len(heights) - 1

        # holds the best area
        bestArea = 0

        # always ensure `l` is before `r`
        while l < r:
            # update current best area
            # calculate area between left wall and right wall
            distanceBetweenWalls = r - l
            bestArea = max(bestArea, min(heights[l], heights[r]) * distanceBetweenWalls)

            # see if we should move `l` towards `r` or vice versa
            # we move the pointer that points at the smaller wall
            if heights[l] > heights[r]:
                # right pointer must move towards the left
                r -= 1
            else:
                # left pointer must move towards the right
                l += 1

        # return the best area so far
        return bestArea

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(1)$
    Since we store a few integer variables.

And we are done.