You are given an array of k sorted integer arrays, where each array is sorted in ascending order. Merge these arrays into a single sorted array.

Function Signature:

from typing import List

def merge_sorted_arrays(arrays: List[List[int]]) -> List[int]:
    """
    Merge the given sorted arrays into a single sorted array.

    Parameters:
    - arrays: A list of k sorted integer arrays.

    Returns:
    - List[int]: The merged sorted array.
    """
    # Your code here

Example:

arrays = [
    [1, 3, 5],
    [2, 4, 6],
    [0, 7, 8]
]

result = merge_sorted_arrays(arrays)
# Merged Sorted Array: [0, 1, 2, 3, 4, 5, 6, 7, 8]
assert result == [0, 1, 2, 3, 4, 5, 6, 7, 8]
print(result)

Note:

  • The input arrays are sorted in ascending order.
  • The length of each array can vary.
  • The final merged array should also be sorted in ascending order.

Instructions:

  • Write the merge_sorted_arrays function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊