Sort K-Sorted Array
Medium Problems DSA practice problem on Onlearn.
Difficulty: easy.
Topics: How can you efficiently sort a k-sorted array?, Arrays, Sorting, Merge Sort, Divide and Conquer, Priority Queue, Heap, Time Complexity, Space Complexity, divide and conquer, sorting algorithms, complexity analysis, min-heap, K-Sorted Array, Min-Heap.
Problem Statement You are given K sorted arrays of integers. Your task is to merge them into a single sorted array. The input arrays are already sorted individually. You must combine all elements from these K arrays and output them in non decreasing order. This problem requires an efficient approach to handle a potentially large total number of elements. Input Specification The first line contains an integer K, denoting the number of sorted arrays. The next K lines describe the arrays. Each line is formatted as follows: The first integer N denotes the size of the array. This is followed by N space separated integers representing the elements of that sorted array. Output Specification A single line containing all integers from the input arrays, sorted in ascending order and separated by spaces. Constraints 1 ≤ K ≤ 100 0 ≤ N (Size of each array) ≤ 500 10^9 ≤ Array elements ≤ 10^9 The total number of elements across all K arrays will not exceed 10^5. The input arrays are guaranteed to be sorted in ascending order. Sample Test Cases Sample Input 1 Explanation: We have 3 arrays: [1, 3, 5], [2, 4, 6], and [0, 9]. Merging them results in [0, 1, 2, 3, 4, 5, 6, 9]. Sample Output 1 Sample Input 2 Explanation: We have 2 arrays: [10, 20] and [5, 15]. Merging them results in [5, 10, 15, 20]. Sample Output 2 Difficulty Level Easy