# Container with Most Water - Leet Code Solution

September 13, 2019

## Problem Statement

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 may not slant the container and n is at least 2.

## Algorithm-1 (Brute force)

``````public int maxArea(int[] height) {
int max = 0;
int l = height.length;

for (int i=0; i<l; i++) {
for (int j=i+1; j<l; j++) {
int area = (j-i) * Math.min(height[i], height[j]);
if (area > max) {
max = area;
}
}
}

return max;
}``````

## Algorithm-2

Lets think of optimizing this computation. What if we start with max range, and move either left or right. Since, lower height determines the area. And, we can move greedily towards point with high height. And, compare the area.

We can start with left and right pointer, calculate area. Then we can move towards point with higher height. i.e. the side which is having less height, we should move that pointer. Example: If left pointer value is less, move it right. Similarly, if right pointer value is less than right, move it left.

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

while (i < j) {
int area = (j-i) * Math.min(height[i], height[j]);
if (result < area) {
result = area;
}

if (height[i] < height[j]) {
i++;
}
else j--;
}

return result;
}``````

## Similar Posts

System design interview is pretty common these days, specially if you are having…

### Integer to Roman conversion - Leet Code Solution

Problem Statement Roman numerals are represented by seven different symbols: I…

### Add two numbers(reverse order) link list Problem - Leet Code Solution

Problem Statement You are given two non-empty linked lists representing two non…

### First Unique Character in a String - Leet Code Solution

Problem Statement Given a string, find the first non-repeating character in it…

### Quick Sort Algorithm

This algorithm is very useful for large input. And, is quite efficient one. It…

### Young Tableau problem - Cormen

Young Tableau A a X b matrix is Young Tableau if all rows(from left to right…

## Latest Posts

### Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

### How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

### How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

### Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

### Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

### Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…