In this lesson, you’ll see an attempt at improving the brute force solution. You’ll see how this solution is still **suboptimal**, but it’s important to understand before moving on to the optimal solution. The suboptimal solution will be available at the end of the course.

# Hard Interview Question (Suboptimal Solution)

**00:00**
In that first video, you saw a brute force solution where you just put all the values of the linked list into a list, sorted it, and created a final linked list—this should be `# final linked list`

—from those values.

**00:10**
The resulting runtime was *k* * *n* * *log(k * n)*. Let’s see if we can do better.

**00:17**
This solution actually didn’t take advantage that each linked list is sorted. This solution would have worked for any linked list, but let’s see if we can take advantage of the fact that they’re sorted.

**00:28**
So, if you were the computer, how would you actually build this linked list? Basically, how do you know `1`

is supposed to be the first number? Well, you know, all of them are sorted, and you know `1`

is the smallest of all these numbers, so you know `1`

goes here. Then, in your mind, you’re going to be like, “Okay, I’ve already included this one so I’ll just, like, remove it in my mind and then, now, look at which number should I include here?” Well, it’s going to be the smallest, so it’s basically like this is the `2`

, and then this is the `2`

. And then now it’s, “Oh, this is the smallest, so let’s put that in there. This is the smallest, so let’s put that in there.” It’s okay that you’re always looking at the front, because these linked lists are sorted, so you can always guarantee that the front value will be smaller than the rest of the values. Okay, so conceptually, that doesn’t seem too hard, but in the code, that might be a little difficult.

**01:16**
I’m just going to delete all this code. It’ll all be in the ZIP file at the very end, but basically, let’s try to implement that algorithm. `# look at the front value of all the linked lists`

`find the minimum, put it in the result linked list`

`"remove"`

—I’m going to put it in quotes because obviously, we don’t want to, like, mutate the input, but it’s—like, in our minds—removing that value that we’ve added.

**01:41**
`# "remove" that value that we've added`

. `keep going until there are no more values to add`

.

**01:49**
Let’s put this `Link()`

back and then get started. Okay, so let’s try to look at the front value of all the linked lists. Something like `link.val for link in linked_list`

. Okay, find the minimum. `min_val`

is going to be the `min()`

of `front_vals`

.

**02:05**
`# put it in the result linked list`

. So, we need a `result = Link(0)`

, then a `pointer`

equal to `result`

, same concept as part one where basically, the `result`

is going to be this head node, and then `pointer`

is going to move along the `result`

and add nodes.

**02:22**
Now that we have the `min_val`

, let’s loop through the links again. `for link in linked_list:`

`if link.val == min_val`

, now add it to `result`

.

**02:35**
So, `pointer.next = Link(link.val)`

,

**02:39**
then `pointer = pointer.next`

. And now, `# "remove" that value that we've added`

. So, how are we going to “remove” this `Link`

from our thought process? Well, we can do something like this: get the index like this, enumerate through the linked list, and then do

**02:58**
`linked_lists[i]= link.next`

. So, this is going to mutate the index of the linked list, change it to now be `Link(2)`

.

**03:11**
This is actually not good practice to mutate the input, because in Python you pass by reference, so if something else is referencing this `linked_lists`

list and then you’re mutating it, then that’s not very good.

**03:23**
So really, we need to do something like `copy_linked_list`

(copy of linked list) will be `linked_lists`

, like this, and then—add `s`

—use this whenever we’re doing anything.

**03:36**
So, what this is going to do is copy a reference to each of these linked lists. It won’t copy each linked list, but basically, it’ll create a copy of the list and it will point to each linked list. And then, when we mutate, here, it’s going to just mutate this copy we’ve made, and the initial input will still stay preserved.

**03:56**
You could ask the interviewer, though, if it’s okay to mutate the input, but most of the time I feel like it’s better to create a copy. Okay. So, let’s do something like `print(result, copy_linked_lists)`

, and see what just this code did.

**04:10**
Okay. We got `Link(0)`

, `Link(1)`

. So, it added the `Link(1)`

to `result`

correctly. It got `<hard_interview.Link object>`

. Oh. That’s because, in our `Link`

class, there’s a `__str__()`

method, but this should really be a `__repr__()`

method. That’s a little bit better. Okay.

**04:23**
Now, let’s look at what the `copy_linked_list`

is. So, `copy_linked_list`

has `Link(2)`

, so it actually “removed” this `Link(1)`

from the copy, then `Link(2, Link4))`

, then `Link(3, Link(3))`

, so it didn’t touch either of these.

**04:35**
So, that’s good. So, we have to actually do this over and over again until there are no more values to add. So, `while any(copy_linked_lists)`

—that’s going to check, “Are any of the values in `copy_linked_lists`

not `None`

?” Then, we know that there are still values. Put all of this, like this.

**04:55**
Save. `return result.next`

.

**05:01**
Maybe that’ll just work. `'NoneType' object has no attribute 'val'`

[…] `link.val for link`

. This is line 38. Okay. Well, why does that happen? Well, it’s because some of the values in `copy_linked_lists`

could be `None`

, but this is just checking that any of them are not `None`

, so we need to do a check `if link`

, here, to make sure that we only get the front values of the ones that aren’t `None`

. Okay, now, `link.val == min_val`

. Same issue, here.

**05:27**
When you’re looping for the linked lists of the `copy_linked_lists`

, it could be that they are `None`

already. So, we need to do something like `if link and link.val == min_val`

. And it actually passed.

**05:39**
Let’s look at what the algorithm actually did. It looked at the front values of all the linked lists, found the minimum, which is `1`

, then looped through the front values again to find which linked list is equal to the minimum, remove that, did that process again—`2`

, `2`

, `3`

. This is the minimum, remove that.

**05:58**
So now, really, there’s a `None`

, here. I don’t care about the `None`

, I care about `2`

and `3`

—remove this. `4`

and `3`

—remove this. `4`

and `3`

—remove this.

**06:11**
`4`

, `None`

. Now, this `while any()`

is now going to return `False`

because all of them are `None`

, and then return the `result`

. Okay, I bet you’re thinking maybe there are some optimizations.

**06:23**
We’ll look at that in the next video. But first, let’s look at the runtime of this solution. We actually defined *k* to be the length of the `linked_lists`

, and then *n* to be the max length of any linked list.

**06:36**
And then *k* * *n* to be the upper bound of number of values in all linked lists.

**06:44**
So, let’s look at the runtime using those variables. Well, copying the linked list is only going to take *O(k)*, because that’s the length of `linked_lists`

.

**06:54**
This is constant. This is constant. `while any(copy_linked_lists)`

—so, the actual `while`

condition is going to take *O(k)*, because it has to loop through all the values in `copy_linked_lists`

and check if they are a `True`

value or a `False`

value. Here, this is going to take *O(k)*, because that’s going to loop through all the values in `copy_linked_lists`

. Finding the minimum is going to be *O(k)*.

**07:17**
This loop right now is going to run *O(k)* times, as well.

**07:22**
This is constant, constant, constant, constant. So, this whole `while`

loop takes *O(k)*, because it’s basically *O(k)* + *O(k)* + *O(k)* + *O(k)*, and that’s still *O(k)*.

**07:35**
But now the question is `# how many times does the while loop run?`

We know that the `while`

loop, each time, will take *O(k)* time.

**07:43**
How many times does it run? Well, looking at that algorithm again, you’d have to look at this value, remove it, then check all these values, remove the minimum, then check this value, remove it, then check these values, remove it, et cetera. By the end, it’s going to have done *k* * *n* iterations, because that’s an upper bound of all values in all linked lists. So, what is our final runtime?

**08:07**
Final runtime is *O(k * n * k)*, because this is the number of times that we executed the `while`

loop, and this is how much time each `while`

loop took. Okay, so remember from part one, the brute force solution—`# brute force`

—

**08:24**
final runtime was *k* * *n* * *log(k * n)*, and now this current solution is *k* * *n* * *k*. So, this solution is actually slower than the brute force solution, unless of course, *n* is really, really, really large, and this log becomes greater than this *k*. But most of the time, this solution is actually worse.

**08:47**
But this idea of sort of finding these values and mutating it, or removing it, or something like that will be really useful in the next video, where we optimize this solution to be better than the brute force solution.

**mdwikira** on Sept. 14, 2021

My solution for the suboptimal version.

```
class Link:
def __init__(self, val, next=None):
self.val = val
self.next = next
def __str__(self):
if not self.next:
return f"Link({self.val})"
return f"Link({self.val}, {self.next})"
def merge_k_linked_lists(linked_lists):
'''
Merge k sorted linked lists into one
sorted linked list.
>>> print(merge_k_linked_lists([
... Link(1, Link(2)),
... Link(3, Link(4))
... ]))
Link(1, Link(2, Link(3, Link(4))))
>>> print(merge_k_linked_lists([
... Link(1, Link(2)),
... Link(2, Link(4)),
... Link(3, Link(3)),
... ]))
Link(1, Link(2, Link(2, Link(3, Link(3, Link(4))))))
'''
result = None
last = None
ll = linked_lists[:]
while ll[0:]:
smallest = min(ll, key=lambda x: x.val)
ll.remove(smallest)
if smallest.next:
ll.append(smallest.next)
smallest.next = None
if result == None:
last = smallest
result = last
continue
last.next = smallest
last = last.next
return result
```

Become a Member to join the conversation.

ambreen2006on Nov. 19, 2020Thank you for this wonderful tutorial. I’m finding it very useful.

I think in the sub-optimal solution provided in the video + code, there is no need to separately iterate for the min value and the index to which the min val belongs to. So I can write something like this:

But please do correct me if I overlook something.