LeetCode 11 – Container with most water

Solution to LeetCode Container with most water problem.

The naive version would solve this in \(O(n^2)\) time. It can be improved as follows to linear time:

Keep two indices \(i\) and \(j\), that start on both ends of the array to process, height. Our final goal is to find \(i\),\(j\), such that \[ A(i,j) = (j-i) \times \min(\mathrm{height}(i), \mathrm{height}(j)) \] is maximized. At every step, if height[i] < height[j], move i up by one. Otherwise move j down by one, until the two pointers meet. We now show that this gives the maximal answer. Suppose we just computed \(A(i,j)\), and height[i] < height[j]. If we increase \(i\) by one, we will ignore all the values \(A(i,k)\) for \(i \leq k \lt j\). We now show that \(A(i,j) \gt A(i,k)\). Since height[i] < height[j], \(A(i,k)\) is bounded by the height[i] term, and since \(k < j\), it follows that \(A(i,j) \gt A(i,k)\), and we can safely ignore all of the \(A(i,k)\) and move on to inspecting \(A(i+1,j)\). The case with height[i] > height[j] is symmetric.

public int maxArea(int[] height) {
  int maxA = 0;
  int i = 0;
  int j = height.length-1;

  while(i < j){
    int curArea = (j-i) * (Math.min(height[i], height[j]));
    maxA = Math.max(curArea,maxA);
    if(height[i] < height[j]) i++;
    else j--;
  }

  return maxA;
}