LeetCode #350. Intersection of Two Arrays II

### Time Complexity: O(n + m)

Let:
    * n = nums1.length
    * m = nums2.length

Breakdown:

* Building the frequency map:

for (int i = 0; i < nums1.length; i++) { ... }

Runs in O(n)

* Scanning nums2 and building the result list:

for (int i = 0; i < nums2.length; i++) { ... }

Runs in O(m)
Each operation (containsKey, get, put) on a HashMap is O(1) 
average case

* Converting List<Integer> to int[]:

    for (int i = 0; i < list.size(); i++) { ... }

    * In the worst case, the result list has min(n, m) elements
    * So this is O(k), where k = size of result list

---

Space Complexity: O(n + k)

freqMap:

 * Stores counts of all elements in nums1
 * Worst case: all elements are unique → O(n)

list:

 * Stores the intersection → O(k), where k ≤ min(n, m)

intersection array:

 * Stores the same elements as the list → also O(k)

---

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        List<Integer> list = new ArrayList<>();

        // store and count occurrences of nums1 - use hashmap
        for (int i = 0; i < nums1.length; i++) {
            freqMap.put(nums1[i], freqMap.getOrDefault(nums1[i], 0) +1);
        }

        // check occurences of nums1 with nums2 - check previous hashmap
        // store already present occurences in LinkedList
        for (int i = 0; i < nums2.length; i++) {
            if (freqMap.containsKey(nums2[i]) && freqMap.get(nums2[i]) > 0) {
                list.add(nums2[i]);
                freqMap.put(nums2[i], freqMap.get(nums2[i]) - 1);
            }
        }

        // trasform ArrayList to Array
        int[] intersection = new int[list.size()];        
        for (int i = 0; i < list.size(); i++) {
            intersection[i] = list.get(i);
        }

        //return Array
        return intersection;

    }
}