Leetcode 11: Container With Most Water

Problem:
Problem Statement

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 the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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 2:

Input: height = [1, 1]
Output: 1

Example 3:

Input: height = [4,3,2,1,4]
Output: 16

Example 4:

Input: height = [1,2,1]
Output: 2

Constraints:

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

Thinking and Solutions:
Well, I thought since this is a Dynamic Programming problem, we can create a recursion function.

And matrix is a 2 dimension matrix and matrix[i][j] store the maximal area from the i-th index to j-th index.

Then I want to find the maximal area among matrix[i][j-1], matrix[i+1][j] and matrix[i]j.

public class Solution {
    public static int maxArea(int[] height) {
        // Using Dynamic Programming
        // This is the area matrix. The first index is the start index. The second index is the ending index.
        int[][] matrix = new int[height.length][height.length];
        for (int i = 0; i < height.length; i++) {
            for (int j = 0; j < height.length; j++) {
                matrix[i][j] = -1;
            }
        }
        return maxAreaSub(height, 0, height.length-1, matrix);
    }

    public static int maxAreaSub(int[] height, int starting, int ending, int[][] matrix) {
        if(matrix[starting][ending] != -1){
            return matrix[starting][ending];
        }
        if (ending - starting == 1) {
            return Math.min(height[ending], height[starting]);
        }

        int left = maxAreaSub(height, starting, ending - 1, matrix);
        int right = maxAreaSub(height, starting + 1, ending, matrix);
        int current = (ending - starting) * Math.min(height[ending], height[starting]);
        int maxV = Math.max(Math.max(left, current), right);
        matrix[starting][ending] = maxV;
        return maxV;
    }
}

But a problem was that if the list is very long, like 1000 elements in the list, the matrix is 4M ($4 \time 1000 \time 1000$) for integer matrices.

So I thought building the dynamic programming from bottom to top could be a better way because it is more reasonable. Also, you don't need to store the maximal area matrix. Instead, storing the maximal area list for a certain length could be a good idea to reduce the storage pressure.

public class Solution2 {
    public static int maxArea(int[] height) {
        // Using Dynamic Programming
        // This is the area matrix. The first index is the start index. The second index is the ending index.
        int[] miniArea = new int[height.length];
        for (int i = 0; i < height.length; i++) {
            miniArea[i] = 0;
        }
        return maxAreaSub(height, 1, miniArea);
    }

    public static int maxAreaSub(int[] height, int length, int[] miniArea) {
        int[] areas = new int[height.length - length];
        for (int i = 0; i < height.length - length; i++) {
            int left = miniArea[i];
            int right = miniArea[i + 1];
            int current = length * Math.min(height[i], height[i + length]);
            areas[i] = Math.max(current, Math.max(left, right));
        }
        if (areas.length == 1) {
            return areas[0];
        }
        return maxAreaSub(height, length + 1, areas);
    }
}

The storage problem seems to be solved but actually since the recursion function is still too slow, time limit is still exceeded. So here, I sought for others' solutions. This is much easier solution but it seems to work well.

class Solution {
 public int maxArea(int[] height) {
    int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        while(left < right) {
            maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
            if(height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

It uses a global maximal area. With 2 pointers right and left, we can find a local area and judge which is the current maximal area.

Also, it has a basic idea that the maximal area is from the maximal length or from shorter length with two higher heights. So just greedy search the longer 2 heights could reduce the running time.

Conclusion

According to the problem, I realize 2 things:

Reasonable greedy search could be a good way to reduce the running time.
Writing a while instead of using a recursion function could be a good way for running dynamic programming.

Blog