package coding4fun;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Find all the common elements in two sorted lists of numbers.
 *
 * <pre>
 * Input : [2, 5, 5, 5], [2, 2, 3, 5, 5, 7]
 * Output: [2, 5, 5]
 *
 * Input : [2, 3, 5, 5, 6], [2, 2, 3, 5, 5, 7]
 * Output: [2, 3, 5, 5]
 *
 * Input : [1, 3], [3, 1, 1]
 * Output: [1, 3]
 *
 * Input : [1, 3], [2, 4]
 * Output: []
 * </pre>
 */
public class Problem22 {
    public static List<Integer> findCommonElements(List<Integer> list1, List<Integer> list2) {
        Map<Integer, Integer> map1 = new HashMap<>();
        for (int i : list1) {
            if (!map1.containsKey(i)) {
                map1.put(i, 1);
            } else {
                map1.put(i, map1.get(i)+1);
            }
        }
        Map<Integer, Integer> map2 = new HashMap<>();
        for (int i : list2) {
            if (!map2.containsKey(i)) {
                map2.put(i, 1);
            } else {
                map2.put(i, map2.get(i)+1);
            }
        }
        List<Integer> result = new ArrayList<>();
        map1.forEach((key, value) -> {
            if (map2.containsKey(key)) {
                int val1 = value;
                int val2 = map2.get(key);
                int n = Math.min(val1, val2);
                for (int i = 0; i < n; i++) {
                    result.add(key);
                }
            }
        });
        return result;
    }

    public static void main(String[] args) {
        System.out.println(findCommonElements(
            Arrays.asList(2, 5, 5, 5), Arrays.asList(2, 2, 3, 5, 5, 7)));

        System.out.println(findCommonElements(
            Arrays.asList(2, 3, 5, 5, 6), Arrays.asList(2, 2, 3, 5, 5, 7)));

        System.out.println(findCommonElements(
            Arrays.asList(1, 3), Arrays.asList(3, 1, 1)));

        System.out.println(findCommonElements(
            Arrays.asList(1, 3), Arrays.asList(2, 4)));
    }
}

@@ -88,60 +88,12 @@
 til.
-HashMap;%0Aimport java.util.List;%0Aimport java.util.Map
+List
 ;%0A%0A/
@@ -249,24 +249,27 @@
  Input : %5B2,
+ 2,
  3, 5, 5, 6%5D
@@ -270,18 +270,15 @@
  5, 
-6
+7
 %5D, %5B2,
- 2,
  3, 
@@ -275,33 +275,33 @@
 %5D, %5B2, 3, 5, 5, 
-7
+6
 %5D%0A * Output: %5B2,
@@ -333,23 +333,23 @@
 1, 3%5D, %5B
-3
+1
 , 1, 
-1
+3
 %5D%0A * Out
@@ -359,24 +359,68 @@
 : %5B1, 3%5D%0A *%0A
+ * Input : %5B1, 1, 3%5D, %5B3%5D%0A * Output: %5B3%5D%0A *%0A
  * Input : %5B
@@ -585,35 +585,36 @@
 ) %7B%0A        
-Map
+List
 %3CInteger
 , Integer%3E m
@@ -605,206 +605,179 @@
 eger
-, Integer%3E map1 = new HashMap%3C%3E();%0A        for (int i : list1) %7B%0A            if (!map1.containsKey(i)) %7B%0A                map1.put(i, 1);%0A            %7D else %7B%0A                map1.put(i, map
+%3E result = new ArrayList%3C%3E();%0A        int idx1 = 0;%0A        int idx2 = 0;%0A        while (idx1 %3C list1.size() && idx2 %3C list2.size()) %7B%0A            int val1 = list
 1.get(i
-)+
+dx
 1);%0A
@@ -792,392 +792,168 @@
     
-%7D%0A        %7D%0A        Map%3CInteger, Integer%3E map2 = new HashMap%3C%3E();%0A        for (int i : list2) %7B%0A            if (!map2.containsKey(i)) %7B%0A                map2.put(i, 1);%0A            %7D else %7B%0A                map2.put(i, map2.get(i)+1);%0A            %7D%0A        %7D%0A        List%3CInteger%3E result = new ArrayList%3C%3E();%0A        map1.forEach((key, value) -%3E %7B%0A            if (map2.containsKey(key))
+int val2 = list2.get(idx2);%0A            if (val1 == val2) %7B%0A                idx1++;%0A                idx2++;%0A                result.add(val1);%0A            %7D else
  %7B%0A 
@@ -972,156 +972,76 @@
    i
-nt 
+f (
 val1 
-= value;%0A                int val2 = map2.get(key);%0A                int n = Math.min(val1, val2);%0A                for (int i = 0; i %3C n; i++)
+%3C val2) %7B%0A                    idx1++;%0A                %7D else
  %7B%0A 
@@ -1063,23 +1063,14 @@
     
-result.add(key)
+idx2++
 ;%0A  
@@ -1108,18 +1108,16 @@
        %7D
-);
 %0A       
@@ -1381,16 +1381,19 @@
 sList(2,
+ 2,
  3, 5, 5
@@ -1394,17 +1394,17 @@
 , 5, 5, 
-6
+7
 ), Array
@@ -1406,35 +1406,32 @@
 Arrays.asList(2,
- 2,
  3, 5, 5, 7)));%0A
@@ -1416,33 +1416,33 @@
 ist(2, 3, 5, 5, 
-7
+6
 )));%0A%0A        Sy
@@ -1529,15 +1529,119 @@
 ist(
-3
+1
 , 1, 
-1
+3)));%0A%0A        System.out.println(findCommonElements(%0A            Arrays.asList(1, 1, 3), Arrays.asList(3
 )));

Update problem 22 (one pass)