Problem: Given an array of heights, find out the max area that can be formed between any two bars.
Solution: The key to solve this problem is to start from the extreme edge. Calculate the current area between two bars and compare it with the max area seen so far. Next step is to move the one side that is comparatively shorter. Meaning if the left bar is short then increment left bar index. If the right bar is short then decrement the right bar index. Do it till left bar index < right bar index.
Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
public class WaterContainer { public static void main(String[] args){ int heights[] = {4,2,6,1,8,1}; System.out.println(calMaxArea(heights)); } public static int calMaxArea(int[] heights){ int maxArea = -1; int left = 0; int right = heights.length - 1; while(left<right){ maxArea = Math.max (maxArea,((right - left - 1) * Math.min(heights[right], heights[left]))); if(heights[left] < heights[right]){ left++; }else{ right--; } } return maxArea; } } |
Complexity: O(n)
As at max, it does one pass. The case could be heights are in descending order or ascending order.
Git url: https://github.com/Niravkumar-Patel/SnippetExampleRepo/blob/master/SnippetExamplePractice/src/hackerrank/WaterContainer.java