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