Katkat
Back

Merge K Sorted Arrays Without Duplicates

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently merge multiple sorted sequences into a single sorted stream while managing duplicate values using a priority queue.

Merge K Sorted Arrays Without Duplicates

Given an array of k sorted integer arrays, write a function to return a single sorted array containing all elements from the input arrays, with all duplicates removed.

Function Signature

def merge_k_sorted_arrays(arrays: List[List[int]]) -> List[int]:

Constraints

  • k (number of arrays) is between 0 and 10^3.
  • The total number of elements N across all arrays is at most 10^5.
  • Arrays are pre-sorted in ascending order.
  • You should aim for a time complexity of O(N log k) and space complexity of O(k) (excluding the output array).

Examples

Example 1: Input: [[1, 3, 5], [2, 3, 6], [1, 5, 7]] Output: [1, 2, 3, 5, 6, 7] Explanation: After merging, 1, 3, and 5 appear multiple times but are kept only once in the final result.

Example 2: Input: [[], [1, 2], [2]] Output: [1, 2]

Considerations

  • How will you handle an empty list of arrays or arrays that are empty?
  • Ensure your duplicate handling is efficient (avoiding unnecessary re-scans of the merged list).
  • Consider using a min-heap to keep track of the smallest current element across the k arrays.

Hints

Hint 1

Maintain a min-heap containing tuples of (value, array_index, element_index) to track the smallest available element across all arrays.

Hint 2

Whenever you extract the minimum value from the heap, compare it with the last value added to your result list to skip duplicates.

Hint 3

After extracting an element, insert the next element from the same source array into the heap if one exists.

Follow-up questions

  • How would your approach change if the input arrays were sorted in descending order instead of ascending?
  • If the total number of elements N is extremely large (e.g., too large to fit in memory), how would you modify your solution to return an iterator instead of a list?
  • What is the impact on your time complexity if you use a hash set to deduplicate instead of comparing with the last inserted element?