Leetcode - Contain With Most Water

Here is the link to the description: https://leetcode.com/problems/container-with-most-water/description/

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

Explanation

By brute-forcing, we could select all the possible combinations of the two lines. However, this is not the best idea based on the contstraints that 2 <= n <= 10^5. The time complexity of the brute-force approach is O(n^2).
Greedy approach reduces the time complexity to O(n^2). First, let's say we have the pair (left_line, right_line). left_line points to the first line(0) and right_line points to the last line(n-1). Then we find the smaller ones between the two lines. If left_line < right_line, we move left_line to the right by one since it's meaningless to move right_line to the left because the height of the container would stay the same and the width would decrease.

Proof by loop invariant.

If the following condition holds true at the beggning and the end of each itertion, we can prove that the algorithm finds the answer.

maximum_area has the maximum amount of water or the lines that can have the maximum amount of water is within the range (i,j)

• Base case: for the first iteration the condition holds true.
• Induction case: Suppose our condition is true for kth iteration. Let's assume maximum amount of water is not in maximum_area otherwise the proof would be trivial. for (k+1)th iteration, it would be still true since if height[i] <= height[j], decreasing j leads give less amount of water and if height[i] >= height[j], increasing i give less amount of water as well. So the best area is still between [left_area, right_area] after the iteration.