Find Container with Most Water in Java

Find Container with Most Water.

---

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

Note: You cannot slant the container.

Lets understand what is the input and the expected output.

Algorithm 

---

How much level of water we can get in between two different heights?

Say there is only two heights, 2 and 5, how much water can be collected between this two heights. Water that can be collected between two height would be Lower value between two heights and rest water would overflow from side. so in this case max water level would be 2.

As we want to calculate the area, we can start by comparing first and last height, whichever is less among two height minHeight = (leftHeight, rightHeight) that is the max level of water we can get at height less among both of them.

Distance between the two heights = rightIndex - leftIndex;

MaxArea = MinHeight * Distance between the two heights.

Increment/Decrement the pointer whose height is less as max area at that height we just calculated and continue until all lower heights are examined.

Example:
Step 1

 Step 2:

Step 3:

Step 4

Step 5

Step 6

Step 7

Step 8

Max area we got in all the above steps is 49. so container that can hold maximum water is 49.

Find Container with Most Water in Java

---

package com.javabypatel.misc;

public class FindContainerWithMostWater {
    public static void main(String[] args) {
        //int arr[] = new int[] {1,8,6,2,5,4,8,3,7};
        //int arr[] = new int[] {1,5,4,3};
        //int arr[] = new int[] {3, 1, 2, 4, 5};
        int arr[] = new int[] {3, 0};

        System.out.println(findMaxArea(arr));
    }

    private static int findMaxArea (int arr[]) {
        int left = 0;
        int right = arr.length-1;
        int maxArea = 0;

        while (left < right) {
            int min = Math.min(arr[left], arr[right]);
            int distance = right - left;
            int area = min * distance;

            maxArea = area > maxArea ? area : maxArea;
            if(arr[left] < arr[right]) {
                left ++;
            } else {
                right --;
            }
        }
        return maxArea;
    }
}

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.