Leetcode 255 Verify Preorder Sequence in Binary Search Tree

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up:
Could you do it using only constant space complexity?

Solution 1: Use iterative pre-order traversal.

 public class Solution {  
   public boolean verifyPreorder(int[] preorder) {  
     int n=preorder.length;  
     int i=0, lo=Integer.MIN_VALUE;  
     Deque<Integer> stack=new LinkedList<>();  
     while (i<n) {  
       if (stack.isEmpty() || preorder[i]<stack.peek()) {  
         if (preorder[i]<=lo) return false;  
         stack.push(preorder[i++]);  
       }  
       else if (preorder[i]==stack.peek()) return false;  
       else lo=stack.pop();  
     }  
     return true;  
   }  
 }  

Leetcode 232 Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Solution 1: use 2 stacks, push to stack 1 and pop from stack 2, when stack 2 is empty, move all elements from stack 1 to stack 2. It is O(1) solution like re-size array.

 class MyQueue {  
   Deque<Integer> stack1=new LinkedList<>();  
   Deque<Integer> stack2=new LinkedList<>();  
   // Push element x to the back of queue.  
   public void push(int x) {  
     stack1.push(x);  
   }  
   // Removes the element from in front of queue.  
   public void pop() {  
     if (stack2.isEmpty()) {  
       while (!stack1.isEmpty()) stack2.push(stack1.pop());  
     }  
     stack2.pop();  
   }  
   // Get the front element.  
   public int peek() {  
     if (stack2.isEmpty()) {  
       while (!stack1.isEmpty()) stack2.push(stack1.pop());  
     }  
     return stack2.peek();  
   }  
   // Return whether the queue is empty.  
   public boolean empty() {  
     return stack1.isEmpty() && stack2.isEmpty();  
   }  
 }  

Leetcode 227 Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Solution 1: O(n) complexity and O(1) space

 public class Solution {  
   public int calculate(String s) {  
     int n=s.length();  
     int pre=0, curr=1;   
     boolean blank=true; //if s only contains ' '  
     boolean preSign=true, sign=true; //preSign: + or -; sign: * or /  
     for (int i=0; i<n; i++) {  
       if (s.charAt(i)==' ') continue;  
       else if (s.charAt(i)=='*') sign=true;  
       else if (s.charAt(i)=='/') sign=false;  
       else if (s.charAt(i)=='+' || s.charAt(i)=='-') {  
         pre=preSign? pre+curr:pre-curr;  
         preSign=s.charAt(i)=='+';  
         curr=1;  
         sign=true;  
       }  
       else {  
         blank=false;  
         int j=i+1;  
         while (j<n && s.charAt(j)>='0' && s.charAt(j)<='9') j++;  
         curr=sign? curr*Integer.valueOf(s.substring(i,j)):curr/Integer.valueOf(s.substring(i,j));  
         i=j-1;  
       }  
     }  
     if (blank) return 0;  
     return preSign? pre+curr:pre-curr;  
   }  
 }  

Leetcode 225 Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

Solution 1:  O(n) push, others O(1)

 class MyStack {  
   // Push element x onto stack.  
   Deque<Integer> qu=new LinkedList<>();  
   public void push(int x) {  
     qu.offer(x);  
     int n=qu.size();  
     for (int i=0; i<n-1; i++) qu.offer(qu.poll());  
   }  
   // Removes the element on top of the stack.  
   public void pop() {  
     qu.poll();  
   }  
   // Get the top element.  
   public int top() {  
     return qu.peek();  
   }  
   // Return whether the stack is empty.  
   public boolean empty() {  
     return qu.size()==0;  
   }  
 }  

Leetcode 224 Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Solution 1: Use stack

 public class Solution {  
   public int calculate(String s) {  
     Deque<Integer> stack=new LinkedList<>();  
     int n=s.length();  
     int res=0, sign=1;  
     for (int i=0; i<n; i++) {  
       if (s.charAt(i)<='9' && s.charAt(i)>='0') {  
         int j=i, num=0;  
         while (j<n && s.charAt(j)<='9' && s.charAt(j)>='0') num=num*10+s.charAt(j++)-'0';  
         res+=sign*num;  
         i=j-1;  
       }  
       else if (s.charAt(i)=='+') sign=1;  
       else if (s.charAt(i)=='-') sign=-1;  
       else if (s.charAt(i)=='(') {  
         stack.push(res);  
         stack.push(sign);  
         res=0;  
         sign=1;  
       }  
       else if (s.charAt(i)==')') {  
         sign=stack.pop();  
         int pre=stack.pop();  
         res=pre+sign*res;  
       }  
     }  
     return res;  
   }  
 }  

Leetcode 155 Min Stack

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.

Solution 1: Use 2 stack, one stock the regular operation, the other one only store the min value.

 class MinStack {  
   Deque<Integer> stack1=new LinkedList<>();  
   Deque<Integer> stack2=new LinkedList<>();  
   public void push(int x) {  
     stack1.push(x);  
     if (stack2.isEmpty() || x<=stack2.peek()) stack2.push(x);  
     else stack2.push(stack2.peek());  
   }  
   public void pop() {  
     stack2.pop();  
     stack1.pop();  
   }  
   public int top() {  
     return stack1.peek();  
   }  
   public int getMin() {  
     return stack2.peek();  
   }  
 }  

Leetcode 150 Evaluate Reverse Polish Notation

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

Solution 1: Use stack, when it is symbol, get two number out and do the calculation then put it back. if it is number then simply put in stack.

 public class Solution {  
   public int evalRPN(String[] tokens) {  
     Deque<Integer> stack=new LinkedList<>();  
     for (String s: tokens) {  
       if (s.equals("+")) stack.push(stack.pop()+stack.pop());  
       else if (s.equals("-")) {  
         int temp=stack.pop();  
         stack.push(stack.pop()-temp);  
       }  
       else if (s.equals("*")) stack.push(stack.pop()*stack.pop());  
       else if (s.equals("/")) {  
         int temp=stack.pop();  
         stack.push(stack.pop()/temp);  
       }  
       else stack.push(Integer.valueOf(s));  
     }  
     return stack.pop();  
   }  
 }  

Leetcode 94 Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1: recursive

 public class Solution {  
   public List<Integer> inorderTraversal(TreeNode root) {  
     List<Integer> res=new ArrayList<>();  
     travel(root, res);  
     return res;  
   }  
   private void travel(TreeNode x, List<Integer> res){  
     if (x==null) return;  
     travel(x.left,res);  
     res.add(x.val);  
     travel(x.right,res);  
   }  
 }  

Solution 2: iterative

 public class Solution {  
   public List<Integer> inorderTraversal(TreeNode root) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     List<Integer> res=new ArrayList<>();  
     TreeNode x=root;  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         x=stack.pop();  
         res.add(x.val);  
         x=x.right;  
       }  
     }  
     return res;  
   }  
 }  

Leetcode 85 Maximal Rectangle

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

Solution 1: translate this problem to max rectangular in histogram. Calculate max histogram in each row. Details below:

 public class Solution {  
   public int maximalRectangle(char[][] matrix) {  
     int m=matrix.length;  
     if (m==0) return 0;  
     int n=matrix[0].length;  
     int[][] his=new int[m][n];  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         if (i==0) his[i][j]=matrix[i][j]=='0'?0:1;  
         else his[i][j]=matrix[i][j]=='0'?0:1+his[i-1][j];  
       }  
     }  
     int res=0;  
     for (int i=0; i<m; i++) res=Math.max(res,calHis(his[i]));  
     return res;  
   }  
   private int calHis(int[] nums) {  
     int n=nums.length, res=0;  
     Deque<Integer> stack=new LinkedList<>();  
     for (int i=0; i<n; i++) {  
       while (!stack.isEmpty() && nums[stack.peek()]>nums[i]) {  
         int j=stack.pop();  
         int left=stack.isEmpty()?0:stack.peek()+1;  
         res=Math.max(res,nums[j]*(i-left));  
       }  
       stack.push(i);  
     }  
     while (!stack.isEmpty()) {  
       int j=stack.pop();  
       int left=stack.isEmpty()?0:stack.peek()+1;  
       res=Math.max(res,nums[j]*(n-left));  
     }  
     return res;  
   }  
 }  

Leetcode 84 Largest Rectangle in Histogram

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.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Solution 1: The best solution use O(n) time and stack. The idea is for given index i, let us see the max rectangle use height[i] as the height. Then the length should be determined but [left,right], left-1 will lower than heigh[i] and right+1 will be lower than height[i]. With this in mind, then use a stack store increasing element to solve it in O(n), details as below:

 public class Solution {  
   public int largestRectangleArea(int[] height) {  
     int n=height.length, res=0;  
     Deque<Integer> stack=new LinkedList<>();  
     for (int i=0; i<n; i++) {  
       while (!stack.isEmpty() && height[stack.peek()]>height[i]) {  
         int j=stack.pop();  
         int left=stack.isEmpty()?0:stack.peek()+1;  
         res=Math.max(res,height[j]*(i-left));  
       }  
       stack.push(i);  
     }  
     while (!stack.isEmpty()) {  
       int j=stack.pop();  
       int left=stack.isEmpty()?0:stack.peek()+1;  
       res=Math.max(res,height[j]*(n-left));  
     }  
     return res;  
   }  
 }  

Leetcode 71 Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Solution 1: Use stack. One thing to be noticed is that, when use String split function, it may contains blank strings.

 public class Solution {  
   public String simplifyPath(String path) {  
     String[] strs=path.split("/"); //note: may have blank string  
     Deque<String> stack=new LinkedList<>();  
     for (String x:strs) {  
       if (x.equals("..")) {  
         if (!stack.isEmpty()) stack.pop();  
       }  
       else if (x.length()>0 && !x.equals(".")) stack.push(x); //  
     }  
     StringBuilder res=new StringBuilder();  
     while (!stack.isEmpty()) {  
       res.insert(0,stack.pop());  
       res.insert(0,'/');  
     }  
     if (res.length()==0) return "/";  
     return res.toString();  
   }  
 }  

Leetcode 20 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.

Solution 1: Use stack, trick part is to check stack.isEmpty() at the end.

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