LeetCode: Problem 23 - Merge K Sorted Lists

Question

The problem stated on LeetCode is as follows:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6

I am able to pass 129 out of 131 test cases but hit "time limit exceeded" on case 130. Below is my implementation.

Can someone spot the bottleneck? Any suggestions on improving time complexity?

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # def print_lists(self, lists):
    #     idx = 0
    #     while idx < len(lists):
    #         ptr = lists[idx]
    #         _l = []
    #         while ptr is not None:
    #             _l.append(ptr.val)
    #             ptr = ptr.next
    #         idx += 1
    #         print(_l)

    def min_idx(self, lists):
        idx = 0

        for i in range(len(lists)):
            if lists[i] is None:
                continue
            elif lists[idx] is None:
                idx = i
            elif lists[i].val < lists[idx].val:
                idx = i
        return idx

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        head = tail = ListNode(-1)

        while len(lists) > 0:
            m_idx = self.min_idx(lists)

            if lists[m_idx] is None:
                return head.next

            tail.next = lists[m_idx]
            tail = tail.next
            lists[m_idx] = lists[m_idx].next

            if lists[m_idx] is None:
                del lists[m_idx]

        return head.next

I run into the "time limit exceeded" issue with our without using del. Test case 130 contains 10,000 LinkedLists.

Don't use del lists[m_idx], it will convert your algorithm into a quadratic one.. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented May 7, 2019 at 18:30
Look into priority queues. The idea is keep the first element of each list along with the list it came from. Then you repeatedly take the smallest element from the queue and replenish it from the list it came from. heapq.merge() already implements this, but using it might be considered cheating so you may want to go a level deeper. docs.python.org/3/library/heapq.html#heapq.merge — NPE
– NPE, Commented May 7, 2019 at 18:40
I got accepted with your code using python3, tle using python ^^ — juvian
– juvian, Commented May 7, 2019 at 18:42
For some reason, switching from python3 to python, then back to python3 resolved the issue. Interesting spot @juvian — bcr
– bcr, Commented May 7, 2019 at 18:47

juvian · Accepted Answer · 2019-05-07 19:00:13Z

1

Here is a simpler and faster version of your code that avoids several ifs:

def min_idx(self, lists):
    idx = 0

    for i in range(len(lists)):
        if lists[i].val < lists[idx].val:
            idx = i
    return idx

def mergeKLists(self, lists):
    head = tail = ListNode(-1)

    lists = list(filter(lambda x: x is not None, lists))

    while len(lists) > 0:
        m_idx = self.min_idx(lists)

        tail.next = lists[m_idx]
        tail = tail.next
        lists[m_idx] = lists[m_idx].next

        if lists[m_idx] is None:
            del lists[m_idx]

    return head.next

For an even better time you will need to change the implementation to either:

Use heap to reduce the min_idx operation to O(log k) instead of O(k) being k the amount of lists
Just throw all to a single array, sort it and put it back into a ListNode
Make the merging of 2 lists in O(length of longest list) and recursively merge in pairs until 1 left

answered May 7, 2019 at 19:00

juvian

16.1k2 gold badges42 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ragtime Over a year ago

fyi: this solution still returns a Time Limit Exceeded on this test case: leetcode.com/submissions/detail/795535228/testcase

juvian Over a year ago

makes sense, I just reimplemented OP's algorithm but as I mentioned below there are multiple improvements to be made

Collectives™ on Stack Overflow

LeetCode: Problem 23 - Merge K Sorted Lists

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related