package org.pilgrim.leetcode.easy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * Given two arrays, write a function to compute their intersection.
 * 
 * Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
 * 
 * Note: Each element in the result should appear as many times as it shows in
 * both arrays. The result can be in any order. Follow up: What if the given
 * array is already sorted? How would you optimize your algorithm? What if
 * nums1's size is small compared to nums2's size? Which algorithm is better?
 * What if elements of nums2 are stored on disk, and the memory is limited such
 * that you cannot load all elements into the memory at once?
 * 
 * @author segoncha
 *
 */
public class IntersectionTwoArraysII {

	public static void main(String[] args) {
		int[] a = { 1, 2, 2, 3 };
		int[] b = { 2, 2 };
		System.out.println(Arrays.toString(intersect(a, b)));

	}

	public static int[] intersect(int[] a, int[] b) {
		// Arrays.asList(Arrays.stream(a).boxed().toArray(Integer[]::new));
		Map<Integer, Integer> m1 = groupToMap(a);
		Map<Integer, Integer> m2 = groupToMap(b);

		if (m1.size() > m2.size()) {
			Map<Integer, Integer> t = m1;
			m1 = m2;
			m2 = t;
		}

		List<Integer> list = new ArrayList<>();

		Iterator<Map.Entry<Integer, Integer>> iterator = m1.entrySet().iterator();
		while (iterator.hasNext()) {
			Map.Entry<Integer, Integer> next = iterator.next();

			Integer key = next.getKey();
			if (m2.containsKey(key)) {
				Integer v1 = next.getValue();
				Integer v2 = m2.get(key);

				int minValue = Math.min(v1, v2);
				for (int i = 0; i < minValue; i++) {
					list.add(key);
				}

				m2.remove(key);
				iterator.remove();
			}
		}

		return list.stream().flatMapToInt(x -> IntStream.of(x.intValue())).toArray();
	}

	private static Map<Integer, Integer> groupToMap(int[] a) {
		Map<Integer, Integer> map = new HashMap<>();
		for (int i : a) {
			Integer count = map.get(i);
			if(null == count){
				count = 0;				
			}
			map.put(i, ++count);
		}
		return map;
	}
}

@@ -1162,24 +1162,575 @@
 );%0D%0A%0D%0A%09%7D%0D%0A%0D%0A
+%09public int%5B%5D intersect2(int%5B%5D nums1, int%5B%5D nums2) %7B%0D%0A%09%09Arrays.sort(nums1);%0D%0A%09%09Arrays.sort(nums2);%0D%0A%09%09ArrayList%3CInteger%3E list = new ArrayList%3CInteger%3E();%0D%0A%09%09int p1 = 0, p2 = 0;%0D%0A%09%09while (p1 %3C nums1.length && p2 %3C nums2.length) %7B%0D%0A%09%09%09if (nums1%5Bp1%5D %3C nums2%5Bp2%5D) %7B%0D%0A%09%09%09%09p1++;%0D%0A%09%09%09%7D else if (nums1%5Bp1%5D %3E nums2%5Bp2%5D) %7B%0D%0A%09%09%09%09p2++;%0D%0A%09%09%09%7D else %7B%0D%0A%09%09%09%09list.add(nums1%5Bp1%5D);%0D%0A%09%09%09%09p1++;%0D%0A%09%09%09%09p2++;%0D%0A%0D%0A%09%09%09%7D%0D%0A%09%09%7D%0D%0A%0D%0A%09%09int%5B%5D result = new int%5Blist.size()%5D;%0D%0A%09%09int i = 0;%0D%0A%09%09while (i %3C list.size()) %7B%0D%0A%09%09%09result%5Bi%5D = list.get(i);%0D%0A%09%09%09i++;%0D%0A%09%09%7D%0D%0A%09%09return result;%0D%0A%09%7D%0D%0A%0D%0A
 %09public stat
@@ -2797,16 +2797,17 @@
 ;%0D%0A%09%09%09if
+ 
 (null ==
@@ -2813,16 +2813,17 @@
 = count)
+ 
 %7B%0D%0A%09%09%09%09c
@@ -2831,20 +2831,16 @@
 unt = 0;
-%09%09%09%09
 %0D%0A%09%09%09%7D%0D%0A

add more faster way how find IntersectionTwoArraysII