Skip to main content
Mapagam

Using K-way Merge Pattern

1. Understanding Multi-List Merging

The K-way merge pattern is a powerful technique for efficiently merging multiple sorted lists or arrays into a single sorted output. It's particularly useful when dealing with large datasets that are already partitioned or distributed across multiple sources.

Aspect Description Use Case
Input Multiple sorted lists/arrays Large datasets split into chunks
Output Single sorted list/array Unified sorted result
Time Complexity O(N log K) Where N is total elements, K is number of lists
Space Complexity O(K) For maintaining heap of size K

Example: Merging K Sorted Lists

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeKLists(lists) {
  const minHeap = new MinHeap();
  
  // Add first node of each list to heap
  for (let i = 0; i < lists.length; i++) {
    if (lists[i]) {
      minHeap.push(lists[i]);
    }
  }

  const dummy = new ListNode(0);
  let current = dummy;

  while (!minHeap.isEmpty()) {
    const node = minHeap.pop();
    current.next = new ListNode(node.val);
    current = current.next;
    
    if (node.next) {
      minHeap.push(node.next);
    }
  }

  return dummy.next;
}

// Example usage:
const list1 = new ListNode(1, new ListNode(4, new ListNode(5)));
const list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
const list3 = new ListNode(2, new ListNode(6));
const lists = [list1, list2, list3];
const merged = mergeKLists(lists);
Note: The heap-based approach ensures we always pick the smallest available element from all lists, maintaining sorted order in the final result.

2. Merging K Sorted Lists

Operation Description Time Complexity Space Complexity
mergeKLists Merges k sorted linked lists into one sorted list O(N * log k) O(k)

Example: Merging K Sorted Lists

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;

  const minHeap = new MinHeap();
  for (let list of lists) {
    if (list) minHeap.push(list);
  }

  const dummy = new ListNode(0);
  let current = dummy;

  while (!minHeap.isEmpty()) {
    const node = minHeap.pop();
    current.next = new ListNode(node.val);
    current = current.next;

    if (node.next) {
      minHeap.push(node.next);
    }
  }

  return dummy.next;
}

// Example usage:
const list1 = new ListNode(1, new ListNode(4, new ListNode(5)));
const list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
const list3 = new ListNode(2, new ListNode(6));
const lists = [list1, list2, list3];
const merged = mergeKLists(lists);
// Result: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
Note: The MinHeap implementation is assumed to be available. It should support push, pop, and isEmpty methods.

3. Finding Kth Smallest in M Sorted Arrays

Property Description Example
k Position of the element to find (1-indexed) k = 5
arrays List of m sorted arrays [[1, 4, 5], [1, 3, 4], [2, 6]]

Example: Finding 4th smallest element

const arrays = [[1, 4, 5], [1, 3, 4], [2, 6]];
const k = 4;

function findKthSmallest(arrays, k) {
  const minHeap = new MinHeap();
  for (let i = 0; i < arrays.length; i++) {
    if (arrays[i].length > 0) {
      minHeap.push({
        value: arrays[i][0],
        arrayIndex: i,
        elementIndex: 0
      });
    }
  }

  let count = 0;
  while (minHeap.size() > 0) {
    const current = minHeap.pop();
    count++;
    if (count === k) return current.value;

    const nextElementIndex = current.elementIndex + 1;
    if (nextElementIndex < arrays[current.arrayIndex].length) {
      minHeap.push({
        value: arrays[current.arrayIndex][nextElementIndex],
        arrayIndex: current.arrayIndex,
        elementIndex: nextElementIndex
      });
    }
  }

  return -1;
}

console.log(findKthSmallest(arrays, k)); // Output: 3
Note: The algorithm uses a min-heap to efficiently track the smallest elements across all arrays.

Algorithm Summary

  • Initialize a min-heap with the first element of each array.
  • Repeatedly extract the minimum element and add the next element from the same array to the heap.
  • Continue until k elements have been extracted.

4. Finding Smallest Range Covering K Lists

Property Description Notes
Input K sorted lists of integers Each list can have different lengths
Output Smallest range [start, end] that covers at least one element from each list Range is inclusive on both ends
Approach Use a min-heap to track the smallest element from each list Iteratively advance the smallest element's list to find minimal range

Example: Finding Smallest Range

const smallestRange = (lists) => {
  const minHeap = new MinHeap();
  let max = -Infinity;
  let rangeStart = 0;
  let rangeEnd = Infinity;

  // Initialize heap with first element of each list
  for (let i = 0; i < lists.length; i++) {
    minHeap.push({ value: lists[i][0], listIndex: i, elementIndex: 0 });
    max = Math.max(max, lists[i][0]);
  }

  while (minHeap.size() === lists.length) {
    const { value, listIndex, elementIndex } = minHeap.pop();
    const currentRange = max - value;

    if (currentRange < rangeEnd - rangeStart || 
        (currentRange === rangeEnd - rangeStart && value < rangeStart)) {
      rangeStart = value;
      rangeEnd = max;
    }

    const nextElementIndex = elementIndex + 1;
    if (nextElementIndex < lists[listIndex].length) {
      const nextValue = lists[listIndex][nextElementIndex];
      minHeap.push({ value: nextValue, listIndex, elementIndex: nextElementIndex });
      max = Math.max(max, nextValue);
    }
  }

  return [rangeStart, rangeEnd];
};

// Example usage:
const lists = [
  [4, 10, 15, 24, 26],
  [0, 9, 12, 20],
  [5, 18, 22, 30]
];
console.log(smallestRange(lists)); // [20, 24]
Note: The algorithm uses a min-heap to efficiently track the smallest element among all lists. It iteratively advances the list containing the current minimum value to find the smallest valid range.

5. Merging K Sorted Arrays

Property Description Example
Input Array of k sorted arrays [[1, 4, 5], [1, 3, 4], [2, 6]]
Output Merged sorted array [1, 1, 2, 3, 4, 4, 5, 6]

Example: Merging K Sorted Arrays

function mergeKSortedArrays(arrays) {
  const minHeap = new MinHeap();
  const result = [];

  // Initialize heap with first element of each array
  for (let i = 0; i < arrays.length; i++) {
    if (arrays[i].length > 0) {
      minHeap.push({
        value: arrays[i][0],
        arrayIndex: i,
        elementIndex: 0
      });
    }
  }

  while (!minHeap.isEmpty()) {
    const { value, arrayIndex, elementIndex } = minHeap.pop();
    result.push(value);

    // Add next element from same array
    if (elementIndex + 1 < arrays[arrayIndex].length) {
      minHeap.push({
        value: arrays[arrayIndex][elementIndex + 1],
        arrayIndex,
        elementIndex: elementIndex + 1
      });
    }
  }

  return result;
}

// Example usage:
const arrays = [[1, 4, 5], [1, 3, 4], [2, 6]];
console.log(mergeKSortedArrays(arrays)); // [1, 1, 2, 3, 4, 4, 5, 6]
Note: The MinHeap implementation is assumed to be available.

6. Finding K Pairs with Smallest Sums

Given two sorted integer arrays nums1 and nums2, find the k smallest pairs (u, v) such that:

  • u is from nums1
  • v is from nums2
  • The sum u + v is minimized

This problem can be solved efficiently using a min-heap to keep track of the smallest sums.

Property Description Example
Input Two sorted arrays nums1, nums2 and integer k nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3
Output List of k pairs with smallest sums [[1,2], [1,4], [1,6]]

Example: Finding K Pairs with Smallest Sums

function kSmallestPairs(nums1, nums2, k) {
    const minHeap = new MinHeap((a, b) => a.sum - b.sum);
    const result = [];

    // Initialize heap with first element from nums1 paired with all elements in nums2
    for (let i = 0; i < Math.min(nums1.length, k); i++) {
        minHeap.push({ sum: nums1[i] + nums2[0], i1: i, i2: 0 });
    }

    while (result.length < k && !minHeap.isEmpty()) {
        const { i1, i2, sum } = minHeap.pop();
        result.push([nums1[i1], nums2[i2]]);

        if (i2 + 1 < nums2.length) {
            minHeap.push({ sum: nums1[i1] + nums2[i2 + 1], i1, i2: i2 + 1 });
        }
    }

    return result;
}

class MinHeap {
    constructor(comparator = (a, b) => a - b) {
        this.heap = [];
        this.comparator = comparator;
    }

    push(value) {
        this.heap.push(value);
        this.bubbleUp(this.heap.length - 1);
    }

    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown(0);
        return top;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    bubbleUp(index) {
        if (index === 0) return;
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.comparator(this.heap[index], this.heap[parentIndex]) < 0) {
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            this.bubbleUp(parentIndex);
        }
    }

    bubbleDown(index) {
        const leftChild = 2 * index + 1;
        const rightChild = 2 * index + 2;
        let minIndex = index;

        if (leftChild < this.heap.length && this.comparator(this.heap[leftChild], this.heap[minIndex]) < 0) {
            minIndex = leftChild;
        }

        if (rightChild < this.heap.length && this.comparator(this.heap[rightChild], this.heap[minIndex]) < 0) {
            minIndex = rightChild;
        }

        if (minIndex !== index) {
            [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
            this.bubbleDown(minIndex);
        }
    }
}

// Example usage:
const nums1 = [1, 7, 11];
const nums2 = [2, 4, 6];
const k = 3;
console.log(kSmallestPairs(nums1, nums2, k)); // [[1,2], [1,4], [1,6]]
Note: The algorithm uses a min-heap to efficiently retrieve the next smallest sum pair. It starts by initializing the heap with the first element from nums1 paired with all elements in nums2. Then, it iteratively pops the smallest sum pair and adds the next possible pair from nums2 for the same element in nums1.
Time Complexity Space Complexity Approach
O(k * log(min(n, k))) O(min(n, k)) Min-heap with initial state

7. Finding Median in Stream of Lists

When dealing with a stream of lists, finding the median involves maintaining a data structure that allows efficient insertion and retrieval of elements in sorted order. The K-way Merge Pattern is particularly useful here, as it enables merging multiple sorted lists efficiently.

Approach Description Time Complexity Space Complexity
Using Min-Heap and Max-Heap Use a max-heap for the lower half and a min-heap for the upper half of elements. The median is either the root of one heap or the average of both roots. O(log n) per insertion O(n)
K-way Merge with Median Tracking Merge lists using a priority queue (min-heap) to maintain sorted order. Keep track of the median by traversing the merged list. O(n log k) where k is the number of lists O(k)

Example: Using Heaps to Find Median

const MaxHeap = require('./MaxHeap');
const MinHeap = require('./MinHeap');

class MedianFinder {
  constructor() {
    this.maxHeap = new MaxHeap(); // stores smaller half
    this.minHeap = new MinHeap(); // stores larger half
  }

  insert(num) {
    if (this.maxHeap.isEmpty() || num <= this.maxHeap.peek()) {
      this.maxHeap.insert(num);
    } else {
      this.minHeap.insert(num);
    }

    // Rebalance heaps
    if (this.maxHeap.size() > this.minHeap.size() + 1) {
      this.minHeap.insert(this.maxHeap.extractMax());
    } else if (this.minHeap.size() > this.maxHeap.size() + 1) {
      this.maxHeap.insert(this.minHeap.extractMin());
    }
  }

  findMedian() {
    if (this.maxHeap.size() === this.minHeap.size()) {
      return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
    } else if (this.maxHeap.size() > this.minHeap.size()) {
      return this.maxHeap.peek();
    } else {
      return this.minHeap.peek();
    }
  }
}

// Example usage:
const mf = new MedianFinder();
mf.insert(5);
mf.insert(15);
mf.insert(10);
console.log(mf.findMedian()); // 10

Example: Merging Lists to Find Median

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeKLists(lists) {
  const heap = new MinHeap();
  lists.forEach((list, i) => {
    if (list) heap.insert({ node: list, index: i });
  });

  const dummy = new ListNode(0);
  let current = dummy;

  while (!heap.isEmpty()) {
    const { node, index } = heap.extractMin();
    current.next = new ListNode(node.val);
    current = current.next;
    if (node.next) {
      heap.insert({ node: node.next, index });
    }
  }

  return dummy.next;
}

function findMedianInStream(lists) {
  const merged = mergeKLists(lists);
  let count = 0;
  let current = merged;

  while (current) {
    count++;
    current = current.next;
  }

  const mid = Math.floor(count / 2);
  current = merged;

  for (let i = 0; i < mid; i++) {
    current = current.next;
  }

  if (count % 2 === 1) {
    return current.val;
  } else {
    const next = current.next;
    return (current.val + next.val) / 2;
  }
}

8. Merging Intervals from K Lists

Property Description Example
Input List of k sorted lists containing intervals [[1,4], [2,5], [7,9]]
Output Merged list of non-overlapping intervals [[1,5], [7,9]]

Example: Merging Intervals from K Lists

function mergeIntervalsFromKLists(lists) {
  const minHeap = new MinHeap();
  const result = [];

  // Add first interval of each list to heap
  for (let i = 0; i < lists.length; i++) {
    if (lists[i].length > 0) {
      minHeap.push({
        interval: lists[i][0],
        listIndex: i,
        elementIndex: 0
      });
    }
  }

  while (!minHeap.isEmpty()) {
    const { interval, listIndex, elementIndex } = minHeap.pop();

    if (result.length === 0 || result[result.length - 1][1] < interval[0]) {
      result.push(interval);
    } else {
      result[result.length - 1][1] = Math.max(result[result.length - 1][1], interval[1]);
    }

    // Add next interval from same list if exists
    if (elementIndex + 1 < lists[listIndex].length) {
      const nextInterval = lists[listIndex][elementIndex + 1];
      minHeap.push({
        interval: nextInterval,
        listIndex,
        elementIndex: elementIndex + 1
      });
    }
  }

  return result;
}
Note: This approach uses a min-heap to efficiently merge intervals from k sorted lists. The heap stores the next interval from each list, ensuring we always process the earliest starting interval.

9. Finding Kth Smallest in Sorted Matrix

Property Description Example
matrix A 2D array where each row and column is sorted in ascending order [[1, 5, 9], [10, 11, 13], [12, 13, 15]]
k The position of the element to find (1-indexed) 8

Example: Finding Kth Smallest Element

function kthSmallest(matrix, k) {
  const minHeap = new MinHeap();
  const n = matrix.length;

  // Initialize heap with first element of each row
  for (let i = 0; i < n; i++) {
    minHeap.push({ value: matrix[i][0], row: i, col: 0 });
  }

  // Extract min k times
  for (let i = 0; i < k; i++) {
    const { value, row, col } = minHeap.pop();
    if (col + 1 < n) {
      minHeap.push({ value: matrix[row][col + 1], row, col: col + 1 });
    }
  }

  return value;
}

// Example usage:
const matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]];
const k = 8;
console.log(kthSmallest(matrix, k)); // Output: 13
Note: This approach uses a min-heap to efficiently find the kth smallest element in O(n + k log n) time.

10. Finding Next Smallest Element in K Lists

Property Description Example
Input K sorted lists of integers [1, 4, 5], [1, 3, 4], [2, 6]
Output Next smallest element in sorted order 1
Approach Use min-heap to track smallest elements from each list

Example: Finding Next Smallest Element

const mergeKLists = (lists) => {
  const minHeap = new MinHeap();
  for (let i = 0; i < lists.length; i++) {
    if (lists[i].length > 0) {
      minHeap.push({ value: lists[i][0], listIndex: i, elementIndex: 0 });
    }
  }

  const result = [];
  while (!minHeap.isEmpty()) {
    const { value, listIndex, elementIndex } = minHeap.pop();
    result.push(value);

    if (elementIndex + 1 < lists[listIndex].length) {
      minHeap.push({
        value: lists[listIndex][elementIndex + 1],
        listIndex,
        elementIndex: elementIndex + 1
      });
    }
  }

  return result;
};

// Example usage:
const lists = [[1, 4, 5], [1, 3, 4], [2, 6]];
console.log(mergeKLists(lists)); // [1, 1, 2, 3, 4, 4, 5, 6]
Note: The min-heap stores the smallest element from each list, allowing efficient retrieval of the next smallest element in O(log K) time.

Was this article helpful?

Related Cheat Sheets