K-way merge is a coding interview pattern used to merge multiple sorted arrays or lists into a single sorted list efficiently. It is often used when dealing with large amounts of sorted data that cannot fit into memory at once.

Here's an example implementation of the K-way merge pattern:

import heapq

def k_way_merge(arrays):
    result = []
    min_heap = []

    # Initialize the min heap with the first element from each array
    for i, array in enumerate(arrays):
        if len(array) > 0:
            heapq.heappush(min_heap, (array[0], i, 0))

    while min_heap:
        val, array_index, element_index = heapq.heappop(min_heap)
        result.append(val)

        # Move to the next element in the same array
        if element_index + 1 < len(arrays[array_index]):
            heapq.heappush(min_heap, (arrays[array_index][element_index + 1], array_index, element_index + 1))

    return result

Now, let's look at a couple of example questions and their solutions using the K-way merge pattern:

Example 1: Merge K Sorted Lists
Given K sorted linked lists, merge them into a single sorted linked list.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists):
    arrays = []
    
    # Convert linked lists into arrays
    for linked_list in lists:
        array = []
        current = linked_list
        while current:
            array.append(current.val)
            current = current.next
        arrays.append(array)
    
    # Use K-way merge to merge the arrays
    merged_array = k_way_merge(arrays)
    
    # Convert the merged array back into a linked list
    dummy = ListNode()
    current = dummy
    for val in merged_array:
        current.next = ListNode(val)
        current = current.next
    
    return dummy.next

Example 2: Merge K Sorted Arrays
Given K sorted arrays, merge them into a single sorted array.

def merge_k_arrays(arrays):
    return k_way_merge(arrays)