[leetcode] Populating Next Right Pointers in Each Node

Problem Description:
Given a binary tree:

class TreeLinkNode {

    TreeLinkNode left;

    TreeLinkNode right;

    TreeLinkNode next;

 } 

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.

• You may ONLY use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).  
• Follow up: What if the given tree could be any binary tree?

For example:

         1                      1-->NULL
       /  \                    / \
      2    3      ==>         2-->3-->NULL
     / \  / \                / \ / \
    4  5  6  7              4->5->6->7-->NULL

My first thought is using BFS to process the tree level by level. However, a regular BFS needs assistance of a queue, which is not constant space.
Anyway, the first problem (assuming a perfect binary tree) is relatively easy. By taking the similar strategy of solving Symmetric Tree problem, I got a very neat approach:

public class PopulatingNextRightPointersInEachNode {

    public void connect(TreeLinkNode root) {

        connect(root.left,root.right);

    }

    private void connect(TreeLinkNode n1,TreeLinkNode n2){

        if(n1==null||n2==null)

            return;

        n1.next=n2;

        connect(n1.left,n1.right);

        connect(n1.right,n2.left);

        connect(n2.left,n2.right);

    }

}

This approach is simple and neat, but has several drawbacks:

1. Not as efficient as optimal solution, as we can see in the following figure:

There are some repeated linking between node 7 and 8, 9 and 7. The result is correct, but when the tree size increases, this repeated linking cost may increase, too.
2. Definitely, this approach can't be applied to an arbitrary binary tree.

So, what can we do when it comes to any binary tree?

We can still try to process the tree level by level, but without a queue.
The trick part is that when we process the nodes of next level, we make sure that the current level has already been linked.
For example, when we deal with the third level, nodes 2 and 3 in level 2 have already been linked, then node5.next = node2.next.left( if not null), otherwise, keep searching towards right.

public class PopulatingNextRightPointersInEachNodeII {
    public void connect(TreeLinkNode root) {
        if(root==null)
            return;
        /**
         * current rightmost node
         */
        TreeLinkNode rightmost = null;
        /**
         * nextHead is the head node which is not null in next level
         *                1                   ----1
         *              /    \ 
         *             2     3               ----2
         *            / \    /   \
         *           6  7 8   9            ----3
         *              /    \     \
         *            10   11  12        ----4
         *            
         * e.g. node 10, it's the head of level 4 but not the left child of 6.
         */ 
        TreeLinkNode nextHead = null;
        TreeLinkNode temp = root;
        //connect next level of current root node level
        while(temp!=null){
            if(temp.left!=null)
                if(rightmost==null){
                    rightmost=temp.left;
                    nextHead=temp.left;
                }
                else{
                    rightmost.next = temp.left;
                    rightmost = rightmost.next;
                }
            if(temp.right!=null)
                if(rightmost==null){
                    rightmost=temp.right;
                    nextHead=temp.right;
                }
                else{
                    rightmost.next = temp.right;
                    rightmost = rightmost.next;
                }
            temp=temp.next;
        }
        //head in next level
        connect(nextHead);
    }
}

[leetcode] Set Matrix Zeroes

Problem Description:
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
It is the same problem as that in the book Cracking the Coding Interview Question 1.7
At first glance, a quick solution coming to mind maybe using two arrays to record the rows and columns that should be set to zeros respectively. And this solution needs O(m+n) space. As suggested by leetcode OJ , can we use constant space ?

Well, yes we can. The tricky part is that we use the first column and the first row of the input matrix to record the rows and columns that needs to set zero. Another point is that since the 1st row and 1st column are intersected at cell (0,0), so matrix[0][0]=0 can't tell us the 1st row or 1st column or both need to be set 0. In my implementation, I use two extra variable firstLine and firstCol to record it.

Here's the code, well, I concede it's a little messy. If there's other neat way to do it, I will appreciate it if you let me know.

public class Solution {

    public void setZeroes(int[][] matrix) {

        int firstLine = 1;

        int firstCol = 1;

        //set the first row and first column to record the rows and cols to be set 0s.

        for(int i=0;i<matrix.length;i++){

            for(int j=0;j<matrix[0].length;j++){

                if(matrix[i][j]==0){

                    if(i==0)

                        firstLine=0;

                    if(j==0)

                        firstCol=0;

                    matrix[0][j]=0;

                    matrix[i][0]=0;

                }

            }

        }

        //set rows and columns

        for(int i=1;i<matrix.length;i++){

            if(matrix[i][0]==0){

                for(int j=1;j<matrix[0].length;j++)

                    matrix[i][j]=0;

            }

        }

        for(int j=1;j<matrix[0].length;j++){

            if(matrix[0][j]==0){

                for(int i=1;i<matrix.length;i++)

                    matrix[i][j]=0;

            }

        }

        //set first row and column

        if(firstLine==0){

            for(int j=0;j<matrix[0].length;j++)

                matrix[0][j]=0;

        }

        if(firstCol==0){

            for(int i=0;i<matrix.length;i++)

                matrix[i][0]=0;

        }

    }

}

Solving Maximal Rectangle Problem based on "Largest Rectangle in Histogram" Problem

First of all, we get two problems here.
1. The Maximal Rectangle Problem and a good step-by-step solution
     The author presents there illustrates a number of principles that are widely applicable in algorithm design.
2. Largest Rectangle in Histogram Problem.
     If you are a Chinese guy, you can get a better understanding at Wangsishuang's Blog.

Then, how are these two problems here related?
Let's look at the Largest Rectangle in Histogram Problem first.
For example:
Given array [2,1,5,6,2,3] which represents the following histogram:

The Expected "Largest Rectangle" in this histogram is in shaded area which equals 10 unit.





As I stated at the beginning, there's O(n) solution for this problem by taking advantage of stacks. I'm not going to the details of that algorithm, assuming we now have a function 

int findMax(int[] heights)

which can get the max rectangle area in the histogram in O(n) time, then we can easily solve the Maximal Rectangle Problem  . How? 

We need to construct an assistant matrix to help us record the "histogram" of each row. As shown in the red rectangle, the corresponding row in the assistant matrix is the histogram of that row in the original matrix.


Then we just need to process the input matrix row by row, and for each row, we use findMax function to calculate the largest rectangle area:

public int maximalRectangle(int[][] matrix) {
        if(matrix.length<1)
            return 0;
        
        int maxRectangle = 0;
        int[][] cache = new int[matrix.length][matrix[0].length];
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j]==0)
                    cache[i][j]=0;
                else{
                    if(i>0)
                        cache[i][j]=cache[i-1][j]+1;
                    else
                        cache[i][j]=1;
                }
            }
            int rowMax = findMax(cache[i]);
            if(rowMax>maxRectangle)
                maxRectangle = rowMax;
        }
        return maxRectangle;

}

The outer loop is O(m) (m=no. of rows) and the inner loop is O(n) (n=no. of columns). Therefore the total runtime complexity is O(mn).


The Youtube video link I gave at the beginning shows how can we program the findMax function. And I paste it here:

private int findMax(int[] height){
        Stack<Integer> heights = new Stack<Integer>();
        Stack<Integer> indices = new Stack<Integer>();
        int max = 0;
        int lastIndex = 0;
        
        for(int i=0;i<height.length;i++){
            if(heights.empty() || height[i]>heights.peek()){ //current > top,just push in
                heights.push(height[i]);
                indices.push(i);
            }else if(height[i]<heights.peek()){ //current < top
                while(!heights.empty() && heights.peek()>height[i]){
                    lastIndex=indices.pop();
                    int temp = heights.pop();
                    if((i-lastIndex)*temp > max)
                        max = (i-lastIndex)*temp;
                }
                
                heights.push(height[i]);
                indices.push(lastIndex);
            }
            //note:if current = top , just ignore it.
        }
        /**
         * note: after processing, there still maybe elements in the stack.
         *       but they MUST BE in ascending order in the stack from bottom to top.
         */
        while(!heights.empty()){
            int temp = (height.length-indices.pop())*heights.pop();
            if(temp>max)
                max = temp;
        }
        return max;    

}

That's pretty much my general idea. In order to make it more efficient, we can merge findMax function into our maximalRectangle(). Therefore we don't need to create new stacks by scanning each row. And we don't need to traversal each row twice either. 

You can try these two problems on Leetcode Online Judge.
There are also some other variations of Rectangle Problem . 

New Start

人生过去的三年都没有按照我的计划来走，
人生未来的半年也不会按照我的原计划去走。

如果人生是一场Dota，那我现在打的是逆风的不能再逆风的逆风局。
既然如此，三年的账就在2012的末尾，一并清算吧。
坚信自己是后期，一定会翻盘。