Showing posts with label Stack. Show all posts
Showing posts with label Stack. Show all posts

Wednesday, January 21, 2015

Evaluate Reverse Polish Notation (LeetCode Stack)

Question: Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Idea: Use stack. Scan the input string array from left to right. If the current position is a number, push it to the stack, otherwise pop two numbers and apply the operator and push the result back to the stack. The last element in the stack is the final result.

Time: O(n) Space: O(n)

Code:
 public class Solution {  
   public int evalRPN(String[] tokens) {  
     Stack<Integer> stack=new Stack<Integer>();  
     for(int i=0;i<tokens.length;i++)  
     {  
       String s=tokens[i];  
       if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))  
       {  
         int second=stack.pop();  
         int first=stack.pop();  
         int result=0;  
         if(s.equals("+"))  
           result=first+second;  
         if(s.equals("-"))  
           result=first-second;  
         if(s.equals("*"))  
           result=first*second;  
         if(s.equals("/"))  
           result=first/second;  
         stack.push(result);  
       }  
       else  
         stack.push(Integer.parseInt(s));  
     }  
     return stack.pop();  
   }  
 }  

Tuesday, January 13, 2015

Min Stack (LeetCode Data Structure)

Question: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Idea: Use two stacks. One stack (valStack) is a normal stack to store the values. The other stack (minStack) only pushes the minimum values until now and only pops if the popped value from valStack equals the top of the minStack.
For example: input 5, 3,9, 1, 1, 2
Push:
valStack:   5,  3,   9,            1, 1, 2
minStack:  5,  3,  not push, 1, 1, not push
Pop:
valStack:            2,  1,  1,  9,     3,  5
minStack:not pop,   1,  1, not,   3,  5
So we can see the minStack pushes only if the new input is smaller than its top and only pops if the value popped from the valStack equals the top of the minStack.

Time: O(1) Space: O(n) (we used an extra stack)

Code:
 class MinStack {  
   Stack<Integer> minStack=new Stack<Integer>();  
   Stack<Integer> valStack=new Stack<Integer>();  
   public void push(int x) {  
     if(minStack.isEmpty()||x<=minStack.peek())  
       minStack.push(x);  
     valStack.push(x);  
   }  
   public void pop() {  
     if(valStack.isEmpty())  
       return;  
     int val=valStack.pop();  
     if(val==minStack.peek())  
       minStack.pop();  
   }  
   public int top() {  
     if(valStack.isEmpty())  
       return -1;  
     return valStack.peek();  
   }  
   public int getMin() {  
     if(minStack.isEmpty())  
       return Integer.MAX_VALUE;  
     return minStack.peek();  
   }  
 }  

Monday, January 12, 2015

Valid Parentheses (LeetCode String)

Question: 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.

Idea: Use a stack to check the pairs.

Time: O(n) Space: O(n)

Code:
 public class Solution {  
   public boolean isValid(String s) {  
     Stack<Character> stack=new Stack<Character>();  
     for(int i=0;i<s.length();i++)  
     {  
       char c=s.charAt(i);  
       if(c=='('||c=='{'||c=='[')  
         stack.push(c);  
       else   
       {  
         if(stack.isEmpty())  
           return false;  
         char right=stack.pop();  
         if(c==')'&&right!='(')  
           return false;  
         if(c=='}'&&right!='{')  
           return false;  
         if(c==']'&&right!='[')  
           return false;  
       }  
     }  
     if(stack.isEmpty())  
       return true;  
     else  
       return false;  
   }  
 }  

Sunday, January 11, 2015

Simplify Path (LeetCode String)

Question: Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Idea: First split the input string by "/+", then the dirs are stored in a string array. Scan the array from left to right and add the dirs to a arraylist, if ".." (goes up one level) shows up, delete the last dir to go up one level.  At the end, remove the last "/" is the intended output is not "/".

Time: O(n) Space: O(n)

Code:
 public class Solution {  
   public String simplifyPath(String path) {  
     StringBuilder result=new StringBuilder("/");  
     String[] cols=path.split("/+");  
     ArrayList<String> dirs=new ArrayList<String>();  
     for(String s:cols)  
     {  
       if(s.equals(".."))  
       {  
         if(dirs.isEmpty()==false)  
           dirs.remove(dirs.size()-1);  
       }  
       else if(!s.equals(".")&&!s.equals(""))  
       {  
         dirs.add(s);  
       }  
     }  
     for(String dir:dirs)  
     {  
       result.append(dir);  
       result.append("/");  
     }  
     if(result.length()>1)  
       result.deleteCharAt(result.length()-1);  
     return result.toString();  
   }  
 }  

Saturday, January 10, 2015

Longest Valid Parentheses (LeetCode String)

Question: Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Idea: Use a stack to validate the parentheses. Use a pointer i to scan the string from left to right,

  • when a '(' is visited: push i to the stack; 
  • when a ')' is visited and the top of the stack is '(': first pop the top of the stack, then calculate the length of the parentheses following these rules:

       1) if the stack is empty, then from 0 to i is a valid parentheses, the length is i+1;
       2) if the stack is not empty, then from the current top of the stack to the current i is a valid parentheses, the length is i-stack.peek().

  • when a ')' is visited, but the top of the stack is not '(': this means the former parentheses in the stack is not valid. push i to the stack to terminate the former parentheses cached, in other words, to make the position of ')' as a new start point for following validations.
Time: O(n) Space: O(1)

Code:
 public class Solution {  
   public int longestValidParentheses(String s) {  
     if(s.length()<=1)  
       return 0;  
     Stack<Integer> stack=new Stack<Integer>();  
     int result=0;  
     for(int i=0;i<s.length();i++)  
     {  
       if(s.charAt(i)=='(')  
         stack.push(i);  
       else  
       {  
         if(!stack.isEmpty()&&s.charAt(stack.peek())=='(')  
         {  
           stack.pop();  
           int curLength=(stack.isEmpty())?i+1:i-stack.peek();  
           result=Math.max(result,curLength);  
         }  
         else  
           stack.push(i);  
       }  
     }  
     return result;  
   }  
 }  

Tuesday, December 30, 2014

Maximal Rectangle (LeetCode Array)

Question:  Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

Idea: I made use of the "maximum area size in histogram". For each block in the matrix, calculate its height (consecutive 1's above it). The apply "maximum area size in histogram" on each row and update the maximal rectangle size.

Time: O(n^2) Space: O(n^2)

Code:
 public class Solution {  
   public int maximalRectangle(char[][] matrix) {  
     if(matrix.length==0||matrix[0].length==0)  
       return 0;  
     int[][] height=new int[matrix.length][matrix[0].length];  
     for(int i=0;i<matrix.length;i++)  
     {  
       for(int j=0;j<matrix[0].length;j++)  
       {  
         if(matrix[i][j]=='0')  
         {  
           height[i][j]=0;  
         }  
         else  
         {  
           height[i][j]=(i==0)?1:height[i-1][j]+1;  
         }  
       }  
     }  
     int result=0;  
     for(int i=0;i<matrix.length;i++)  
       result=Math.max(result,maxAreaHist(height[i]));  
     return result;  
   }  
   public int maxAreaHist(int[] height)  
   {  
     if(height==null||height.length==0)  
       return 0;  
     Stack<Integer> indexStack=new Stack<Integer>();  
     int maxArea=0;  
     for(int i=0;i<=height.length;i++)  
     {  
       int current=(i==height.length)?-1:height[i];  
       while(!indexStack.isEmpty()&&height[indexStack.peek()]>=current)  
       {  
         int h=height[indexStack.pop()];  
         int w=indexStack.isEmpty()?i:i-1-indexStack.peek();  
         maxArea=Math.max(maxArea,h*w);  
       }  
       indexStack.push(i);  
     }  
     return maxArea;  
   }  
 }  

Largest Rectangle in Histogram (LeetCode Array)

Question:  Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. (full problem with examples please refer to Leetcode website).

Idea: Stack. Scan the array from left to right. When the integers in the array are monotonically increasing, the minimum value of the height does not change, but the width increases. In this case, there is no need to update the result unless reaching the end of the array. 
However, the integers in the array may not increase monotonically. Whenever a decrease happens (e.g. at position "k"), the minimum height may change. Now we compute the max area before k and pop the values bigger than height[k] to make height[k] the new minimum height. Then repeat doing that until the end of the array. Since we only update result when a decrease happens, to simplify the implementation, we can consider the right boundary of the array is a new minimum (e.g. -1), to avoid to write extra code on handling the boundary cases.

Time: O(n) Space: O(1)

Code:
 public class Solution {  
   public int largestRectangleArea(int[] height) {  
     if(height==null||height.length==0)  
       return 0;  
     Stack<Integer> indexStack=new Stack<Integer>();  
     int result=0;  
     for(int i=0;i<=height.length;i++)  
     {  
       int cur=(i==height.length)?-1:height[i];  
       while(!indexStack.isEmpty()&&height[indexStack.peek()]>=cur)  
       {  
         int h=height[indexStack.pop()];  
         int w=indexStack.isEmpty()?i:i-1-indexStack.peek();  
         result=Math.max(result,h*w);  
       }  
       indexStack.push(i);  
     }  
     return result;  
   }  
 }