Baseline Arrays · Easy O(n + m) · O(1) auxiliary (excluding the output)
Two replicas each keep their own sorted stream of audit event ids, and a compliance job needs the combined set of distinct ids. Both streams are long enough that concatenating and re-sorting would be wasteful, so the merge should walk them side by side and emit each id exactly once.
Input: Two sorted arrays arr1 and arr2 with sizes n and m respectively.
Output: A sorted array containing every distinct value that appears in either input.
1 <= n, m <= 10^5-10^9 <= arr1[i], arr2[j] <= 10^9arr1 and arr2 are each sorted in non-decreasing orderInput: {"n":5,"arr1":[1,2,3,4,5],"m":3,"arr2":[1,2,3]}
Output: [1,2,3,4,5]
Every id of the shorter stream already appears in the longer one, so the union is just the longer stream.
Input: {"n":5,"arr1":[2,2,3,4,5],"m":5,"arr2":[1,1,2,3,4]}
Output: [1,2,3,4,5]
Repeated ids inside each stream are collapsed, and shared ids are emitted once.