Problem 5: Common Elements | Hashing Basics

Software Development
#1

Common Elements

Problem Description

Given two integer array A and B of size N and M respectively. Your task is to find all the common elements in both the array.

NOTE:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

Problem Constraints

1 <= N, M <= 105

1 <= A[i] <= 109

Input Format

First argument is an integer array A of size N.

Second argument is an integer array B of size M.

Output Format

Return an integer array denoting the common elements.

Example Input

Input 1:

A = [1, 2, 2, 1] B = [2, 3, 1, 2]

Input 2:

A = [2, 1, 4, 10] B = [3, 6, 2, 10, 10]

Example Output

Output 1:

[1, 2, 2]

Output 2:

[2, 10]

Example Explanation

Explanation 1:

Elements (1, 2, 2) appears in both the array. Note 2 appears twice in both the array.

Explanation 2:

Elements (2, 10) appears in both the array.

#2

Common Elements Solution in Java

Problem Description

Given two integer array A and B of size N and M respectively. Your task is to find all the common elements in both the array.

NOTE:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.
import java.util.HashMap;
public class Solution {
    public ArrayList<Integer> solve(ArrayList<Integer> A, ArrayList<Integer> B) {
        ArrayList<Integer> op = new ArrayList<Integer>();
        HashMap<Integer, Integer> hmap = new HashMap<>();
        for (int val: A){
            if ( !hmap.containsKey(val) ) {
                hmap.put( val, 1 );
            }
            else {
                hmap.put( val, hmap.get(val) + 1 );
            }
        }

        for(int val: B) {
            if ( hmap.containsKey(val) && hmap.get(val) > 0 ) {
                hmap.put( val, hmap.get(val) - 1 );
                op.add(val);
            }
        }
        return op;
        
    }
}