Longest Increasing Subsequence -- Leetcode

Question:

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Answer:
DP + Binary Search! Time:O(n*logn), Space:O(n)!
public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0)return 0;
        int len = nums.length, maxLen=0;
        int[] dp = new int[len];
        dp[0] = nums[0];
        //dp + Binary Search, time: O(n*logn), space: O(n)
        for(int i=1; i<len; ++i){
            if(nums[i] > dp[maxLen]){
                dp[++maxLen] = nums[i];
            }else{
                int index = Arrays.binarySearch(dp, 0, maxLen, nums[i]);
                if(index < 0){
                    index = -(index+1);
                    dp[index] = nums[i];
                }
            }
        }
        return maxLen + 1;
    }
}

Russian Doll Envelopes -- Leetcode

Question:

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,

Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Answer:

Method 1: normal dp. Time: O(n*n), Space:O(n).

 public class Envelope {

int w;

int h;

public Envelope(int w, int h) {

this.w = w;

this.h = h;

}

@Override

public String toString() {

return "[" + w + "," + h + "]";

}

}

public int maxEnvelopes(int[][] envelopes) {

if (envelopes == null)

return 0;

int m = envelopes.length;

if (m == 0)

return 0;

// [2,3],[5,4],[6,4],[6,7]

Comparator<Envelope> cmp = new Comparator<Envelope>() {

@Override

public int compare(Envelope l, Envelope r) {

   //ascending order!

if (l.w > r.w) {

return 1;

} else if (l.w == r.w) {

if (l.h > r.h) {

return 1;

} else if (l.h == r.h) {

return 0;

} else {

return -1;

}

} else {

return -1;

}

}

};

Envelope[] list = new Envelope[m];

int[] count = new int[m];

int max = 1;

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

Envelope t = new Envelope(envelopes[i][0], envelopes[i][1]);

list[i] = t;

count[i] = 1;

}

Arrays.sort(list, cmp);

//System.out.print(Arrays.asList(list));

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

for (int j = i - 1; j >= 0; j--) {

if (list[i].w > list[j].w && list[i].h > list[j].h) {

if (count[j] + 1 > count[i]) {

count[i] = count[j] + 1;

}

}

}

if (count[i] > max) {

max = count[i];

}

}

return max;

}

Method 2: dp + binary search! Time: O(n*logn), Space:O(n).
public class Solution {
public int maxEnvelopes(int[][] envelopes) {
if (envelopes==null || envelopes.length==0 || envelopes[0]==null ||  envelopes[0].length!=2)
return 0;
int m = envelopes.length;

// [2,3],[5,4],[6,7],[6,4]
Comparator<int[]> cmp = new Comparator<int[]>() {
@Override
public int compare(int[] w1, int[] w2) {
                if(w1[0] != w2[0]){
                    return w1[0] - w2[0];
                }else{
                    return w2[1] - w1[1];
                }
}
};
    Arrays.sort(envelopes, cmp);

int[] dp = new int[m];
int maxLen = 0;
dp[0] = envelopes[0][1];
for (int i = 1; i < m; i++) {
   if(envelopes[i][1] > dp[maxLen]){
       dp[++maxLen] = envelopes[i][1];
   }else{
       int index = Arrays.binarySearch(dp,0,maxLen,envelopes[i][1]);
       if(index < 0){
           index = -(index + 1);
           dp[index] = envelopes[i][1];
       }
   }
}
return maxLen + 1;
}

}

public int lengthOfLIS(int[] nums) {

        if(nums == null || nums.length == 0)return 0;

        int len = nums.length, maxLen=0;

        int[] dp = new int[len];

        dp[0] = nums[0];

        //dp + Binary Search, time: O(n*logn), space: O(n)

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

            if(nums[i] > dp[maxLen]){

                dp[++maxLen] = nums[i];

            }else{

                int index = Arrays.binarySearch(dp, 0, maxLen, nums[i]);

                if(index < 0){

                    index = -(index+1);

                    dp[index] = nums[i];

                }

            }

        }

        return maxLen + 1;

    }

Plus One Linked List -- Leetcode

Question:

Given a non-negative number represented as a singly linked list of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Example:

Input:
1->2->3

Output:
1->2->4

Answer:

public class Solution {

    public ListNode plusOne(ListNode head) {

        boolean flag = Util(head);

        if(flag){

            ListNode newHead = new ListNode(1);

            newHead.next = head;

            return newHead;

        }

        return head;

    }

    

    public boolean Util(ListNode node){

        if(node == null)return true;

        

        ListNode next = node.next;

        //DFS

        boolean flag = Util(next);

        

        if(flag){

           if(node.val == 9){

              node.val = 0;

              return true;

           }else{

              node.val += 1;

           }

        }

        return false;

    }

}

Largest Divisible Subset -- Leetcode

Question:

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]

Answer:
Method: similar to Longest Increasing Subsequence. Using DP!
Time: O(n*n), Space:O(n)

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if(nums == null || nums.length==0){
            return res;
        }
     
        int length = nums.length;
        Arrays.sort(nums);
        //dp[i] record the previous element index satisfy longest divisible sequence ending with nums[i].
        int[] dp = new int[length];
        //len[i] record the longest divisible sequence ending with nums[i] length.
        int[] len = new int[length];
        int maxLen = 1;
        int maxLenFinalIndex = 0;
     
        for(int i=0;i<length;i++){
           dp[i] = i;
           len[i] = 1;

           for(int j=i-1;j>=0;j--){
               if(nums[i] % nums[j] == 0){
                   if(len[j] + 1 > len[i]){
                       len[i] = len[j] + 1;
                       dp[i] = j;
                   }
               }
           }
         
           if(len[i] > maxLen){
               maxLen = len[i];
               maxLenFinalIndex = i;
           }
        }
     
        int index = maxLenFinalIndex;
        int dpLen = maxLen;
        while(index >= 0 && dpLen > 0){
            res.add(nums[index]);
            index = dp[index];
            dpLen--;
        }
        Collections.reverse(res);
        return res;
    }
}

Queue with Min() -- FB

public class MinQueue {

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

Deque<Integer> minData = new LinkedList<Integer>();

public void offer(Integer val){

data.offer(val);

while(!minData.isEmpty() && minData.peekLast() > val){

minData.pollLast();

}

minData.offerLast(val);

}

public Integer poll(){

if(data.isEmpty()) return null;

Integer peek = data.peek();

Integer minPeek = minData.peekFirst();

if(peek == minPeek){

minData.pollFirst();

}

return data.poll();

}

public Integer getMin(){

return minData.peek();

}

public static void main(String[] args) {

// TODO Auto-generated method stub

        MinQueue mq = new MinQueue();

        

        mq.offer(2);

        System.out.println(mq.getMin());

        

        mq.offer(3);

        System.out.println(mq.getMin());

        

        mq.offer(8);

        System.out.println(mq.getMin());

        

        mq.offer(4);  

        System.out.println(mq.getMin());

        

        mq.poll();

        mq.poll();

        System.out.println(mq.getMin());  

}

}

Max Sum of Rectangle No Larger Than K -- Leetcode

Question:

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:

Given matrix = [
  [1,  0, 1],
  [0, -2, 3]
]
k = 2

The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).

Note:

1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?

Answer:
Solution:
Binary Search. Time:O(m*m*n*logn) , m<n

    public int maxSumSubmatrix(int[][] matrix, int k) {

        if(matrix==null || matrix.length==0)return 0;
        int m = matrix.length;
        if(matrix[0]==null || matrix[0].length==0)return 0;
        int n = matrix[0].length;
        int max = Integer.MIN_VALUE;
       //ensure m <= n
        boolean flag = m <= n ? true : false;
        if(!flag){
            int tmp = n;
            n = m;
            m = tmp;
        }
       
        for(int start=0;start<m;start++){
            int[] col = new int[n];
            TreeSet<Integer> set = new TreeSet<Integer>();
           
            for(int i=start;i<m;i++){
                set.clear();
                int colSum = 0;
                set.add(colSum);
               
                for(int j=0;j<n;j++){
                    if(flag){
                        col[j] += matrix[i][j];
                    }else{
                        col[j] += matrix[j][i];
                    }
                    colSum += col[j];
                   
                    //colSum - x <= k --> colSum - k <= x
                    //TreeSet binary search: O(logn)!  If treeSet cannot find a ceiling ele of (colSum - k), return NULL!
                    if(set.ceiling(colSum - k) != null){
                        int ceiling = set.ceiling(colSum - k);
                        int maxCur = colSum - ceiling;
                        max = Math.max(max, maxCur);
                    }
                    set.add(colSum);
                }
            }
        }
        return max;
    }

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

}

}