Hard
Merge K Sorted Lists
Hard
0 submissions
50 coins
+200 XP
Divide and Conquer
Heap (Priority Queue)
Linked List
Sorting
Problem Description
## Problem
You are given an array of `k` sorted integer arrays. Merge all the arrays into one sorted array and return the **length** of the merged array.
Each sub-array is already sorted in non-decreasing order.
## Examples
**Example 1:**
```
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: 8
Explanation: Merged list is [1,1,2,3,4,4,5,6] which has length 8.
```
**Example 2:**
```
Input: lists = []
Output: 0
```
**Example 3:**
```
Input: lists = [[]]
Output: 0
```
## Approach Hints
Use a min-heap of size `k` to always extract the smallest current element across all lists in O(N log k) time, where N is the total number of elements.
Constraints
- `k == lists.length`
- `0 <= k <= 10000`
- `0 <= lists[i].length <= 500`
- `-10000 <= lists[i][j] <= 10000`
- Each `lists[i]` is sorted in non-decreasing order.
- The sum of `lists[i].length` will not exceed 10000.
Need help?
Connect with expert programmers for real-time collaborative coding, video meetings, and whiteboard sessions via CodeConnect.
Video Call
Whiteboard
Live Coding
Screen Share