Tasks

K-Way Merge

May 2023

Index	Task	Number	Difficulty	Link
1	Merge k Sorted Lists	23	Hard	https://leetcode.com/problems/merge-k-sorted-lists/
2	Find K Pairs with Smallest Sums	373	Medium	https://leetcode.com/problems/find-k-pairs-with-smallest-sums/
3	Smallest Range Covering Elements from K Lists	632	Hard	https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/
4	Find Kth Smallest Pair Distance	719	Hard	https://leetcode.com/problems/find-k-th-smallest-pair-distance/
5	Merge K Sorted Arrays	23	Hard	https://leetcode.com/problems/merge-k-sorted-arrays/
6	Merge K Sorted Lists II	104	Hard	https://leetcode.com/problems/merge-k-sorted-lists-ii/
7	Kth Smallest Element in a Sorted Matrix	378	Medium	https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
8	Sort Lists	148	Medium	https://leetcode.com/problems/sort-list/
9	Merge Sorted Array	88	Easy	https://leetcode.com/problems/merge-sorted-array/
10	Reduce Array Size to The Half	1338	Medium	https://leetcode.com/problems/reduce-array-size-to-the-half/

// 23. Merge k Sorted Lists

// Time: O(n log k) | Space: O(k)
var mergeKLists = function(lists) {
    if (!lists.length) {
        return null;
    }
    const minHeap = new Heap((a, b) => a.val > b.val);
    for (const head of lists) {
        if (head) {
            minHeap.add(head);
        }
    }
    let result = { next: null };
    const head = result;
    while(!minHeap.isEmpty()) {
        const { val, next } = minHeap.pop();
        result.next = new ListNode(val);
        result = result.next;
        if (next) {
            minHeap.add(next);
        }
    }
    return head.next;
};

/*
 * MinHeap. K-Way Merge
 * --------------------------------
 * 1. Create min heap.
 * 2. Push the head node of every list to the minHeap.
 * 3. Pop from the heap and add to the result.
 * 4. Add popped next to the heap.
 * 5. Return result list head.
 * --------------------------------
 * Time: O(n log k) where n -> length of the longest list and k -> number of lists.
 * Space: O(k) where k is the number of lists.
 */

// 373. Find K Pairs with Smallest Sums

// Time: O(m log m) | Space: O(m)
var kSmallestPairs = function(nums1, nums2, k) {
    const result = [];
    const minHeap = new Heap((a, b) => a.sum > b.sum);
    for (let i = 0; i < Math.min(nums1.length, k); i++) {
        minHeap.add({
            indexes: [i, 0],
            sum: nums1[i] + nums2[0]
        });
    }
    let count = 0;
    while (minHeap.size() && count < k) {
        const node = minHeap.pop();
        const [i, j] = node.indexes;
        const nextJ = j + 1;
        count++;
        result.push([nums1[i], nums2[j]]);
        if (nextJ < nums2.length) {
            minHeap.add({
                indexes: [i, nextJ],
                sum: nums1[i] + nums2[nextJ]
            });
        }
    }
    return result;
};

/*
 * MinHeap, K-Way Merge
 * --------------------------
 * 1. Create minHeap.
 * 2. Push all pairs of the first list items (till k-th element).
 * 3. While heap.size && count < k -> pop, push to result and add new pair to the heap.
 * 4. Return result.
 * --------------------------
 * Time: O(m log m) where m is Math.min(nums1.length, k)
 * Space: O(m) where m is Math.min(nums1.length, k)
 */

// 378. Kth Smallest Element in a Sorted Matrix

// Time: O(n log k) | Space: O(k)
var kthSmallest = function(matrix, k) {
    const length = matrix.length;
    const minHeap = new Heap((a, b) => a.val > b.val);
    for (let i = 0; i < length; i++) {
        minHeap.add({
            val: matrix[i][0],
            valIndex: 0,
            rowIndex: i,
        });
    }
    let result = null;
    let count = 0;
    while(!minHeap.isEmpty()) {
        const { val, valIndex, rowIndex } = minHeap.pop();
        result = val;
        count++;
        if (count === k) {
            break;
        }
        const next = valIndex + 1;
        if (next < length) {
            minHeap.add({
                val: matrix[rowIndex][next],
                valIndex: next,
                rowIndex,
            });
        }
    }
    return result;
};

/*
 * Min Heap, K-Way Merge
 * -----------------------------
 * 1. Create minHeap.
 * 2. Push all rows first element to the heap.
 * 3. Create count and result items.
 * 4. Pop. Update result and count.
 * 5. If count === k -> break.
 * 6. Return result.
 * ------------------------------
 * Time: O(n log k) | Space: O(k)
 */

// 88. Merge Sorted Array

// Time: O(m + n) | Space: O(1)
var merge = function(nums1, m, nums2, n) {
    let i = m + n - 1;
    m--;
    n--;
    for (; i >= 0; i--) {
        if (n < 0) {
            break;
        }
        if (m >= 0 && nums1[m] > nums2[n]) {
            nums1[i] = nums1[m];
            m--;
        } else {
            nums1[i] = nums2[n];
            n--;
        }
    }
};