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).

Convert Binary Search Tree to Sorted Doubly Linked List

Problem:

A Binary Search Tree can be mapped to a sorted Circular Doubly-Linked List.

In a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

The left and right pointers in a binary search tree are mapped to the predecessor and successor pointers in a doubly-linked list.

Write a function to do the transformation in place, the function takes the root node of the tree as input and returns the pointer to the smallest element of the linked list.

For example,
Given binary search tree

      5
     / \
    3   8
   / \   \
  2   4   9

the circular double linked list is:
2 <-> 3 <-> 4 <-> 5 <-> 8 <-> 9 <-> 2
return the pointer to node 2 in the linked list

Solution:

The requirement of in place conversion leave us no other choice but convert it during in-order traversal of the binary search tree. We first handle left node, then current node, then right node. 

At the time we deal with current node, we should already have already converted the left subtree. The last node of the linked list is all we need to add the current node. After we added the current node, we need to pass the last node of the new linked list to the right sub tree. 

If we pass the last node of the linked list to the in-order traversal function as a parameter, the recursive call to left subtree and right subtree won't be symmetric. At the current node, when deal with the left subtree, we don't know what node to pass in; when deal with the right subtree, we can pass in the current node as the last node of the linked list. 

To deal with the above problem, we can store the last node as a global variable. At current node, we don't have to pass in anything, and when the recursive call for the left node finishes, the last node of the linked list is updated. The same applies when deal with the right node.

If we don't have to create a circular double linked list, we don't have to store the smallest node, however, this problem asked for it. So we need to store it. The way to store it is to walk to the left most tree node. This point is where we update the first node of the circular double linked list, it is also where our recursive calls start to return.

import java.util.*;
class Solution {
  LNode first;
  LNode last;
 
  public static void main(String...args) {
    Node root = new Node(5, new Node(3, new Node(2), new Node(4)), new Node(8, null, new Node(9)));
    Solution s = new Solution();
    s.transform(root);
    s.last.next = s.first;
    s.first.pre = s.last;
   
    LNode cur = s.first;
    while(cur.next != s.first) {
      System.out.print(cur.val + "<->");
      cur = cur.next;
    }
    System.out.print(cur.next.val);
  }
  /*
    3 
   / \ 
  2   4
 
  3  2<->3 first=2 last=3   
   2 first=2 last=2         4  2<->3<->4   first=2 last=4
    null                       null   null
 
  */
  private void transform(Node root) {//
    if(root == null)
      return;
    //move to left most node
    transform(root.left);
    LNode cur = new LNode(root.val, null, null);
    if(first == null) {
      first = cur;
      last = cur;
      return;
    }
    last.next = cur;
    cur.pre = last;
    last = cur;
   
    transform(root.right);
  }
 
  private static class Node {
    Node left;
    Node right;
    int val;
    public Node(int val, Node left, Node right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
    public Node(int val) {
      this.val = val;
      this.left = null;
      this.right = null;
    }
  }
 
  private static class LNode {
    int val;
    LNode pre;
    LNode next;
    public LNode(int val, LNode pre, LNode next) {
      this.val = val;
      this.pre = pre;
      this.next = next;
    }
  }
}

The time complexity is O(N) we need to deal with each one of the tree node, the space complexity is O(N), the double linked list size is proportional to the total number of tree node.

Binary Tree Level Order Traversal

Problem:

Write a program to in order traversal a binary tree from left to right and level by level.

For example:

Given binary tree 

    1

   / \

  2   3

 / \   \

4   5   6

it's in order traversal sequence is:

1 

2 3 

4 5 6

follow up question:

I see, you did this iteratively (recursively). Can you also solve it with recursive (iterative) approach?

Solution:

Iterative approach is easier. We are actually BFS traversal the binary tree start from root. We use a queue to store the nodes, after process the node at the top of the queue, we add its children nodes. The number of nodes at each level can be calculated by the queue size before we start processing the nodes at that level.

The recursive approach need a helper List<List<Integer>>. We add a new List<Integer> for each new level. At a particular level, we add the current processing node to the corresponding List<List<Integer>. Then we recursively process the left node and the right node.

import java.util.*;
class Solution {
  public static void main(String...args) {
    Node root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, null, new Node(6)));
    levelOrderIterative(root);
    System.out.println();
    levelOrderRecursive(root);
  }
 
  private static void levelOrderIterative(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    int size = queue.size();
    while(!queue.isEmpty()) {
      size = queue.size();
      for(int i = 1; i <= size; i++) {
        root = queue.poll();
        System.out.print(root.val + " ");
        if(root.left != null)
          queue.offer(root.left);
        if(root.right != null)
          queue.offer(root.right);
      }
      System.out.println();
    }
  }
 
  private static void levelOrderRecursive(Node root) {
    List<List<Integer>> result = new ArrayList<>();
    levelOrder(root, 0, result);
    for(List<Integer> lNodes : result) {
      for(Integer i : lNodes) {
        System.out.print(i + " ");
      }
      System.out.println();
    }
  }
 
  private static void levelOrder(Node root, int level, List<List<Integer>> result) {
    if(root == null)
      return;
    if(level == result.size())
      result.add(new ArrayList<>());
    result.get(level).add(root.val);
    levelOrder(root.left, level + 1, result);
    levelOrder(root.right, level + 1, result);
  }
  private static class Node {
    Node left;
    Node right;
    int val;
    public Node(int val, Node left, Node right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
    public Node(int val) {
      this.val = val;
      this.left = null;
      this.right = null;
    }
  }
}

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

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).

Combinations

Problem:

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2

Output:

[

  [2,4],

  [3,4],

  [2,3],

  [1,2],

  [1,3],

  [1,4],

]

Solution:

We want to take k numbers out of n numbers, the order doesn't matter. There will be C(n, k) possible combinations. To code it, we need to backtrack.

public void backtrack(int first, LinkedList<Integer> curr) {

    // if the combination is done

    if (curr.size() == k)

      output.add(new LinkedList(curr));

    for (int i = first; i < n + 1; ++i) {

      // add i into the current combination

      curr.add(i);

      // use next integers to complete the combination

      backtrack(i + 1, curr);

      // backtrack

      curr.removeLast();

    }

  }

the reason i start at first instead of 0 is because, we don't want to include duplicate elements, if the order do matter, the code will be

public void backtrack(int first, LinkedList<Integer> curr) {

    // if the combination is done

    if (curr.size() == k)

      output.add(new LinkedList(curr));

    for (int i = 1; i < n + 1; ++i) {

      // add i into the current combination

      if(curr.contains(i)) continue;

      curr.add(i);

      // use next integers to complete the combination

      backtrack(i + 1, curr);

      // backtrack

      curr.removeLast();

    }

  }

import java.util.*;
class Solution {
    public static void main(String...args) {
      List<List<Integer>> result = combine(4, 2);
      for(List<Integer> l : result) {
          for(Integer i : l) {
              System.out.print(i + " ");
          }
          System.out.println();
      }
    }
    public static List<List<Integer>> combine(int n, int k) {
      List<List<Integer>> result = new ArrayList<>();
      List<Integer> tmp = new ArrayList<>();
      List<Integer> nums = new ArrayList<>();
      for(int i = 0; i < n; i++) {
        nums.add(i+1);
      }
      backtrack(result, nums, 0, tmp, k);
      return result;
    }
    //1 2 3 4 5 6 7
    //            .         
    private static void backtrack(List<List<Integer>> result, List<Integer> nums, int pos, List<Integer> tmp, int k) {
      if(k <= 0) {
        result.add(new ArrayList(tmp));
        return;
      }
      for(int i = pos; i < nums.size(); i++) {
        tmp.add(nums.get(i));
        backtrack(result, nums, i+1, tmp, k - 1);
        tmp.remove(nums.get(i));
      }
    }
}

The are C(n, k) combinations, for each combination, we have a have to copy a k sized array, the time complexity is O(kC(n,k)), the space complexity is O(kC(n,k)) too.

Robot Room Cleaner

Problem:

The product robot room cleaner works as follows:

robot room cleaner

The robot can move forward, turn 90 degrees left, turn 90 degrees right.These movement allows it to move around. The robot also has a sensor to detect obstacles. Before the robot moves forward, the sensor will detect if an obstacle is located on the position it will move to, if yes, the robot cancels the move, then does a left or right turn then attempts to move forward.

Given a robot cleaner and a room floor that is divided into cells.

Each cell can be empty or blocked.

Design an algorithm to clean the entire floor using only the 4 given APIs shown below.

interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is blocked and robot stays on the current cell.
  boolean forward();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  // Clean the current cell.
  void clean();
}
For Example:

Given room cells
room = [
  [1,0,1,1,1,0,1,1],
  [1,0,0,0,1,0,1,1],
  [1,0,1,1,1,0,1,0],
  [0,0,0,0,0,0,0,0],
  [1,1,1,1,1,1,1,0]
],
All cells in the room are marked by either 0 or 1. All the cells outside of the matrix are blocked.
1 means the cell is blocked, while 0 means the cell is open. All open cells are connected.

The robot is put on a random open position, for example room[0][1] with initial direction of facing up.

Solution:

This is a standard dfs maze traversal problem. The news about this problem is the robot need to take corresponding actions during the dfs traversal, therefore we need to have a deep understanding of dfs process.

import java.util.*;
//import you.hardware.provider.package.*;
//invoke the program with command: java -cp .:HardwareVendorProvided.jar Solution
class Solution {
  private Set<Point> visited = new HashSet<>();
  /*replace this with a large enough all 0 2-d array when used with hardware
     the (room size / distance of robot forward moving) will decide the size of the 2-d array. It is large enough so that you can put the robot at center and there are cells in all 4 directions to cover the whole room area. */
  private static int[][] room = {
      {1,0,1,1,1,0,1,1},
      {1,0,0,0,0,0,1,1},
      {1,0,1,1,1,0,1,0},
      {0,0,0,0,0,0,0,0},
      {1,1,1,1,1,1,1,0}
    };
  private static int N = room.length;
  private static int M = room[0].length;
  //private static Robot robot = RobotFactory.makeRobot();

  public static void main(String[] args) {
    int x = 0;
    int y = 1;
    Solution s = new Solution();
    s.dfs(x, y);
    printRoom();
  }

  private void dfs(int row, int col) {
    visited.add(new Point(row, col));
    //robot.clean();
    room[row][col] = 2;
    int[] rowMask = new int[]{-1, 0, 1, 0};
    int[] colMask = new int[]{0, 1, 0, -1};
    for(int i = 0; i < rowMask.length; i++) {
      int nextRow = row + rowMask[i];
      int nextCol = col + colMask[i];
      if(canMove(nextRow, nextCol)) {
        dfs(nextRow, nextCol);
      } else {
        //robot.turnRight();
      }
    }
    //moveBack();
  }

  private void moveBack() {
    //robot.turnRight();
    //robot.turnRight();
    //robot.forward();
    //robot.turnLeft();
  }

  private boolean canMove(int row, int col) {
    if(visited.contains(new Point(row, col)))
      return false;
    //simulate sensor
    //return robot.forward();
    if(row < 0 || row >= N || col < 0 || col >= M)
      return false;
    return room[row][col] == 0;
  }

  private static class Point {
    int x;
    int y;
    public Point(int x, int y) {
      this.x = x;
      this.y = y;
    }
    public boolean equals(Object o) {
      if(o == null) return false;
      if(!(o instanceof Point)) return false;
      Point other = (Point)o;
      return this.x == other.x && this.y == other.y;
    }
 
    public int hashCode() {
      return 31*x + y;
    }
  }
  private static void printRoom() {
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < M; j++) {
        System.out.print(room[i][j] + " ");
      }
      System.out.println();
    }
  }
}

Time complexity is O(4^N) where N is the number of open cells. At each open cell, there are 4 directions to choose, total number of choices are 4^N. The space complexity is O(N), it is the max size of the caller stack.

N-Queens II

Problem:

The N-Queens puzzle is one of the classical puzzle.

On a chess board, a queen can attack any chess on the same row, same column and on the cells in the 2 diagonal directions. 

Given an integer n, we want to place n queens on a nxn chessboard, so that no two queens can attack each other.

We need to find the number of distinct solutions to the n-queens puzzle.

For Example:

given n = 4

There are two distinct solutions to put 4 queens on a 4x4 chessboard so that they can not attack each other. So the answer should be 2.

[

 ["xQxx",  // Solution 1

  "xxxQ",

  "Qxxx",

  "xxQx"],

 ["xxQx",  // Solution 2

  "Qxxx",

  "xxxQ",

  "xQxx"]

]

Solution:

This is a classic chess puzzle, we are seeking solution under constraint with try error. Track back is the technique we should use.

backtrack cell

  iterate chess board cells

    if cell is safe

       put chess

       if on last row

           increase count

       else

           backtrack next cell

       remove chess

When put a chess, we need to mark the cells on the same row, same column, same up slope diagonal and same down slope diagonal as unsafe. 

These cells' can be grouped by their column and row numbers.

• cells on the same row has the same row number, the column number doesn't matter, we can use an array to group them int[] row = new int[N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element row[3] = 1, then all the cells with same row number 3 are marked as 1, no matter what are their column number.
• cells on the same column has the same column number, the row number doesn't matter, we can use another array to group them int[] col = new int[N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element col[2] = 1, then all the cells with the same column number 2 are marked as 1, no matter what are their row number.
• cells on the same up slope diagonal has the row number decrease while the column number increase, therefore the row + col number remains the same, we can use another array to group them int[] up = new int[2*N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element up[3+2] = 1, then all the cells on the up slope diagonal are marked as 1, they are row 5 column 0, row 4 column 1, row 3 column 2, row 2 column 3, row 1 column 4 and row 0 column 5.
• cells on the same down slope diagonal has both the row number and column number increase, therefore the row - col number remains the same, we can use another array to group them int[] down = new int[3*N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element down[2-3+2*N] unsafe, then all the cells on the down slope diagonal are marked as 1. The reason we add 2*N is because row - col can be a negative number, array index has to be non-negative. The range of row - col is from -2N to N, therefore, we add 2*N and the array size is 3*N. Given N = 6 for example, the same down slope cells are [0, 1], [1, 2], [2, 3], [3, 4], [4, 5].

Actually, we don't have to back track cell by cell, once we put a queen on a cell, we know the cells on the same row are invalid, so we should move a row instead of a cell for the next move. 

class Solution {
  int numOfSol = 0;
  public static void main(String[] args) {
    int n = 4;
    int[][] board = new int[n][n];
    int[] cols = new int[n];  //cells on the same column
    int[] up = new int[2*n];  //cells on the up slop diagonal
    int[] down = new int[3*n]; //cells on the down slop diagonal
    System.out.println(nQueens(board, 0, 0, cols, up, down));
  }
 
  public static int nQueens(int[][] board, int row, int count, int[] cols, int[] up, int[] down) {
    int n = board.length;
    for(int col = 0; col < n; col++) {
      /*
      System.out.println("row=" + row + " col=" + col + " count =" + count);
      Arrays.stream(cols).forEach(i -> System.out.print(i + " "));
      System.out.println();
      Arrays.stream(up).forEach(i -> System.out.print(i + " "));
      System.out.println();
      Arrays.stream(down).forEach(i -> System.out.print(i + " "));
      System.out.println();
      */
      if(isSafe(row, col, n, cols, up, down)) {
        board[row][col] = 1;
        cols[col] = 1;    //mark cells on the same col unsafe, cells' row doesn't matter
        up[row + col] = 1;  //mark cells on the same up slope unsafe, cells' row decrease, col increase,the sum is the same
        down[row - col + 2*n] = 1; //mark cells on the same down slope unsafe, cells' row and col increase, row - col is the same, add 2n to prevent ArrayIndexOutOfBoundsException
        if(row + 1 == n) {
          count++;
          printBoard(board);
          System.out.println();
        } else {
          count = nQueens(board, row + 1, count, cols, up, down);
        }
        board[row][col] = 0;
        cols[col] = 0;  //mark the same col cells safe
        up[row + col] = 0; //mark the same up slope diagonal cells safe
        down[row - col + 2*n] = 0; //mark the same down slope diagonal cells safe
      }
    }
    return count;
  }
 
  private static boolean isSafe(int row, int col, int n, int[] cols, int[] up, int[] down) {
    return cols[col] + up[row + col] + down[row-col + 2*n] == 0;
  }
 
  private static void printBoard(int[][] board) {
    for(int i = 0; i < board.length; i++) {
      for(int j = 0; j < board[i].length; j++) {
        System.out.print(board[i][j] + " ");
      }
      System.out.println();
    }
  }
}

The time complexity's upper bound is O(N!). Before we have conclusion, we have tried all the possibilities. The way we try all the possibilities is: pick one of the columns from first row, then pick a column at the second row with constraint, then third row, so on and so forth. There are N choices at first row, then at most (ignore diagonal constraint) N - 1 choices at the second row, then N - 2 choices at the next row, finally 1 choice at the last row. The space complexity is O(N*N), it is calculated as the sum of marker arrays and board array size. Actually, if we only need the count, the board array can be omitted, the marker array has O(N) size.

See also:

sudoku solver

Search a 2D Matrix II

Problem:

Given a m x n matrix, which has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Given a target value, return if the matrix contains this value.

For Example:

Given the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 9, return true.

Given target = 16, return true.

Given target = 25, return false.

Solution:

brutal force solution is loop through the 2D array, compare each single element with the target, the time complexity is O(mn), the space complexity is O(1).

The above solution didn't use the sorted property. The sorted property can be used by binary search, with some ugly code, we can hope to achieve nlogn performance.

We can also use recursive approach. One way is to start from top left, search row and column, find the boundary points, then shrink the searching range to row+1, rowboundary and col+1, colboundary.

There is an elegant and faster solution using the sorted property.

Let's start at the bottom left corner, and move up and right, if we found the target before moving out of the boundary, we return true, otherwise false. This solution is not hard to come into mind, however, the hard part is: after naturally trying the start point at top-left corner without success, instead of giving up and trying different approaches such as recursive and binary search,  we should realize the approach is the best, the start point caused all the difficulties. 

import java.util.*;
class Solution {
  public static void main(String[] args) {
    int[][] matrix = new int[][] {
      {1,   4,  7, 11, 15},
      {2,   5,  8, 12, 19},
      {3,   6,  9, 16, 22},
      {10, 13, 14, 17, 24},
      {18, 21, 23, 26, 30}
    };
    int row = matrix.length;
    int col = matrix[0].length;
    System.out.println(contains(matrix, 9));
    System.out.println(contains(matrix, 16));
    System.out.println(contains(matrix, 20));
    System.out.println(contains(matrix, 25));
    System.out.println(contains(matrix, 0));
    System.out.println(contains(matrix, 18));
    System.out.println(contains(matrix, 15));
    System.out.println(contains(matrix, 1));
  }

  private static boolean contains(int[][] matrix, int target) {
    int rowMax = matrix.length - 1;
    int colMax = matrix[0].length - 1;
    int i = rowMax;
    int j = 0;
    while(j <= colMax && i >= 0) {
      if(matrix[i][j] == target) return true;
      if(matrix[i][j] > target) --i;
      else ++j;
    }
    return false;
  }
}

The time complexity is O(m+n) the space complexity is O(1).

Validate Binary Search Tree

Problem:

Given a binary tree (BST), determine if it is valid.

A BST satisfy the following rule for any node:

the left subtree's node values are all smaller than the current node value, the right subtree's node values are all bigger than the current node value.

For Example the following BST is invalid, because the right subtree has a node value 3 that is smaller than the root node value 8

    8

   / \

  1   3

In the following example, the BST is valid

    5

   / \

  1   8

     / \

    6   9

Solution:

We can solve this with recursive. One pitfall is to check root.left.value < root.value < root.right.value. That check is not enough. The following BST is invalid, but at each node, the root.left.value < root.value < root.right.value holds. What we want to check is each node fall into a value range of (llimit, ulimit)

    5

   / \

  1   6

     / \

    4   9

    

import java.util.*;

class Solution {

  public static void main(String[] args) {

    Node root = new Node(5, new Node(1, null, null), new Node(8, new Node(6, null, null), new Node(9, null, null)));

    System.out.println(isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE));

    root = new Node(8, new Node(1, null, null), new Node(3, null, null));

    System.out.println(isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE));

    root = new Node(5, null, null);

    System.out.println(isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE));

  }

 

  private static boolean isValid(Node root, int llimit, int ulimit) {

    if(root == null) return true;

    if(root.value < llimit || root.value > ulimit) return false;

    return isValid(root.left, llimit, root.value) 

      && isValid(root.right, root.value, ulimit);

  }

  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;

    }

  }

}

The time complexity is O(N) because we have to visit all the nodes, the space complexity is O(H), where H is the tree's height.

Word Search

Problem:

You are given a 2-d array of letters a-zA-Z. Words can be constructed from neighboring cells in the 2-d array. The current cell's neighboring cells are the ones on top, bottom, left and right. One cell can be used only once for a word.

Check if a given word can be constructed from the given 2-d array.

For Example, Given array

[
  ['A','B','E','D'],
  ['E','F','E','H'],
  ['I','J','K','L']
]

word "BEE" can be constructed, so return true.
"SEE" can not be constructed, so return false.
"ABFE", return true.
"KEHD", return true.
"KLHEK", return false.

Solution:

At the first impression, this is a graph dfs traversal problem. We can start at each grid cell, do a dfs search for the word sequence. A second thought suggests that this problem is more than graph dfs. Our goal is to search the right path matching the word among all the possible dfs traversal paths. So we are actually doing the path permutation, and we need to use backtrack. That is to say, when we visit a node, if that visit turns out to be a wrong move, we should track back, unmark the node, then give another neighboring node a try.

Two small techniques we need to pay attention in the following code. 

1. In order to visit all the neighbor nodes, we create a row mask and a column mask

int[] rowmask = new int[1, 0, -1, 0];

int[] colmask = new int[0, 1, 0, -1];

for(int i = 0; i < 4; i++) {

  int i = row + rowmask[d];

  int j = col + colmask[d];

  ...

}

the i and j combinations will cover all the 4 neighbors.

2. we don't have to use a set to keep track of visited node. We can just set the visited node to any character that is not a-zA-Z, that way we saved row*col memory that the set need. The drawback of this approach is side effect, the original 2D array has been modified.

3. we check word.length() == index at the first line, that way, even we are given a one element array, the function still works without throwing java.lang.StringIndexOutOfBoundsException.

import java.util.*;
class Solution {
  private Set<Integer> visited = new HashSet<>();
  public boolean found(char[][] board, String word) {//"KEHD"
    for(int i = 0; i < board.length; i++) {
      for(int j = 0; j < board[i].length; j++) {
        visited = new HashSet<>();
        if(dfs(board, word, 0, i, j))
           return true;
      }
    }
    return false;
  }
  private boolean dfs(char[][] board, String word, int index, int row, int col) {
    if(word.length() == index) {
      return true;
    }
    if((row < 0 || row == board.length || col < 0 || col == board[0].length) || word.charAt(index) != board[row][col])
      return false;
   
    visited.add(row*board[0].length + col);//10
    //board[row][col] = '!';
    int[] rowmask = new int[] {0, 1, 0, -1};
    int[] colmask = new int[] {1, 0, -1, 0};
    for(int d = 0; d < 4; d++) {
      int i = row + rowmask[d];
      int j = col + colmask[d];
      if(!visited.contains(i*board[0].length + j)) {
        if(dfs(board, word, index + 1, i, j))
        return true;
      }
    }
    visited.remove(row*board[0].length + col);//unmark
    //board[row][col] = word.charAt(index);
    return false;
  }
  public static void main(String[] args) {
    char[][] board = new char[][]{
      {'A','B','E','D'},
      {'E','F','E','H'},
      {'I','J','K','L'}
    };
    printBoard(board);
    Solution sol = new Solution();
    System.out.println(sol.found(board, "BEE"));
    System.out.println(sol.found(board, "SEE"));
    System.out.println(sol.found(board, "ABFE"));
    System.out.println(sol.found(board, "KEHD"));
    System.out.println(sol.found(board, "KLHEK"));
    System.out.println(sol.found(board, "A"));
   
    printBoard(board);
  }
  private static void printBoard(char[][] board) {
    for(int i = 0; i < board.length; i++) {
      for(int j = 0; j < board[i].length; j++) {
        System.out.print(String.format("%3s", board[i][j]));
      }
      System.out.println();
    }
  }
}

The time complexity is O(N*(4^L)), where N is the total number of elements in the array and L is the word length. In the worst case, we do the dfs traversal for all the N cells. During each dfs traversal, we could find mismatch at the last word character, at each step we need to check 4 neighbors, so the cost is 4^L. The space complexity is O(L) which is the max depth of the dfs calling stack.

Sudoku Solver

Problem:

Write a program to solve a Sudoku puzzle.

Sudoku is a popular puzzle game. The goal of Sudoku is to fill a 9×9 grid with numbers so that each row, column and 3×3 section contain all of the digits between 1 and 9.

Solution:

This is a typical backtracking problem. For current cell, we try numbers from 1 to 9, if a number is valid, then we recursively try the rest of the cells. If the current number is invalid or the rest of the cells can not be filled correctly, we try the next number. 

class Solution {
  public static boolean sudoku(int[][] board, int n) {
    int N = board.length;
    if(n > N * N - 1)
      return true;
    int i = n/N;
    int j = n%N;
    if(board[i][j] > 0) { //skip none-empty cell
      return sudoku(board, n+1);
    } else {
      for(int k = 1; k <= N; k++) {
        board[i][j] = k;
        if(isValid(board, i, j) && sudoku(board, n+1)) {
          return true;
        }
      }
      board[i][j] = -1; //put it back
      return false;
    }
  }

  private static boolean isValid(int[][] board, int row, int col) {
    for(int i = 0; i < row; i++) { //cells above
      if(board[i][col] == board[row][col])
        return false;
    }
    for(int j = 0; j < col; j++) { //cells left
      if(board[row][j] == board[row][col])
        return false;
    }
    for(int i = 3 * (row/3); i < 3 * (row/3) + 3; i++) {
      for(int j = 3 * (col/3); j < 3 * (col/3) + 3; j++) {
        if(board[i][j] > 0 && !(i == row && j == col) && board[i][j] == board[row][col]) {
          return false;
        }
      }
    }
    return true;
  }

  public static void main(String[] args) {
    int[][] board = new int[9][9];
    board[2][2] = 4;
    printBoard(board);
    System.out.println(sudoku(board, 0));
    printBoard(board);
  }
  private static void printBoard(int[][] board) {
    for(int i = 0; i < board.length; i++) {
      for(int j = 0; j < board[i].length; j++) {
        System.out.print(String.format("%3d", board[i][j]));
      }
      System.out.println();
    }
  }
}

Since the board size is fixed, there is no big O with N notation.

The time complexity has upper boundary (9^81)*27. The number 9^81 is because for each cell, we can have 9 options, there are 81 cells. For each option, check validity took 27 compares. We check at most 9 same row cells, 9 same column cells and 9 same cubic cells. It is upper bound because not all 81 cells are empty and we only have to compare the cells above and left of the current cell and we compare few cells for those invalid options.

The space complexity is 81, the size of board.

We can trade space for time. If we can keep updating all the allowed numbers for the 81 cells at each step, we don't have to try all the 9 numbers. We only have to try 9! numbers for the 9 cells in a row. There are 9 rows, so the total time complexity will be (9!)^9*81, which is substantially faster than the simple backtrack code above. The space complexity will be more than 81*10, besides associate a value to each cell, we have to associate an extra set to each cell for the allowed numbers. Set's object overhead and references will make 10 fold memory increase an under-estimate.

See also:

N-Queens II

Permutations

Problem:

Given a collection of distinct letters, return all possible permutations.

For Example:

Given: [a,b,c]
the permutations are:
[
  [a,b,c],
  [a,c,b],
  [b,a,c],
  [b,c,a],
  [c,a,b],
  [c,b,a]
]

Solution:

With backtracking, we can find the permutations. 

There are N! number of possible permutations, the time complexity will be bigger than O(N!). It will be bigger because we have to generate all those temporary substrings as parameters for recursive call. The total number of possible substrings is sum(P(N,k)) where k range from 1 to N. The sum(P(N,k)) is the number of all possible substrings by randomly picking k letter from total of N letters to form a string.
since P(N,k) = N!/(N-k)! <= N!, the sum(P(N,k)) <= N*N!.
As a result, the time complexity is between O(N!) and O(N*N!)

The since we generated many substrings as parameters for recursive calls, and java string pool did internal caching, the space complexity is bounded by the total number of possible substrings, which is less than O(N*N!).

class Solution {
  public static void permutations(String s, String remains) {
    if(remains.isEmpty()) {
      System.out.println(s);
      return;
    }
    for(int i = 0; i < remains.length(); i++) {
      char c = remains.charAt(i);
      permutations(s + c, remains.substring(0, i) + remains.substring(i+1));  //take out a character
    }
  }

  public static void main(String[] args) {
    permutations("", "abc");
  }
}

time complexity O(N!) to O(N*N!), space complexity O(N*N!)

Use string to do the permutations is easy, however it took extra space to store temporary strings, we can use a reusable char array to avoid extra space.

class Solution {
  public static void permutations(char[] orig, int n) {
    if(n == orig.length) {
      System.out.println(new String(orig));
      return;
    }
    for(int i = n; i < orig.length; i++) {
      swap(orig, n, i);
      permutations(orig, n+1);
      swap(orig, n, i);  //restore original array
    }
  }
 
  private static void swap(char[] orig, int i, int j) {
    char tmp = orig[i];
    orig[i] = orig[j];
    orig[j] = tmp;
  }
 
  public static void main(String[] args) {
    permutations("abc".toCharArray(), 0);
  }
}

time complexity O(N!) to O(N*N!), space complexity O(N) for the char array.

see also: number permutations with restrictions

Regular Expression Matching

Problem:

A regular expression can be empty or contains '.', '*' and charecters a-z, write a function to tell if the regular expression can match the entire input string. The input string can be emtpy, or contains only charecters a-z.

'.' can match any single character.
'*' can match zero or more of the preceding element.

You can assume the regular expression is a valid one.

For example:
Given regular expression "ab." and input string "abc", the result is true.
Given regular expression "ab*" and input string "abbbbb", the result is true.
Given regular expression "ab*" and input string "abc", the result is false.
Given regular expression "ab*x.*" and input string "abxyzz", the result is true.

Solutions:

This is a hard problem, because of the *. However we can start with simple case first. If the regex don't have *, the problem can be solved with a simple recursive function: For regex string p and input string s, if p.charAt(0) matches s.charAt(0), the problem reduces to match p.substring(1) to s.substring(1).

boolean backtrace(String p, String s) {

  ...

  if(s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')

    return backtrace(p.substring(1), s.substring(1));

  ...

}

Now the * makes the condition harder, so we have to modify the simple recursive function.

We need to know what is the character before *. 

One approach is to pass the previous character in the recursive call. 

boolean backtrace(char pre, String p, String s) {...}

then look back one character when meet *.

Another approach is to look forward 2 characters for potential .* or a-z* match.

No matter what approach, dealing with * has two conditions:

1. * matches nothing, skip *, problem reduces to backtrack(p.substring(1), s)
2. * matches something, problem reduces to backtrack(p, s.substring(1))

The following code gives 2 methods using the look back and look forward approaches for *.

class Solution {
  public static boolean canMatch(char pre, String p, String s) {
    //System.out.println("pre=" + pre + ", s="+s+", p="+p);
    if(s.isEmpty()) {
      if(p.isEmpty() || p.equals("*") || p.equals(".*"))
        return true;
      else return false;
    }
    if(p.isEmpty())
      return false;
    if(p.charAt(0) == s.charAt(0) || p.charAt(0) == '.') {
      return canMatch(p.charAt(0), p.substring(1), s.substring(1));
    } else {
      //* matches nothing
      if(canMatch(pre, p.substring(1), s))
        return true;
      //* matches something
      if(pre == '.') {
        return canMatch(pre, p, s.substring(1));
      } else {
        if(s.charAt(0) != pre) return false;
        return canMatch(pre, p, s.substring(1));
      }
    }
  }
 
  public static boolean canMatch(String p, String s) {
    //System.out.println("s="+s+", p="+p);
    if(p.isEmpty()) return s.isEmpty();
    if(s.isEmpty()) {
      if(p.equals("*") || p.equals(".*"))
        return true;
      else
        return false;
    }
    boolean match = false;
    if(p.charAt(0) == '.' || p.charAt(0) == s.charAt(0)) {
      match = true;
    }
    if(p.length() > 1 && p.charAt(1) == '*') {
      if(match) {
        //* matches nothing
        if(canMatch(p.substring(2), s.substring(1)))
          return true;
        return canMatch(p, s.substring(1));
      }
      return false;
    } else {
      return match && canMatch(p.substring(1), s.substring(1));
    }
  }
 
  public static void main(String[] args) {
    System.out.println(canMatch('$', "ab.", "abc"));
    System.out.println(canMatch('$', "ab*", "abbbbb"));
    System.out.println(canMatch('$', "ab*", "abc"));
    System.out.println(canMatch('$', "ab*x.*", "abxyzz"));
    System.out.println(canMatch('$', "", ""));
    System.out.println(canMatch('$', ".*", ""));
    System.out.println(canMatch('$', ".*", "x"));
    System.out.println(canMatch('$', "b*", "x"));
    System.out.println();
    System.out.println(canMatch("ab.", "abc"));
    System.out.println(canMatch("ab*", "abbbbb"));
    System.out.println(canMatch("ab*", "abc"));
    System.out.println(canMatch("ab*x.*", "abxyzz"));
    System.out.println(canMatch("", ""));
    System.out.println(canMatch(".*", ""));
    System.out.println(canMatch(".*", "x"));
    System.out.println(canMatch("b*", "x"));
  }
}

The time complexity and space complexity calculation is even harder, it is O((T+P)2
${}^{T+\frac{P}{2}}$$)$. ,where T is the length of the input string and P is the length of regular expression. Prove it need a paper, lets don't worry about it.

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.

Letter Combinations of a Phone Number

Problem:

A phone pad has the number 2-9 maps to enlish characters as the following, 

    "2", "abc"

    "3", "def"

    "4", "ghi"

    "5", "jkl"

    "6", "mno"

    "7", "pqrs"

    "8", "tuv"

    "9", "wxyz"

Given a number, find all the possible lettters the given number can represent. The order of the letters doesn't matter.

For Example,

Given number : "23"

All the possible letters the number 23 can represent are: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Solution:

We can use backtrack to find the answer. What passed in the recursive call is the remaining digits and the accumulative letters. Once the remaining digits are exausted, we meet the exit condition.

import java.util.*;
class Solution {
  public static void main(String[] args) {
    String letter = "23";
    Map<String, String> map = new HashMap<>();
    map.put("2", "abc");
    map.put("3", "def");
    map.put("4", "ghi");
    map.put("5", "jkl");
    map.put("6", "mno");
    map.put("7", "pqrs");
    map.put("8", "tuv");
    map.put("9", "wxyz");
    backTrace(letter, "", map);
  }

  private static void backTrace(String letter, String cur, Map<String, String> map) {
    if(letter.length() == 0) {
      System.out.print(cur + " ");
    } else {
      for(char c : map.get(letter.substring(0, 1)).toCharArray())
      backTrace(letter.substring(1), cur + c, map);
    }
  }
}

Time complexity O(N^3 * M^4), where N is the number of digits in the number that maps to 3 characters, and M is the number of digits in the number that maps to 4 characters.

The space complexity O(N^3 * M^4), because this is the total number of possible combinations.

Closest Binary Search Tree Value II

Problem:

Given a binary search tree and a target value, find k values (k < total nodes) in the BST that are closest to the target.

For example:

given the following tree and target = 4, and k = 2

    5

   / \

  2   9

 / \

1   3

Output: [3,5]

Solution:

One way to solve this is to convert the tree into an array, then use a priority queue to find the top k. Notice the priority queue element needs 2 fields -- the node value, the delta between the node value and target. The delta is used by the comparator. 

We can avoid converting the tree into an array, we just need to visit all the node once, we can use tree traversal for that purpose. 

import java.util.*;
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(1, null, null)
                        );
    PriorityQueue<int[]> pq = new PriorityQueue<>((i, j) -> j[1] - i[1]);
    int target = 4;
    int k = 2;
    closest(root,target, k, pq);
    while(!pq.isEmpty()){
      int[] x = pq.poll();
      System.out.print(x[0] + " ");
    }
    System.out.println();
  }
 
  private static void closest(Node root, int target, int k, PriorityQueue<int[]> pq) {
    if(root == null) return;
    closest(root.left, target, k, pq);
    pq.offer(new int[]{root.value, Math.abs(root.value - target)});
    if(pq.size() > k)
      pq.poll();
    closest(root.right, target, k, pq);
  }
 
  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;
    }
  }
}

The time complexity is O(N + klogk), the space complexity is O(logN + k)

Recover Binary Search Tree

Problem:

We start with a binary search tree (BST), that has 2 elements swapped out of order.  Design an algorithm to recover the tree without changing its structure.

Example:

Input: 

   3

  / \

 1   4

    / \

   2   5

Output:

   2

  / \

 1   4

    / \

   3   5

Solution:

We can convert the tree to an inorder traversal array, find the out of order elements, then go back to the original tree, find the 2 nodes, then swap the value.

It is worth studying the classical one path algorithm for finding the 2 swapped elements in an almost ordered array. The same principle can be used to find the 2 swapped elements in the tree without first converting it into an array.

import java.util.*;
class Solution {
  Node x = null;
  Node y = null;
  Node pre = null;
  public static void main(String...args) {
    Node root = new Node(3, new Node(1, null, null),
                    new Node(4, new Node(2, null, null), new Node(5, null, null))
                        );
    inOrder(root);
    System.out.println();
    Solution so = new Solution();
    so.findDisOrders(root);
    so.swap();
    inOrder(root);
    System.out.println();
  }

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

  private void swap() {
    int val = x.value;
    x.value = y.value;
    y.value = val;
  }

  private void findDisOrders(Node root) {
    if(root == null) return;
    findDisOrders(root.left);
    if(pre != null && pre.value > root.value) {
      y = root;
      if(x == null)
        x = pre;
      else
        return;
    }
    pre = root;
    findDisOrders(root.right);
  }

  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 is O(N) because we have to visit the N nodes. The space complexity is O(1).

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