🔀 Merge Two Sorted Arrays
Category: dsa
Difficulty: hard
Merging two sorted arrays is a fundamental algorithm used as a building block in merge sort and many other applications. This O(n + m) solution uses the two-pointer technique to efficiently combine arrays while maintaining sorted order. ✅ Implementation [code example] 🧪 Example [code example] ⏱️ Time Complexity O(n + m) — linear in total elements No sorting or mutation Merging K Sorted Arrays For merging more than two arrays, we can use a min-heap approach for optimal performance. ✅ Problem Given an array of sorted arrays, merge them into one fully sorted array efficiently. 🧠 Atom-of-Thoughts Approach Atom 1: Use a Min-Heap to track the smallest current element from each array We need to efficiently get the smallest item across all arrays — a min-heap (priority queue) is perfect for this. Atom 2: Initialize the heap with the first element of each array Each heap entry will track: val: the number arrIdx: which array it came from elemIdx: its position in that array Atom 3: Repeatedly extract the smallest item, and push its next element into the heap This guarantees sorted order. Do this until the heap is empty. Atom 4: Output the final merged array ✅ Code (Readable) ```js function mergeKSortedArrays(arrays) { const result = []; const minHeap = [];