Merge K Sorted Lists Solution for Amazon

Company: Amazon · Difficulty: Hard · Topics: Linked List, Divide and Conquer, Heap, Merge Sort

Problem Statement

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.

Examples

Example 1:

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

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

Explanation: Merging the three sorted lists gives us a sorted list.

Example 2:

Input: lists = []

Output: []

Explanation: No lists to merge.

Example 3:

Input: lists = [[]]

Output: []

Explanation: Empty list.

Example 4:

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

Output: [1,2,3,4,5,6,7,8,9]

Explanation: Merging three sorted lists.

Intuition

The key insight is to use a divide-and-conquer approach or a min-heap to efficiently merge multiple sorted lists. We can merge lists two at a time or use a heap to always pick the smallest element.

Approach

Approach 1: Divide and Conquer (Optimal)

1. Merge lists two at a time

2. Continue until only one list remains

3. This reduces the problem to merging two sorted lists repeatedly

Approach 2: Min Heap

1. Use a min heap to store the head of each list

2. Extract the minimum element and add it to result

3. Add the next element from the same list to heap

Approach 3: Brute Force

1. Collect all elements from all lists

2. Sort the combined list

3. Create a new linked list from sorted elements

Dry Run

Let's trace through Example 1: lists = [[1,4,5],[1,3,4],[2,6]]

Divide and Conquer Approach:

Step 1: Merge [1,4,5] and [1,3,4] → [1,1,3,4,4,5]
Step 2: Merge [1,1,3,4,4,5] and [2,6] → [1,1,2,3,4,4,5,6]

Min Heap Approach:

Heap: [1,1,2] (heads of all lists)
Extract 1, add 4 to heap: [1,2,4]
Extract 1, add 3 to heap: [2,3,4]
Extract 2, add 6 to heap: [3,4,6]
Continue...

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Divide and Conquer (Optimal)

Time Complexity: O(n log k) - We merge log k times

Space Complexity: O(1) - Only need a few variables

Solution 2: Min Heap

Time Complexity: O(n log k) - Each element is inserted/extracted once

Space Complexity: O(k) - Heap size

Solution 3: Brute Force

Time Complexity: O(n log n) - Sort all elements

Space Complexity: O(n) - Store all elements