Day 1
Tags: coding, leetcode, java, 100daysofcode
Published: 2022-02-14 04:19:37

# Problem 1:

(Intersection of Two Arrays)
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

**Example 1:**

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

**Example 2:**

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

**Approach:**
Brute Force --> Use two for loops to iterate over both the loops and find out the common element and store them in a different array.
Time - O(n*n) | Space - O(n)

Note: If you are using an array list, then make sure, that you have a method in your solution called "listToArray()"

  `private int[] listToArray(List<Integer> list){
        int[] result = new int[list.size()];
        for(int i =0; i< list.size(); i++){
            result[i] = list.get(i);
        }
        return result;    
    }`

Two Pointer --> Sort the two arrays and iterate over to find out the intersections. Use an array list because we want to space some space and hence we will dynamically update the array list every time we find an intersection.

Ref: https://medium.com/@punitkmr/intersection-of-two-arrays-ii-ffb26f04dfd1

Using HashMap: 
- Populate the hashmap with first array with the keys as the numbers and it's frequency as the count
- Create an array list 
- Iterate over the second array and find the common elements
- Imp: Make sure you are reducing the count from the map, so that ONLY the INTERSECTION is getting returned.
- Return the matched values in the array list
- Convert this array list to array using custom listToArray() method, in which you are just feeding every element from the array list to this array and return it.

**<u>Code (HashMap):</u>**

`class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0){
            return new int[0];
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        
        //populating the hash map with the array 1 values
        for(int num: nums1){
            if(map.containsKey(num)){
                map.put(num, map.get(num)+1); // if value is repeated, then save the value, but increment the key count, that's why "get()+1".
            }
            else
                map.put(num, 1);
        }
        //create an arrayList to store the result
        
        List<Integer> result = new ArrayList<>();
        
        //iterate and match with nums2 now;
        for(int num: nums2){
            if(map.containsKey(num) && map.get(num) > 0){
                result.add(num); //adding the matched value in the array list -- intersection operation
                int count = map.get(num);
                count--;
                map.put(num, count);
            }
        }
        return listToArray(result);
    }
    private int[] listToArray(List<Integer> list){
        int[] result = new int[list.size()];
        for(int i =0; i< list.size(); i++){
            result[i] = list.get(i);
        }
        return result;    
    }
    
}`