Katkat
Back

Merge Multiple Sorted Arrays

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently merge multiple sorted arrays into a single sorted list using a priority queue (min-heap) to optimize performance.

Problem Statement

Given an array of k sorted integer arrays, write a function to merge all of them into one single sorted array. You should aim for an efficient solution that minimizes time and space complexity.

Function Signature

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

Constraints

  • k (number of arrays) is between 0 and 10^4.
  • The total number of elements n across all arrays is between 0 and 10^5.
  • All input integers are within the range [-10^6, 10^6].

Example 1

Input: [[1, 4, 5], [1, 3, 4], [2, 6]] Output: [1, 1, 2, 3, 4, 4, 5, 6]

Example 2

Input: [[], [1], []] Output: [1]

Edge Cases

  • Empty input list of arrays.
  • Arrays containing different lengths or empty sub-arrays.
  • Handling arrays with identical values (duplicates should be preserved).

Hints

Hint 1

Consider using a min-heap to keep track of the smallest current element among all arrays.

Hint 2

Store a tuple in the heap containing the value, the index of the array it came from, and the index of the element within that array.

Hint 3

After extracting the minimum element from the heap, insert the next element from the same source array into the heap until all elements are exhausted.

Follow-up questions

  • What is the time and space complexity of your solution in terms of `n` (total elements) and `k` (number of arrays)?
  • How would your approach change if the arrays were stored on disk and could not all fit into memory simultaneously?
  • Can you solve this using a divide and conquer strategy (similar to merge sort), and how does that compare to the heap-based approach?