Practice › Hashing & Two Pointers
Intersection of Two Arrays
Easy · Hashing & Two Pointers · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Print the distinct values that appear in both arrays in increasing order, or -1 if there are none.
Input
Line 1: n. Line 2: n integers. Line 3: m. Line 4: m integers.
Output
The common values in increasing order, or -1.
Constraints
- 1 ≤ n, m ≤ 10^5
Example 1
Input
4 1 2 2 1 2 2 2
Output
2
Example 2
Input
2 1 3 2 2 4
Output
-1
Hints
- Put the first array's values in a set.
- Collect each value of the second array that is in that set — into another set, so it is reported only once — then sort.
Approach
Build a set from array a. Walk array b and add every value that is in a's set to a result set, which removes duplicates. Sort the result and print it, or -1 if it's empty. Two sorted sets intersected directly works too.
Complexity: O((n + m) log(n + m)) time · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n;
set<long long> a;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
a.insert(x);
}
cin >> m;
set<long long> common;
for (int i = 0; i < m; i++) {
long long x;
cin >> x;
if (a.count(x)) common.insert(x);
}
if (common.empty()) {
cout << -1 << "\n";
return 0;
}
bool first = true;
for (long long x : common) {
cout << (first ? "" : " ") << x;
first = false;
}
cout << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a = set(data[1 : n + 1])
m = data[n + 1]
b = set(data[n + 2 : n + 2 + m])
common = sorted(a & b)
print(*common if common else [-1])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Set<Long> a = new HashSet<>();
for (int i = 0; i < n; i++) a.add(sc.nextLong());
int m = sc.nextInt();
TreeSet<Long> common = new TreeSet<>();
for (int i = 0; i < m; i++) {
long x = sc.nextLong();
if (a.contains(x)) common.add(x);
}
if (common.isEmpty()) {
System.out.println(-1);
return;
}
StringBuilder sb = new StringBuilder();
for (long x : common) sb.append(sb.length() > 0 ? " " : "").append(x);
System.out.println(sb);
}
}Solve Intersection of Two Arrays online · All practice problems