Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Naive Way: Let me start from the begin, when I met some bar that is no less than current bar, I am able to determine how much water can trap from current bar to that some bar. Better use a stack to keep track of bars that are smaller than current bar.

Run time is One Pass, O(n). Space is O(n).

 public class Solution {  
   public int trap(int[] A) {  
     Stack<Integer> stack = new Stack<Integer>();  
     int sum = 0;  
     int pre = 0;  
     int i = -1;  
     while(++i < A.length){  
       if(A[i]==0){pre = 0;continue;}  
       while(!stack.isEmpty() && A[i] >= A[stack.peek()]){  
         sum += (A[stack.peek()] - pre) * (i-stack.peek()-1);  
         pre = A[stack.pop()];  
       }  
       if(!stack.isEmpty()){  
         sum += (A[i] - pre) * (i-stack.peek()-1);  
         pre = A[i];  
       }  
       stack.push(i);  
     }  
     return sum;  
   }  
 }  

Improved Way: Is there a way to make the space O(1)? Based on my previous code, the stack is not replaceable. So I cannot make up an O(1) algorithm with the stack.

Consider the bars as a whole, only the left most and right most bars will become boundaries/walls. Anything in between will take the unit place of water. This is a thinking. Let me give it a try.

The following algorithm is the implementation of my idea. Track from both ends to middle, keep increase the boundary bar, while deleting any lower bar in the middle.

 public class Solution {  
   public int trap(int[] A) {  
     int left = 0 , right = A.length-1;  
     int sum = 0;  
     int pre = 0;  
     while(left < right){  
       sum += (Math.min(A[left], A[right])-pre) * (right-left-1);  
       pre = Math.min(A[left],A[right]);  
       if(A[left] > A[right]){   
         int temp = right-1;  
         while(left < temp && A[temp] <= pre){sum-=A[temp];temp--;}  
         if(left < temp) sum -= pre;  
         right = temp;  
       }else{  
         int temp = left+1;  
         while(temp < right && A[temp] <= pre){sum-=A[temp];temp++;}  
         if(temp < right) sum -= pre;  
         left = temp;  
       }  
     }  
     return sum;  
   }  
 }  

There is a much more concise implementation java-10-lines-accepted-code-time-space-there-better-solution

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.


Naive Way:  Use a stack would be straightforward. But it's O(n) space.

 public class Solution {  
   public boolean isValid(String s) {  
     Stack<Integer> stack = new Stack<Integer>();  
     for(int i = 0;i < s.length();i++){  
       if(isLeft(s.charAt(i))) stack.push(i);  
       else if(!stack.isEmpty() && s.charAt(stack.peek())== opposite(s.charAt(i))) stack.pop();  
       else return false;  
     }  
     return stack.isEmpty();  
   }  
   private boolean isLeft(char c){  
     return c=='(' || c=='{' || c =='[';  
   }  
   private char opposite(char c){  
     if(c==')') return '(';  
     if(c=='}') return '{';  
     else return '[';  
   }  
 }  

I know if there were only one type of parentheses, it can be done in O(1). When there are multiple parentheses, some one argue that for the reason of Context Free Grammar, It can not be done in O(1).

Improved Way: It would be better to use a Hashmap to map left parentheses to right parentheses.

 public class Solution {  
   private static final Map<Character, Character> map = new HashMap<Character, Character>(){{  
     put('(',')');  
     put('{','}');  
     put('[',']');  
   }};  
   public boolean isValid(String s) {  
     Stack<Integer> stack = new Stack<Integer>();  
     for(int i = 0;i < s.length();i++){  
       if(map.containsKey(s.charAt(i))) stack.push(i);  
       else if(!stack.isEmpty() && map.get(s.charAt(stack.peek()))==s.charAt(i)) stack.pop();  
       else return false;  
     }  
     return stack.isEmpty();  
   }  
 }