CodingGyan

Set Operations

easy Java Collections

Problem

Two arrays are given. Treat them as sets (repeated values count once). Print three lines: union: all different values in any of them, intersection: values in both, difference: values in the first array but not in the second. Each list is sorted in ascending order. Print none if a list is empty.

Constraints

  • 1 <= n, m <= 10^5

Examples

Input

3
1 2 3
3
2 3 4

Output

union: 1 2 3 4
intersection: 2 3
difference: 1

Solutions

Best approachTime O((n + m) log(n + m))Space O(n + m)

Set operations are built into the collections: addAll is the union, retainAll the intersection, removeAll the difference. Always copy the set first, because these methods change the set you call them on.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Set operations.
 * Input   : Two arrays.
 * Output  : Three lines.
 * Approach: Sets.
 * Time    : O((n + m) log(n + m))
 * Space   : O(n + m)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Makes the text of one sorted set. An empty set is printed as none.
        static String text(java.util.Set<Integer> values) {
            if (values.isEmpty()) {
                return "none";
            }
            StringBuilder text = new StringBuilder();
            for (int value : values) {
                text.append(text.length() == 0 ? "" : " ").append(value);
            }
            return text.toString();
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(int[] a, int[] b) {
        // Step 1: Copy both arrays into TreeSets. A TreeSet removes duplicates and keeps the values sorted.
        java.util.TreeSet<Integer> first = new java.util.TreeSet<>();
        java.util.TreeSet<Integer> second = new java.util.TreeSet<>();
        for (int value : a) {
            first.add(value);
        }
        for (int value : b) {
            second.add(value);
        }

        // Step 2: The set operations: addAll = union, retainAll = intersection, removeAll = difference. Each works on a copy.
        java.util.TreeSet<Integer> union = new java.util.TreeSet<>(first);
        union.addAll(second);
        java.util.TreeSet<Integer> intersection = new java.util.TreeSet<>(first);
        intersection.retainAll(second);
        java.util.TreeSet<Integer> difference = new java.util.TreeSet<>(first);
        difference.removeAll(second);

        return new String[] {"union: " + text(union), "intersection: " + text(intersection), "difference: " + text(difference)};
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        int sizeB = scanner.nextInt();
        int[] b = new int[sizeB];
        for (int i = 0; i < sizeB; i++) {
            b[i] = scanner.nextInt();
        }
        System.out.println(String.join("\n", solve(a, b)));
    }
}
Hints (1)
  1. Which method keeps only the common values?