bittib’s gists

bittib / TrappingRainWater.java

Created May 22, 2013 12:31

Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6

	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 / InsertInterval.java

Last active December 9, 2016 07:04

Insert Interval Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]. Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], inser…

	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 / MergeInterval.java

Created May 24, 2013 12:10

Merge Interval Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

	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 / LongestIncreasingSequence

Created May 26, 2013 06:09

Longest Increasing Sequence

	/*
	* 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 / BinarySearchOfLeftOrRightBoundary.java

Last active December 9, 2016 07:03

Sorted array, given a key, find its left most index or right most index in array. If it isn't in array, return -1.

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

bittib / FindTopKSmallestElements.java

Last active December 9, 2016 07:03

Select Top K smallest Elements

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

bittib / MergeTwoSortedArrays.java

Created May 26, 2013 15:04

Merge Two Sorted Arrays Given two sorted integer arrays A and B, merge B into A as one sorted array. Note: You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

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

bittib / LargestRectangleInHistogram.java

Created May 26, 2013 16:42

Largest Rectangle in Histogram Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. For example, Given height = [2,1,5,6,2,3], return 10.

	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;

bittib / SearchInRotatedSortedArray.java

Last active December 9, 2016 07:02

Search in rotated sorted array Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array.

	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;

bittib / SearchInRotatedSortedArrayII.java

Last active August 9, 2020 14:18

Search In Rotated Sorted Array II Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array.

	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;