bittib

/*
 * Dynamic Programming Solution
 * f[i] : longest increasing sequence of A[0..i], f[i] = max{f[j]} + 1,  0<= j < i
 * Time complexity : O(n^2) ; Space complexity : O(n)
 */
public int lis(int[] A){
    int n = A.length, maxLength = 0;
    int[] f = new int[n];
    for (int i=0; i<n; i++){
        f[i] = 1;

bittib

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    ArrayList<Interval> list = new ArrayList<Interval>();
    Collections.sort(intervals, new Comparator<Interval>(){
        public int compare(Interval x, Interval y) {
            if (x.start == y.start)
                return x.end - y.end;
            else
                return x.start - y.start;
        }
    });

bittib

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval x) {
    	ArrayList<Interval> list = new ArrayList<Interval>();
    	boolean done = false;
    	Itrator<Interval> iterator = intervals.iterator();
    	while (iterator.hasNext() {
		Interval itv = iterator.next();
		if (done || itv.end < x.start){
			list.add(itv);
		}else if (x.end < itv.start){
			list.add(x);

bittib

public int trap(int[] A){
    int n = A.length, sum = 0;
    if (n < 3) return 0;
    int[] leftBar = new int[n], rightBar = new int[n];
    for (int i=1; i<n; i++)
        leftBar[i] = Math.max(leftBar[i-1], A[i-1]);
    for (int i=n-2; i>=0; i--)
        rightBar[i] = Math.max(rightBar[i+1], A[i+1]);
    for (int i=0; i<n; i++)
        sum += Math.max(0, Math.min(leftBar[i], rightBar[i]) - A[i]);

bittib

class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode(int val){
        this.val = val;
    }
}

public String serialize(TreeNode root){
    StringBuilder sb = new StringBuilder();

bittib

class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode(int val){
        this.val = val;
    }
}

public void flatten(TreeNode root){
    root = flatten(root, null);

bittib

/**
 * LeetCode Add Binary Probem

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

 */

bittib

/**
 * Time Complexity : Comparision time : 3 * n/2 + 1
 */
public int[] findMinMax(int[] A){
    int n = A.length;
    if (n == 0) return null;
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int i=0; i < n-1; i+=2){
        int smaller = A[i], bigger = A[i+1];
        if (A[i] > A[i+1){

bittib

/**
 * Time Complexity: O(n)
 */
public int[] minOfSlidingWindow(int[] A, int k){
    int n = A.length;
    int[] B = new int[n - k + 1];
    int[] queue = new int[n];
    int head = 0, tail = 0;
    for (int i=0; i<n; i++){
        while (head < tail && A[i] <= A[queue[tail-1]])

bittib

/**
 * http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
 * O(lgm + lgn) Solution
 */

static final int MIN = Integer.MIN_VALUE;
static final int MAX = Integer.MAX_VALUE;

public static int kthSmallest(int[] A, int[] B, int k){
    if (A == null || B == null || k > A.length + B.length)