Container With Most Water – Leetcode #11

PROBLEM STATEMENT

This problem is from Leetcode – Container With Most Water. Problem statement i short is as below:

Given an array of line heights, find two lines that form a container holding the most water. Return the maximum area, where area = distance × min height.

SOLUTION

FIRST APPROACH

public int maxArea(int[] height) {

		int maxArea = 0;

		int altitude = 0;
		int width = 0;
		
		// start right from 1 and keep increasing
		for(int right=1; right< height.length; right++) {
			
			// start left from 0 and go towards right
			for(int left=0; left<right; left++) {
				
				altitude = Math.min(height[left] , height[right]);
		    	width = right - left;
		    	maxArea = Math.max(maxArea, altitude*width);
			}
					
		}
				
		return maxArea;
	}

You can checkout the code from Github here – Container With Most Water – First Approach.

PERFORMANCE ANALYSIS

COMPLEXITY

O (N2)

SECOND APPROACH

public int maxArea(int[] height) {
		    
		    int maxArea = 0;
		    int left = 0;
		    int right = height.length-1;
		    int altitude = 0;
		    int width = 0;
		    
		    while(left <= right) {
		    			    	
		    	altitude = Math.min(height[left] , height[right]);
		    	width = right - left;
		    	maxArea = Math.max(maxArea, altitude*width);
		    	
		    	// compare the two heights and move towards bigger
		    	if(height[left] < height[right])
		    		left++;
		    	else
		    		right--;	    	
		    	
		    }
		    	    
		    return maxArea;
	    }

You can checkout the code from Github here – Container With Most Water – Second Approach.

PERFORMANCE ANALYSIS

RUNTIME	5 ms | Beats 76.15 %
MEMORY	57.80 MB | Beats 72.21 %
TIME COMPLEXITY	O (N)
SPACE COMPLEXITY	O (1)