# How to improve this method (Java)

• The idea is keep two pointer, one from left, the other from right. For a given left number, find the first one from right that is no less than it. I try to make it O(n) by using two hashmap keep track of each number I come across.

But there is a problem when left is 2, and right is 200000, I need to put into map 199998 times.

``````public class Solution {
public int maxArea(int[] height) {
Map<Integer, Integer> rightMost = new HashMap<Integer,Integer>();
Map<Integer, Integer> leftMost = new HashMap<Integer, Integer>();
int left = 0, right = height.length-1;
int max = 0;
while(left < right){
while(left < right && leftMost.containsKey(height[left])) left++;
leftMost.put(height[left],left);
if(rightMost.containsKey(height[left])) max = Math.max(max,(right-left)*height[left]);
else{
while(left < right && height[right] < height[left]){
max = Math.max(max,(right-left)*height[right]);
rightMost.put(height[right], right);
right--;
}
for(int i = height[left];i <= height[right];i++)
rightMost.put(i,right);
max = Math.max(max,(right-left)*height[left]);
}
}
return max;
}
}``````

• As your idea "find the first one from right that is no less than it". I write the following code, which cost 382ms

``````public class Solution {
public int maxArea(int[] height) {
int max = 0, i = 0, j = height.length - 1;//i from left, j from right
max=Math.min(height[i],height[j])*(j-i);
while(i<j){
int h=height[j];
if(height[i]<height[j]){
h=height[i]; //h=1
i++;
while(i<j && height[i]<=h) i++;
}else{
j--;
while(i<j && height[j]<=h) j--;
}
h=Math.min(height[i], height[j]);
max=Math.max(h*(j-i), max);
}
return max;
}
}
``````

As a comparation, I post my original two pointer code here, which costs 391ms

``````public class Solution {
public int maxArea(int[] height) {
int max = 0, i = 0, j = height.length - 1;
while (i < j) {
int h = height[j],size;
if (height[i] < height[j]) {
h = height[i];
i++;
} else j--;
size = h * (j - i + 1);
if (size > max) max = size;
}
return max;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.