Problem 🤔

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1

Input: lists = [[1,4,5],[1,3,4],[2,6]]

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

Explanation

The linked-lists are:

merging them into one sorted list:

Example 2

Input: lists = []

Output: []

Example 3

Input: lists = [[]]

Output: []

Note

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length won’t exceed 10^4

Real World Applications 🌎

When creating data sets merging multiple sources is a very common task.

The Finer Details 🔎

The naive way to do this would throw all the values of all nodes in linked list into a list. We could then sort, and build the output in order. This is very inefficient though.

Solution 💡 - Naive Solution

Complexity Analysis 🧮

Time complexity

O(n*log(n)):

Getting all values from all lists is O(n). Sorting is O(n*log(n))

Space complexity

O(n)

Creating and returning new list of nodes of size n.

Solution 💡 - Using a Heap

Any better ideas? Remember, k sorted elements should always give you a hint to see whether or not a heap (priority queue) can be used.

So — is there are oppurtunity to use a priority queue here? Absolutely :) Let’s put the first values in our sorted linked list into a minheap. We can always pop the smallest value in the heap and increment to the next of the popped node. And then we insert that into our minheap as well! This will let us create our output without sorting and take advantage of the fact that each list is sorted within itself.

At any given point we’ll need to hold references to the current node in every linked list that hasn’t been sorted yet. We can hold all those “current nodes in a list” and for every iteration sort them. This will work!

Complexity Analysis 🧮

Time complexity

O(n*log(k)) -> To build the heap we iterate through n points. For every point we perform and insert (or pop) on the heap with a complexity of log(k).

Space complexity O(n) -> Creating and returning our output of size n.

Takeaways 🎉🥳

Needing to keep track of k elements should always hint at using a heap! Keep this trick in mind :)

Resources 📚 💻

Leetcode