Merge K sorted arrays
You have been given ‘K’ different arrays/lists, which are sorted individually (in ascending order). You need to merge all the given arrays/list such that the output array/list should be sorted in ascending order.

Input Format :

The first line of input contains an integer T, the number of test cases. The first line of each test case contains an integer that denotes the value of K. The next 2*K lines of each test case follow: The first line contains an integer ‘N’ denoting the size of the array. The second line contains N space-separated integers.

Output Format :

The first and only line of output contains space-separated elements of the merged and sorted array, as described in the task.

Note :

You don’t have to print anything; it has already been taken care of. Just implement the function.

Constraints :

1

Question

Merge K sorted arrays

You have been given ‘K’ different arrays/lists, which are sorted individually (in ascending order). You need to merge all the given arrays/list such that the output array/list should be sorted in ascending order.

Input Format :

The first line of input contains an integer T, the number of test cases.

The first line of each test case contains an integer that denotes the value of K.

The next 2*K lines of each test case follow: 
The first line contains an integer ‘N’ denoting the size of the array. 

The second line contains N space-separated integers.

Output Format :

The first and only line of output contains space-separated elements of the merged and sorted array, as described in the task.

Note :

You don’t have to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 5
1 <= K <= 5
1 <= N <= 20
-10^5 <= DATA <= 10^5

Time Limit: 1 sec

Accepted Answer

Approach 1 (Brute Force) :

Create an output array and and one by one copy all arrays to it. Finally, sort the output array using. This approach takes O(N Logn N) time where N is count of all elements.

Approach 2 (Using Min-Heap) :

1. Create an output array.

2. Create a min heap of size k and insert 1st element in all the arrays into the heap

3. Repeat following steps while priority queue is not empty.
3.1) Remove minimum element from heap (minimum is always at root) and store it in output array.
3.2) Insert next element from the array from which the element is extracted. If the array doesn’t have any more elements, then do nothing.

TC : O(N*log(K))
SC : O(N)

Accepted Answer

Sorting

Create an output array ‘RESULT’.
Traverse all the given arrays from start to end and insert all the elements in the output array ‘RESULT’.
Sort the ‘RESULT’ and return it.

Space Complexity: O(2^n)Explanation:

O(N * K), Where ‘K’ is the number of arrays and ‘N’ is the average number of elements in every array.

We are using an array/list of size O(N * K) to store all the elements of the ‘K’ arrays/lists. Then, we are sorting the output array in ascending order which takes at-least log(N * K) additional space. Thus, the total space complexity is O(K * N).

Time Complexity: OtherExplanation:

O((N * K) * log(N * K)), Where ‘K’ is the number of arrays and ‘N’ is the average number of elements in every array.

We are traversing all the ‘K’ arrays and then we are sorting the output array. Thus, the total time complexity will be O((N * K) * log(N * K)).

Java (SE 1.8)

/*

    Time Complexity: O((N * K) * log(N * K))

    Space Complexity: O(N * K)



    Where K is the number of arrays and N is the average number of elements in every array.

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution 

{

    public static ArrayList mergeKSortedArrays(ArrayList> kArrays, int k) 

    {

        // Output array.

        ArrayList result = new ArrayList();



        // Traverse all the k ArrayLists.

        for (int i = 0; i < k; i++) 

        {



            for (int j = 0; j < kArrays.get(i).size(); j++) 

            {

                // Add the element to the output array.

                result.add(kArrays.get(i).get(j));

            }

            

        }



        // Sort the output array.

        Collections.sort(result);



        return result;

    }

}

Python (3.5)

'''
    Time Complexity: O((N * K) * log(N * K))
    Space Complexity: O(N * K)

    Where K is the number of arrays and N is the average number of elements in every array.
'''
    
def mergeKSortedArrays(kArrays, k):
    
    result = []
    
    for lst in kArrays:
        result.extend(lst)
    
    return sorted(result)

C++ (g++ 5.4)

/*

    Time Complexity: O((N * K) * log(N * K))

    Space Complexity: O(N * K)

    

    Where K is the number of arrays and N is the average number of elements in every array.

*/



#include



vector mergeKSortedArrays(vector>&kArrays, int k)

{

    // Output array.

    vector result;

    

    // Traverse all the k vectors.

    for(int i = 0;i < k; i++)

    {

        for(int j = 0; j < kArrays[i].size(); j++)

        {

            // Add the element to the output array.

            result.push_back(kArrays[i][j]);

        }

    }

    

    // Sort the output array.

    sort(result.begin(), result.end());

    

    return result;

}

Accepted Answer

Divide and Conquer

The idea is based on the divide and conquer strategy. We take pairs of arrays at each step. Then merge the pairs using the two-pointer technique of merging two sorted arrays. Thus, after merging all the pairs, the number of arrays will reduce by half.

We will continue this till the number of remaining arrays doesn’t become 1.

Algorithm:

Create a recursive function which takes ‘K’ arrays and returns the output array.
In the recursive function, if the value of ‘K’ is 1 then return the array else if the value of ‘K’ is 2 then merge the two arrays in linear time using two-pointers and return the merged array.
If the value of ‘K’ is greater than 2, then divide the group of ‘K’ arrays into two equal halves and recursively call the function, i.e 0 to K/2 array in one recursive function and K/2 to ‘K’ array in another recursive function.
Return the output array.

Space Complexity: O(n^2logn)Explanation:

O((N * K )* log(K)), Where ‘K’ is the number of arrays and ‘N’ is the average number of elements in every array.

There are log (K) levels because in each level the ‘K’ arrays are divided into half. And O(N * K) space is required to store the answer. Thus, the total time complexity is O((N * K) * log(K)).

Time Complexity: O(n^2logn)Explanation:

O((N * K) * log(K)), Where ‘K’ is the number of arrays and ‘N’ is the average number of elements in every array.

There are log(K) levels because in each level the ‘K’ arrays are divided into half. Also, at each level, the ‘K’ arrays are traversed to merge. Thus, the total time complexity is O((N * K) * log(K)).

C++ (g++ 5.4)

/*

    Time Complexity: O((N * K) * log(K))

    Space Complexity: O((N * K )* log(K))

    

    Where K is the number of arrays and N is the average number of elements in every array. 

*/



vector merge(vector&a, vector&b)

{

    vectorans; 

    

    int n = a.size(), m = b.size();

    int i = 0, j = 0;

    

    // Traverse the both arrays.

    while(i < n and j < m)

    {

        if(a[i] < b[j])

        {

            ans.push_back(a[i]);

            i += 1;

        }

        else

        {

            ans.push_back(b[j]);

            j += 1;

        }

    }

    

    // Add remaining elements of the first array.

    while(i < n)

    {

        ans.push_back(a[i]);

        i += 1;

    }

    

    // Add remaining elements of the second array.

    while(j < m)

    {

        ans.push_back(b[j]);

        j += 1;

    }

    

    return ans; 

}



vector  mergeKSortedArraysHelper(vector>&kArrays, int start, int end)

{

    // If there is only one array.

    if(start == end)

    {

        return kArrays[start];

    }

    

    // If there are only two arrays, merge them.

    if(start + 1 == end)

    {

        return merge(kArrays[start], kArrays[end]);

    }

    

    int mid = start + (end - start)/2;

    

    // Divide the arrays into two halves.

    vector first = mergeKSortedArraysHelper(kArrays, start, mid);

    vector second = mergeKSortedArraysHelper(kArrays, mid + 1, end);

    

    // Return the final merged array.

    return merge(first, second);

    

}



vector mergeKSortedArrays(vector>&kArrays, int k)

{

    vector result = mergeKSortedArraysHelper(kArrays, 0, k - 1);

    return result;

}

Java (SE 1.8)

/*

    Time Complexity: O((N * K) * log(K))

    Space Complexity: O((N * K )* log(K))



    Where K is the number of arrays and N is the average number of elements in every array.

*/



import java.util.ArrayList;



public class Solution 

{

	private static ArrayList merge(ArrayList a, ArrayList b) 

	{

		ArrayListans = new ArrayList();



		int n = a.size(), m = b.size();

		int i = 0, j = 0;



		// Traverse the both arrays.

		while (i < n && j < m) 

		{

			if (a.get(i) < b.get(j)) 

			{

				ans.add(a.get(i));

				i ++;

			} 

			else 

			{

				ans.add(b.get(j));

				j ++;

			}

		}



		// Add remaining elements of the first array.

		while (i < n) 

		{

			ans.add(a.get(i));

			i ++;

		}



		// Add remaining elements of the second array.

		while (j < m) 

		{

			ans.add(b.get(j));

			j ++;

		}



		return ans;

	}



	private static ArrayList  mergeKSortedArraysHelper(ArrayList> kArrays, int start, int end) 

	{

		// If there is only one array.

		if (start == end) 

		{

			return kArrays.get(start);

		}



		// If there are only two arrays, merge them.

		if (start + 1 == end) 

		{

			return merge(kArrays.get(start), kArrays.get(end));

		}



		int mid = start + (end - start) / 2;



		// Divide the arrays into two halves.

		ArrayList first = mergeKSortedArraysHelper(kArrays, start, mid);

		ArrayList second = mergeKSortedArraysHelper(kArrays, mid + 1, end);



		// Return the final merged array.

		return merge(first, second);



	}



	public static ArrayList mergeKSortedArrays(ArrayList>kArrays, int k) 

	{

		ArrayList result = mergeKSortedArraysHelper(kArrays, 0, k - 1);

		return result;

	}

}

Python (3.5)

'''
    Time Complexity: O((N * K) * log(K))
    Space Complexity: O((N * K )* log(K))

    Where K is the number of arrays and N is the average number of elements in every array.
'''

def merge(a, b):
    
    ans = []
    
    n = len(a)
    m = len(b)
    i = 0
    j = 0
    
    # Traverse the both arrays.
    while i < n and j < m:
        
        if a[i] < b[j]:
            
            ans.append(a[i])
            i += 1
            
        else:
            
            ans.append(b[j])
            j += 1
            
    
    # Add remaining elements of the first array.        
    while i < n:
        
        ans.append(a[i])
        i += 1
        
    # Add remaining elements of the second array.
    while j < m:
        
        ans.append(b[j])
        j += 1
        
    return ans
    

def mergeKSortedArraysHelper(kArrays, start, end):
    
    # If there is only one array.
    if start == end:
        
        return kArrays[start]
        
    # If there are only two arrays, merge them.
    if start + 1 == end:
        
        return merge(kArrays[start], kArrays[end])
        
    mid = start + (end - start) // 2
    
    # Divide the arrays into two halves.
    first = mergeKSortedArraysHelper(kArrays, start, mid)
    second = mergeKSortedArraysHelper(kArrays, mid + 1, end)
    
    # Return the final merged array.
    return merge(first, second)
    

def mergeKSortedArrays(kArrays, k):
    
    result = mergeKSortedArraysHelper(kArrays, 0, k - 1)
    
    return result

Accepted Answer

Heaps

The idea is to use the concept of min-heap. As we know, the root of the min-heap is always the minimum element in the heap. Thus, insert the first elements of all the ‘K’ arrays into the heap along with their indices, and then removing the minimum ( root ) element and adding it to the output array will give us the required result. We will store indices into the heap because we can get the next greater element from the same array where the current element has been popped.

Algorithm:

Create an output array ‘RESULT’.
Create a min-heap of size K and insert the first element of all the arrays, along with its indices, into the heap.
The heap is ordered by the element of the array/list.
While the min-heap is not empty, we will keep doing the following operations :
- Remove the minimum element from the min-heap (the minimum element is always at the root) and store it in the output array.
- Insert the next element from the array for which the current element is extracted. If the array doesn’t have any more elements i.e. if the index of the above-removed component is equal to ‘LENGTH-1’ of the array from which the element is extracted, then do nothing. Because we are done with this array.
After the above process, 'RESULT' will contain all the elements of ‘K’ arrays in ascending order.
Return the output array i.e. ‘RESULT’.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N * K), where ‘K’ is the number of arrays and ‘N’ is the average number of elements in every array.

Since we are using a min-heap of size K arrays for the average N elements present in every array, therefore, the space complexity of the approach is O(N * K).

Time Complexity: O(n^2logn)Explanation:

O((N * K) * log(K)), Where ‘K’ is the number of arrays and ‘N’ is the average number of elements in every array.

We are using the min-heap of size K. Due to the insertion and the removal of elements in the heap, the final complexity of this approach is O(K * N * log(K)).

Python (3.5)

'''
    Time Complexity: O((N * K) * log(K)) 
    Space Complexity: O(N * K)

    Where N is the total number of elements in all the arrays, and K is the number of arrays.
'''

import heapq

def mergeKSortedArrays(kArrays, k):
    
    result = []
    
    # Create a min heap to store atmost k heap nodes at a time.
    minHeap = []
    
    for i in range(len(kArrays)):
        
        heapq.heappush( minHeap, (kArrays[i][0], i, 0) )
        
    while len(minHeap) > 0:
        
        # Remove the minimum element from the heap.
        curr = heapq.heappop(minHeap)
        
        # i is the array number and j is the index of the removed element in the ith array.
        i = curr[1]
        j = curr[2]
        
        # Add the removed element to the output array.
        result.append(curr[0])
        
        # If the next element of the extracted element exists, add it to the heap.
        if j + 1 < len(kArrays[i]):
            
            heapq.heappush( minHeap, (kArrays[i][j + 1], i, j + 1) )
    
            
    # Return the output array.        
    return result

C++ (g++ 5.4)

/*

    Time Complexity: O((N * K) * log(K)) 

    Space Complexity: O(N * K)

    

    Where N is the total number of elements in all the arrays, and K is the number of arrays.

*/



#include



vector mergeKSortedArrays(vector>&kArrays, int k)

{

    vector result; 

  

    // Create a min heap to store atmost k heap nodes at a time.

    priority_queue >, vector > >, greater > > > minHeap; 

  

    for (int i = 0; i < kArrays.size(); i++)

    {

        minHeap.push({ kArrays[i][0], { i, 0 } }); 

    }

  

    while (minHeap.empty() == false) 

    { 

    

        // Remove the minimum element from the heap.

        pair > curr = minHeap.top(); 

        minHeap.pop(); 

  

        // i is the array number and j is the index of the removed element in the ith array.

        int i = curr.second.first; 

        int j = curr.second.second; 

    

        // Add the removed element to the output array.

        result.push_back(curr.first); 

  

        // If the next element of the extracted element exists, add it to the heap.

        if (j + 1 < kArrays[i].size())

        {

            minHeap.push({ kArrays[i][j + 1], { i, j + 1 } }); 

        }

    } 

  

    // Return the output array.

    return result; 

}

Java (SE 1.8)

/*

    Time Complexity: O((N * K) * log(K)) 

    Space Complexity: O(N * K)

    

    Where N is the total number of elements in all the arrays, and K is the number of arrays.

*/



import java.util.Objects;

import java.util.HashSet;

import java.util.ArrayList;

import java.util.Comparator;

import java.util.Collections;

import java.util.PriorityQueue;



class Pair 

{

	public int first, second, third;



	Pair(int first, int second, int third) 

	{

		this.first = first;

		this.second = second;

		this.third = third;

	}

}





// Implements Comparator interface for min-heap.

class PqComparator implements Comparator 

{

	public int compare(Pair pair1, Pair pair2) 

	{

		if (pair1.first < pair2.first) 

		{

			return -1;

		}

		if (pair1.first == pair2.first) 

		{

			return 0;

		}

		return 1;

	}

}



public class Solution 

{



	public static ArrayList mergeKSortedArrays(ArrayList> kArrays, int k) 

	{

		ArrayList result = new ArrayList();



		// Create a min heap to store atmost k heap nodes at a time.

		PriorityQueue minHeap = new PriorityQueue < Pair>(new PqComparator());



		for (int i = 0; i < kArrays.size(); i++) 

		{

			minHeap.add(new Pair( kArrays.get(i).get(0), i, 0 ));

		}





		while (minHeap.isEmpty() == false) 

		{



			// Remove the minimum element from the heap.

			Pair curr = minHeap.remove();



			// i is the array number and j is the index of the removed element in the ith array.

			int i = curr.second;

			int j = curr.third;



			// Add the removed element to the output array.

			result.add(curr.first);



			// If the next element of the extracted element exists, add it to the heap.

			if (j + 1 < kArrays.get(i).size()) 

			{

				minHeap.add(new Pair( kArrays.get(i).get(j + 1),  i, j + 1 ));

			}

		}



		// Return the output array.

		return result;

	}

}

You have been given ‘K’ different arrays/lists, which are sorted individually (in ascending order). You need to merge all the given arrays/list such that the output array/list should be sorted in ascending order.

Input Format :

Output Format :

Note :

Constraints :

Top Publicis Sapient Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Publicis Sapient Software Developer