C++ Coding Exercise – Container With Most Water (Recursion)

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 is at (i, ai) 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.

container-with-most-water-leetcode-puzzle-coding-exercise

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

This is an interesting problem. You can bruteforce all the pairs n*(n-1)/2 which gives complexity O(n^2). It can be implemented as a recursion which requires O(n) space complexity (recursion stack) as follows:

class Solution {
public:
    int f(vector<int>& height, int j) {
        if (j == 0) return 0;
        if (j == 1) return min(height[0], height[1]);
        int r = f(height, j - 1);
        for (int k = 0; k < j; k ++) {
            r = max(min(height[k], height[j]) * (j - k), r);
        }        
        return r;
    }
    
    int maxArea(vector<int>& height) {        
        return f(height, height.size() - 1);
    }
};

The f(j) returns the maximum water held from 0 to j inclusive. If j is the external post, we compute with O(n) complexity the maximum pairs from 0 to j-1. Of course, we also need to compare with f(j – 1) which means if j is not selected as the external post.

f(j) recursively calls f(j-1) and the overall complexity is O(n^2). However, it could also be implemented as a simple O(n^2) loop with O(1) space complexity.

class Solution {
public:
    int maxArea(vector<int>& height) {        
        auto r = INT_MIN;
        for (auto i = 0; i < height.size(); ++ i) {
            for (auto j = i + 1; j < height.size(); ++ j) {
                r = max(r, (j - i) * min(height[i], height[j]));
            }
        }
        return r;
    }
};

There is actually an O(n) solution with O(1) space. We first construct the posts at the external border which is (0, j – 1) where j is the size of the input array. Let’s say we have two pointers at both side, if we move the pointer at the longer side, we won’t gain any increase of the water capacity because the container is limited by the shorter size. On the other hand, if we move side with a shorter border, we may gain more area to compensate the reduction of X-length.

This is greedy algorithm!

class Solution {
public:   
    int maxArea(vector<int>& height) {        
        int maxarea = 0, l = 0, r = height.size() - 1;
        while (l < r) {
            maxarea = max(maxarea, min(height[l], height[r]) * (r - l));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return maxarea;
    }
};

To give you a rough idea of both O(n^2) and O(n) solution: the first two approaches (bruteforce) passed 50 tests on leetcode and used around 1 second while the O(n) solution took around 12ms.

You may also like: C++ 编程练习题 – 最多水容器 (递归)

–EOF (The Ultimate Computing & Technology Blog) —