Binary Tree Longest Consecutive Sequence

Question:

Similar to https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
but the difference is : path can start from and end at any internal node or leaf node.

Answer:

public class BinaryTreeLongestConsecutiveSeq2 {

static int maxLen = 0;

static class Node {

int val;

Node left;

Node right;

public Node(int val) {

this.val = val;

left = null;

right = null;

}

}

public static int[] longestPathUtil(Node root) {

int[] res = { 0, 0 };

if (root == null)

return res;

//System.out.println("root = " + root.val);

//edge case for leaf node!

int smallerPathLen = 1;

int biggerPathLen = 1;

int[] leftPathRes = longestPathUtil(root.left);

int[] rightPathRes = longestPathUtil(root.right);

        //System.out.println("left res: " + res[0] + "," + res[1]);

if (root.left != null) {

if (root.left.val < root.val) {

smallerPathLen = Math.max(smallerPathLen, leftPathRes[0] + 1);

} else if (root.left.val > root.val) {

biggerPathLen = Math.max(biggerPathLen, leftPathRes[1] + 1);

}

}

if (root.right != null) {

if (root.right.val < root.val) {

smallerPathLen = Math.max(smallerPathLen, rightPathRes[0] + 1);

} else if (root.right.val > root.val) {

biggerPathLen = Math.max(biggerPathLen, rightPathRes[1] + 1);

}

}

// update longest increasing path len!

int totalLen = smallerPathLen + biggerPathLen - 1;

maxLen = Math.max(maxLen, totalLen);

res[0] = smallerPathLen;

res[1] = biggerPathLen;

//System.out.println("left = " + res[0] + ", right = " + res[1]);

return res;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Node root = new Node(8);

root.left = new Node(4);

root.right = new Node(10);

root.left.left = new Node(3);

root.left.right = new Node(7);

root.right.left = new Node(9);

root.right.right = new Node(11);

root.left.right.left = new Node(6);

longestPathUtil(root);

System.out.println(maxLen);

}

}

Permutations II -- Leetcode

Question:

Answer:

    vector<vector<int> > permuteUnique(vector<int> &num) {

        vector<vector<int> > res;

        perm(num, 0, (num.size()-1), res);

        return res;

    }

    

    void perm(vector<int> num,int k,int n, vector<vector<int> > &res){

        if (k==n){

            res.push_back(num);

            return;

        }

        else{

            unordered_set<int> used;

            

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

                //avoid swap with same element in same level!!!

                if(used.count(num[i]))continue;

                else{

                  used.insert(num[i]);

                  

                  //swap(num[k], num[i])

                  int tmp = num[k];

                  num[k]=num[i];

                  num[i]=tmp;

                

                //k+1!!!

                perm(num, k+1, n, res);

                

                //swap(num[k], num[i])

                tmp = num[k];

                num[k]=num[i];

                num[i]=tmp;

              }

           }

        }

    }

Combinations -- Leetcode

Question:

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

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Answer:

public List<List<Integer>> combine(int n, int k) {

        List<Integer> subres = new ArrayList<Integer>();

        List<List<Integer>> res = new ArrayList<List<Integer>>();

        DFS(subres, res, n, k, 1);

        return res;

    }

    

    public void DFS(List<Integer> subres, List<List<Integer>> res, int n, int k, int start){

        if(subres.size()==k){

            List<Integer> newsubres = new ArrayList<Integer>(subres);

            res.add(newsubres);

            return;

        }

        

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

            subres.add(i);

            DFS(subres, res, n, k, i+1);

            subres.remove(subres.size()-1);

        }

        return;

    }

set Matrix Zero -- Leetcode

Question:

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Answer:

Space:O(1)

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

        if(matrix == null)return;

        int m = matrix.length;

        if(m == 0)return;

        if(matrix[0] == null)return;

        int n = matrix[0].length;

        if(n==0)return;

        

        boolean left = false;

        boolean top = false;

         

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

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

               left = true;

            }

        }

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

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

                top = true;

            }

        }

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

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

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

                    matrix[i][0]=0;

                    matrix[0][j]=0;

                }

            }

        }

        

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

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

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

                    matrix[i][j] = 0;

                }

            }

        }

        

        if(left){

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

                matrix[i][0] = 0;

            }

        }

        

        if(top){

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

                matrix[0][i] = 0;

            }

        }

        

        return;

    }

Triangle Count -- LintCode

Question:

Given an array of integers, how many three numbers can be found in the array, so that we can build an triangle whose three edges length is the three numbers that we find?

Example

Given array S = [3,4,6,7], return 3. They are:

[3,4,6]
[3,6,7]
[4,6,7]

Answer:

2 pointer: Time:O(n*n)

public int triangleCount(int S[]) {

        // write your code here

        Arrays.sort(S);

        int len = S.length;

        int count = 0;

        for(int k=len-1;k>=2;--k){

            int i=0;

            int j=k-1;

            while(i<j){

                if(S[i] + S[j] > S[k]){

                    //keep j, k, i is a valid segment. Count all the eles in segment ([i,j-1],  j,k)

                    count += j-i;

                    j--;

                }else{

                    //S[i] + S[j] <= S[k]

                    i++;

                }

            }

        }

        return count;

    }

Verify Preorder Sequence in Binary Search Tree -- Leetcode

Question:

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

You may assume each number in the sequence is unique.

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

Answer:

1. Recursion: O(n*logn) time, Space:O(n)!

public boolean verifyPreorder(int[] preorder) {

       return verify(preorder, 0, preorder.length - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);

}

//Recursive in array range [start, end]

//Verify root in the [min, max], then recursive in left subtree and right subtree!

private boolean verify(int[] preorder, int start, int end, int min, int max) {

    //tricky!!!

    if (start > end) {

        return true;

    }

    int root = preorder[start];

    if (root > max || root < min) {

        return false;

    }

    int rightIndex = start;

    //find the first element > root; if non, return end+1!

    while (rightIndex <= end && preorder[rightIndex] <= root) {

        rightIndex++;      

    }

    return verify(preorder, start + 1, rightIndex - 1, min, root) && verify(preorder, rightIndex, end, root, max);

    }

2. Iteratively using stack! Time : O(n), Space:O(n)

    public boolean verifyPreorder(int[] preorder) {

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

        int lastSmallerRoot = Integer.MIN_VALUE;

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

            int t = preorder[i];

            

            if(stack.isEmpty() || t < stack.peek()){

                if(t > lastSmallerRoot){

                    stack.push(t); 

                }else{

                    //current element > most closest smaller root assumed!

                    return false;

                }

            }else{

                  //pop up stack elements to ensure descending order!

                while(!stack.isEmpty() && stack.peek() < t){

                    lastSmallerRoot = stack.pop();

                }

                stack.push(t);

            }

        }

        return true;

    }


3. Iteratively: Time: O(n), extra Space:O(1)!
 public boolean verifyPreorder(int[] preorder) {
        int lastSmallerRoot = Integer.MIN_VALUE;
        //modify preorder[0-k] used as stack! Extra Space: O(1)!
        int k = -1;
        for(int i=0; i<preorder.length; i++){
            int t = preorder[i];
            if(t < lastSmallerRoot){
                return false;
            }
            while(k >= 0 && t > preorder[k]){
                lastSmallerRoot = preorder[k--];
            }
            preorder[++k] = t;
        }
        return true;
    }

Verify Preorder Serialization of a Binary Tree -- Leetcode

Question:

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

Answer:

public boolean isValidSerialization(String preorder) {

        if(preorder==null || preorder.length()==0)return true;
        int len = preorder.length();
       //"#", return true!
        if(preorder.charAt(0)=='#')return len==1;
        int count = 1;

        String[] strArr = preorder.split(",");
        for(int i=0; i<strArr.length; i++){
            if(!strArr[i].equals("#")){
                count++;
            }else{
                count--;
                if(count == 0){
                    return i==strArr.length-1;
                }
            }
        }
        return count==0;

    }

Closest BST value I + II -- Leetcode

1. Closest BST value I:
Question:

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

• Given target value is a floating point.
• You are guaranteed to have only one unique value in the BST that is closest to the target.

Answer:
   public int closestValue(TreeNode root, double target) {
         int res = root.val;
         while(root!=null){
             if(Math.abs(root.val - target) < Math.abs(res - target)){
                 res = root.val;
             }
           
             if(root.val < target){
                 root = root.right;
             }else if(root.val > target){
                 root = root.left;
             }else{
                 return root.val;
             }
         }
         return res;
    }

2. Closest BST value II:
Question:

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

• Given target value is a floating point.
• You may assume k is always valid, that is: k ≤ total nodes.
• You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Answer:
 2.1. BST inorder traversal using Stack + maintain K closest element in a queue! 
Time: < O(n), Space: O(k)!

   public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        Queue<Integer> queue = new LinkedList<Integer>();
        if(root==null)return (List<Integer>)queue;
       
        while(root!=null){
            stack.push(root);
            root = root.left;
        }
        while(!stack.isEmpty()){
            TreeNode stackPeekNode = stack.pop();
            Integer stackPeek = stackPeekNode.val;
           
            if(queue.size() < k){
                queue.add(stackPeek);
            }else if(queue.size() == k){
                Integer quePeek = queue.peek();
                if(Math.abs(target - quePeek) > Math.abs(stackPeek - target)){
                    queue.poll();
                    queue.offer(stackPeek);
                }else{
                    //already find k closest!
                    break;
                }
            }
            //push all right subtree nodes into stack!
            TreeNode node = stackPeekNode.right;
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
        }
        return (List<Integer>)queue;
    }

2.2. Using two Stacks!: smaller element stack + larger element stack!
Time: < O(n), Space: O(k)!

public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> result = new LinkedList<Integer>();
        // populate the predecessor and successor stacks
        Stack<TreeNode> pred = new Stack<TreeNode>();
        Stack<TreeNode> succ = new Stack<TreeNode>();
        TreeNode curr = root;
        while (curr != null) {
            if (target <= curr.val) {
                succ.push(curr);
                curr = curr.left;
            } else {
                pred.push(curr);
                curr = curr.right;
            }
        }
        while (k > 0) {
            if (pred.empty() && succ.empty()) {
                break;
            } else if (pred.empty()) {
                result.add( getSuccessor(succ) );
            } else if (succ.empty()) {
                result.add( getPredecessor(pred) );
            } else if (Math.abs(target - pred.peek().val) < Math.abs(target - succ.peek().val)) {
                result.add( getPredecessor(pred) );                  
            } else {
                result.add( getSuccessor(succ) );
            }
            k--;
        }
        return result;
     }

    private int getPredecessor(Stack<TreeNode> st) {
        TreeNode popped = st.pop();
        TreeNode p = popped.left;
        while (p != null) {
            st.push(p);
            p = p.right;
        }
        return popped.val;
    }

    private int getSuccessor(Stack<TreeNode> st) {
        TreeNode popped = st.pop();
        TreeNode p = popped.right;
        while (p != null) {
            st.push(p);
            p = p.left;
        }
        return popped.val;
    }

Course Schedule II -- Leetcode -- Topological Sort

Question:

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

Answer:

Topological Sort + BFS:

public int[] findOrder(int numCourses, int[][] prerequisites) {

        int[] res = new int[numCourses];

        int k = 0;

        int[] indegree = new int[numCourses];

        Map<Integer, List<Integer>> hmap = new HashMap<Integer, List<Integer>>();

        

        //build directed graph

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

            if(!hmap.containsKey(prerequisites[i][1])){

            hmap.put(prerequisites[i][1], new ArrayList<Integer>());

            }

            hmap.get(prerequisites[i][1]).add(prerequisites[i][0]);

            indegree[prerequisites[i][0]]++;

        }

        

        //BFS, append level by level

        Queue<Integer> queue = new LinkedList<Integer>();

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

            if(indegree[i]==0){

                queue.offer(i);

            }

        }

        

        while(!queue.isEmpty()){

            Integer index = queue.poll();

            res[k++] = index;

            

            if(hmap.containsKey(index)){

                for(int child : hmap.get(index)){

                    indegree[child]--;

                    if(indegree[child]==0){

                    //System.out.println(child);

                        queue.offer(child);

                    }

                }

            }

        }

        int[] nullArr = {};

        if(k < numCourses)return nullArr;

        return res;

}