# K-way Merge — Data Structures and Algorithms: Patterns for Interviews

Source: https://www.skillbyai.com/en/dsa/k-way-merge

> Merge k sorted lists efficiently using a min-heap that always holds the next-smallest candidate from each list.

## Beyond two-way merge

Merging two sorted lists is `O(n)` with two pointers. For **k** sorted lists, a **min-heap** holding one candidate per list generalizes this: always pop the smallest, then push that list's next element.

## Merge k sorted lists

Seed the heap with the first element of each list (tagged with its list/index so we know where to fetch the next value from).

```python
import heapq

def merge_k_sorted(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, i, j = heapq.heappop(heap)
        result.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return result
```

Output:

```
merge_k_sorted([[1,4,5],[1,3,4],[2,6]])
# [1, 1, 2, 3, 4, 4, 5, 6]
```

## Complexity & uses

With `n` total elements across `k` lists, this runs in `O(n log k)` — the heap never holds more than `k` elements. Used for merging sorted log files, external sorting, and the 'smallest range covering k lists' family of problems.

## Final quiz 1 of 8

Final quiz

**Quiz:** What is the time complexity of binary search?

- [ ] O(n)
- [ ] O(1)
- [x] O(log n)
- [ ] O(n log n)

*Answer:* O(log n). Each step halves the search range.

## Final quiz 2 of 8

Final quiz

**Quiz:** Which structure gives average O(1) lookup by key?

- [ ] Linked list
- [ ] Stack
- [ ] Sorted array scan
- [x] Hash map

*Answer:* Hash map. A hash function maps keys to buckets.

## Final quiz 3 of 8

Final quiz

**Quiz:** Which structure suits balanced-bracket checks?

- [x] Stack
- [ ] Queue
- [ ] Trie
- [ ] Heap

*Answer:* Stack. Push openings, pop on closings.

## Final quiz 4 of 8

Final quiz

**Quiz:** Which traversal finds shortest paths in an unweighted graph?

- [ ] DFS
- [x] BFS
- [ ] In-order
- [ ] Post-order

*Answer:* BFS. BFS explores level by level.

## Final quiz 5 of 8

Final quiz

**Quiz:** When does Dijkstra's algorithm give correct results?

- [ ] The graph is a tree
- [ ] The graph is undirected
- [x] All edge weights are non-negative
- [ ] The graph is small

*Answer:* All edge weights are non-negative. Negative edges need Bellman-Ford.

## Final quiz 6 of 8

Final quiz

**Quiz:** What is the worst-case time of merge sort?

- [ ] O(n^2)
- [ ] O(n)
- [ ] O(log n)
- [x] O(n log n)

*Answer:* O(n log n). It always splits and merges evenly.

## Final quiz 7 of 8

Final quiz

**Quiz:** Which pattern handles longest-substring problems in one pass?

- [x] Sliding window
- [ ] Union-find
- [ ] Bit manipulation
- [ ] K-way merge

*Answer:* Sliding window. Expand right, shrink left as needed.

## Final quiz 8 of 8

Final quiz

**Quiz:** What makes a problem suitable for dynamic programming?

- [ ] Random inputs
- [x] Overlapping subproblems and optimal substructure
- [ ] Large strings
- [ ] Sorted data

*Answer:* Overlapping subproblems and optimal substructure. Store subproblem answers to avoid recomputation.