Merge K Sorted Lists

Problem Statement

Write a Java program that merges k sorted arrays into a single sorted array using a priority queue. The program should enqueue the first element of each array along with its array index and value, and repeatedly dequeue the smallest element and enqueue the next element from the same array, continuing until all elements are processed. Test the implementation with various cases, including multiple arrays, single arrays, empty arrays, and arrays with duplicate elements. You can visualize this as combining k sorted lists of exam scores into one sorted list, using a priority queue to always pick the smallest score available from the lists.

Input:

• A list of k sorted arrays, where each array contains integers (e.g., [[1,4,5], [1,3,4], [2,6]]).
• k is the number of arrays (0 ≤ k ≤ 10^3). Output: A single sorted array containing all elements from the input arrays (e.g., [1,1,2,3,4,4,5,6]). Constraints:
• Each array is sorted in non-decreasing order.
• Array lengths are between 0 and 10^4.
• Elements are integers in the range [-10^9, 10^9].
• Total number of elements across all arrays is at most 10^4. Example:
• Input: arrays=[[1,4,5], [1,3,4], [2,6]]
• Output: [1,1,2,3,4,4,5,6]
• Explanation: Merges three sorted arrays into one sorted array.
• Input: arrays=[[]]
• Output: []
• Explanation: Single empty array results in an empty output.

Pseudocode

CLASS Element
    SET value to integer
    SET arrayIndex to integer
    SET elementIndex to integer
ENDCLASS

CLASS MinPriorityQueue
    SET array to new Element array of size 1000
    SET size to 0
    
    FUNCTION enqueue(value, arrayIndex, elementIndex)
        IF size equals array length THEN
            RETURN false
        ENDIF
        SET array[size] to new Element(value, arrayIndex, elementIndex)
        CALL siftUp(size)
        INCREMENT size
        RETURN true
    ENDFUNCTION
    
    FUNCTION siftUp(index)
        WHILE index > 0
            SET parent to (index - 1) / 2
            IF array[index].value >= array[parent].value THEN
                BREAK
            ENDIF
            SWAP array[index] and array[parent]
            SET index to parent
        ENDWHILE
    ENDFUNCTION
    
    FUNCTION dequeue()
        IF size equals 0 THEN
            RETURN null
        ENDIF
        SET result to array[0]
        SET array[0] to array[size - 1]
        DECREMENT size
        IF size > 0 THEN
            CALL siftDown(0)
        ENDIF
        RETURN result
    ENDFUNCTION
    
    FUNCTION siftDown(index)
        SET minIndex to index
        WHILE true
            SET left to 2 * index + 1
            SET right to 2 * index + 2
            IF left < size AND array[left].value < array[minIndex].value THEN
                SET minIndex to left
            ENDIF
            IF right < size AND array[right].value < array[minIndex].value THEN
                SET minIndex to right
            ENDIF
            IF minIndex equals index THEN
                BREAK
            ENDIF
            SWAP array[index] and array[minIndex]
            SET index to minIndex
        ENDWHILE
    ENDFUNCTION
ENDCLASS

FUNCTION mergeKSortedLists(arrays)
    IF arrays is empty THEN
        RETURN empty array
    ENDIF
    CREATE queue as new MinPriorityQueue
    CREATE result as new list
    FOR i from 0 to arrays length - 1
        IF arrays[i] is not empty THEN
            ENQUEUE (arrays[i][0], i, 0) to queue
        ENDIF
    ENDFOR
    WHILE queue is not empty
        SET element to queue.dequeue()
        ADD element.value to result
        SET arrayIndex to element.arrayIndex
        SET elementIndex to element.elementIndex + 1
        IF elementIndex < arrays[arrayIndex] length THEN
            ENQUEUE (arrays[arrayIndex][elementIndex], arrayIndex, elementIndex) to queue
        ENDIF
    ENDWHILE
    RETURN result as array
ENDFUNCTION

FUNCTION main()
    SET testCases to array of lists of sorted arrays
    FOR each testCase in testCases
        PRINT test case details
        CALL mergeKSortedLists(testCase)
        PRINT merged sorted array
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define an Element class to store a value, its array index, and its position in that array.
2. Define a MinPriorityQueue class using a min-heap with: a. An array to store Element objects, prioritized by value. b. enqueue: Add element, sift up to maintain min-heap. c. siftUp: Move smaller value up. d. dequeue: Remove smallest value, sift down. e. siftDown: Move larger value down.
3. In mergeKSortedLists: a. If input is empty, return empty array. b. Create a min-heap and result list. c. Enqueue first element of each non-empty array with its array index and position. d. While queue is not empty:
   • Dequeue smallest element, add to result.
   • If more elements exist in its array, enqueue the next element. e. Return result as array.
4. In main, test with multiple arrays, single arrays, empty arrays, and duplicates.

Java Implementation

import java.util.*;

public class MergeKSortedLists {
    // Class to store element value, array index, and element index
    static class Element {
        int value;
        int arrayIndex;
        int elementIndex;

        Element(int value, int arrayIndex, int elementIndex) {
            this.value = value;
            this.arrayIndex = arrayIndex;
            this.elementIndex = elementIndex;
        }
    }

    // Custom min-heap priority queue for elements
    static class MinPriorityQueue {
        private Element[] array;
        private int size;
        private static final int DEFAULT_SIZE = 1000;

        public MinPriorityQueue() {
            array = new Element[DEFAULT_SIZE];
            size = 0;
        }

        public boolean enqueue(int value, int arrayIndex, int elementIndex) {
            if (size == array.length) {
                return false; // Queue full
            }
            array[size] = new Element(value, arrayIndex, elementIndex);
            siftUp(size);
            size++;
            return true;
        }

        private void siftUp(int index) {
            while (index > 0) {
                int parent = (index - 1) / 2;
                if (array[index].value >= array[parent].value) {
                    break;
                }
                // Swap
                Element temp = array[index];
                array[index] = array[parent];
                array[parent] = temp;
                index = parent;
            }
        }

        public Element dequeue() {
            if (size == 0) {
                return null; // Queue empty
            }
            Element result = array[0];
            array[0] = array[size - 1];
            size--;
            if (size > 0) {
                siftDown(0);
            }
            return result;
        }

        private void siftDown(int index) {
            int minIndex = index;
            while (true) {
                int left = 2 * index + 1;
                int right = 2 * index + 2;
                if (left < size && array[left].value < array[minIndex].value) {
                    minIndex = left;
                }
                if (right < size && array[right].value < array[minIndex].value) {
                    minIndex = right;
                }
                if (minIndex == index) {
                    break;
                }
                // Swap
                Element temp = array[index];
                array[index] = array[minIndex];
                array[minIndex] = temp;
                index = minIndex;
            }
        }
    }

    // Merges k sorted arrays into one sorted array
    public int[] mergeKSortedLists(int[][] arrays) {
        if (arrays == null || arrays.length == 0) {
            return new int[0];
        }

        MinPriorityQueue queue = new MinPriorityQueue();
        List<Integer> result = new ArrayList<>();

        // Enqueue first element of each non-empty array
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i] != null && arrays[i].length > 0) {
                queue.enqueue(arrays[i][0], i, 0);
            }
        }

        // Process queue
        while (true) {
            Element element = queue.dequeue();
            if (element == null) break;
            result.add(element.value);
            int arrayIndex = element.arrayIndex;
            int elementIndex = element.elementIndex + 1;
            if (elementIndex < arrays[arrayIndex].length) {
                queue.enqueue(arrays[arrayIndex][elementIndex], arrayIndex, elementIndex);
            }
        }

        // Convert result to array
        int[] merged = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            merged[i] = result.get(i);
        }
        return merged;
    }

    // Helper class for test cases
    static class TestCase {
        int[][] arrays;

        TestCase(int[][] arrays) {
            this.arrays = arrays;
        }
    }

    // Main method to test merge k sorted lists
    public static void main(String[] args) {
        MergeKSortedLists merger = new MergeKSortedLists();

        // Test cases
        List<TestCase> testCases = new ArrayList<>();
        
        // Test case 1: Multiple arrays
        testCases.add(new TestCase(
            new int[][]{{1,4,5}, {1,3,4}, {2,6}}
        ));
        
        // Test case 2: Single array
        testCases.add(new TestCase(
            new int[][]{{1,2,3}}
        ));
        
        // Test case 3: Empty arrays
        testCases.add(new TestCase(
            new int[][]{{}}
        ));
        
        // Test case 4: Arrays with duplicates
        testCases.add(new TestCase(
            new int[][]{{1,1,1}, {2,2}, {1,3}}
        ));
        
        // Test case 5: Mixed empty and non-empty
        testCases.add(new TestCase(
            new int[][]{{}, {1,2}, {3}}
        ));

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            TestCase test = testCases.get(i);
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input arrays: " + Arrays.deepToString(test.arrays));
            int[] result = merger.mergeKSortedLists(test.arrays);
            System.out.println("Merged sorted array: " + Arrays.toString(result) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input arrays: [[1, 4, 5], [1, 3, 4], [2, 6]]
Merged sorted array: [1, 1, 2, 3, 4, 4, 5, 6]

Test case 2:
Input arrays: [[1, 2, 3]]
Merged sorted array: [1, 2, 3]

Test case 3:
Input arrays: [[]]
Merged sorted array: []

Test case 4:
Input arrays: [[1, 1, 1], [2, 2], [1, 3]]
Merged sorted array: [1, 1, 1, 1, 2, 2, 3]

Test case 5:
Input arrays: [[], [1, 2], [3]]
Merged sorted array: [1, 2, 3]

Explanation:

• Test case 1: Merges three arrays, producing sorted output [1,1,2,3,4,4,5,6].
• Test case 2: Single array [1,2,3] remains unchanged.
• Test case 3: Single empty array results in empty output.
• Test case 4: Arrays with duplicates merge into [1,1,1,1,2,2,3].
• Test case 5: Empty and non-empty arrays merge into [1,2,3].

How It Works

• Element: Stores a value, its array index, and position in that array.
• MinPriorityQueue:
  • Uses a min-heap to prioritize smallest values.
  • enqueue: Adds element, sifts up.
  • dequeue: Removes smallest element, sifts down.
• mergeKSortedLists:
  • Handles empty input by returning empty array.
  • Enqueues first element of each non-empty array.
  • Dequeues smallest element, adds to result, enqueues next element from same array.
  • Converts result list to array.
• Example Trace (Test case 1):
  • arrays=[[1,4,5], [1,3,4], [2,6]].
  • Enqueue: (1,0,0), (1,1,0), (2,2,0) → heap=[(1,0,0),(1,1,0),(2,2,0)].
  • Dequeue: (1,0,0), add 1, enqueue (4,0,1) → heap=[(1,1,0),(4,0,1),(2,2,0)].
  • Dequeue: (1,1,0), add 1, enqueue (3,1,1) → heap=[(2,2,0),(4,0,1),(3,1,1)].
  • Continue until heap empty: result=[1,1,2,3,4,4,5,6].
• Main Method: Tests multiple arrays, single array, empty arrays, duplicates, and mixed cases.

Complexity Analysis Table

Note:

• k is the number of arrays, N is the total number of elements.
• Time complexity: O(log k) for enqueue/dequeue; O(N log k) for N elements with heap of size k.
• Space complexity: O(k) for heap, O(N) for result array.
• Worst case: O(N log k) time, O(k + N) space for large N.

✅ Tip: Use a min-heap with size k to efficiently merge sorted arrays by always selecting the smallest available element. Track array indices to enqueue the next element.

⚠ Warning: Handle empty arrays and null inputs to avoid errors. Ensure the priority queue size is sufficient for k arrays.