Merging Sorted Arrays | Dataford Interview Questions

The Nielsen measurement pipeline receives k sorted arrays of event timestamps from separate sources. Merge them into one sorted array while preserving duplicates and the overall nondecreasing order.

Use an algorithm that remains efficient when there are many input arrays and each array may have a different length.

Formal Specification

Implement merge_sorted_arrays(arrays).

Input: arrays, a list of k arrays. Each inner array contains integers sorted in nondecreasing order.
Output: A single array containing every input value exactly once per occurrence, sorted in nondecreasing order.
Empty inner arrays are valid. If arrays is empty or all inner arrays are empty, return [].

Constraints

0 <= k <= 10^4
0 <= sum(len(array) for array in arrays) <= 10^5
-10^9 <= array[i] <= 10^9
Every inner array is sorted in nondecreasing order

Function Signature

def merge_sorted_arrays(arrays):

Your question is Merging Sorted Arrays. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem