Finding Commons

09 Jun, 2021

Problem

Given two sets A and B, write a program that extracts the common elements of the two sets and outputs them in ascending order.

input

The first line gives the size N of set A (1<=N<=30,000).
The second line gives N elements. Duplicate elements are not given.
The third line gives the size M of set B (1<=M<=30,000).
The fourth line gives M elements. Duplicate elements are not given.
The elements of each set are natural numbers less than or equal to 1,000,000,000.

output

Outputs the common elements of two sets sorted in ascending order.

Solution

O(2n)

function solution(arr1, arr2) {
	let answer = [];
	arr1.sort((a, b) => a - b);
	for (let x of arr1) {
		if (arr2.includes(x)) answer.push(x);
	}
	return answer;
}

O(2n)

function solution(arr1, arr2) {
	let answer = [];
	arr1.sort((a, b) => a - b);
	arr2.sort((a, b) => a - b);

	let cnt = 0;

	while (arr1.length > cnt && arr2.length > cnt) {
		if (arr2.includes(arr1[cnt])) answer.push(arr1[cnt++]);
		else cnt++;
	}

	return answer;
}

O(n+m) : Two Pointers Algorithm

function solution(arr1, arr2) {
	let answer = [];
	arr1.sort((a, b) => a - b);
	arr2.sort((a, b) => a - b);
	let p1 = (p2 = 0);

	while (arr1.length > p1 && arr2.length > p2) {
		if (arr1[p1] === arr2[p2]) {
			answer.push(arr1[p1++]);
			p2++;
		} else if (arr1[p1] < arr2[p2]) p1++;
		else p2++;
	}

	return answer;
}