Array Rotation - Three Solutions

Array rotation by k places can be done by using extra space of k sized array, by shifting array by one position in loop of k, by shifting array by gcd(array.length, k) in gcd number of sets. Following program has all the implementations:

	package arrays;
	public class ArrayRotation {
	public static void rotateByOne(int[] a) {
	int n = a.length, tmp=a[0];
	for(int i=0;i<n-1;i++) {
	a[i]=a[i+1];
	}
	a[n-1]=tmp;
	print(a);
	}
	public static void rotateByX(int[] a, int init, int x) {
	int n = a.length, tmp=a[init];
	int d =n-x+init;
	for(int i=init;i<d;i=i+x) {
	a[i]=a[i+x];
	}
	a[d]=tmp;
	print(a);
	}
	public static void rotateNoExtraSpace(int[] a,int k) {
	for(int i=0;i<k;i++) {
	rotateByOne(a);
	}
	}
	public static int gcd2(int a,int b) {
	if(a==0)
	return b;
	return gcd2(b%a,a);
	}
	public static void rotateJuggle(int[] a,int k) {
	int n = a.length;
	int g = gcd2(n,k);
	for(int i=0;i<g;i++) {
	rotateByX(a,i,g);
	}
	}
	public static void rotateExtraSpace(int[] a,int k) {
	int n = a.length;
	print(a);
	int[] tmp = new int[k];
	for(int i=0;i<k;i++) {
	tmp[i]=a[i];
	}
	for(int i=0;i<n-k;i++) {
	a[i]=a[i+k];
	}
	int j=0;
	for(int i=n-k;i<n;i++) {
	a[i]=tmp[j++];
	}
	print(a);
	}
	public static void print(int[] a) {
	System.out.println();
	for(int i:a)
	System.out.print("---"+i);
	}
	public static void main(String[] args) {
	int[] a1= {1,2,3,4,5};
	rotateExtraSpace(a1,2);//3,4,5,1,2
	rotateNoExtraSpace(a1,2);
	int[] a2={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
	rotateJuggle(a2,3);
	}
	}

view raw ArrayRotation.java hosted with ❤ by GitHub

Top K Frequent Elements - Hashing Problem

Problem : Get top K frequent elements.

Implementation:

	package hashTables.problems;
	import java.util.ArrayList;
	import java.util.LinkedHashMap;
	import java.util.Map;
	public class TopKFrequentEles {
	static ArrayList<Integer> TopK(int[] arr, int k) {
	//int[] arr = array.stream().mapToInt(i->i).toArray();
	int l1 = arr.length;
	Map<Integer, Integer> countMap = new LinkedHashMap<>();
	for (int i = 0; i < l1; i++) {
	if (countMap.containsKey(arr[i])) {
	countMap.put(arr[i], countMap.get(arr[i]) + 1);
	} else {
	countMap.put(arr[i], 1);
	}
	}
	ArrayList<Integer> result = new ArrayList<Integer>();
	countMap.entrySet().stream().sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed().thenComparing(Map.Entry.<Integer, Integer>comparingByKey().reversed())).forEach(e -> {
	int key = e.getKey();
	int val = e.getValue();
	for (int i = 0; i < val; i++) {
	if(!result.contains(key) && result.size()<k)
	result.add(key);
	else
	break;
	}
	});
	return result;
	}
	public static void main(String[] args) {
	int arr2[]= {8,1,1,2,2,3,3,3,4};
	ArrayList<Integer> result = TopK(arr2,2);
	for(int i: result) {
	System.out.println(i);
	}
	}
	}

view raw TopKFrequentEles.java hosted with ❤ by GitHub

Sort By Frequency - Hashing Problem

Problem : Sort elements by their frequency.

Following is the implementation where we store the frequency in hashmap:

	package hashTables.problems;
	import java.util.ArrayList;
	import java.util.LinkedHashMap;
	import java.util.Map;
	public class SortByFrequency {
	public static ArrayList<Integer> sortByFrequency(int arr[]) {
	int l1 = arr.length;
	Map<Integer, Integer> countMap = new LinkedHashMap<>();
	for (int i = 0; i < l1; i++) {
	if (countMap.containsKey(arr[i])) {
	countMap.put(arr[i], countMap.get(arr[i]) + 1);
	} else {
	countMap.put(arr[i], 1);
	}
	}
	ArrayList<Integer> result = new ArrayList<Integer>();
	countMap.entrySet().stream().sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed().thenComparing(Map.Entry.<Integer, Integer>comparingByKey())).forEach(e -> {
	int key = e.getKey();
	int val = e.getValue();
	for (int i = 0; i < val; i++) {
	result.add(key);
	}
	});
	return result;
	}
	public static void main(String[] args) {
	int arr1[]= {6,6,2,3,1,4,1,5,6,2,8,7,4,2,1,3,4,5,9,6};
	ArrayList<Integer> result = sortByFrequency(arr1);
	for(int i: result) {
	System.out.println(i);
	}
	}
	}

view raw SortByFrequency.java hosted with ❤ by GitHub

Count Distinct Elements In Every Window - Hashing Problem

Problem: Count distinct elements in every window of given K size.

Following is the implementation, which rotates the array window:

	package hashTables.problems;
	import java.util.ArrayList;
	import java.util.HashMap;
	public class CountDistinctElements {
	public static ArrayList<Integer> countDistinct(int arr[], int k) {
	int n = arr.length;
	HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	for (int i = 0; i < k; i++)
	hM.put(arr[i], hM.getOrDefault(arr[i], 0) + 1);
	list.add(hM.size());
	for (int i = k; i < n; i++) {
	if (hM.get(arr[i - k]) == 1) {
	hM.remove(arr[i - k]);
	}else
	hM.put(arr[i - k], hM.get(arr[i - k]) - 1);
	hM.put(arr[i], hM.getOrDefault(arr[i], 0) + 1);
	list.add(hM.size());
	}
	return list;
	}
	public static void main(String[] args) {
	int arr[] = {1,2,1,3,4,2,3};
	int k = 4;
	ArrayList<Integer> list = countDistinct(arr,k);
	for(int i : list) {
	System.out.println(i);
	}
	}
	}

view raw CountDistinctElements.java hosted with ❤ by GitHub

Print Non-repeated Elements - Hashing Problems

Problem : Print the non-repeated elements of an array.

Following is the implementation:

	package hashTables.problems;
	import java.util.ArrayList;
	import java.util.HashMap;
	public class PrintNonRepeated {
	static ArrayList<Integer> printNonRepeated(int arr[]){
	int n = arr.length;
	HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	for(int i=0;i<n;i++) {
	int val = arr[i];
	if(!hM.containsKey(val)) {
	hM.put(val,i);
	list.add(val);
	}else {
	list.remove((Integer)val);
	}
	}
	return list;
	}
	public static void main(String[] args) {
	int arr[]= {1,1,2,2,3,3,4,5,6,7};
	ArrayList<Integer> list = printNonRepeated(arr);
	for(int i:list) {
	System.out.println(i);
	}
	}
	}

view raw PrintNonRepeated.java hosted with ❤ by GitHub

Relative Sorting - Hashing Problems

Problem : Sort array1 in the order of array2 elements.

Following is the implementation:

	package hashTables.problems;
	import java.util.HashMap;
	import java.util.SortedSet;
	import java.util.TreeSet;
	public class RelativeSorting {
	public static void sortA1ByA2(int a1[], int a2[]) {
	int n1 = a1.length, n2 = a2.length;
	HashMap<Integer, Integer> map = new HashMap<>();
	for (int i = 0; i < n1; i++) {
	map.put(a1[i], map.getOrDefault(a1[i], 0) + 1);
	}
	int c = 0;
	for (int i = 0; i < n2; i++) {
	if (map.containsKey(a2[i])) {
	int tmp = map.get(a2[i]);
	map.remove(a2[i]);
	for (int j = 0; j < tmp; j++) {
	a1[c] = a2[i];
	c++;
	}
	}
	}
	SortedSet<Integer> keySet = new TreeSet<>(map.keySet());
	for (int i : keySet) {
	int tmp = map.get(i);
	for (int j = 0; j < tmp; j++) {
	a1[c] = i;
	c++;
	}
	}
	}
	public static void printArray(int[] b1) {
	for(int i: b1) {
	System.out.println(i);
	}
	}
	public static void main(String[] args) {
	int[] d1= {45,15,23,8,5,12,26,444,888,151,12,23,45,15,56};
	int[] d2= {15,888,444,5,8,12,23};
	sortA1ByA2(d1,d2);
	printArray(d1);
	}
	}

view raw RelativeSorting.java hosted with ❤ by GitHub

Zero Sum Sub-arrays Count - Hashing Problems

Problem : Find the number of sub-arrays whose sum evaluates to zero.

Following is the implementation:

	package hashTables.problems;
	import java.util.HashMap;
	public class ZeroSumSubCount {
	public static int findSubarrayCount(int[] nums ,int n) {
	int count = 0, sum = 0;
	HashMap <Integer,Integer> map = new HashMap<>();
	map.put(0, 1);
	for (int i = 0; i < nums.length; i++) {
	sum += nums[i];
	if (map.containsKey(sum))
	count += map.get(sum);
	map.put(sum, map.getOrDefault(sum, 0) + 1);
	}
	return count;
	}
	public static void main(String[] args) {
	int arr4[]= {9,-10,-1,5,17,-18,6,19,-12,5,18,14,4,-19,11,8,-19,18,-20,14,8,-14,12,-12,16,-11,0,3,-19,16};
	System.out.println(findSubarrayCount(arr4, arr4.length));
	}
	}

view raw ZeroSumSubCount.java hosted with ❤ by GitHub

Largest Sub-array With Sum Zero - Hashing Problem

Problem : Find the maximum length of the largest sub-array with sum zero.

Following is the implementation, where we store the sum at every index in hashmap and look for sum already being present in hashmap(only possible if sum of the sub-array is zero):

	package hashTables.problems;
	import java.util.HashMap;
	public class LargestSubWithSumZero {
	public static int maxLen(int arr[], int n) {
	HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
	int sum = 0,maxLength = 0;
	for (int i = 0; i < n; i++) {
	sum += arr[i];
	if (arr[i] == 0 && maxLength == 0)
	maxLength = 1;
	if (sum == 0)
	maxLength = i + 1;
	Integer prevIndx = hM.get(sum);
	if (prevIndx != null)
	maxLength = Math.max(maxLength, i - prevIndx);
	else
	hM.put(sum, i);
	}
	return maxLength;
	}
	public static void main(String[] args) {
	int a6[]= {67,-3,3,-10,1,9,13,56};
	System.out.println(maxLen(a6, a6.length));
	}
	}

view raw LargestSubWithSumZero.java hosted with ❤ by GitHub

Four Sum - Hashing Problems

Problem : Find four elements in array whose sum equals to x.

Following is the implementation using hashmap:

	package hashTables.problems;
	import java.util.List;
	import java.util.ArrayList;
	import java.util.Arrays;
	public class FourSum {
	public static ArrayList<ArrayList<Integer>> fourSum(int[] arr, int k) {
	ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
	int n = arr.length;
	Arrays.sort(arr);
	int l, r;
	for(int i=0;i<n-3;i++) {
	if(i!=0 && arr[i]==arr[i-1])
	continue;
	for(int j=i+1;j<n-2;j++) {
	if(j!=i+1 && arr[j]==arr[j-1])
	continue;
	l=j+1;
	r=n-1;
	while(l<r) {
	if(arr[i]+arr[j]+arr[l]+arr[r]==k) {
	System.out.println(arr[i]+"--"+arr[j]+"--"+arr[l]+"--"+arr[r]);
	ArrayList<Integer> tmpList = new ArrayList<Integer>();
	tmpList.addAll(Arrays.asList(arr[i],arr[j],arr[l],arr[r]));
	list.add(tmpList);
	l++;
	r--;
	while (arr[l] == arr[l - 1] && (l < r)) l ++; // skip duplicates
	while (arr[r] == arr[r + 1] && (l < r)) r --; // skip duplicates
	}else if(arr[i]+arr[j]+arr[l]+arr[r]<k) {
	l++;
	}else if(arr[i]+arr[j]+arr[l]+arr[r]>k) {
	r--;
	}
	}
	}
	}
	return list;
	}
	public static void main(String[] args) {
	int[] a2= {88,84,3,51,54,99,32,60,76,68,39,12,26,86,94,39,95,70,34,78,67,1,97,2,17,92,52};
	fourSum(a2,179);
	}
	}

view raw FourSum.java hosted with ❤ by GitHub

Two Sum - Hashing Problem

Problem : Find two elements in an array whose sum is x.

Following is the implementation:

	package hashTables.problems;
	import java.util.HashMap;
	import java.util.Map;
	public class TwoSum {
	public static int[] twoSum(int[] a, int x) {
	int n = a.length;
	Map<Integer,Integer> m = new HashMap();
	for(int i=0;i<n;i++) {
	int k = a[i];
	int other = x-k;
	if(m.containsKey(other)) {
	return new int[] {other,k};
	}else {
	m.put(k, i);
	}
	}
	return new int[] {};
	}
	public static void main(String[] args) {
	int[] a = {1, 35, 4, 6, 10, 11};
	int x = 16;
	int[] y = twoSum(a, x);
	for(int i:y) {
	System.out.println(i);
	}
	}
	}

view raw TwoSum.java hosted with ❤ by GitHub

Longest Consequent Sub-sequence - Hashing Problem

To find longest consequent sub-sequence in an array, following is the implementation using hashmap:

	package hashTables.problems;
	import java.util.Arrays;
	import java.util.HashMap;
	import java.util.Map;
	public class LongestConseqSubSeq {
	public static int findLongestConseqSubseq(int a[], int n){
	Map<Integer,Integer> hm = new HashMap<>();
	int max =0,prevMax=0;
	Arrays.sort(a);
	for(int i=0;i<n;i++) {
	if(hm.containsKey(a[i]-1) && !hm.containsKey(a[i])) {
	prevMax++;
	if(prevMax>max) {
	max=prevMax;
	}
	}else if(!hm.containsKey(a[i]-1) && prevMax!=0) {
	prevMax=0;
	}
	hm.put(a[i],i);
	}
	return max+1;
	}
	public static void main(String[] args) {
	int a5[]= {86,77,15,93,35,86,92,49,21,62,27,90,59,63,26,40,26,72,36,11,68,67,29,82,30,62,23,67,35,29,2,22,58,69,67,93,56,11,42,29,73,21,19,84,37,98,24,15,70,13,26,91,80,56,73,62,70,96,81,5,25,84,27,36,5,46,29,13,57,24,95,82,45,14,67,34,64,43,50,87,8,76,78,88};
	System.out.println(findLongestConseqSubseq(a5,a5.length));
	}
	}

view raw LongestConseqSubSeq.java hosted with ❤ by GitHub

Maximum Distance Between Two Occurences Of Same Element - Hashing Problem

To find the maximum distance between two occurrences of same element, we can store the elements in hashmap and compare max index distance. Following is the implementation:

	package hashTables;
	import java.util.HashMap;
	import java.util.Map;
	public class MaxDistanceBtnOccurances {
	public static int maxDistance(int arr[], int n) {
	Map<Integer,Integer> hm = new HashMap<>();
	int max =0,prevMax=0;
	for(int i=0;i<n;i++) {
	if(hm.containsKey(arr[i])) {
	prevMax = i-hm.get(arr[i]);
	if(prevMax>max)
	max=prevMax;
	}else
	hm.put(arr[i],i);
	}
	return max;
	}
	public static void main(String[] args) {
	int a4[]= {3,2,1,2,1,4,5,8,6,7,4,2};
	System.out.println(maxDistance(a4, 12));
	}
	}

view raw MaxDistanceBtnOccurances.java hosted with ❤ by GitHub

Check If Two Arrays Are Equal - Hashing Problems

To check if two arrays are equals, lengths and elements along with their frequency need to be considered. For this, a hashmap can be used. Following is the implementation:

	package hashTables;
	import java.util.HashMap;
	import java.util.Map;
	public class EqualArrays {
	public static boolean check(long arr[],long brr[]){
	int n1= arr.length;
	int n2= brr.length;
	if(n1!=n2)
	return false;
	Map<Long,Integer> hm = new HashMap<>();
	for(int i=0;i<n1;i++) {
	hm.put(arr[i],hm.getOrDefault(arr[i], 0)+1);
	}
	for(int i=0;i<n1;i++) {
	long key = brr[i];
	if(!hm.containsKey(key))
	return false;
	else {
	int count = hm.get(key);
	if(count==0)
	return false;
	hm.put(key, --count);
	}
	}
	return true;
	}
	public static void main(String[] args) {
	long[] a1= {4,1,4,2,4,2,3,3,3,4};
	long[] a2= {1,2,2,3,3,3,4,4,4,4};
	long[] a3= {1,2,2,3,3,3,4,4,4,3};
	if(check(a1,a2))
	System.out.println("a2 equal arrays");
	if(check(a1,a3))
	System.out.println("a3 equal arrays");
	}
	}

view raw EqualArrays.java hosted with ❤ by GitHub

Linear Probing - Coursera Algorithms

Linear probing is used to resolve collisions in hashing. It takes less space and has better cache performance.

An array of size M > number of elements N is used such that:

1. Hash - map key to i between 0 and M-1.
2. Insert - at table index i, if not free - try i+1, i+2 etc

3. Search - search table index i, if occupied and no match - try i+1, i+2 etc

Following is the implementation :

	package hashTables;
	public class LinearProbing<Key,Value> {
	private int M=30001;
	private Value[] vals = (Value[]) new Object[M];
	private Key[] keys = (Key[]) new Object[M];
	private int hash(Key key) {
	return (key.hashCode() & 0x7fffffff)%M;
	}
	public void put(Key key, Value val) {
	int i;
	for(i=hash(key);keys[i]!=null;i=(i+1)%M)
	if(keys[i].equals(key))
	break;
	keys[i] = key;
	vals[i] = val;
	}
	public Value get(Key key) {
	for(int i=hash(key);keys[i]!=null;i=(i+1)%M)
	if(keys[i].equals(key))
	return vals[i];
	return null;
	}
	public void print() {
	int l = keys.length;
	for(int j=0;j<l;j++) {
	if(keys[j]!=null)
	System.out.println(j+"----"+keys[j]+"---"+vals[j]);
	}
	}
	public static void main(String[] args) {
	LinearProbing lp = new LinearProbing();
	for(int i=0;i<100;i++) {
	lp.put("key"+i,"val"+i);
	}
	lp.print();
	System.out.println("fetch key9 "+lp.get("key9"));
	}
	}

view raw LinearProbing.java hosted with ❤ by GitHub

Separate Chaining - Coursera Algorithms

To deal with collisions in hashing, separate chaining implementation can be used, where M linked lists(<number of elements N) are used such that :

1. Hash - map key to i between 0 and M-1.
2. Insert - at the front of ith chain.

3. Search - in ith chain.

Easier to implement and clustering less sensitive to poorly designed hash function.

Following is the implementation:

	package hashTables;
	public class SeparateChaining<Key,Value> {
	private int M=97;
	private Node[] st = new Node[M];
	private static class Node{
	private Object key;
	private Object val;
	private Node next;
	Node(Object key,Object val,Node next) {
	this.key = key;
	this.val=val;
	this.next=next;
	}
	}
	private int hash(Key key) {
	return (key.hashCode() & 0x7fffffff)%M;
	}
	public Value get(Key key) {
	int i = hash(key);
	for(Node x=st[i];x!=null;x=x.next)
	if(key.equals(x.key))
	return (Value) x.val;
	return null;
	}
	public void put(Key key, Value val) {
	int i = hash(key);
	for(Node x=st[i];x!=null;x=x.next) {
	if(key.equals(x.key)) {
	x.val=val;
	return;
	}
	}
	st[i] = new Node(key,val,st[i]);
	}
	public void print() {
	SeparateChaining sc = new SeparateChaining();
	for(int i=0;i<M;i++) {
	Node n = st[i];
	if(n!=null) {
	System.out.print(i+"----"+sc.hash(i)+":"+n.val);
	while(n.next!=null) {
	n = n.next;
	System.out.print(", "+n.val);
	}
	System.out.println();
	}
	}
	}
	public static void main(String[] args) {
	SeparateChaining sc = new SeparateChaining();
	for(int i=0;i<100;i++) {
	sc.put("key"+i,"val"+i);
	}
	sc.print();
	System.out.println("fetch key99 "+sc.get("key99"));
	}
	}

view raw SeparateChaining.java hosted with ❤ by GitHub

Hash Functions - Coursera Algorithms

We can do better than the sequential/binary search or search through BST/red-black BST, by storing the data in key-indexed table. Hash functions compute the array index from key. We need to handle the hash implementation, equality test and collision resolution when two keys hash to the same index.

There are several hashing implementations, some of them being :
1. 31*initial_hash_value+ current element value or current object hashcode.
2. Modular - Math.abs(key.hashCode() & 0x7fffffff)%M returning a hash between 0 and M-1

Following code experiments with what happens when we override equals/hashcode:

	package hashTables;
	import java.util.HashMap;
	import java.util.Map;
	public class ExperimentEqHC {
	static int M=97;
	public static class Person0<Key,Value>{
	int id;
	public Person0(int id) {
	this.id = id;
	}
	public int hashCode() {
	return this.id;//(key.hashCode() & 0x7fffffff)%M;
	}
	}
	public static class Person1<Key,Value>{
	int id;
	public Person1(int id) {
	this.id = id;
	}
	public boolean equals(Object p) {
	if(((Person1)p).id==this.id)
	return true;
	else
	return false;
	}
	}
	public static class Person2<Key,Value>{
	int id;
	public Person2(int id) {
	this.id = id;
	}
	@Override
	public int hashCode() {
	//return (key.hashCode() & 0x7fffffff)%M;
	return this.id;
	}
	public boolean equals(Person2 p) {
	if(p.id==this.id)
	return true;
	else
	return false;
	}
	}
	public static class Person3<Key,Value>{
	int id;
	public Person3(int id) {
	this.id = id;
	}
	public int hashCode() {
	return this.id;//(key.hashCode() & 0x7fffffff)%M;
	}
	public boolean equals(Object p) {
	if(((Person3)p).id==this.id)
	return true;
	else
	return false;
	}
	}
	public static void main(String[] args) {
	Person0 p01 = new Person0(1);
	Person0 p02 = new Person0(1);
	System.out.println("p0 hashcodes "+p01.hashCode()+"---"+p02.hashCode());//1
	Map<Person0,Integer> m1 = new HashMap<>();
	m1.put(p01, 10);
	m1.put(p02, 20);
	for(Person0 p : m1.keySet()) {
	System.out.println(m1.get(p).toString()+"---"+m1.get(p).hashCode());
	}
	if(p01.equals(p02))
	System.out.println("hash overriden and equal");//not equal - doesn't print
	Person1 p11 = new Person1(1);
	Person1 p12 = new Person1(1);
	System.out.println("p1 hashcodes "+p11.hashCode()+"---"+p12.hashCode());//random values
	Map<Person1,Integer> m2 = new HashMap<>();
	m2.put(p11, 10);
	m2.put(p12, 20);
	for(Person1 p : m2.keySet()) {
	System.out.println(m2.get(p).toString()+"---"+m2.get(p).hashCode());
	}
	if(p11.equals(p12))
	System.out.println("equals overriden and equal");//equal
	Person2 p21 = new Person2(1);
	Person2 p22 = new Person2(1);
	System.out.println("p2 hashcodes "+p21.hashCode()+"---"+p22.hashCode());//1
	Map<Person2,Integer> m3 = new HashMap<>();
	m3.put(p21, 10);
	m3.put(p22, 20);
	for(Person2 p : m3.keySet()) {
	System.out.println(m3.get(p).toString()+"---"+m3.get(p).hashCode());
	}
	if(p21.equals(p22))
	System.out.println("hash+equals person overriden and equal");//equal
	Person3 p31 = new Person3(1);
	Person3 p32 = new Person3(1);
	System.out.println("p3 hashcodes "+p31.hashCode()+"---"+p32.hashCode());//1
	Map<Person3,Integer> m4 = new HashMap<>();
	m4.put(p31, 10);
	m4.put(p32, 20);
	for(Person3 p : m4.keySet()) {
	System.out.println(m4.get(p).toString()+"---"+m4.get(p).hashCode());//only one element - as hash matches, first one gets replaced
	}
	if(p31.equals(p32))
	System.out.println("hash+equals obj overriden and equal");//equal
	}
	}

view raw ExperimentEqHC.java hosted with ❤ by GitHub

Heap Sort - Coursera Algorithms

Heap Sort is an in place sort that builds a max binary heap and then repeatedly deletes the maximum element. It's not stable and it's inner loop takes longer than Quick Sort. It has poor cache usage. To build a heap, it takes O(N) and for sort, it takes O(NlogN).

Following is the program:

	package sorting.heapSort;
	public class HeapSort<Key extends Comparable<Key>> {
	public void sort(Comparable[] a) {
	int indx = a.length-1;
	for(int k=indx/2;k>=1;k--) {
	sink(a,k,indx);
	}
	print(a); //max heap
	while(indx>1) {
	exchange(a,1,indx);
	sink(a,1,--indx);
	}
	}
	public boolean less(Comparable[] a,int aa, int bb) {
	return a[aa].compareTo(a[bb])<0;
	}
	public void exchange(Comparable[] a,int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public void print(Comparable[] a) {
	System.out.println();
	int indx = a.length-1;
	for(int i=1;i<=indx;i++) {
	System.out.print(a[i]+"--");
	}
	}
	private void sink(Comparable[] a,int k, int indx) {
	while(2*k <= indx) {
	int j = 2*k;
	if(j<indx && less(a,j,j+1)) j++;
	if(!less(a,k,j)) break;
	exchange(a,k, j);
	k=j;
	}
	}
	public static void main(String[] args) {
	HeapSort<String> pq = new HeapSort<String>();
	Integer[] a = {-1,5,2,4,6,1,3};
	// String[] a = {"*","S","O","R","T","E","X","A","M","P","L","E"};
	pq.print(a);
	pq.sort(a);
	pq.print(a);
	}
	}

view raw HeapSort.java hosted with ❤ by GitHub

Related Posts:

Binary Heap

Binary Heap - Coursera Algorithms

A binary tree is either empty or points to a root node with links to left and right binary trees. A tree is complete if it is balanced perfectly, excluding the bottom level. A binary heap is an array representation of a heap ordered complete binary tree.

Max node is root at a[1]. For a node k, it's parent is at k/2 and it's children are at 2k and 2k+1.
Swim: When a child node is greater than parent, keep exchanging them till they are ordered.
Sink: When a parent node is lesser than child, keep exchanging them till they are ordered.
In insert operation, add the child at end and swim it. --> O(logN)
In delete operation, exchange root with node at end and sink the top node. -->O(logN)

Following is the program:

	package priorityQueue;
	public class BinaryHeap<Key extends Comparable<Key>> {
	private Key[] pq;
	private int indx;
	public BinaryHeap(int cap) {
	pq = (Key[]) new Comparable[cap+1];
	}
	public boolean less(int a, int b) {
	return pq[a].compareTo(pq[b])<0;
	}
	public void exchange(int i, int j) {
	Key tmp = pq[i];
	pq[i] = pq[j];
	pq[j] = tmp;
	}
	public boolean isEmpty() {
	return (indx==0);
	}
	public void resize(int cap) {
	Key[] copy = (Key[])new Comparable[cap];
	for(int i=1;i<indx;i++) {
	copy[i]=pq[i];
	}
	pq = copy;
	}
	public void insert(Key k) {
	int l = pq.length;
	if(++indx==l) {
	resize(2*l);
	}
	pq[indx]=k;
	swim(indx);
	}
	public Key delMax() {
	Key max=pq[1];
	exchange(1, indx--);
	sink(1);
	pq[indx+1] = null;
	return max;
	}
	public void print() {
	System.out.println();
	for(int i=1;i<indx+1;i++) {
	System.out.print(pq[i]+"--");
	}
	}
	private void swim(int k) {
	while(k>1 && less(k/2,k)) {
	exchange(k,k/2);
	k=k/2;
	}
	}
	private void sink(int k) {
	while(2*k <= indx) {
	int j = 2*k;
	if(j<indx && less(j,j+1)) j++;
	if(!less(k,j)) break;
	exchange(k, j);
	k=j;
	}
	}
	public static void main(String[] args) {
	BinaryHeap<Integer> pqi = new BinaryHeap<Integer>(5);
	pqi.insert(5);
	pqi.insert(2);
	pqi.insert(4);
	pqi.insert(6);
	pqi.insert(1);
	pqi.insert(3);
	pqi.insert(7);
	pqi.print();
	System.out.println("delMax "+pqi.delMax());
	pqi.print();
	BinaryHeap<String> pq = new BinaryHeap<String>(5);
	pq.insert("P");
	pq.insert("Q");
	pq.insert("E");
	pq.print();
	System.out.println("delMax "+pq.delMax());
	pq.print();
	pq.insert("X");
	pq.insert("A");
	pq.insert("M");
	pq.print();
	System.out.println("delMax "+pq.delMax());
	pq.print();
	}
	}

view raw BinaryHeap.java hosted with ❤ by GitHub

Maximum Priority Queue - Coursera Algorithms

Max priority queues pick the maximum element for deletion instead of picking the first in element as done in Queues. It takes O(N) for extracting the max. Following is the program:

	package priorityQueue;
	public class UnorderedMaxPQ<Key extends Comparable<Key>>{
	private Key[] pq;
	private int indx;
	public UnorderedMaxPQ(int cap) {
	pq = (Key[]) new Comparable[cap];
	}
	public boolean less(int a, int b) {
	return pq[a].compareTo(pq[b])<0;
	}
	public void exchange(int i, int j) {
	Key tmp = pq[i];
	pq[i] = pq[j];
	pq[j] = tmp;
	}
	public boolean isEmpty() {
	return (indx==0);
	}
	public void insert(Key k) {
	pq[indx++]=k;
	}
	public Key delMax() {
	int max=0;
	for(int i=1;i<indx;i++)
	if(less(max,i)) max=i;
	exchange(max, indx-1);
	return pq[--indx];
	}
	public void print() {
	System.out.println();
	for(int i=0;i<indx;i++) {
	System.out.print(pq[i]+"--");
	}
	}
	public static void main(String[] args) {
	UnorderedMaxPQ<String> pq = new UnorderedMaxPQ<String>(5);
	pq.insert("P");
	pq.insert("Q");
	pq.insert("E");
	pq.print();
	System.out.println("delMax "+pq.delMax());
	pq.print();
	pq.insert("X");
	pq.insert("A");
	pq.insert("M");
	pq.print();
	System.out.println("delMax "+pq.delMax());
	pq.print();
	}
	}

view raw UnorderedMaxPQ.java hosted with ❤ by GitHub

Three Way Quick Sort - Coursera Algorithms

Three Way Quick Sort uses multiple partition elements, such that the there are no larger entries to their left and no smaller entries to their right. It is in place, but not a stable sort. This is used to deal with duplicate elements.

Time complexity: O(NlgN)


Following is the program, partition elements are from lt to gt:

	package sorting.quickSort;
	import sorting.insertionSort.InsertionSort;
	public class ThreeWayQuickSort {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public static void shuffle(Comparable[] a) {
	int n = a.length;
	for(int i=0;i<n;i++) {
	int r = (int)Math.random()*(i+1);
	exchange(a, i, r);
	}
	}
	public static void sort(Comparable[] a, int lo, int hi) {
	int cutoff=7;
	if(hi<=lo+ cutoff -1) {
	InsertionSort is = new InsertionSort();
	is.sort(a);
	}
	if(hi<=lo) return;
	int lt=lo,gt=hi;
	Comparable v=a[lo];
	int i=lo;
	while(i<=gt) {
	int cmp = a[i].compareTo(v);
	if(cmp<0) exchange(a,lt++,i++);
	else if(cmp>0) exchange(a,i,gt--);
	else i++;
	}
	sort(a,lo,lt-1);
	sort(a,gt+1,hi);
	}
	public static void sort(Comparable[] a) {
	shuffle(a);
	sort(a,0,a.length-1);
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void main(String[] args) {
	Comparable[] a = {5,2,3,1,1,3,2,4,5,6,7,2,2,8,4,3,2,9,6};
	//Comparable[] a = {5,2,4,6,1,3,5,2,4,6,1,3};
	print(a);
	sort(a);
	print(a);
	}
	}

view raw ThreeWayQuickSort.java hosted with ❤ by GitHub

Related Posts: 

Quick Sort

Insertion Sort 

Quick Select - Coursera Algorithms

Quick select finds k^th smallest element by partitioning. It takes linear time and O(N²) in worst case.

Following is the program:

	package sorting.quickSort;
	public class QuickSelect {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public static void shuffle(Comparable[] a) {
	int n = a.length;
	for(int i=0;i<n;i++) {
	int r = (int)Math.random()*(i+1);
	exchange(a, i, r);
	}
	}
	public static int partition(Comparable[] a, int lo, int hi) {
	int i=lo,j=hi+1;
	while(true) {
	while(less(a[++i],a[lo])) {
	if(i==hi) break;
	}
	while(less(a[lo],a[--j])) {
	if(j==lo) break;
	}
	if(i>=j) break;
	exchange(a,i,j);
	}
	exchange(a,lo,j);
	return j;
	}
	public static Comparable select(Comparable[] a, int k) {
	shuffle(a);
	int lo = 0, hi = a.length - 1;
	while (hi > lo)
	{
	int j = partition(a, lo, hi);
	if (j < k) lo = j + 1;
	else if (j > k) hi = j - 1;
	else return a[k];
	}
	return a[k];
	}
	public static void main(String[] args) {
	Comparable[] a1 = {5,2,4,6,1,3};
	int i = 3;
	System.out.println("element at index "+i+ " is "+ select(a1,i));
	}
	}

view raw QuickSelect.java hosted with ❤ by GitHub

Quick Sort - Coursera Algorithms

Quick Sort uses a partition element, such that the there are no larger entries to it's left and no smaller entries to it's right. It is in place, but not a stable sort.

Time complexity: O(NlgN)
Worst case : O(N²)

Following is the program:

	package sorting.quickSort;
	import sorting.insertionSort.InsertionSort;
	public class QuickSort {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public static void shuffle(Comparable[] a) {
	int n = a.length;
	for(int i=0;i<n;i++) {
	int r = (int)Math.random()*(i+1);
	exchange(a, i, r);
	}
	}
	public static int partition(Comparable[] a, int lo, int hi) {
	int i=lo,j=hi+1;
	while(true) {
	while(less(a[++i],a[lo])) {
	if(i==hi) break;
	}
	while(less(a[lo],a[--j])) {
	if(j==lo) break;
	}
	if(i>=j) break;
	exchange(a,i,j);
	}
	exchange(a,lo,j);
	return j;
	}
	public static void sort(Comparable[] a, int lo, int hi) {
	int cutoff=7;
	if(hi<=lo+ cutoff -1) {
	InsertionSort is = new InsertionSort();
	is.sort(a);
	}
	if(hi<=lo) return;
	//int m = median(a,lo,lo+(hi-lo)/2,hi);
	//exchange(a, lo, m);
	int p = partition(a,lo,hi);
	sort(a,lo,p-1);
	sort(a,p+1,hi);
	}
	public static void sort(Comparable[] a) {
	shuffle(a);
	sort(a,0,a.length-1);
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void main(String[] args) {
	Comparable[] a = {18,8,16,9,12,5,7,2,4,14,6,1,11,3,10,13,15,19,17,20};
	print(a);
	sort(a);
	print(a);
	Comparable[] a1 = {5,2,4,6,1,3};
	print(a1);
	sort(a1);
	print(a1);
	}
	}

view raw QuickSort.java hosted with ❤ by GitHub

Merge Sort - Coursera Algorithms

Merge sort uses divide and conquer approach to sort the elements. It takes at most NlgN compares and 6NlgN array accesses with total running time of NlgN.

Following is an optimized merge sort - it uses insertion sort for less number of elements. Please see Insertion Sort for the insertion sort algorithm. It also has a method for bottom up merge sort which is not as efficient as the recursive merge sort.

	package sorting.mergeSort;
	import sorting.insertionSort.InsertionSort;
	public class MergeSort {
	static Comparable[] aux;
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public static void merge(Comparable[] a,Comparable[] aux, int lo, int mid, int hi) {
	for(int k=lo;k<=hi;k++) {
	aux[k] = a[k];
	}
	int i=lo,j=mid+1;
	for(int k=lo;k<=hi;k++) {
	if(i>mid) a[k] =aux[j++];
	else if(j>hi) a[k] = aux[i++];
	else if(less(aux[j],aux[i])) a[k] = aux[j++];
	else a[k]=aux[i++];
	}
	}
	public static void sort(Comparable[] a,Comparable[] aux, int lo, int hi) {
	int cutoff=7;
	if(hi<=lo+ cutoff -1) {
	InsertionSort is = new InsertionSort();
	is.sort(a);
	}
	if(hi<=lo) return;
	int mid = lo + (hi-lo)/2;
	sort(a,aux,lo,mid);
	sort(a,aux,mid+1,hi);
	if(!less(a[mid+1],a[mid]))return;
	merge(a,aux,lo,mid,hi);
	}
	public static void sort(Comparable[] a) {
	aux = new Comparable[a.length];
	sort(a,aux,0,a.length-1);
	}
	public static void bottomUpMS(Comparable[] a) {
	int n = a.length;
	Comparable[] aux = new Comparable[n];
	for(int sz=1; sz<n;sz=2*sz) {
	for(int lo=0;lo<n-sz;lo+=2*sz) {
	merge(a,aux,lo,lo+sz-1,Math.min(lo+2*sz-1,n-1));
	}
	}
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void main(String[] args) {
	Comparable[] a = {18,8,16,9,12,5,7,2,4,14,6,1,11,3,10,13,15,19,17,20};
	print(a);
	sort(a);
	print(a);
	Comparable[] a1 = {5,2,4,6,1,3};
	print(a1);
	bottomUpMS(a1);
	print(a1);
	}
	}

view raw MergeSort.java hosted with ❤ by GitHub

Related Posts: 

Insertion Sort

Shell Sort - Coursera Algorithms

Shell sort moves entries by more than one position at a time. It is basically insertion sort with a stride length h - it considers h interleaved sequences and sorts them using insertion sort. When the increment(h) is big, the sub-arrays are smaller and when the increment gets shorter in subsequent iterations, the array is already partially sorted. In both cases, insertion sort works great and hence, it's the best option here.

The optimal value for h is provided by Knuth as 3X+1, but no accurate model has been found for this algorithm yet.

It takes O(N3/2) compares in worst case. It's fast unless array size is large and it has less footprint for code. These make it a perfect choice for hardware sort prototype, linux/kernel, embedded systems etc.

Following is the program:

	package sorting.shellSort;
	public class ShellSort {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	private static boolean isSorted(Comparable[] a) {
	int n = a.length;
	for(int i=1;i<n;i++) {
	if(less(a[i],a[i-1]))
	return false;
	}
	return true;
	}
	public void sort(Comparable[] a) {
	int n = a.length;
	int h=1;
	while(h<n/3) {
	h = 3*h + 1;
	}
	while(h>=1) {
	for(int i=h;i<n;i++) {
	for(int j=i;j>=h && less(a[j],a[j-h]);j-=h) {
	exchange(a,j,j-h);
	}
	}
	h = h/3;
	}
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void main(String[] args) {
	//Comparable[] a = {5,7,2,4,6,8,1,3,9};
	Comparable[] a = {5,2,4,6,1,3};
	print(a);
	ShellSort insertionSort = new ShellSort();
	insertionSort.sort(a);
	print(a);
	}
	}

view raw ShellSort.java hosted with ❤ by GitHub

Related Posts: 

Insertion Sort

Insertion Sort - Coursera Algorithms

Insertion Sort swaps an element with a larger entry to it's left.

It take ~1/4 N2 compares and ~1/4 N2 exchanges.
Best case(already sorted) : N-1 compares and zero exchanges.
Worst case(reverse sorted):  ~1/2 N2 compares and ~1/2 N2 exchanges.
Partially sorted(when number of inversions <= cN): linear time as number of exchanges equal the number of inversions.

Following is the program, it also uses shuffle to make the order as random as possible. This is done by swapping each element with a random index r such that r is between 0 and iteration i. This takes linear time.

	package sorting.insertionSort;
	public class InsertionSort {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	private static boolean isSorted(Comparable[] a) {
	int n = a.length;
	for(int i=1;i<n;i++) {
	if(less(a[i],a[i-1]))
	return false;
	}
	return true;
	}
	public void sort(Comparable[] a) {
	int n = a.length;
	for(int i=1;i<n;i++) {
	for(int j=i;j>0;j--) {
	if(less(a[j],a[j-1]))
	exchange(a,j,j-1);
	else
	break;
	}
	}
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void shuffle(Comparable[] a) {
	int n = a.length;
	for(int i=0;i<n;i++) {
	int r = (int)Math.random()*(i+1);
	exchange(a, i, r);
	}
	}
	public static void main(String[] args) {
	Comparable[] a = {5,2,4,6,1,3};
	shuffle(a);
	print(a);
	InsertionSort insertionSort = new InsertionSort();
	insertionSort.sort(a);
	print(a);
	}
	}

view raw InsertionSort.java hosted with ❤ by GitHub

Selection Sort - Coursera Algorithms

Selection sort finds the minimum element and swaps it with the first element, till the complete array is sorted. It takes N²/2 compares and N exchanges.

Following is the program:

	package sorting.selectionSort;
	public class SelectionSort {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	private static boolean isSorted(Comparable[] a) {
	int n = a.length;
	for(int i=1;i<n;i++) {
	if(less(a[i],a[i-1]))
	return false;
	}
	return true;
	}
	public void sort(Comparable[] a) {
	int n = a.length;
	int min = 0;
	for(int j=0;j<n;j++) {
	min = j;
	for(int i=j+1;i<n;i++) {
	if(less(a[i],a[min])){
	min = i;
	}
	}
	exchange(a,min,j);
	}
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void main(String[] args) {
	Comparable[] a = {5,2,4,6,1,3};
	print(a);
	SelectionSort selectionSort = new SelectionSort();
	selectionSort.sort(a);
	print(a);
	}
	}

view raw SelectionSort.java hosted with ❤ by GitHub

Decimal To Binary Conversion Using Stack

Stack can be used to convert a number into it's binary form.

1. Push the remainder into stack after dividing the number by 2.
2. Keep doing 1, till number>0.
3. Pop the binary remainders 1/0 to get the binary form.

 Following is the program:

	package stacks;
	import java.util.Iterator;
	public class BinaryConvStack {
	public String convert(int n) {
	GenericStackResizeArrayItr<Integer> bitStack = new GenericStackResizeArrayItr<Integer>(5);
	StringBuffer sb = new StringBuffer();
	while(n>0) {
	bitStack.push(n%2);
	n=n/2;
	}
	Iterator<Integer> itr = bitStack.iterator();
	while(itr.hasNext()) {
	Integer i = bitStack.pop();
	if(i==null)
	break;
	sb.append(i);
	}
	return sb.toString();
	}
	public static void main(String[] args) {
	BinaryConvStack stack = new BinaryConvStack();
	int i = 50;
	System.out.println(i+" in binary is "+ stack.convert(i));
	i=12345678;
	System.out.println(i+" in binary is "+ stack.convert(i));
	}
	}

view raw BinaryConvStack.java hosted with ❤ by GitHub

 

Arithmetic Expression Evaluation Using Stack

Arithmetic expressions can be evaluated using two stacks - one for operands and other for numeric values.

Algorithm:

1. If element is numeric, push to numeric stack.
2. If element is operand, push to operand stack.
3. If element is "(", ignore. 
4. If element is ")", pop operand from operand stack and pop two numerics from numeric stack - perform the operation and push the result back into numeric stack. 

 Following is the program based on the generic stack implementation using arrays.

	package stacks;
	import java.util.Arrays;
	import java.util.List;
	public class TwoStackDijkstra {
	public int arith(int a, int b, String opr) {
	if(opr.equals("+")) {
	return a+b;
	}else if(opr.equals("-")) {
	return b-a;
	}else if(opr.equals("*")) {
	return a*b;
	}else if(opr.equals("/")) {
	return b/a;
	}else if(opr.equals("%")) {
	return b%a;
	}
	return -1;
	}
	public int evaluate(String arith) {
	String[] operators = {"+","-","*","/","%"};
	List oprList = Arrays.asList(operators);
	GenericStackResizeArrayItr<Integer> valStack = new GenericStackResizeArrayItr<Integer>(5);
	GenericStackResizeArrayItr<String> oprStack = new GenericStackResizeArrayItr<String>(5);
	String[] arithExpr = arith.split("");
	for(String item : arithExpr) {
	if(oprList.contains(item)) {
	oprStack.push(item);
	}else if(item.equals(")")) {
	valStack.push(arith(valStack.pop(), valStack.pop(), oprStack.pop()));
	}else if(item.equals("(")) {
	continue;
	}else {
	valStack.push(Integer.parseInt(item));
	}
	}
	return valStack.pop();
	}
	public static void main(String[] args) {
	TwoStackDijkstra twoStack = new TwoStackDijkstra();
	String s = "((1+2)*(5-3))";
	System.out.println("value of "+ s + " is "+twoStack.evaluate(s));
	s = "(((1+2)*(5-3))/((1+2)*(5-3)))";
	System.out.println("value of "+ s + " is "+twoStack.evaluate(s));
	}
	}

view raw TwoStackDijkstra.java hosted with ❤ by GitHub

Generic Queue Using Resized Array And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a queue from client, we can use Generics and Iterator.

Following is the program:

	package queues;
	import java.util.Iterator;
	public class GenericQueueResizeArrayItr<Item> implements Iterable<Item>{
	public class ArrayIterator implements Iterator<Item>{
	private int i = fwdIndex;
	@Override
	public boolean hasNext() {
	return (i<bckIndex);
	}
	@Override
	public Item next() {
	return queue[i++];
	}
	}
	@Override
	public Iterator<Item> iterator() {
	return new ArrayIterator();
	}
	int fwdIndex=0, bckIndex=0;
	Item[] queue;
	public GenericQueueResizeArrayItr(int cap) {
	queue = (Item[]) new Object[cap];
	}
	public void enqueue(Item s) {
	int l = queue.length;
	if(bckIndex==l) {
	resize(2*l);
	}
	queue[bckIndex++] = s;
	if(isEmpty()) {
	fwdIndex = bckIndex;
	}
	}
	public Item dequeue() {
	if(isEmpty()) {
	System.out.println("empty Q");
	return null;
	}
	int l = queue.length;
	if(bckIndex==l/2) {
	resize(l/4);
	}
	Item s = queue[fwdIndex];
	queue[fwdIndex++] = null;
	return s;
	}
	public int size() {
	return (bckIndex-fwdIndex);
	}
	public boolean isEmpty() {
	return (size()==0);
	}
	public void print() {
	System.out.println("==========================");
	for(int i=fwdIndex;i<bckIndex;i++) {
	System.out.println(queue[i]);
	}
	}
	public void resize(int cap) {
	Item[] copy = (Item[])new Object[cap];
	for(int i=fwdIndex;i<bckIndex;i++) {
	copy[i]=queue[i];
	}
	queue = copy;
	}
	public int length() {
	return queue.length;
	}
	public static void main(String[] args) {
	GenericQueueResizeArrayItr<String> queue = new GenericQueueResizeArrayItr<String>(5);
	queue.enqueue("to");
	queue.enqueue("be");
	queue.enqueue("or");
	queue.enqueue("not");
	queue.enqueue("to");
	queue.print();
	System.out.println("stack util is "+queue.size()+" out of "+queue.length());
	queue.enqueue("be");
	System.out.println("stack util is "+queue.size()+" out of "+queue.length());
	//queue.print();
	System.out.println("-------------Iterator-----------");
	for(String s: queue) {
	System.out.println(s);
	}
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	queue.print();
	//===========Integer===============
	GenericQueueResizeArrayItr<Integer> queueInt = new GenericQueueResizeArrayItr<>(5);
	queueInt.enqueue(1);
	queueInt.enqueue(2);
	queueInt.enqueue(3);
	queueInt.enqueue(4);
	queueInt.enqueue(5);
	queueInt.enqueue(6);
	//queueInt.print();
	System.out.println("-------------Iterator-----------");
	for(Integer i: queueInt) {
	System.out.println(i);
	}
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	queueInt.print();
	}
	}

view raw GenericQueueResizeArrayItr.java hosted with ❤ by GitHub

Generic Queue Using Linked List And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a queue from client, we can use Generics and Iterator.

Following is the program:

	package queues;
	import java.util.Iterator;
	public class GenericQueueLLItr<Item> implements Iterable<Item> {
	Node first;
	Node last;
	static int size;
	public class Node{
	Item value;
	Node next;
	public Node(Item s) {
	this.value = s;
	}
	}
	public class ListIterator implements Iterator<Item>{
	private Node current = first;
	@Override
	public boolean hasNext() {
	return (current!=null);
	}
	@Override
	public Item next() {
	Item val = current.value;
	current = current.next;
	return val;
	}
	}
	@Override
	public Iterator<Item> iterator() {
	return new ListIterator();
	}
	public void enqueue(Item s) {
	Node prevLast = last;
	last = new Node(s);
	if(!isEmpty())
	prevLast.next = last;
	else {
	first = last;
	}
	size++;
	}
	public Item dequeue() {
	if(isEmpty()) {
	System.out.println("queue empty");
	return null;
	}
	Item s = first.value;
	first = first.next;
	size--;
	return s;
	}
	public boolean isEmpty() {
	return (first==null);
	}
	public int size() {
	return size;
	}
	public void print() {
	System.out.println("==========================");
	Node n = first;
	while(n!=null) {
	System.out.println(n.value);
	n = n.next;
	}
	}
	public static void main(String[] args) {
	//===========String===============
	GenericQueueLLItr<String> queue = new GenericQueueLLItr<String>();
	queue.enqueue("to");
	queue.enqueue("be");
	queue.enqueue("or");
	queue.enqueue("not");
	queue.enqueue("to");
	queue.enqueue("be");
	//queue.print();
	System.out.println("-------------Iterator-----------");
	for(String s: queue) {
	System.out.println(s);
	}
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	queue.print();
	//===========Integer===============
	GenericQueueLLItr<Integer> queueInt = new GenericQueueLLItr<>();
	queueInt.enqueue(1);
	queueInt.enqueue(2);
	queueInt.enqueue(3);
	queueInt.enqueue(4);
	queueInt.enqueue(5);
	queueInt.enqueue(6);
	//queueInt.print();
	System.out.println("-------------Iterator-----------");
	for(Integer i: queueInt) {
	System.out.println(i);
	}
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	queueInt.print();
	}
	}

view raw GenericQueueLLItr.java hosted with ❤ by GitHub

Generic Stack Using Resized Array And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a stack from client, we can use Generics and Iterator.

Following is the program:

	package stacks;
	import java.util.Iterator;
	public class GenericStackResizeArrayItr<Item> implements Iterable<Item>{
	Item[] stack;
	int index=0;
	public GenericStackResizeArrayItr(int cap) {
	stack = (Item[])new Object[cap];
	}
	public class ArrayIterator implements Iterator<Item>{
	private int i=index;
	@Override
	public boolean hasNext() {
	return (i>0);
	}
	@Override
	public Item next() {
	return stack[--i];
	}
	}
	@Override
	public Iterator<Item> iterator() {
	// TODO Auto-generated method stub
	return new ArrayIterator();
	}
	public void push(Item s) {
	int l = stack.length;
	if(index==l) {//full array-double size
	resize(2*l);
	}
	stack[index++] = s;
	}
	public int size() {
	return index;
	}
	public int length() {
	return stack.length;
	}
	public boolean isEmpty() {
	return (index==0);
	}
	public Item pop() {
	if(isEmpty()) {
	System.out.println("stack empty");
	return null;
	}
	int l = stack.length;
	if(index<=l/4) {//25% of array is filled-half the array
	resize(l/2);
	}
	Item s = stack[--index];
	stack[index] = null;
	return s;
	}
	public void print() {
	System.out.println("============================");
	for(int i=0;i<index;i++) {
	System.out.println(stack[i]);
	}
	}
	public void resize(int cap) {
	Item copy[] = (Item[])new Object[cap];
	for(int i=0;i<index;i++) {
	copy[i]=stack[i];
	}
	stack = copy;
	}
	public static void main(String[] args) {
	GenericStackResizeArrayItr<String> stack = new GenericStackResizeArrayItr<String>(5);
	stack.push("to");
	stack.push("be");
	stack.push("or");
	stack.push("not");
	stack.push("to");
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.push("be");
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	//stack.print();
	System.out.println("-------------Iterator-----------");
	for(String s: stack) {
	System.out.println(s);
	}
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	//Integer
	GenericStackResizeArrayItr<Integer> stack1 = new GenericStackResizeArrayItr<Integer>(5);
	stack1.push(1);
	stack1.push(2);
	stack1.push(3);
	stack1.push(4);
	stack1.push(5);
	System.out.println("stack util is "+stack1.size()+" out of "+stack1.length());
	stack1.push(6);
	System.out.println("stack util is "+stack1.size()+" out of "+stack1.length());
	//stack1.print();
	System.out.println("-------------Iterator-----------");
	for(Integer s: stack1) {
	System.out.println(s);
	}
	stack1.pop();
	stack1.pop();
	stack1.print();
	System.out.println("stack util is "+stack1.size()+" out of "+stack1.length());
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.print();
	System.out.println("stack util is "+stack1.size()+" out of "+stack1.length());
	}
	}

view raw GenericStackResizeArrayItr.java hosted with ❤ by GitHub

Generic Stack Using Linked List And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a stack from client, we can use Generics and Iterator.

Following is the program:

	package stacks;
	import java.util.Iterator;
	public class GenericStackLLIterator<Item> implements Iterable<Item> {
	private Node first = null;
	static int size = 0;
	public class Node{
	Item value;
	Node next;
	}
	@Override
	public Iterator<Item> iterator() {
	// TODO Auto-generated method stub
	return new ListIterator();
	}
	public class ListIterator implements Iterator<Item>{
	private Node current = first;
	@Override
	public boolean hasNext() {
	return (current!=null);
	}
	@Override
	public Item next() {
	Item val= current.value;
	current = current.next;
	return val;
	}
	}
	public void push(Item val) {//insert at the beginning of the LL
	Node n1 = new Node();
	n1.value = val;
	n1.next = first;
	first = n1;
	size++;
	}
	public Item pop() {//pop the first ele - LIFO
	if(isEmpty()) {
	System.out.println("stack empty");
	return null;
	}
	Item val = first.value;
	first = first.next;
	size--;
	return val;
	}
	public int size() {
	return size;
	}
	public boolean isEmpty() {
	return (first==null);
	}
	public void print() {
	System.out.println("============================================");
	Node n = first;
	while(n!=null) {
	System.out.println(n.value);
	n = n.next;
	}
	}
	public static void main(String[] args) {
	GenericStackLLIterator<Integer> stack = new GenericStackLLIterator<Integer>();
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(4);
	stack.push(5);
	//stack.print();
	System.out.println("-------------Iterator-----------");
	for(Integer i: stack) {
	System.out.println(i);
	}
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("size is "+stack.size());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	//String
	GenericStackLLIterator<String> stack1 = new GenericStackLLIterator<String>();
	stack1.push("to");
	stack1.push("be");
	stack1.push("or");
	stack1.push("not");
	stack1.push("to");
	stack1.push("be");
	//stack1.print();
	System.out.println("-------------Iterator-----------");
	for(String s: stack1) {
	System.out.println(s);
	}
	stack1.pop();
	stack1.pop();
	stack1.print();
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.print();
	}
	}

view raw GenericStackLLIterator.java hosted with ❤ by GitHub

Queue Using Array Resizing - Coursera Algorithms

Queues follow FIFO standard. To implement, we need to maintain two indices to first and last elements of the array, for enqueue and dequeue operations.

Following is the program:

	package queues;
	public class QueueResizeArray {
	int fwdIndex=0, bckIndex=0;
	String[] queue;
	public QueueResizeArray(int cap) {
	queue = new String[cap];
	}
	public void enqueue(String s) {
	int l = queue.length;
	if(bckIndex==l) {
	resize(2*l);
	}
	queue[bckIndex++] = s;
	if(isEmpty()) {
	fwdIndex = bckIndex;
	}
	}
	public String dequeue() {
	if(isEmpty()) {
	System.out.println("empty Q");
	return "";
	}
	int l = queue.length;
	if(bckIndex==l/2) {
	resize(l/4);
	}
	String s = queue[fwdIndex];
	queue[fwdIndex++] = null;
	return s;
	}
	public int size() {
	return (bckIndex-fwdIndex);
	}
	public boolean isEmpty() {
	return (size()==0);
	}
	public void print() {
	System.out.println("==========================");
	for(int i=fwdIndex;i<bckIndex;i++) {
	System.out.println(queue[i]);
	}
	}
	public void resize(int cap) {
	String[] copy = new String[cap];
	for(int i=fwdIndex;i<bckIndex;i++) {
	copy[i]=queue[i];
	}
	queue = copy;
	}
	public int length() {
	return queue.length;
	}
	public static void main(String[] args) {
	QueueResizeArray queue = new QueueResizeArray(5);
	queue.enqueue("to");
	queue.enqueue("be");
	queue.enqueue("or");
	queue.enqueue("not");
	queue.enqueue("to");
	queue.print();
	System.out.println("stack util is "+queue.size()+" out of "+queue.length());
	queue.enqueue("be");
	System.out.println("stack util is "+queue.size()+" out of "+queue.length());
	queue.print();
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	queue.print();
	}
	}

view raw QueueResizeArray.java hosted with ❤ by GitHub

Related Posts: 

Queue Using Linked List - Coursera Algorithms

Queue Using Linked List - Coursera Algorithms

Queues follow FIFO standard. To implement, we need to maintain two pointers to first and last nodes of linked list, as we insert at the end of the list and removed the first element of the list for enqueue and dequeue operations.

Following is the program:

	package queues;
	public class QueueLL {
	Node first;
	Node last;
	static int size;
	public class Node{
	String value;
	Node next;
	public Node(String s) {
	this.value = s;
	}
	}
	public void enqueue(String s) {
	Node prevLast = last;
	last = new Node(s);
	if(!isEmpty())
	prevLast.next = last;
	else {
	first = last;
	}
	size++;
	}
	public String dequeue() {
	if(isEmpty()) {
	System.out.println("queue empty");
	return "";
	}
	String s = first.value;
	first = first.next;
	size--;
	return s;
	}
	public boolean isEmpty() {
	return (first==null);
	}
	public int size() {
	return size;
	}
	public void print() {
	System.out.println("==========================");
	Node n = first;
	while(n!=null) {
	System.out.println(n.value);
	n = n.next;
	}
	}
	public static void main(String[] args) {
	QueueLL queue = new QueueLL();
	queue.enqueue("to");
	queue.enqueue("be");
	queue.enqueue("or");
	queue.enqueue("not");
	queue.enqueue("to");
	queue.enqueue("be");
	queue.print();
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	queue.print();
	}
	}

view raw QueueLL.java hosted with ❤ by GitHub

Stack Using Array Resizing - Coursera Algorithms

When implementing stacks using arrays, we may run into overflow and underflow problems. We can resize the array on need basis by doubling the array in push op when the array has reached it's limit and by halving the array in pop op when the array is just 25% utilized. 

This will result in constant amortized time operations, but ~N in worst case.

Linked list on the other hand has constant time even in worst case. But still, linked list may take more time and memory because of the links. 

If occasional slow ops are bearable, then arrays would be a better option than linked lists. 

Following is the complete program:

	package stacks;
	public class StackResizeArray {
	String[] stack;
	int index=0;
	public StackResizeArray(int cap) {
	stack = new String[cap];
	}
	public void push(String s) {
	int l = stack.length;
	if(index==l) {//full array-double size
	resize(2*l);
	}
	stack[index++] = s;
	}
	public int size() {
	return index;
	}
	public int length() {
	return stack.length;
	}
	public boolean isEmpty() {
	return (index==0);
	}
	public String pop() {
	if(isEmpty()) {
	System.out.println("stack empty");
	return "";
	}
	int l = stack.length;
	if(index<=l/4) {//25% of array is filled-half the array
	resize(l/2);
	}
	String s = stack[--index];
	stack[index] = null;
	return s;
	}
	public void print() {
	System.out.println("============================");
	for(int i=0;i<index;i++) {
	System.out.println(stack[i]);
	}
	}
	public void resize(int cap) {
	String copy[] = new String[cap];
	for(int i=0;i<index;i++) {
	copy[i]=stack[i];
	}
	stack = copy;
	}
	public static void main(String[] args) {
	StackResizeArray stack = new StackResizeArray(5);
	stack.push("to");
	stack.push("be");
	stack.push("or");
	stack.push("not");
	stack.push("to");
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.push("be");
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.print();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	}
	}

view raw StackResizeArray.java hosted with ❤ by GitHub

Related Posts:  

Stack Using Linked List - Coursera Algorithms

Stack Using Array - Coursera Algorithms

Stack Using Array - Coursera Algorithms

Stack works in a LIFO order. It supports insert, remove, iteration and test for empty operations.

They can be represented using array. An initial capacity for this array is taken as input. We manipulate an index variable for push and pop, instead of actually deleting items from stack.

If using objects in stack, avoid loitering(holding references to objects and preventing GC) by using following code in pop operation:

public String pop() { String item = s[--N]; s[N] = null; return item; } 

Following is the complete program:

	package stacks;
	import stacks.StackLL.Node;
	public class StackA {
	int[] stack;
	int index=0;
	public StackA(int cap) {
	stack = new int[cap];
	}
	public void push(int v) {
	stack[index++] = v;
	}
	public int pop() {
	if(isEmpty()) {
	System.out.println("stack empty");
	return Integer.MIN_VALUE;
	}
	return stack[--index];
	}
	public boolean isEmpty() {
	return (index==0);
	}
	public int size() {
	return index;
	}
	public void print() {
	System.out.println("============================================");
	for(int j=index-1;j>=0;j--) {
	System.out.println(stack[j]);
	}
	}
	public static void main(String[] args) {
	StackA stack = new StackA(10);
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(4);
	stack.push(5);
	stack.print();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("size is "+stack.size());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	}
	}

view raw StackA.java hosted with ❤ by GitHub

Related Posts:  

Stack Using Linked List - Coursera Algorithms

Stack Using Linked List - Coursera Algorithms

Stack works in a LIFO order. It supports insert, remove, iteration and test for empty operations.

They can be represented using linked list. Push and pop operations are done on the first element. This takes constant time for any operation and about ~36N Bytes for N stack items - 16B overhead + 8B inner Node class + 8B reference to Node object + 4B for integer values.

Following is the program:

	package stacks;
	public class StackLL {
	private Node first = null;
	static int size = 0;
	public class Node{
	int value;
	Node next;
	}
	public void push(int val) {//insert at the beginning of the LL
	Node n1 = new Node();
	n1.value = val;
	n1.next = first;
	first = n1;
	size++;
	}
	public int pop() {//pop the first ele - LIFO
	if(isEmpty()) {
	System.out.println("stack empty");
	return Integer.MIN_VALUE;
	}
	int val = first.value;
	first = first.next;
	size--;
	return val;
	}
	public int size() {
	return size;
	}
	public boolean isEmpty() {
	return (first==null);
	}
	public void print() {
	System.out.println("============================================");
	Node n = first;
	while(n!=null) {
	System.out.println(n.value);
	n = n.next;
	}
	}
	public static void main(String[] args) {
	StackLL stack = new StackLL();
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(4);
	stack.push(5);
	stack.print();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("size is "+stack.size());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	}
	}

view raw StackLL.java hosted with ❤ by GitHub

Finding maximum and minimum in union find algorithm

This post is a problem based on union find algorithm. For the algorithm, please see "Weighted Quick Union With Path Compression - Coursera Algorithms"

Problem: Given an element, find the max/min of it's connected components tree.

Following is my, probably brute force, solution to find max/min. For this, we use extra arrays to store the max and min values. We updated the max and min only for root nodes. For all other nodes, just find the root and it's max/min.

	package Union;
	public class CWQuickUnionMaxMin {
	private int[] id;
	private int[] sz;
	private int[] max;
	private int[] min;
	public CWQuickUnionMaxMin(int N) {
	id = new int[N];
	for(int i=0;i<N;i++) {
	id[i]=i;
	}
	sz = new int[N];
	for(int i=0;i<N;i++) {
	sz[i]=1;
	}
	max = new int[N];
	for(int i=0;i<N;i++) {
	max[i]=i;
	}
	min = new int[N];
	for(int i=0;i<N;i++) {
	min[i]=i;
	}
	}
	public void print() {
	System.out.println("************************");
	int n = id.length;
	for(int i=0;i<n;i++) {
	System.out.println(i+"---------"+id[i]+"--------"+sz[i]+"--------"+max[i]+"--------"+min[i]);
	}
	}
	public int root(int i) {
	while(i!=id[i]) {//go all the way up till you find an element whose root is itself
	id[i]=id[id[i]];//point each node on path to grandparent to flatten the tree
	i=id[i];
	}
	return i;
	}
	public boolean connected(int p, int q) {
	if(root(p)==root(q)) {
	System.out.println("Connected");
	return true;
	}
	else {
	System.out.println("Not Connected");
	return false;
	}
	}
	/*
	public int max(int p, int q) {
	return (p>=q? p : q);
	}
	public int min(int p, int q) {
	return (p<=q? p : q);
	}*/
	public int maxInConnComp(int x) {
	int n = id.length;
	int tmp = 0;
	for(int i=0;i<n;i++) {
	if(root(i)==x) {//eles in same component - with same root
	if(i>tmp) {
	tmp = i;
	}
	}
	}
	return tmp;
	}
	public int findMax(int x) {
	return maxInConnComp(root(x));
	}
	public int findMin(int x) {
	return minInConnComp(root(x));
	}
	public int minInConnComp(int x) {
	int n = id.length;
	int tmp = 0;
	for(int i=0;i<n;i++) {
	if(root(i)==x) {//eles in same component - with same root
	if(i<tmp) {
	tmp = i;
	}
	}
	}
	return tmp;
	}
	public void union(int p, int q) {
	// unite the sets by setting the root of small set root to large set root
	//balance trees by always choosing the smaller tree to link up to larger tree
	int proot = root(p),qroot = root(q);
	if(proot==qroot) return;
	if(sz[proot]<sz[qroot]) {
	id[proot] = qroot;
	max[qroot] = maxInConnComp(qroot);
	min[qroot] = minInConnComp(qroot);
	sz[qroot]+=sz[proot];
	}else{
	id[qroot] = proot;
	max[proot] = maxInConnComp(proot);
	min[proot] = minInConnComp(proot);
	sz[proot]+=sz[qroot];
	}
	//print();
	}
	public static void main(String[] args) {
	CWQuickUnionMaxMin cwqu = new CWQuickUnionMaxMin(10);
	cwqu.union(4, 3);
	cwqu.union(3, 8);
	cwqu.union(6, 5);
	cwqu.union(9, 4);
	cwqu.union(2, 1);
	cwqu.connected(0, 7);
	cwqu.connected(8, 9);
	cwqu.union(5, 0);
	cwqu.union(7, 2);
	cwqu.connected(0, 7);
	cwqu.union(6, 1);
	cwqu.union(7,3);
	cwqu.print();
	System.out.println(cwqu.findMax(7));
	System.out.println(cwqu.findMin(7));
	}
	}

view raw CWQuickUnionMaxMin.java hosted with ❤ by GitHub

Weighted Quick Union With Path Compression - Coursera Algorithms

Weighted Quick Union can be improved further by path compression. The idea here is to avoid flatten the tree. After computing the root of a node,  we set the id of each examined node to point to that root.

Running Time:
For M union-find operations on N elements, running time  ≤ c ( N + M lg* N ) array accesses. 

lg*N = number of times we have to take log of N to get 1.

It's almost linear and union find doesn't have any linear algorithm.

Following is the program:

	package Union;
	public class CompressWeightQuickUnion {
	private int[] id;
	private int[] sz;
	public CompressWeightQuickUnion(int N) {
	id = new int[N];
	for(int i=0;i<N;i++) {
	id[i]=i;
	}
	sz = new int[N];
	for(int i=0;i<N;i++) {
	sz[i]=1;
	}
	}
	public void print() {
	System.out.println("************************");
	int n = id.length;
	for(int i=0;i<n;i++) {
	System.out.println(i+"---------"+id[i]+"--------"+sz[i]);
	}
	}
	public int root(int i) {
	while(i!=id[i]) {//go all the way up till you find an element whose root is itself
	id[i]=id[id[i]];//point each node on path to grandparent to flatten the tree
	i=id[i];
	}
	return i;
	}
	public boolean connected(int p, int q) {
	if(root(p)==root(q)) {
	System.out.println("Connected");
	return true;
	}
	else {
	System.out.println("Not Connected");
	return false;
	}
	}
	public void union(int p, int q) {
	// unite the sets by setting the root of small set root to large set root
	//balance trees by always choosing the smaller tree to link up to larger tree
	int proot = root(p),qroot = root(q);
	if(proot==qroot) return;
	if(sz[proot]<sz[qroot]) {
	id[proot] = qroot;
	sz[qroot]+=sz[proot];
	}else{
	id[qroot] = proot;
	sz[proot]+=sz[qroot];
	}
	//print();
	}
	public static void main(String[] args) {
	CompressWeightQuickUnion cwqu = new CompressWeightQuickUnion(10);
	cwqu.union(4, 3);
	cwqu.union(3, 8);
	cwqu.union(6, 5);
	cwqu.union(9, 4);
	cwqu.union(2, 1);
	cwqu.connected(0, 7);
	cwqu.connected(8, 9);
	cwqu.union(5, 0);
	cwqu.union(7, 2);
	cwqu.connected(0, 7);
	cwqu.union(6, 1);
	cwqu.union(7,3);
	cwqu.print();
	}
	}

view raw CompressWeightQuickUnion.java hosted with ❤ by GitHub

Weighted Quick Union Algorithm - Coursera Algorithms

Quick Find and Quick Union were slow in performing union and finding if two elements are connected respectively. However, Quick Union can be improvised by using weighted trees. The idea here is to avoid tall trees of Quick Union and always balance the trees such that smaller trees always link up to the larger trees.

We use array to initialize elements to indices itself. To weigh trees, we use an extra array to track the size of trees at each element.

Any node x's depth increases by one when it's tree T1 is merged into another T2.
As |T2|>=|T1| , the size of tree containing x at least doubles.
As N*lg N = N, the size of tree containing x can double at most lg N times.
So the depth of any node at x is at most lg N.

Running Time:
initialize - N
union(p,q) - lg N⁺ - including the root calculations
connected(p,q) - lg N - proportional to depth of p and q


Following is the program:

	package Union;
	public class WeightedQuickUnion {
	private int[] id;
	private int[] sz;
	public WeightedQuickUnion(int N) {
	id = new int[N];
	for(int i=0;i<N;i++) {
	id[i]=i;
	}
	sz = new int[N];
	for(int i=0;i<N;i++) {
	sz[i]=1;
	}
	}
	public void print() {
	System.out.println("************************");
	int n = id.length;
	for(int i=0;i<n;i++) {
	System.out.println(i+"---------"+id[i]+"--------"+sz[i]);
	}
	}
	public int root(int i) {
	while(i!=id[i]) {//go all the way up till you find an element whose root is itself
	i=id[i];
	}
	return i;
	}
	public boolean connected(int p, int q) {
	if(root(p)==root(q)) {
	System.out.println("Connected");
	return true;
	}
	else {
	System.out.println("Not Connected");
	return false;
	}
	}
	public void union(int p, int q) {
	// unite the sets by setting the root of small set root to large set root
	//balance trees by always choosing the smaller tree to link up to larger tree
	int proot = root(p),qroot = root(q);
	if(proot==qroot) return;
	if(sz[proot]<sz[qroot]) {
	id[proot] = qroot;
	sz[qroot]+=sz[proot];
	}else{
	id[qroot] = proot;
	sz[proot]+=sz[qroot];
	}
	//print();
	}
	public static void main(String[] args) {
	WeightedQuickUnion wqu = new WeightedQuickUnion(10);
	wqu.union(4, 3);
	wqu.union(3, 8);
	wqu.union(6, 5);
	wqu.union(9, 4);
	wqu.union(2, 1);
	wqu.connected(0, 7);
	wqu.connected(8, 9);
	wqu.union(5, 0);
	wqu.union(7, 2);
	wqu.connected(0, 7);
	wqu.union(6, 1);
	wqu.union(7,3);
	wqu.print();
	}
	}

view raw WeightedQuickUnion.java hosted with ❤ by GitHub

Quick Union Algorithm - Coursera Algorithms

Quick Find was very slow with quadratic operations. Quick Union is a lazy union-find algorithm to unite sets and to see if an element is connected to another. We use array to initialize elements to indices itself. Later, we update the elements to point to it's parent.  This way we create trees out of elements.


Array accesses:
initialize - N
union(p,q) - N⁺ including the cost of root calculations
connected(p,q) -N

The trees can get quite tall, making the connected operation quite slow.

Following is the program:

	package Union;
	public class QuickUnion {
	private int[] id;
	public QuickUnion(int N) {
	id = new int[N];
	for(int i=0;i<N;i++) {
	id[i]=i;
	}
	}
	public void print() {
	System.out.println("************************");
	int n = id.length;
	for(int i=0;i<n;i++) {
	System.out.println(i+"---------"+id[i]);
	}
	}
	public int root(int i) {
	while(i!=id[i]) {//go all the way up till you find an element whose root is itself
	i=id[i];
	}
	return i;
	}
	public boolean connected(int p, int q) {
	if(root(p)==root(q)) {
	System.out.println("Connected");
	return true;
	}
	else {
	System.out.println("Not Connected");
	return false;
	}
	}
	public void union(int p, int q) {
	// unite the sets by setting the root of first set root to second set root
	int proot = root(p),qroot = root(q);
	id[proot] = qroot;
	//print();
	}
	public static void main(String[] args) {
	QuickUnion qu = new QuickUnion(10);
	qu.union(4, 3);
	qu.union(3, 8);
	qu.union(6, 5);
	qu.union(9, 4);
	qu.union(2, 1);
	qu.connected(0, 7);
	qu.connected(8, 9);
	qu.union(5, 0);
	qu.union(7, 2);
	qu.connected(0, 7);
	qu.union(6, 1);
	qu.union(7,3);
	qu.print();
	}
	}

view raw QuickUnion.java hosted with ❤ by GitHub

Quick Find Algorithm - Coursera Algorithms

Quick Find is an eager union-find algorithm.

Purpose: To find if two elements are connected and to perform union operation on two elements.

We will consider the elements as simple int array. We initialize array to index elements itself and then change the ids in the array when an union operation is performed.

Array accesses: 2N+1
initialize - N
union(p,q) - N
connected(p,q) - 1

If N unions are performed on N elements, union takes N² array access. Quadratic operations don't scale.

Following is the program:

	package Union;
	public class QuickFind {
	private int[] id;
	public QuickFind(int N) {
	id = new int[N];
	for(int i=0;i<N;i++) {
	id[i]=i;
	}
	}
	public void print() {
	System.out.println("************************");
	int n = id.length;
	for(int i=0;i<n;i++) {
	System.out.println(i+"---------"+id[i]);
	}
	}
	public boolean connected(int p, int q) {
	if(id[p]==id[q])
	return true;
	else
	return false;
	}
	public void union(int p, int q) {
	//get all elements with p's id
	//change ids to q's id
	int n = id.length, pid = id[p], qid = id[q];
	for(int i=0;i<n;i++) {
	if(id[i] == pid) {
	id[i]=qid;
	}
	}
	}
	public static void main(String[] args) {
	QuickFind qf = new QuickFind(10);
	qf.union(4, 3);
	qf.union(3, 8);
	qf.print();
	qf.union(6, 5);
	qf.union(9, 4);
	qf.union(2, 1);
	qf.connected(0, 7);
	qf.connected(8, 9);
	qf.union(5, 0);
	qf.union(7, 2);
	qf.connected(0, 7);
	qf.union(1, 0);
	qf.union(6, 1);
	qf.print();
	}
	}

view raw QuickFind.java hosted with ❤ by GitHub