Frontend School

Merge K Sorted Arrays

DSA
easy

Merge K Sorted Arrays

Easy
Heap
Priority Queue
Arrays
Sorting

Overview

At Meta, efficiently processing and combining large datasets is crucial for many services, from data analytics to user feed generation. Imagine you're working on a system that aggregates data from multiple sources, each providing its information in a pre-sorted list. Your task is to combine these individual sorted lists into one comprehensive, globally sorted list. This problem tests your ability to manage and merge data streams efficiently.

What you need to do / Task

Implement a function mergeKSortedArrays that takes an array of k sorted integer arrays and merges them into a single sorted array.

Input & output

Input:

  • arrays: An array of k arrays, where each inner array arrays[i] contains integers sorted in non-decreasing order.

Output:

  • A single array containing all elements from the input k arrays, sorted in non-decreasing order.

Clarifications

  • Empty input arrays: If an inner array arrays[i] is empty, it should be ignored.
  • Empty outer array: If the input arrays itself is empty or contains only empty arrays, the output should be an empty array.
  • Duplicate values: The input arrays may contain duplicate values. The merged array should also include all duplicates.

Examples

1

Example 1

Input:

arrays = [[1,4,5],[1,3,4],[2,6]]

Output:

[1,1,2,3,4,4,5,6]

Note:

Combine all elements [1,4,5,1,3,4,2,6] and sort them to get [1,1,2,3,4,4,5,6]. Using a min-heap helps pick the smallest element from the heads of the arrays efficiently.

2

Example 2

Input:

arrays = [[]]

Output:

[]

Note:

The input contains an empty array, so the result is an empty array.

3

Example 3

Input:

arrays = [[-1,0,1], [2,3], []]

Output:

[-1,0,1,2,3]

Note:

Merging [-1,0,1] and [2,3] (ignoring the empty array) results in [-1,0,1,2,3].

Constraints

Constraints & assumptions

  • 0 <= arrays.length <= 10^4 (number of sorted arrays, k)
  • 0 <= arrays[i].length <= 500 (length of each individual array)
  • 0 <= sum of arrays[i].length <= 10^5 (total number of elements across all arrays, denoted as N)
  • -10^4 <= arrays[i][j] <= 10^4 (value of elements)
  • Each arrays[i] is sorted in non-decreasing order.

What interviewers evaluate

  • Correctness: The solution correctly merges all sorted arrays into a single, globally sorted array.
  • Efficiency: The solution demonstrates optimal time and space complexity for the given constraints, leveraging appropriate data structures.
  • Code Quality: The code is clean, readable, and well-structured, adhering to good programming practices.
  • Problem Solving: The candidate effectively breaks down the problem, considers edge cases, and articulates their thought process.

Loading editor...