Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Put the first array's values in a set.
  2. 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