Merge K Sorted Lists (LeetCode #23)

Image by Tomas Sobek on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Course Schedule.

Introduction

If you’re looking for a walkthrough of an optimal solution to the LeetCode Merge K Sorted Lists problem, you’re in the right spot.

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.

Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.

Let’s get it started!

Understanding the Problem 🕵🏻‍♂️

The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):

1. We’ll be given a variable-length list of singly-linked lists called lists
2. The length of lists will be 0 <= len(lists) <= 10^4
3. Each list will have been sorted in ascending order
4. We should merge the linked lists into one sorted linked list and return it

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

Okay. I think that’s enough housekeeping items for us to get started!

Understanding Heaps 📚

It turns out that this entire problem hinges on knowing what Heaps are and how to use them (or at least, my solution uses them extensively). If you don’t know what the Heap data structure is, you can learn about them right here.

The TLDR is that they allow you to use an ordinary list (e.g. [1, 2, 3, 4, 5] or some other set of values) to insert, order, and retrieve values in O(log n) time (that’s the time complexity for inserts and retrievals).

The reason a Heap can achieve this level of speed is because they utilize a Binary Search pattern to store data in the list. For instance, let’s say I add the number 5 to the list. Here’s what we’ll start with:

heap = [5]

Not too much going on here yet, right?

Next, we’ll add 6 to the list. Under the hood, this is what the data structure looks like:

heap = [5, None, 6]

Wait. What? Why does it look like that?

Start looking at this list as a Tree data structure. The number 5 is the root at the 0 index, its lefthand child is empty (or None) at the index 1, and its righthand child node has the value of 6 at index 2. Makes sense, right?

Is there a pattern for this?

There is. It turns out we can find out the indices for any given “node” in our list by multiplying the current index by 2 and then adding 1 for the lefthand child and 2 for the righthand child.

For the heap in the example above, this means that:

heap = [5, None, 6]
        ^  ^     ^
Index:  0  1     2
Children of root node at index 0:
- Left child is 0 (root index) * 2 + 1 (left child) = 1
- Right child is 0 (root index) * 2 + 2 (right child) = 1

This rule holds true for any new values we add. For instance, let’s add 10 to the heap:

heap = [5, None, 6, None, None, None, 10]

Try doing the mental calculation here as to why we placed 10 in this spot.

I’ll wait.

That’s right. We move down the righthand side of our pseudo-tree structure until we get to 6. Once there, we know we’d want to make a child node under it on the righthand size.

If we were storing this in an actual Binary Search Tree, this is how it would look:

This is how we got the calculations on where to place the value 10 in our heap:

2 (index of value 6) * 2 + 2 (new child is on righthand size)
= 6 (new index of child)

Any index positions in between will be filled with None.

If we wanted to remove something from our heap, we should pop off the root (value 5 in the example above). At this point, our heap would look like this:

heap = [None, None, 6, None, None, None, 10]

From here, the heap logic will bubble up the next minimum values one at a time (in log(n) time) until our heap look like this:

heap = [6, None, 10]

Makes sense, right? We’ve kept our binary search structure but just bubbled up values until the next minimum value (currently 6) is the root value.

We can now search up and down our heap the same way we’d search any other binary tree.

Heaps are very powerful and would make a great article all on their own, but this is probably enough understanding for us to get started with solving the problem!

Initial Problem Setup 🏗

While it’s possible to write a Heap implementation from scratch (note that this link is one I did in JavaScript), that’s honestly for another day. Python as a language has a Heap implementation called heapq that we can use just by importing it.

Let’s go ahead and import the functions we need for this, and then I’ll explain what they do:

There’s quite a bit already going on here, so let’s take it one step at a time:

1. First, we’re importing heappop and heappush from the heap implementation in Python called heapq. heappush adds a new value to the heap and sorts it relative to the other values in log n time and heappop removes a value and sorts remaining values in log n time.
2. Next, we have a definition of a ListNode class that LeetCode provides to us. This is so we know what the incoming lists look like and also to use to create final nodes in the merged list we will return.
3. Finally, we have the start of our merge_k_lists function. We have lists coming in (which is a list of singly-linked lists) and the initial definition of our heap.

Nice 🤌🏻

Let’s go ahead and start adding our values from each list.

Adding Lists to the Heap 📚

Believe it or not, this part is going to be fairly straightforward. All we need to do is iterate through every list, traverse every list, and heappush each value into our heap-ified list. Our heap will sort everything for us.

Here’s what that will look like:

We’re essentially starting at each root node for each list (which we assign to current in the code above), use heappush to put that node’s value into the heap, set current to be current.next, and keep continuing that until our current value is None. We then progress on to the other lists and repeat this process until we’re done.

That’s it! Due to the awesome sorting properties of the heap data structure, we have the minimum value at the top of the heap when we’re done.

This allows us to start in on the final part of the problem — creating our new, merged list. 🔥

Creating Our Sorted Linked List 🖇

The very next thing we need to do is to check if heap is empty. This might happen if we’re given an empty lists argument (e.g. we don’t have any lists to merge).

We can check with a simple if statement:

Right on.

Now, we just need to basically do the reverse of our first loop; we can create a new root node and then progressively heappop values off our heap to add them to a new singly-linked list until we have no more values left.

Here’s what that will look like:

First, we instantiate a new ListNode and pass the result of heappop(heap) into it as the first value (which is the current minimum value in our heap, removed in O(log n) time). This is assigned to a new new_root value that will ultimately be our returned root node.

Next, we create a new current variable which we assign the value of new_root to.

Next, we create a while loop that will run for as long as our heap has length (e.g. has values in it).

Finally, we create a new node inside our loop for every value we heappop off, assign that to the current.next's value, and then update current to be this new node.

Once the heap is empty and our loop is complete, we’re done!

BOOM. ✅

How does it feel to have solved the problem?

This solution will run in a total time complexity of O(n log n) where n is the total length of all lists in the lists parameter. This is because we iterate over every value (the first n pass) and then insert/remove them (in log n time due to us using a heap).

The space complexity is O(n) where n is the total length of all lists in the lists parameter.

Conclusion

Nice work. We got through our first hard LeetCode problem together. That wasn’t so bad, was it?

Keep an eye out for the rest of these Blind 75 coding challenges articles. It’s going to be a fun ride.

Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)