LeetCode: Container With Most Water

 The Problem statement is copy pasted from LeetCode as it is:

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 <= 3 * 104
• 0 <= height[i] <= 3 * 104

My Solution

package madwani.sushil.leetcode.Amazon;

public class ContainerWithMostWater {
    public static void main(String[] args) {
        int[] nums = new int[] {1,8,6,2,5,4,8,3,7};
        int[] nums1 = new int[] {1,1};
        int[] nums2 = new int[] {4,3,2,1,4};
        int[] nums3 = new int[] {1,2,1};
        System.out.println(maxArea1(nums));
        System.out.println(maxArea1(nums1));
        System.out.println(maxArea1(nums2));
        System.out.println(maxArea1(nums3));
        System.out.println(maxArea(nums));
        System.out.println(maxArea(nums1));
        System.out.println(maxArea(nums2));
        System.out.println(maxArea(nums3));
    }
    // time complexity is O(n^2)
    public static int maxArea(int[] height) {
        int area = 0;
        for(int i = 0; i < height.length; i++) {
            for (int j = i+1; j < height.length; j++) {
                // try to find the maximum area
                area = Math.max(area, (Math.min(height[i], height[j]))*(j-i));
            }
        }
        return area;
    }

    // time complexity is O(n)
    public static int maxArea1(int[] height) {
        int area = 0, start_index = 0, end_index = height.length-1;
        while (start_index <= end_index) {
                area = Math.max(area, (Math.min(height[start_index], height[end_index]))*(end_index-start_index));
                if (height[start_index] <= height[end_index]) {
                    start_index++;
                } else{
                    end_index--;
                }
        }
        return area;
    }
}