# K-way Merge — Data Structures और Algorithms: Interviews के लिए Patterns

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

> एक min-heap का उपयोग करते हुए k sorted lists को कुशलता से मिलाएँ, जो हर list से अगला-सबसे-छोटा उम्मीदवार रखता है।

## Two-way merge से आगे

दो sorted lists को मिलाना दो pointers से `O(n)` है। **k** sorted lists के लिए, हर list से एक उम्मीदवार रखने वाला **min-heap** इसे सामान्यीकृत करता है: हमेशा सबसे छोटा pop करें, फिर उस list का अगला element push करें।

## k sorted lists मिलाएँ

Heap को हर list के पहले element से भरें (उसके list/index के साथ चिह्नित ताकि पता चले अगला value कहाँ से लाना है)।

```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 और उपयोग

`k` lists में कुल `n` elements के साथ, यह `O(n log k)` में चलता है — heap में कभी `k` से ज़्यादा elements नहीं होते। Sorted log files मिलाने, external sorting, और 'k lists को कवर करने वाली सबसे छोटी range' जैसी समस्याओं में इस्तेमाल होता है।

## अंतिम क्विज़ 1/8

अंतिम क्विज़

**Quiz:** Binary search की time complexity क्या है?

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

*Answer:* O(log n). हर कदम search range आधी करता है।

## अंतिम क्विज़ 2/8

अंतिम क्विज़

**Quiz:** कौन-सी structure key से औसत O(1) lookup देती है?

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

*Answer:* Hash map. Hash function keys को buckets से map करता है।

## अंतिम क्विज़ 3/8

अंतिम क्विज़

**Quiz:** Balanced-bracket जाँच के लिए कौन-सी structure उपयुक्त है?

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

*Answer:* Stack. Opening push करें, closing पर pop करें।

## अंतिम क्विज़ 4/8

अंतिम क्विज़

**Quiz:** Unweighted graph में shortest paths कौन-सा traversal खोजता है?

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

*Answer:* BFS. BFS level-by-level खोजता है।

## अंतिम क्विज़ 5/8

अंतिम क्विज़

**Quiz:** Dijkstra का algorithm कब सही परिणाम देता है?

- [ ] 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 के लिए Bellman-Ford चाहिए।

## अंतिम क्विज़ 6/8

अंतिम क्विज़

**Quiz:** Merge sort का worst-case time क्या है?

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

*Answer:* O(n log n). यह हमेशा बराबर बाँटता और merge करता है।

## अंतिम क्विज़ 7/8

अंतिम क्विज़

**Quiz:** Longest-substring समस्याओं को एक pass में कौन-सा pattern संभालता है?

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

*Answer:* Sliding window. दाएँ बढ़ाएँ, ज़रूरत पर बाएँ घटाएँ।

## अंतिम क्विज़ 8/8

अंतिम क्विज़

**Quiz:** कौन-सी बात किसी समस्या को dynamic programming के उपयुक्त बनाती है?

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

*Answer:* Overlapping subproblems and optimal substructure. पुनर्गणना से बचने के लिए subproblem उत्तर रखें।