Valid Parentheses

Problem

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"

Output: true

Example 2:

Input: "()[]{}"

Output: true

Example 3:

Input: "(]"

Output: false

Example 4:

Input: "([)]"

Output: false

Example 5:

Input: "{[]}"

Output: true

Solution

We can use a stack to help matching same type parentheses. When we saw an open brackets, we push that into stack. When we saw a close brackets, we pop an element from the stack. If the top element on the stack matches the type, we continue. If the stack is empty or the element type is not matching, we detected an invalid string.

import java.util.*;

class Solution {

  

  public static void main(String[] args) {

    String str = "([)]";

    System.out.println(valid(str));

  }

  

  private static boolean valid(String str) {

    Stack<Character> stack = new Stack<>();

    for(char c : str.toCharArray()) {

      if(c == '{' || c == '[' || c == '(') {

        stack.push(c); //(

      } else if(c =='}') {

        if(stack.isEmpty()) 

          return false;

        char tmp = stack.pop();

        if(tmp != '{')

          return false;

      } else if(c ==']') {

        if(stack.isEmpty()) 

          return false;

        char tmp = stack.pop();

        if(tmp != '[')

          return false;

      } else if(c ==')') {

        if(stack.isEmpty()) 

          return false;

        char tmp = stack.pop();

        if(tmp != '(')

          return false;

      } else {

        throw new RuntimeException("illegal character");

      }

    }

    if(!stack.isEmpty())

      return false;

    return true;

  }

}

The time complexity is O(N) and the space complexity is O(N)

Trapping Rain Water

Problem:

Given a non-negative integer array. Each element represents 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 array [1,4,0,1,0,3,1,2,0,1], the elevation map represented by it can trap 10 units of rain water.

Solution:

The brutal force solution is find the water above each of the bars. For a given bar, we can find the max bar height on the left lBound and the max bar height on the right rBound, then the amount of water above the current bar is the min(lBound, rBound) - currentHeight. For each bar, we can search the other n -1 bars to find the lBound and rBound, the total time complexity is O(N^2) and space complexity is O(1).

An improvement on the brutal force is to trade space for time. At index i, if we know the max bar height on the left is lMax[i], at index i+1, we don't have to search again, we just have to use formula lmax[i] = Math.max(lMax[i-1], height[i]) 

where i from 1 to height.length - 1. 

We can say the same to the rMax, 

rMax[i] = Math.max(rMax[i], height[i+1]) 

where i from arr.length - 2 to 0

That way, we get O(N) time complexity, but space complexity is O(N) as well.

With similar approach used in Largest Rectangle in Histogram, we can use a stack to follow the height values' changing trend, once we find the turning point, we take actions accordingly. In this case, we use the stack to store the decreasing sequence of the height. Once the current bar's height increase, we know we just passed a valley. The 2 bars at the stack top and the current bar formed a valley, the water holding capacity of this valley is (Math.min(height[stack(top-1)], height[current])) - height[stack(top)]) * (current - stack(top)).

import java.util.*;
public class Solution {
  public static int trap(int[] arr) {
    int water = 0;
    Stack<Integer> lMax = new Stack<>();
    lMax.push(0); //1 5 6
    for(int i = 1; i < arr.length; i++) { //5
      while(!lMax.isEmpty() && arr[lMax.peek()] <= arr[i]) {
        int index = lMax.pop();
        if(lMax.isEmpty())
          break;
        water += (Math.min(arr[lMax.peek()], arr[i]) - arr[index]) * (i - lMax.peek() - 1);
      }
      lMax.push(i);
    }
    return water;
  }
  public static void main(String...args) {
    int[] arr = new int[]{1,4,0,1,0,3,1,2,0,1};
    System.out.println(trap(arr));
  }
}

The time complexity is O(N) and the space complexity is O(N) due to the stack.

There is a O(N) time complexity and O(1) space complexity solution.
The intuition is: we can use two pointers to mark a water container with left and right edges. The left pointer start at index 0 and the right pointer start at the last index. The two bars pointing by the 2 pointers formed a water container with capacity bottleneck at the shorter one. The 2 pointers move inward searching for the longer bars as the container's edges. If a bar is shorter than the bottleneck, the bar can hold water. If a bar is longer than the shorter container edge, the pointer moves to it thus form a taller but narrower container.

public class Solution {
  public static int trap(int[] arr) {
    int water = 0;
    int lBound = arr[0];
    int rBound = arr[arr.length - 1];
    int i = 0;
    int j = arr.length - 1;
    while(i < j) {
      if(lBound < rBound) {
        while(arr[i] <= lBound) {
          water += lBound - arr[i];
          i++;
        }
        lBound = arr[i];
      } else {
        while(arr[j] <= rBound) {
          water += rBound - arr[j];
          j--;
        }
        rBound = arr[j];
      }
    }
    return water;
  }
  public static void main(String...args) {
    int[] arr = new int[]{1,4,0,1,0,3,1,2,0,1};
    System.out.println(trap(arr));
  }
}

See also:

Containers with most water

Largest Rectangle in Histogram

Largest Rectangle in Histogram

Problem:

Given an n sized array of non-negative integers. The array represents a histogram made of width 1 columns. Each array element represent a column with width 1 and height equal to the array element value.

Write a function take the array as input, returns the largest rectangle in the histogram.

For Example:

Given array [2,1,5,6,2,3], the largest rectangle in the histogram is made by the column at index 2 and 3, the rectangular made by height 5 column and height 6 column has size 10, so the output is 10.

Solution:

The brutal force solution is to have a 3 layers of for loops. For each starting index i, we exam all the ending index at the right. For a pair of starting and ending index, we loop all the elements to find the minimum then calculate the area. The time complexity is O(N^3).

A better solution is to use divide and conquer. Once we found the index of the minimum height bar in an array, the solution came from 3 cases:

1. the largest rectangle in the histogram is (end - start) * height(minIndex)
2. the largest rectangle in the histogram is on the left half.
3. the largest rectangle in the histogram is on the right half.

In order to find the largest rectangle in the left half and right half, we can find it recursively.

If the height array is random, each left and right half divide most likely happen in the middle, the time complexity is O(NlogN).

If the height array is sorted, each left and right half happens at the edge, the performance degrades to O(N^2).

The best solution is to use a stack to help the calculation. The intuition is, when we scan the height values from left to right, if the height is increasing, we know, for sure, no matter where the the largest rectangle is, read more will only make it larger if not the same. Once the height starts to decrease, we know, for sure, the tallest bar we saw so far won't form a bigger rectangle, so we can register its value as the potential largest rectangle. Once processed the tallest bar, we then look at the second largest bar we saw so far. If the current bar is taller than the second tallest bar, then the sequence is still increasing, we want to read more to see if we can make the rectangle formed by the second tallest bar larger, otherwise, we know for sure the rectangle formed by the second tallest bar won't increase anymore, so we can register the area as the potential largest rectangle. Then we look at the third largest bar. 

The algorithm is, as long as the height is increasing, we keep push the index of the height array into a stack. Once the height is decreasing, we pop out all the out of order elements in the stack in order to restore the increasing sequence in the stack. While we pop the out of order elements in the stack, we register the area of the potential largest rectangle. After we added all the height index into the stack and the stack is still not empty, we then know how to calculate the potential largest rectangles.

import java.util.*;
class Solution {
 
  public static void main(String...args) {
    int[] histo = new int[] {2,1,5,6,2,3};
    System.out.println(maxArea(histo));
  }
 
  public static int maxArea(int[] histo) {
    int max = -1;
    //store the index of height increasing sequences
    Stack<Integer> incrSeq = new Stack<>();
    incrSeq.push(-1);
    for(int i = 0; i < histo.length; i++) {
      if(incrSeq.peek() == -1 || histo[incrSeq.peek()] <= histo[i]) {
        incrSeq.push(i);
      } else {
        while(incrSeq.peek() != -1 && histo[incrSeq.peek()] >  histo[i]) { 
          //calculate the hill area bounded by the two descending indexes at left (incrSeq(top - 1)) and right (i)
          max = Math.max(max, histo[incrSeq.pop()] * (i - incrSeq.peek() - 1));
        }
        //now the height increasing sequence is restored, keep pushing
        incrSeq.push(i);
      }
    }
   
    int end = incrSeq.peek();
    while(incrSeq.peek() != -1) {
      int index = incrSeq.pop();
      //clif edge area bounded by the descending indexe at left (incrSeq(top - 1)) and current index (incrSeq(top - 1))
      max = Math.max(max, histo[index] * (end - index + 1));
    }
   
    return max;
  }
}

The time complexity is O(N) and the space complexity is also O(N).

Same Tree

Problem:

Given two binary trees, check if they are the same.

Two binary trees are considered the same if they have the same structure and same node values.

For example, the following trees are the same

    1         1

   / \       / \

  2   3     2   3

but the following trees are not the same

    1         1

   / \       / \

  2   4     2   3

the following trees are not the same too

    1         1

   /           \

  2             2

follow up questions: the recursive solution is trivial, can we solve it with iteration?

Solution:

One of the recursive solution is to do a preorder traversal of the trees. If the current nodes are the same, then we recursively exam the left children and right children.

To convert the recursive solution to iterative solution. We need to use a stack or queue to replace the internal caller stack. We can choose to use a queue to store the nodes, thus make a level order traversal of the tree, or we can use a stack to store the nodes, and do a in-order or pre-order traversal. 

import java.util.*;
class Solution {
 
  public static void main(String...args) {
    Node tree1 = new Node(1, new Node(2), new Node(3));
    Node tree2 = new Node(1, new Node(2), new Node(3));
    System.out.println(isSame(tree1, tree2)); 
    System.out.println(isSame2(tree1, tree2)); 
  }
 
  private static boolean isSame(Node root1, Node root2) {
    if(root1 == null && root2 == null)
      return true;
    if(root1 == null || root2 == null)
      return false;
    if(root1.val != root2.val)
      return false;
    return isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
  }
 
  private static boolean isSame2(Node root1, Node root2) {
    if(root1 == null && root2 == null)
      return true;
    if(root1 == null || root2 == null)
      return false;
    if(root1.val != root2.val)
      return false;
   
    Queue<Node> queue1 = new ArrayDeque<>();
    Queue<Node> queue2 = new ArrayDeque<>();
    queue1.offer(root1);
    queue2.offer(root2);
    while(!queue1.isEmpty()) {
      root1 = queue1.poll();
      root2 = queue2.poll();
      if(!check(root1.left, root2.left)) return false;
      if(root1.left != null) {
        queue1.offer(root1.left);
        queue2.offer(root2.left);
      }
      if(!check(root1.right, root2.right)) return false;
      if(root1.right != null) {
        queue1.offer(root1.right);
        queue2.offer(root2.right);
      }
    }
    return true;
  }
 
  private static boolean check(Node root1, Node root2) {
    if(root1 == null && root2 == null)
      return true;
    if(root1 == null || root2 == null)
      return false;
    if(root1.val != root2.val)
      return false;
    return true;
  }
  public static class Node {
    private int val;
    private Node left;
    private Node right;
    public Node(int val) {
      this.val = val;
    }
    public Node(int val, Node left, Node right) {
      this.left = left;
      this.right = right;
      this.val = val;
    }
  }
}

Both recursive and iterative solution has time complexity O(N) and space complexity O(H).

Generate Parentheses

Problem:

Given a positive integer n, generate combination of all possible well-formed parentheses with n pairs.

For example, when n = 3, the result is:

[
  "()(())",
  "((()))",
  "(())()",
  "(()())",
  "()()()"
]

Solution:

We need to enumerate all the possible combinations, that suggests recursive and backtracking. For backtracking, we need a few elements for the recursive call: an accumulator for the target string, a tracker to tell when to register result or return. Here is one of many possible designs. We can use a string to store the result, use an integer for open parentheses remains, another integer for close parentheses remains. The return condition is when we consumed both open and close parentheses (valid), the remaining open parentheses are more than close parentheses (invalid). The recursive logic is: if we have open parentheses, try it. After try open parentheses, try close parentheses instead.

class Solution {
  public static void main(String...args) {
    int n = 3;
    backtrack(3, 3, "");
  }
  public static void backtrack(int open, int close, String result) {
    if(open == 0 && close == 0) {
      System.out.println(result);
      return;
    }
    if(close < open) {
      return;
    }
    if(open > 0) {
      backtrack(open -  1, close, result + "(");
    }
    backtrack(open, close - 1, result + ")");
  }
  /*
  backtrack(3, 3, "");
  3, 3, ""
     2, 3, "("
        1, 3, "(("
           0, 3, "((("
              0, 2, "((()"
                 0, 1, "((())"
                    0 0 "((()))" return
           1, 2, "(()"
              0, 2, "(()("
                 0, 1, "(()()"
                    0. 0, "(()())" return
              1, 1, "(())"
                 0, 1, "(())("
                 0, 0, "(())()"  return
              1, 0, "(()))"  invalid 
        2, 2, "()"
           1, 2, "()("
              0, 2, "()(("
                 0, 1, "()(()"
                    0, 0, "()(())" return
              1, 1, "()()"
                 0, 1, "()()("
                    0, 0, "()()()" return
                 1, 0, "()())" invalid
           2, 1, "())" invalid 
     3, 2, ")" invalid         
  */
}

Time complexity O(4^n/sqrt(n)). Space complexity O(4^n/sqrt(n)). According to n-th Catalan number.

Binary Tree Postorder traversal

Problem:

Binary Tree Postorder Traversal

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

For Example:

Given:

   1

    \

     2

    /  \

   3    4

Output: [3,4,2,1]

Follow up: are you able to do it iteratively?

Solution:

Postorder traversal goes left to right, bottom to top. However when we iterate the elements, we have to go from top to bottom. The top-down and left-right iteration is close to postorder traversal, we just have to reverse the top-down to down-top. We can use a stack or LinkedList to reverse the order.

import java.util.*;
class Solution {
  public static void main(String...args) {
    Node root = new Node(1,null,
                    new Node(2, new Node(3, null, null), new Node(4, null, null))
                        );
    postOrder(root);
    System.out.println();
    postOrderI(root);
    System.out.println();
  }

  public static void postOrder(Node root) {
    if(root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.value + " ");
  }

  public static void postOrderI(Node root) {
    LinkedList<Integer> store = new LinkedList<>();
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()) {
      root = stack.pop();
      store.addFirst(root.value);
      if(root.left != null)
        stack.push(root.left);
      if(root.right != null)
        stack.push(root.right);
    }
    for(Integer i : store) {
      System.out.print(i + " ");
    }
  }

  private static class Node {
    int value;
    Node left;
    Node right;
    public Node(int value, Node left, Node right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
  }
}

Time complexity O(N), space complexity O(N).

Binary Tree Postorder Traversal

The post-order iteratively solution with only one stack is a little bit harder than the inorder/preorder solution. We still follow the same spirit: before processing a node,  we first travel to the left-most node, while remembering the path, so that we can later back track. We pop out the nodes and trace back. This way, when a node is popped out, we know for sure the left side branch has been done. 

For in-order, pre-order and post-order, The current node needs to fulfill two purposes, the first, reaching to the right branch, the second, process the node itself. 

Fortunately, in-order traversal can fulfill the two purposes at the same time -- we pop out a node from stack, process it, then get the right child, never need the current node later. For pre-order, fulfill the two purpose is easy too. We process the current node before they are pushing to the stack, when we pop the current node out of the stack, we get the right child, never need the current node later.

The code for in-order and pre-order is almost identical. The only difference is: we either process a node before they are pushing on stack (pre-order) or after they are popping out of the stack (in-order). 

We do left branch -> current -> right branch.

For post-order, fulfill the two purposes is trickier. The two purposes are fulfilled at different times. We need to access the current node twice. At first visit, we use it to reach the right branch, then we process the right branch, later we pop it out from the stack to process it. The current node has to remain in the stack for a while after we use it to reach the right child.

There are techniques that can handle this trickier situation. One technique, for example, is to pop out current node, get the right child, then push it back to stack if there is a right child to process. When we done processing a node, we can tell if the processed node is the right child of the stack top node, in order to figure out if we have visited the stack top node before. 

Another technique, for example, is to push the current node into the stack twice, COPYA for processing it, COPYB for reaching the right branch.

import java.util.*;

class Solution {

public static void main(String...args) {

Node root = new Node(1, new Node(5, new Node(9, null, null), null),

new Node(2, new Node(3, null, null), new Node(4, null, new Node(7, null, null)))

);

postOrder(root);

System.out.println("recursive solution");

postOrderK(root);

System.out.println("iterate solution, conditionally push current node back to stack");

postOrderI(root);

System.out.println("iterate solution, push current node twice to stack");

postOrderL(root);

System.out.println("iterate solution, with the aid of another stack");

}

public static void postOrder(Node root) {

if(root == null) return;

postOrder(root.left);

postOrder(root.right);

System.out.print(root.value + " ");

}

public static void postOrderK(Node root) {

Stack<Node> stack = new Stack<>();

while(root != null) {

stack.push(root);

root = root.left;

}

Node lastNode = null;

while(!stack.isEmpty()) {

root = stack.pop();

if(root.right == lastNode) { //right child has been done?

System.out.print(root.value + " "); //yes, now time to process current node.

lastNode = root; //remember this for next node

continue;

}

//no, right child has not been procssed, time to process the right child node

Node t = root.right;

if(t!=null) { //has right child?

stack.push(root); //yes, have to process right child first

while(t != null) {

stack.push(t);

t = t.left;

}

} else {

System.out.print(root.value + " "); //no right child, time to process current node.

lastNode = root; //remember this for next node

}

}

}

public static void postOrderI(Node root) {

Stack<Node> stack = new Stack<>();

while(true) {

while(root != null) { //null means no right child or current node proessed

stack.push(root); //COPYA, use this to process current node

stack.push(root); //COPYB, use this to check the right child of the current node

root = root.left; //travel and push nodes till reaching the left-most node (same spirit as inorder and preorder traversal).

}

if(stack.isEmpty()) return; //just processed the root

root = stack.pop(); //if we pop this node out, that means the left side branch has been processed.

//time to process right branch and the current node

if(!stack.isEmpty() && root == stack.peek()) { //have we checked the right child already? Since we are handling COPYB, so not yet

root = root.right; //before process the current node, process right branch first (right child could be null)

} else { //have we checked the right child already? Since we are handling COPYA, so yes

System.out.print(root.value + " "); //because both left and right children are done, we can now process current node

root = null; //mark current node processed

}

}

}

public static void postOrderL(Node root) {

Stack<Node> store = new Stack<>();

Stack<Node> stack = new Stack<>();

stack.push(root);

while(!stack.isEmpty()) {

root = stack.pop();

store.push(root);

if(root.left != null)

stack.push(root.left);

if(root.right != null)

stack.push(root.right);

}

while(!store.isEmpty()) {

System.out.print(store.pop().value + " ");

}

}

private static class Node {

int value;

Node left;

Node right;

public Node(int value, Node left, Node right) {

this.value = value;

this.left = left;

this.right = right;

}

}

}

Time complexity O(N), space complexity O(N).

see also: Binary Tree Inorder Traversal

Binary Search Tree Iterator

Problem:

Binary Search Tree Iterator

Write a binary search tree iterator that iterates from the smallest element to the biggest element. 

For example:

Given bst:

     5

   /   \

  2     8

 / \   / \

1   3 6   9

MyIterator it = new MyIterator(root);

while(it.hasNext()) {

  System.out.print(it.next() + " ");

}

should print 1 2 3 5 6 8 9

The next() and hasNext() should have the amortized (average) time complexity O(1) and uses O(H) memory, where H is the height of the tree.

Solution:

convert the BST into an ArrayList then return the ArrayList's iterator won't satisfy the time complexity. We need to iterate in place. Slightly modifying the solution for another problem: inorder traversal bst iteratively, will achieve the goal with amortized O(1) time complexity and O(H) space complexity.

class Solution {
  public static void main(String...args) {
    Node root = new Node(5, new Node(2, new Node(1, null, null), new Node(3, null, null)),
                        new Node(8, new Node(6, null, null), new Node(9, null, null)));
    MyIterator it = new MyIterator(root);
    while(it.hasNext()) {
      System.out.print(it.next()+ " ");
    }
  }

  private static class MyIterator implements Iterator<Integer> {
    private Stack<Node> stack;
    public MyIterator(Node root) {
      this.stack = new Stack<>();
      while(root != null) {
        stack.push(root);
        root = root.left;
      }
    }
    public boolean hasNext() {
      return !stack.isEmpty();
    }
    public Integer next() {
      Node t = stack.pop();
      Node result = t;
      t = t.right;
      while(t != null) {
        stack.push(t);
        t = t.left;
      }
      return result.value;
    }
  }
  private static class Node {
    int value;
    Node left;
    Node right;
    public Node(int value, Node left, Node right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
  }
}

Time complexity O(1), space complexity O(H).

Reduce string to smallest lexicographical order

Problem

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: "bcabc"

Output: "abc"

Example 2:

Input: "cbacdcbc"

Output: "acdb"

Solution

The lexicographical order comparison of 2 strings start at index 0, from left to right, compare the characters at the same position, stop at the first position the characters are different.

For example, azzzzzzzz is smaller than baa, because the character a index 0 is different, 'a' is smaller than 'b', the rest of the characters don't matter.

For another examle, aabzzzzz is smaller than aacaa, because the characters at index 0 and 1 are the same, they differ at index 2, and 'b' is smaller than 'c', the rest of the characters don't matter. 

If we scan the character from left to right and decide which one to save and which one to remove. 

For example:

bcabc

we read in b, it ok to keep it, we read in c, bc also makes sense. Now we read in bca, the string doesn't make sense anymore. Keep bc will increase the  lexicographical order, since bca will be larger than a, we should remove bc. Remove them is ok, we won't violate the criteria that each character has to be in the final string, there are another b and c later. Finally we add the rest of bc, abc is the final result, we satisfied the criteria that the lexicographical order is smallest, and we have all the characters.

For another example:

mnzbamnb

we read in mnz, the string makes sense, so we keep them. Now we read in b, the string mnzb doesn't make sense anymore, mnzb is lexicographical larger than b, we should remove mnz. Removing mn is ok, since there are other m and n later. However, remove z is not ok, since z is unique. If we have to keep z, we must keep mn as well because mnz is lexicographical smaller than z. As a result, the unique character z saved all the characters from removing by later characters. We have mnz in the final string, the problem changes to decide what characters in bamnb will be in the final string. mnzba will reduce to mnza, mnzam will be reduced to mnza, because adding a duplicate m increase lexicographical order. mnzan will be reduced to mnza, then we add the b, which is the last appearance of b, therefore unique when we meet it. So the final string is mnzab.

With some observations, we find out that only two kinds of characters left in the final string.

1. global minimal character. Any character comes before this character will increase the lexicographical order, therefore, should be removed. Unless it is unique.
2. unique character. Unique character can not be removed no matter how big it is. As a result, a unique character shields all characters before it from getting removed from the final string. The string before it becomes permanent, we only have to consider the characters after it. A duplicate character becomes unique when we reach the last one of its appearance.

With a stack, we can simulate the above process. From left to right of the string, we push the characters into the stack, before a character enter the stack, it needs to pop out the characters larger than it until the stack is empty or a unique character is met. The character then only enters the stack if it is a unique character so far. Finally, we we reach the end of the string, whatever left in the stack is the final result.

import java.util.*;
public class LexicoGraphicalOrder {
  public static String dedupe(String str) {
    Set<Character> onStack = new HashSet<>();
    Map<Character, Integer> lastIndex = new HashMap<>();
    Stack<Character> stack = new Stack<>();
    int N = str.length(); //8
    //cbacdcbc
    //       .
    //stack  acdb
    //onStack acdb
    for(int i = 0; i < N; i++) {  //c 7, b 6, a 2, d 4
      lastIndex.put(str.charAt(i), i);
    }
    for(int i = 0; i < N; i++) {//7
      char currChar = str.charAt(i);  //c
      if(!onStack.contains(currChar)) {
        while(!stack.isEmpty() && stack.peek() - currChar > 0 && lastIndex.get(stack.peek()) > i) {
          Character lastSeen = stack.peek();  //b
          if(lastSeen - currChar > 0 && lastIndex.get(lastSeen) > i) {
            stack.pop();
            onStack.remove(lastSeen);
          }
        }
        stack.push(currChar);
        onStack.add(currChar);
      }
    }
    StringBuilder sb = new StringBuilder();
    for(char c : stack) {
      sb.append(c);
    }
    return sb.toString();
  }

  public static void main(String...args) {
    System.out.println(dedupe("cbacdcbc"));
    System.out.println(dedupe("mnzamn"));
    System.out.println(dedupe("mnzmnedcbamnnnnnmmmm"));
  }
}

The time complexity is O(N). It is not O(N^2) because no matter how large the string is, the queue size won't be larger than 'z'-'a' which is a constant. For the same reason, the space complexity is also O(N).

Binary Tree Upside Down

Problem

Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

Example:

Input: [1,2,3,4,5]

    1

   / \

  2   3

 / \

4   5

Output: return the root of the binary tree [4,5,2,#,#,3,1]

   4

  / \

 5   2

    / \

   3   1  

Solution

We can walk left until no left. During this journey, we store the node in collections for later retrieval. 

One way is to make 2 collections. Use stack for path nodes, and use queue for the branch nodes.

walk from root to leaf, push node to stack, add branch to queue.

pop the stack to building the new tree, poll the queue for the branches.

The time cost is O(height), the space is O(N).

After some observations, we can get rid of the queue to save space.

import java.util.*;
public class UpsideDown {
  public Node upsideDown(Node root) {
    Stack<Node> stem = new Stack<>();
    addNodes(root, stem);
    return buildTree(stem);
  }
  private void addNodes(Node root, Stack<Node> stem) {
    if(root == null) return;
    stem.push(root);
    addNodes(root.left, stem);
  }
  /*
    1
   / \
  2   3
 / \
4   5
        4
       / \
      5   2
         / \
        3   1
  */
  private Node buildTree(Stack<Node> stem) {
    Node root = stem.pop();
    Node curr = root;
    while(!stem.isEmpty()) {
      Node node = stem.pop();
      curr.left = node.right;
      curr.right = node;
      node.left = null;
      node.right = null;
      curr = node;
    }
    return root;
  }
  public static void main(String...args) {
    Node root = new Node(1, new Node(2, new Node(4, null, null), new Node(5, null, null)), new Node(3, null, null));
    UpsideDown ud = new UpsideDown();
    ud.printTree(root);
    root = ud.upsideDown(root);
    System.out.println();
    ud.printTree(root);
  }
  private int height(Node root) {
    if(root == null) return 0;
    int lheight = height(root.left);
    int rheight = height(root.right);
    return Math.max(lheight, rheight) + 1;
  }
  private void printTree(Node root) {
    int level = height(root);
    for(int i = 1; i <= level; i++) {
      printGivenLevel(root, i);
      System.out.println();
    }
  }
  private void printGivenLevel(Node root, int level) {
    if(root == null) {
      System.out.print("# ");
      return;
    }
    if(level == 1) {
      System.out.print(root.val + " ");
      return;
    }
    printGivenLevel(root.left, level - 1);
    printGivenLevel(root.right, level - 1);
   
  }
  private static class Node {
    int val;
    Node left;
    Node right;
    public Node(int val, Node left, Node right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
}

The time cost is O(N), the space cost is O(N). 

Binary Tree Inorder traversal

Problem

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

For Example:

Given:
   1
    \
     2
    /  \
   3    4

Output: [1,3,2,4]
Follow up: are you able to do it iteratively?

Solution

The inorder recursive traversal took O(N) time cost to visit all the nodes. The caller stack is ~logN on average and N at worst, each stack has finite number of variables. so that gives the space cost O(logN) to O(N).

For iterative solution, we need to store lots of nodes before we can start to print. We can store in queue or stack, queue is first-in last-out, won't work here. Stack is closer to what we are trying to do. When we traversal to the first node to print, we can store the nodes on the route to a stack. After we print, we use the stack to trace back. After we pop out a node, we store it, before pop out another node, we should process the right node. We do the same thing, store all the node in the stack before we move to the first node to print, then we trace back. Each node is push in and pop out of the stack once, the time cost is O(N). The space is bound by the stack size, which is O(N).

bst inorder traversal

import java.util.*;
class InOrder{
  public static void recurInOrder(Node root, List<Integer> inOrder) {
    if(root == null) return;
    recurInOrder(root.left, inOrder);
    inOrder.add(root.value);
    recurInOrder(root.right, inOrder);
  }
  public static void iterInOrder(Node root, List<Integer> inOrder) {
    Stack<Node> stack = new Stack<>();
    while(root != null) {
      stack.push(root);
      root = root.left;
    }
    while(!stack.isEmpty()) {
      Node t = stack.pop();
      inOrder.add(t.value);
      t = t.right;
      while(t != null) {
        stack.push(t);
        t = t.left;
      }
    }
  }
  public static void main(String...args) {
    Node root = new Node(1, null, new Node(2, null, new Node(3, null, null)));
    List<Integer> inOrder = new ArrayList<>();
    recurInOrder(root, inOrder);
    for(int i : inOrder) {
      System.out.print(i + " ");
    }
    System.out.println();
    inOrder = new ArrayList<>();
    iterInOrder(root, inOrder);
    for(int i : inOrder) {
      System.out.print(i + " ");
    }
  }
  private static class Node {
    int value;
    Node left;
    Node right;
    public Node(int value, Node left, Node right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
  }
}

Time cost O(N), space cost O(N).

see also:
Binary Tree Preorder traversal
Binary Tree Postorder Traversal
Binary Tree Level Order Traversal

Hanoi Towers

Problem

In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of different sizes which can slide onto any tower. How can you transfers N rings from one peg to another. The only operation you can perform is taking a single ring from the top of one peg and placing it on the top of another peg. You must never place a larger ring above a smaller ring.

Solution

It is hard to start, so let's start from smallest. 

Move 1 disk from tower 1 to tower 3. An easy success.

Let's move 2 disks from tower 1 to tower 3. We have to move top disk to tower 2 then move bottom to tower 3, then move top to tower 3 as well. There's not much to think about in this case, there is only one way of doing this: move top to the tower other than the target tower, then move bottom to the target tower, then move top to the target tower.

Now let's move 3 disks from tower 1 to tower 3. After playing for a while, we suddenly realize the recursive pattern -- think of the top 2 disks as one piece, we already know how to move them anywhere -- since all the disks below the top 2 disks are larger, they are no different than flat ground and can be ignored when we move the top 2 disks around. With the confidence that we can handle the top 2 disks regardless of the other disks, we can now treat the 2 disks as one disk. 

At this point, the cursive code start to reveal itself, but haven't crystal clear.

Let's start coding, the code will express our thought, make the details fall into places. We need 3 stack to model the towers, we need to calculate the empty slots other than source and destination, we can code 1 disk move case, we can code 2 disks move case, the only thing left is recursive part. Let's fill in that blank and work out a working code.

/*
  -                                                                                                          -
 ---   |    ---        |                 |           -     |       -         |             |       ---   |  ---
-----  |   -----     - |  -----  ---  -  |   -----  ---    |      ---  ----- | - --- ----- | -    -----  | -----

*/
import java.util.*;
class HanoiTowers {
  private Stack<Integer>[] slots = new Stack[3];
  private int n = 0;

  public HanoiTowers(int n) {
    this.n = n;
    for(int i = 0; i < 3; i++) {
      slots[i] = new Stack<Integer>();
    }
    for(int i = n; i >= 1; i--) {
      slots[0].push(i);
    }
  }
  //
  private void move(int topN, int source, int target) {  //5 0 2
    int emptySlot = emptySlot(source, target);//1
    if(topN == 1) {
      slots[target].push(slots[source].pop());
    } else if(topN == 2) {
      slots[emptySlot].push(slots[source].pop());
      slots[target].push(slots[source].pop());
      slots[target].push(slots[emptySlot].pop());
    } else {
      move(topN - 1, source, emptySlot);  //4 0 1 -> 3 0 2 | 2 0 1, 2 1 2
      slots[target].push(slots[source].pop());
      move(topN - 1, emptySlot, target);  //4 1 2
    }
  }
  public void move() {
    move(n, 0, 2);
  }
  public static void main(String...args) {
    HanoiTowers ht = new HanoiTowers(5);
    //ht.printTowers();
    ht.move();
    ht.printTowers();
  }
  private void printTowers() {
    for(int i = 0; i < 3; i++) {
      System.out.println("=========");
      Stack<Integer> stack = slots[i];
      while(!stack.isEmpty()) {
        System.out.print(stack.pop() + ", ");
      }
    }
  }
  private int emptySlot(int a, int b) {
    if(a == 0 && b == 1 || a == 1 && b == 0) return 2;
    else if(a == 0 && b == 2 || a == 2 && b == 0) return 1;
    else return 0;
  }
}

The time complexity is O(2^n), we for 1 disk, 1 move; 2 disks 3 moves; 3 disks top 2 need to move twice, so double the cost; 4 disks, the top 3 need to move twice, double the cost again, so the trend is 2^n. The space complexity is the 3 stacks, which is O(N)

minimum value in stack

Problem

Find the minimum value in a stack with O(1) time complexity.

Solution

Iterate through the stack elements for the minimum value takes O(N), won't satisfy the criteria. The only way to make it work is to have the minimum value stored so that we can return it in instant time. How to store the minimum value? A variable won't work. Once we pop out the min value, we won't be able to know what is the next minimum value in the stack. We need to store a sequence of minimum values in a stack or queue. We are not clear what should be stored, so let's play with an example. 

push 3, 5, 7, 2, 5

when push 3, we record 3 as min.

when push 5, 7, we don't care, they are larger anyway.

when push 2, we got a new min, so we store 2 above 3, that tells us we need a stack as the storage.

when push 5, we don't care.

Now we got two stacks:

value stack:   5, 2, 7, 5, 3    

min stack:     2, 3

Now let's pop the value stack. 

pop 5, we don't care, it didn't change min value.

pop 2, our min value changes, so we also pop 2 from the min stack.

pop 7, 5 we don't care.

pop 3, the min value changes, so we pop 3 from the min stack.

Coding the above is straight forward.

//[5, 3, 3, 7, 2, 8]
//3 3 5
//3 3 5
import java.util.*;
class FastMinStack {
  private Stack<Integer> values = new Stack<>();
  private Stack<Integer> mins = new Stack<>();
  public int getMin() {
    if(mins.isEmpty()) throw new RuntimeException("stack is empty");
    return mins.peek();
  }
  public void pop() {
    int val = values.pop();
    if(val == mins.peek()) mins.pop();
    return val;
  }
  public int push(int val) {
    values.push(val);
    if(mins.isEmpty() || val <= mins.peek())
      mins.push(val);
  }
  public static void main(String[] args) {
    FastMinStack fms = new FastMinStack();
    fms.push(5);
    fms.push(3);
    fms.push(3);
    fms.push(7);
    fms.push(2);
    fms.push(8);
    System.out.println(fms.getMin());//2
    fms.pop();
    System.out.println(fms.getMin());//2
    fms.pop();
    System.out.println(fms.getMin());//3
    fms.pop();
    fms.pop();
    System.out.println(fms.getMin());//3
    fms.pop();
    System.out.println(fms.getMin());//5
  }
}

The time complexity is O(1) for getMin, the space cost is O(N) in worst case, where the stack is 5 4 3 2 1, we have to store all of them for min values.

validate brackets

Problem

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.  

For example: the following is valid

({}{[ ]} )

the following is invalid

({}{[ ]}} )

Solution

If we observe the valid pattern, a right bracket should always have a matching left bracket. 

For example 

({}{[ ]} )

[] is a pair, if we remove it 

({}{} )

the next pair is {}

remove it

({} )

the next pair is {}

remove it

( )

the next pair is

()

This is a valid expression.

We can use a stack to remove the matching pairs from the expression. we push the left bracket into the stack. Whenever a right bracket is met, we pop an element from the stack and check. Once we exampled all the characters, the stack should be empty. 

A detail is to prevent the stack to throw exceptions, we need to check isEmpty before pop.

import java.util.*;
class Validator {
  public static boolean validate(char[] a) {
    Stack<Character> stack = new Stack<>();
    //({}{[ ]} )
    //
    for(int i = 0; i < a.length; i++) {
      char v = a[i];
      if(v == '(' || v == '{' || v == '[') {
        stack.push(v);
      } else if(v == ')' || v == '}' || v == ']') {
        char w = stack.iEmpty() ? '#': stack.pop();
        if(v == '}' && w != '{')
          return false;
        if(v == ']' && w != '[')
          return false;
        if(v == ')' && w != '(')
          return false;
      } else if(v == ' '){
          //do nothing
      } else {
        System.out.println("unexpected character" + v);
      }
    }
    if(stack.isEmpty())
      return true;
    else
      return false;
  }
  public static void main(String...args) {
    String str = "({}{[ ]} )";
    System.out.println(validate(str.toCharArray()));
  }
}

The time complexity is to iterate the array O(N), the space complexity is bound by the stack size, which is O(N)

Find Kth smallest number

Problem

Given an integer array, find the Kth smallest number in the array.
For example, given array {3, 0, -1, 0, 8, 7}, the 3rd smallest number is 0.

Solution

Solution 1:

We can sort the array with cost NlogN, then the Kth smallest number is at index K - 1.

Solution 2:
We can iterate the array 3 times, the first time, we find the smallest value.
The second time, if the current value equal to the smallest value we found last time, we ignore it, then continue to find the next smallest value.
The third time, if the current value matches any of the 2 smallest values we already saw, we  ignore the position, continue to find the 3rd smallest value.
After k loops, we found the Kth smallest value. The time complexity is O(KN).

Solution 3:

We can iterate the array once, find the smallest K numbers, then the largest in those K numbers are the solution. The cost is O(N).

If K = 3

we set r1 = r2 = r3 = Integer.MAX_VALUE before start traversal the array. Name current array value t.

    r1   r2    r3

  t         

if t <= r1

    r3 = r2

    r2 = r1

    r1 = t

else if t <= r2

    r3 = r2

    r2 = t

else if t <= r3 

    r3 = t

finally we out put r3 as the answer.

class KthSmallest {
  public static void main(String[] args) {
    int[] a = new int[]{3, 0, -1, 0, 8, 7};
    System.out.println(getKthSmallest(a));
  }
  public static int getKthSmallest(int[] a) {
    int N = a.length;
    if(N < 2) return Integer.MAX_VALUE;
    int r1 = Integer.MAX_VALUE;
    int r2 = Integer.MAX_VALUE;
    int r3 = Integer.MAX_VALUE;
    //  3, 0, -1, 0, 8, 7
    //               i
    //  r1   r2    r3
    //                t
    //  -1   0      0         
    for(int i = 0; i < N; i++) {
      int t = a[i];
      if(t <= r1) {
        r3 = r2;
        r2 = r1;
        r1 = a[i];
      } else if(t <= r2) {
        r3 = r2;
        r2 = t;
      } else if(t < r3) {
        r3 = t;
      }
    }
    return r3;
  }
}

The time complexity is O(N), the space complexity is O(1).

If K is a big number such as 20, this method won't be great. We need to use a stack instead. the current value t is compared with the top element in the stack. If t is smaller, the stack pop out, then the t is added to the stack in the right position. Finally, pop out the top of the stack, which is the answer.