Queue: Given 2 sorted arrays, you need to merge them using priority queue

Problem Statement:

You are given 2 sorted arrays, you need to merge them by using priority Queue

Example:

Input: 

a = [1, 2, 3]
b = [4, 5, 6]

Output:

[1, 2, 3, 4, 5, 6]

Solution Explanation:

We will use min priority queue to solve the problem.

We will push both the array elements into the queue

Then insert the elements into the final array for the solution.

Time Complexity: O((N+M)* log(N+M)). TC of PQ is O(N*log(N)). We are using PG of size N+M.

Space Complexity: O(N+M)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;



void solution(int arr1[], int arr2[], int N, int M)
{
    int res[N + M];

    priority_queue<int, vector<int>, greater<int> > pq;

    for (int i = 0; i < N; i++)
        pq.push(arr1[i]);

    for (int i = 0; i < M; i++)
        pq.push(arr2[i]);

    int j = 0;

    while (!pq.empty()) 
    {

        res[j++] = pq.top();

        pq.pop();
    }

    for (int i = 0; i < N + M; i++)
        cout << res[i] << ' ';
}

int main()
{

    int arr1[] = { 1, 2, 3 };
    int arr2[] = { 4, 5, 6 };

    int N = sizeof(arr1) / sizeof(arr1[0]);
    int M = sizeof(arr2) / sizeof(arr2[0]);

    solution(arr1, arr2, N, M);

    return 0;
}

Output

1 2 3 4 5 6