Merge K Sorted Runs
medium
HeapSortingDivide And ConquerMerge K Sorted
Asked atGoogleAmazonMicrosoftLinkedinBloomberg
Problem Description
You are given `k` sorted integer arrays (called "runs"). Merge them into a single sorted array and return it.
**Example 1:**
```
Input: runs = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
```
**Example 2:**
```
Input: runs = [[10, 20], [5, 15, 25], [1]]
Output: [1, 5, 10, 15, 20, 25]
```
Constraints
- 1 <= k <= 10^4
- 0 <= runs[i].length <= 500
- Total number of elements across all runs <= 10^4
- runs[i] is sorted in non-decreasing order
- -10^4 <= runs[i][j] <= 10^4
Follow-up
Can you solve this iteratively using a divide-and-conquer merge strategy? How does its complexity compare?
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.