Problems / Merge K Sorted Lists
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