7. Union and Intersection of Two Sorted Arrays

Given two sorted arrays, print their union (sorted, distinct values present in either array) on the first line, then their intersection (sorted, distinct values present in both) on the second line. If the intersection is empty, print 'None' on the second line.

Input: The first line contains n1 followed by a line with n1 space-separated sorted integers. The next line contains n2 followed by a line with n2 space-separated sorted integers. Output: Print the union on the first line and the intersection on the second line, both sorted and distinct; print 'None' on the second line if the intersection is empty.

1 <= n1, n2 <= 10^5

This problem elegantly computes two related results (union and intersection) in a SINGLE pass, rather than two separate passes - recognizing that both can share the same underlying two-pointer walk avoids redundant work.

Given two sorted arrays, find both their union (every distinct value from either array) and their intersection (only the values present in both). Brute force: Use hash sets to compute the union and intersection directly - this works and is simple, but doesn't take advantage of the fact that both arrays are ALREADY sorted, which allows an even simpler two-pointer merge without any hashing at all. Optimised: Since both arrays are sorted, a single two-pointer merge-style walk computes BOTH the union and intersection simultaneously in one pass - matching values go to both results, smaller values go only to the union, and duplicates within the same array are simply skipped when encountered again.

Insert all elements of both arrays into a hash set to get the union directly (duplicates collapse automatically), then sort that set for printing. For the intersection, insert the first array's elements into a hash set and then iterate through the second array checking membership in that set, collecting each match once and removing it from the set afterward to avoid duplicates. This uses hashing instead of the arrays' sortedness, giving linear expected time without exploiting the two-pointer merge structure. Time: O(n1+n2) expected Space: O(n1+n2)

Since both arrays are already sorted, walk them simultaneously with two pointers as in a merge-sort merge step: whenever the current elements differ, output the smaller one to the union and advance only that pointer (skipping any immediate duplicate repeats within the same array); whenever they're equal, output the value to both the union and the intersection and advance both pointers. This produces both results in a single linear pass with no hashing and only O(1) extra bookkeeping space beyond the output. Time: O(n1+n2) Space: O(1) extra (excluding output)

Compute the union by inserting every element of both arrays into a set and then sorting that set. Compute the intersection by, for every element of the first array, scanning the entire second array with a nested loop to see if it appears there, adding it to the intersection result only once. This works regardless of whether the arrays are sorted, but it ignores the sorted structure and pays a quadratic cost for the intersection. Time: O(n1*n2) for intersection, O((n1+n2) log(n1+n2)) for union Space: O(n1+n2)

1. Keep a pointer into each array, both starting at the beginning. 2. Compare the two pointers' current values: if they match, that value belongs to BOTH the union and the intersection - record it once in each, and advance both pointers. 3. If one value is smaller, it belongs to the union only (unless it's a duplicate of something already added) - record it and advance just that pointer. 4. Once one array is exhausted, append any remaining distinct values from the other array directly to the union.

Time: O(n1 + n2) - a single linear pass across both arrays combined. Space: O(n1 + n2), for the union and intersection result lists.

n1 = n2 = 1 (smallest arrays); duplicate values within a single array, which must be de-duplicated in the output; no overlap between the arrays (print 'None' for the intersection); and n1 or n2 at 10^5 (confirming the two-pointer merge is O(n1+n2)).

Be careful to skip duplicate VALUES within the same array (not just across arrays) so the union and intersection both contain only distinct values, exactly as the problem requires.