Teaching Kids Programming – Container With Most Water (Bruteforce, Two Pointer/Greedy Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Bruteforce Algorithm to Find the Two Vertical Bars that Holds Most Water

Given there are N bars, we want to find the optimal two – a hint to use bruteforce algorithms. There are ways which indicates time complexity.

The volume of water is determined by the shortest bar and we can easily compute the area of a rectangle.

1
2
3
4
5
6
7
8

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        for L in range(n):
            for R in range(L, n):
                ans = max(ans, min(height[L], height[R]) * (R - L))
        return ans            

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        for L in range(n):
            for R in range(L, n):
                ans = max(ans, min(height[L], height[R]) * (R - L))
        return ans            

Two Pointer Algorithm to Find the Two Vertical Bars that Holds Most Water

Two Pointer can usually be used to improve O(N^2) to O(N). We initialize the two pointers left and right – which is located at the left-most and right-most bars. We then update the max volume and move the shorter bar towards the other (Greedy Strategy).

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        L = 0
        R = n - 1
        while L < R:
            ans = max(ans, min(height[L], height[R]) * (R - L))
            if height[L] <= height[R]:
                L += 1
            else:
                R -= 1
        return ans

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        L = 0
        R = n - 1
        while L < R:
            ans = max(ans, min(height[L], height[R]) * (R - L))
            if height[L] <= height[R]:
                L += 1
            else:
                R -= 1
        return ans

Proof of Two Pointer Algorithms

Current volume is where t is the distance between L and R. If we move the longer bar which has a new height R1, and the distance t1, we get:

.

We know and

Therefore, we don’t get a larger volume by moving the longer bar towards the shorter bar – then we don’t need to bruteforce those situations. Instead, we can skip and move the shorter bar.

The two pointer has O(N) time complexity.

–EOF (The Ultimate Computing & Technology Blog) —