manishsat

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

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

manishsat

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

manishsat

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

manishsat

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

manishsat

/*
 * 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;

manishsat

public static int findLeftMostElement(int[] A, int key){
    if (A.length == 0) return -1;
    int low = 0, high = A.length-1;
    while (low < high-1){
        int mid = low + (high - low)/2;
        if (A[mid] < key)
            low = mid;
        else
            high = mid;
    }    

manishsat

public static int[] firstKSmallestElements(int[] A, int k){
    	int n = A.length;
	if (n == 0 || k == 0 || n < k) return null;
	int idx = selectK(A, 0, n-1, k);
//	int idx = selectKIterative(A, 0, n-1, k);
	return Arrays.copyOf(A, k);
}

static int selectK(int[] A, int low, int high, int k){
	int pivot = partition(A, low, high);

manishsat

public void merge(int A[], int m, int B[], int n) {
    int k = n + m - 1;
    while (m > 0 && n > 0){
        if (A[m-1] > B[n-1])
            A[k--] = A[--m];
        else
            A[k--] = B[--n]; 
    }
    while (n > 0)
        A[k--] = B[--n];

manishsat

class Bar{
    int height, startIdx;
    Bar(int h, int i){ this.height = h; this.startIdx = i; }
}
public int largestRectangleArea(int[] height) {
    int maxArea = 0;
    Stack<Bar> stack = new Stack<Bar>();
    stack.push(new Bar(-1, 0));
    for (int i=0; i<=height.length; i++){
        int h = i < height.length ? height[i] : 0;

manishsat

public int search(int[] A, int target) {
    int low = 0, high = A.length-1;
    
    while (low <= high){
        int mid = low + (high - low)/2;
        if (A[mid] == target)
            return mid;
        if (A[low] <= A[mid]){
            if (A[low] <= target && target < A[mid])
                high = mid-1;