Merge 2 Sorted Array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
432 upvotes
Asked in company
MakeMyTrip

Problem statement

Given two sorted arrays, ‘a’ and ‘b’, of size ‘n’ and ‘m’, respectively, return the union of the arrays.


The union of two sorted arrays can be defined as an array consisting of the common and the distinct elements of the two arrays. The final array should be sorted in ascending order.


Note: 'a' and 'b' may contain duplicate elements, but the union array must contain unique elements.


Example: 
Input: ‘n’ = 5 ‘m’ = 3
‘a’ = [1, 2, 3, 4, 6]
‘b’ = [2, 3, 5]

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

Explanation: Common elements in ‘a’ and ‘b’ are: [2, 3]
Distinct elements in ‘a’ are: [1, 4, 6]
Distinct elements in ‘b’ are: [5]
Union of ‘a’ and ‘b’ is: [1, 2, 3, 4, 5, 6]
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line contains two integers, ‘n’ and ‘m’, denoting the size of the array ‘a’ and ‘b’, respectively.
The following line contains ‘n’ integers, denoting the 'a'.
The next line contains ‘m’ integers, denoting the ‘b’.
Output format: 
Return the union of both arrays sorted in ascending order.
Note:- 
You don't need to print anything. Just implement the given function.
Sample Input 1 :
5 3
1 2 3 4 6
2 3 5
Sample Output 1 :
1 2 3 4 5 6
Explanation Of Sample Input 1 :
Input: ‘n’ = 5 ‘m’ = 3
‘a’ = [1, 2, 3, 4, 6]
‘b’ = [2, 3, 5]

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

Explanation: Common elements in ‘a’ and ‘b’ are: [2, 3]
Distinct elements in ‘a’ are: [1, 4, 6]
Distinct elements in ‘b’ are: [5]
Union of ‘a’ and ‘b’ is: [1, 2, 3, 4, 5, 6]
Sample Input 2:
4 3
1 2 3 3
2 2 4
Sample Output 2:
1 2 3 4
Explanation Of Sample Input 2 :
Input: ‘n’ = 5 ‘m’ = 3
‘a’ = [1, 2, 3, 3]
‘b’ = [2, 2, 4]

Output: [1, 2, 3, 4]

Explanation: Common elements in ‘a’ and ‘b’ are: [2]
Distinct elements in ‘a’ are: [1, 3]
Distinct elements in ‘b’ are: [4]
Union of ‘a’ and ‘b’ is: [1, 2, 3, 4]
Expected Time Complexity:
O(( N + M )), where 'N' and ‘M’ are the sizes of Array ‘A’ and ‘B’.
Constraints :
1 <= 'n', 'm' <= 10^5
-10^9 <= 'a'[i], 'b'[i] <= 10^9

Time Limit: 1 sec
Hint

Use a set to store all elements.

Approaches (2)
Set

The solution to the problem can be to store all the elements of array ‘A’ and array ‘B’ in a set.

This way, all the elements of array ‘A’ and array ‘B’ will be included in the set. 

Also, one number will not be present more than once (because we are using a set). 

In the end, we can take all the elements of the set and store them in a ‘dynamic array’, then we can return it.

 

The steps are as follows:-

 

// Function to find the union of two sorted arrays

            function sortedArray(int[] A, int[] B, int N, int M):
 

  1. Int 'N', and ‘M’ be the size of arrays ‘A’ and ‘B’, respectively.
  2. Initialize a set ‘st’ of type ‘int’.
  3. Iterate over array ‘A’ and insert elements into set ‘st’.
  4. Iterate over array ‘B’ and insert elements into set ‘st’.
  5. Initialize a 1-D array ‘unionArray’.
  6. Iterate over the set and insert elements into the array unionArray.
  7. Return unionArray.
Time Complexity

O(( N + M ) * log( N + M )), where 'N' and ‘M’ are the sizes of Array ‘A’ and ‘B’.
 

Since we are using set here,

 

Hence the time complexity is O(( N + M ) * log( N + M )).

 

Space Complexity

O(N + M), where 'N' and ‘M’ are the sizes of Array ‘A’ and ‘B’.
 

Here we are using a set, which in the worst-case scenario stores ‘N + M’ elements.

 

Hence the space complexity is O(N + M).

Code Solution
(100% EXP penalty)
Merge 2 Sorted Array
Full screen
Console