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;

manishsat

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

manishsat

/*
Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],