Jobs

Interviews

Discussions

Merge k Sorted Lists

Hard

Palantir

0 views

Topics:

Linked Lists

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:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted linked list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

k == lists.length
0 <= k <= 10⁴
0 <= lists[i].length <= 500
-10⁴ <= lists[i][j] <= 10⁴
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 10⁴.

Merge k Sorted Lists

Hard

Palantir

0 views

Topics:

Linked Lists

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:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted linked list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

k == lists.length
0 <= k <= 10⁴
0 <= lists[i].length <= 500
-10⁴ <= lists[i][j] <= 10⁴
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 10⁴.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of linked lists (k) and what is the maximum length of each linked list in the input array?
Can the linked lists contain negative values, zero, or just positive integers?
Is it possible for the input list `lists` to be null or empty, and if so, what should the return value be in those cases?
Are duplicate values allowed within and across the linked lists, and should they be preserved in the merged result?
Is there a requirement for the merged linked list to be a new list, or can I modify the existing linked lists in place to create the merged list (avoiding creating new nodes if possible)?

Brute Force Solution

Approach

The brute force way to combine many sorted lists into one big sorted list is simple, but not very efficient. We basically dump everything into one big pile, then sort the whole pile from scratch. This ensures the final result is correctly sorted, but involves a lot of extra work.

Here's how the algorithm would work step-by-step:

First, take all the numbers from all the lists and put them into one single, big list.
Now that you have one big list with all the numbers, completely forget that the original lists were sorted.
Next, sort this entire big list from the smallest number to the largest number, using any sorting method.
The result is a single, sorted list containing all the numbers from all the original lists, merged together.

Code Implementation

def merge_k_sorted_lists_brute_force(list_of_lists):
    merged_list = []

    # Combine all elements from all lists into a single list.
    for sorted_list in list_of_lists:
        merged_list.extend(sorted_list)

    # Sort the combined list.
    merged_list.sort()

    return merged_list

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(N log N) – The brute force approach first gathers all elements from the k sorted lists into a single list. If the total number of elements across all k lists is N, then this step takes O(N) time. The next step sorts this combined list of N elements. A typical efficient sorting algorithm like merge sort or quicksort has a time complexity of O(N log N). Therefore, the dominant operation is the sorting step, making the overall time complexity O(N log N).

Space Complexity

O(N) – The brute force approach first gathers all elements from the k sorted lists into a single, big list. This requires creating a new list to store all N total elements, where N is the sum of the lengths of all input lists. Sorting this big list in-place might reduce auxiliary space, but this explanation doesn't specify in-place sorting. Therefore, the dominant space usage is the temporary list of size N, which leads to O(N) auxiliary space.

Optimal Solution

Approach

We want to combine multiple sorted lists into one big sorted list as quickly as possible. The best way to do this is to use a 'divide and conquer' strategy, like organizing a tournament bracket. This approach breaks the big problem into smaller, easier-to-solve subproblems.

Here's how the algorithm would work step-by-step:

Pair up the lists and merge each pair into a single sorted list. This means combining two lists at a time in a way that keeps everything in order.
Repeat this process, pairing up the newly merged lists and merging them again. Keep doing this until you have only one list left.
Each merge step efficiently combines two sorted lists by repeatedly comparing the first elements of each list and picking the smaller one to add to the result. This is faster than other approaches because you only need to compare the beginning of each list.
By repeatedly merging pairs of lists, we systematically reduce the number of lists until we arrive at the single, fully sorted result.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(list_of_linked_lists):
    if not list_of_linked_lists:
        return None

    while len(list_of_linked_lists) > 1:
        merged_lists = []
        for i in range(0, len(list_of_linked_lists), 2):
            list1 = list_of_linked_lists[i]
            list2 = list_of_linked_lists[i + 1] if (i + 1) < len(list_of_linked_lists) else None
            
            # Pair up the lists and merge them
            merged_lists.append(merge_two_lists(list1, list2))

        list_of_linked_lists = merged_lists

    return list_of_linked_lists[0]

def merge_two_lists(list1, list2):
    dummy_node = ListNode()
    tail = dummy_node

    # Iteratively pick the smaller node
    while list1 and list2:
        if list1.val < list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next

    # Append the remaining nodes, if any
    if list1:
        tail.next = list1
    if list2:
        tail.next = list2

    return dummy_node.next

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(N log k) – Let k be the number of sorted lists, and N be the total number of elements across all lists. The algorithm repeatedly merges pairs of lists. In each merge step, we are effectively processing all N elements once. Since we are halving the number of lists in each step (like a binary tree), there are log k merge steps. Therefore, the total time complexity is O(N log k), where N is the total number of elements and k is the number of lists.

Space Complexity

O(N) – The algorithm merges lists in pairs, creating new sorted lists. In the worst case, during intermediate merge steps, we may need to hold lists containing close to all N elements (where N is the total number of elements across all k lists) before the final merged list is constructed. The space is used to store the newly merged lists at each step. Therefore, the auxiliary space used is proportional to the total number of elements N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input list (lists is null or empty)	Return null immediately, as there are no lists to merge.
Input list contains null or empty lists	Treat null or empty lists as if they don't exist, skipping them during the merge process.
All input lists are empty	The merged list should be empty (return null) since all contributing lists are empty.
Input list contains only one non-empty list	Return the single non-empty list directly, as it's already sorted.
Lists contain duplicate values within themselves and across different lists	The solution should correctly handle duplicates, maintaining their order in the merged list.
Lists contain a very large number of elements, approaching memory limits	Consider a divide-and-conquer approach or using an iterative merge to avoid stack overflow or excessive memory consumption.
Lists contain extremely large or small integer values	Ensure integer overflow is handled appropriately, using `long` if necessary, depending on language constraints.
One list is significantly longer than all others	The algorithm's performance should not degrade significantly; priority queue based solutions handle this gracefully.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of linked lists (k) and what is the maximum length of each linked list in the input array?
Can the linked lists contain negative values, zero, or just positive integers?
Is it possible for the input list `lists` to be null or empty, and if so, what should the return value be in those cases?
Are duplicate values allowed within and across the linked lists, and should they be preserved in the merged result?
Is there a requirement for the merged linked list to be a new list, or can I modify the existing linked lists in place to create the merged list (avoiding creating new nodes if possible)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, take all the numbers from all the lists and put them into one single, big list.
Now that you have one big list with all the numbers, completely forget that the original lists were sorted.
Next, sort this entire big list from the smallest number to the largest number, using any sorting method.
The result is a single, sorted list containing all the numbers from all the original lists, merged together.

Code Implementation

def merge_k_sorted_lists_brute_force(list_of_lists):
    merged_list = []

    # Combine all elements from all lists into a single list.
    for sorted_list in list_of_lists:
        merged_list.extend(sorted_list)

    # Sort the combined list.
    merged_list.sort()

    return merged_list

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Pair up the lists and merge each pair into a single sorted list. This means combining two lists at a time in a way that keeps everything in order.
Repeat this process, pairing up the newly merged lists and merging them again. Keep doing this until you have only one list left.
Each merge step efficiently combines two sorted lists by repeatedly comparing the first elements of each list and picking the smaller one to add to the result. This is faster than other approaches because you only need to compare the beginning of each list.
By repeatedly merging pairs of lists, we systematically reduce the number of lists until we arrive at the single, fully sorted result.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(list_of_linked_lists):
    if not list_of_linked_lists:
        return None

    while len(list_of_linked_lists) > 1:
        merged_lists = []
        for i in range(0, len(list_of_linked_lists), 2):
            list1 = list_of_linked_lists[i]
            list2 = list_of_linked_lists[i + 1] if (i + 1) < len(list_of_linked_lists) else None
            
            # Pair up the lists and merge them
            merged_lists.append(merge_two_lists(list1, list2))

        list_of_linked_lists = merged_lists

    return list_of_linked_lists[0]

def merge_two_lists(list1, list2):
    dummy_node = ListNode()
    tail = dummy_node

    # Iteratively pick the smaller node
    while list1 and list2:
        if list1.val < list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next

    # Append the remaining nodes, if any
    if list1:
        tail.next = list1
    if list2:
        tail.next = list2

    return dummy_node.next

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input list (lists is null or empty)	Return null immediately, as there are no lists to merge.
Input list contains null or empty lists	Treat null or empty lists as if they don't exist, skipping them during the merge process.
All input lists are empty	The merged list should be empty (return null) since all contributing lists are empty.
Input list contains only one non-empty list	Return the single non-empty list directly, as it's already sorted.
Lists contain duplicate values within themselves and across different lists	The solution should correctly handle duplicates, maintaining their order in the merged list.
Lists contain a very large number of elements, approaching memory limits	Consider a divide-and-conquer approach or using an iterative merge to avoid stack overflow or excessive memory consumption.
Lists contain extremely large or small integer values	Ensure integer overflow is handled appropriately, using `long` if necessary, depending on language constraints.
One list is significantly longer than all others	The algorithm's performance should not degrade significantly; priority queue based solutions handle this gracefully.