Question

Formatted question description: https://leetcode.ca/all/11.html

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th 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.

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

Constraints:

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

Algorithm

The following is an example: [4,6,2,6,7,11,2] to explain.

First, suppose we find the vertical line that can take the maximum volume as i, j (assuming i<j), then the maximum volume C = min(a[i], a[j]) * (j- i);
Below we look at such a property:
- No line at the right end of j will be higher than it! Suppose there is k (j < k && a[k] > a[j]), then a[k] > a[j], so min(a[i], a[j], a[k]) = min(a[i], a[j]), so the volume of the container formed by i, k C' = min(a[i], a[j]) * (k-i) > C, which is the most contradictory value with C, so there will be no line higher than it behind the proof j;
- Similarly, there will be no higher line on the left side of i;
What is this indicating? If we currently get the candidate: set x, y as two lines (x < y), then the two new edges that can be larger than it must be in the interval [x,y] and a[x'] >= a[x], a[y'] >= a[y];
So we move closer from the two ends to the middle, and update the candidate values at the same time; when shrinking the interval, first shrink from the smaller edge of x, y;

The intuitive explanation is: volume is area, which is affected by length and height. When the length decreases, the height must increase to increase the area, so we start to decrease from the longest length, and then look for a higher line to update Alternate.

Code

public class Container_With_Most_Water {

	public static void main(String[] args) {
		Container_With_Most_Water out = new Container_With_Most_Water();
		Solution2 s = out.new Solution2();

		System.out.println(s.maxArea(new int[]{2,0,2}));
	}

    // time: O(N)
    // space: O(1)
	public class Solution {
	    public int maxArea(int[] height) {
	        int[] h = height;

	        if(h == null || h.length == 0) {
	            return 0;
	        }

	        int l = 0; // left
	        int r = h.length - 1; // right

	        int max = (r - l) * Math.min(h[l], h[r]); // possibly very first position is max area
	        while(l < r) {
	            if(h[l] < h[r]) {
	                l++;
	            } else {
	                r--;
	            }

	            max = Math.max(max, (r - l) * Math.min(h[l], h[r]));
	        }

	        return max;
	    }
	}

	// N^2. Time Limit Exceeded
	public class Solution2 {
		public int maxArea(int[] h) { // h: height
			if (h == null || h.length == 0) {
				return 0;
			}

			// possibly sanity check for negative int in array, throw something for debugging
			// never trust the passed in parameter!

			int i = 0;
			int max = Integer.MIN_VALUE;
			while (i < h.length) {

				int j = i + 1;
				while (j < h.length) {

					max = Math.max(max, (j - i) * Math.min(h[i], h[j]));
					j++;
				}

				i++;
			}

			return max;
		}
	}

}

############

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

// OJ: https://leetcode.com/problems/container-with-most-water/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int maxArea(vector<int>& A) {
        int N = A.size(), ans = 0;
        for (int i = 0; i < N; ++i) {
            if (!A[i]) continue;
            for (int j = i + 1 + ans / A[i]; j < N; ++j) {
                ans = max(ans, min(A[i], A[j]) * (j - i));
            }
        }
        return ans;
    }
};

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j = 0, len(height) - 1
        res = 0
        while i < j:
            t = (j - i) * min(height[i], height[j])
            res = max(res, t)
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return res

############

class Solution(object):
  def maxArea(self, height):
    """
    :type height: List[int]
    :rtype: int
    """
    ans = left = 0
    right = len(height) - 1
    while left < right:
      ans = max(ans, (right - left) * min(height[left], height[right]))
      if height[left] <= height[right]:
        left += 1
      else:
        right -= 1
    return ans

func maxArea(height []int) int {
    i, j := 0, len(height) - 1
    res := 0
    for i != j {
        t := (j - i) * min(height[i], height[j])
        res = max(res, t)
        if height[i] < height[j] {
            i++
        } else {
            j--
        }
    }
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

function maxArea(height: number[]): number {
    const n = height.length;
    let res = 0;
    for (let i = 0; i < n - 1; i++) {
        for (let j = n - 1; j >= 0; j--) {
            if (height[i] * (j - i) < res) {
                break;
            }
            res = Math.max(res, Math.min(height[i], height[j]) * (j - i));
        }
    }
    return res;
}

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
    let i = 0,
        j = height.length - 1;
    let res = 0;
    while (i < j) {
        const t = (j - i) * Math.min(height[i], height[j]);
        res = Math.max(res, t);
        if (height[i] < height[j]) ++i;
        else --j;
    }
    return res;
};

impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let mut i = 0;
        let mut j = height.len() - 1;
        let mut res = 0;
        while i < j {
            res = res.max(height[i].min(height[j]) * (j - i) as i32);
            if height[i] <= height[j] {
                i += 1;
            } else {
                j -= 1;
            }
        }
        res
    }
}

public class Solution {
    public int MaxArea(int[] height) {
        int i = 0, j = height.Length - 1;
        int ans = 0;
        while (i < j) {
            int t = Math.Min(height[i], height[j]) * (j - i);
            ans = Math.Max(ans, t);
            if (height[i] < height[j]) {
                ++i;
            } else {
                --j;
            }
        }
        return ans;
    }
}

11 - Container With Most Water

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions