11. Container With Most Water

LeetCode
,

My Solution (BF)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;

        for (int i = 0; i < height.length - 1; i++){
            for (int j = i + 1; j < height.length; j++)
            {
                int area = (j-i)*Math.min(height[i], height[j]);
                if (area > maxArea){
                    maxArea = area;
                }
            }
        }

        return maxArea;
    }
}

Remarks:

  1. use .length but NOT .size() for an array
  2. area in decided by the min of two heights
  3. TC: $O(n!)$ too big!!

Double Pointer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            int area = (right - left) * Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, area);

            // move the short bar
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}

Remarks:

  1. TC: $O(n)$
  2. Why it works? if we move the longer line, the height is still the smaller one, while the base width is smaller. Thus, no matter how we move the longer line, the size always decreases. Hence, we move the shorter line.