-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathUnion of Two Sorted Arrays
143 lines (101 loc) · 2.48 KB
/
Union of Two Sorted Arrays
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
Union of two arrays can be defined as the common and distinct elements in the two arrays.
Given two sorted arrays of size N and M respectively, find their union.
Example 1:
Input:
N = 5, arr1[] = {1, 2, 3, 4, 5}
M = 3, arr2 [] = {1, 2, 3}
Output: 1 2 3 4 5
Explanation: Distinct elements including
both the arrays are: 1 2 3 4 5.
Example 2:
Input:
N = 5, arr1[] = {2, 2, 3, 4, 5}
M = 5, arr2[] = {1, 1, 2, 3, 4}
Output: 1 2 3 4 5
Explanation: Distinct elements including
both the arrays are: 1 2 3 4 5.
Example 3:
Input:
N = 5, arr1[] = {1, 1, 1, 1, 1}
M = 5, arr2[] = {2, 2, 2, 2, 2}
Output: 1 2
Explanation: Distinct elements including
both the arrays are: 1 2.
Your Task:
You do not need to read input or print anything. Complete the function findUnion() that takes two arrays arr1[], arr2[], and their size N and M as input parameters and returns a list containing the union of the two arrays.
Expected Time Complexity: O(N+M).
Expected Auxiliary Space: O(N+M).
Constraints:
1 <= N, M <= 105
1 <= arr[i], brr[i] <= 106
// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
//arr1,arr2 : the arrays
// n, m: size of arrays
vector<int> findUnion(int arr1[], int arr2[], int n, int m)
{
vector<int> ans;
int i=0,j=0;
while(i<n&&j<m)
{
if(arr1[i]<arr2[j])
{
if(i==0)
ans.push_back(arr1[i]);
else if(arr1[i]!=arr1[i-1])
ans.push_back(arr1[i]);
i++;
}
else if(arr1[i]>arr2[j])
{
if(j==0)
ans.push_back(arr2[j]);
else if(arr2[j]!=arr2[j-1])
ans.push_back(arr2[j]);
j++;
}
else
{
if(arr1[i]!=arr1[i-1]&&arr2[j]!=arr2[j-1])
ans.push_back(arr1[i]);
i++;
j++;
}
}
while(i<n)
{
if(arr1[i]!=arr1[i-1])
ans.push_back(arr1[i]);
i++ ;
}
while(j<m)
{
if(arr2[j]!=arr2[j-1])
ans.push_back(arr2[j]);
j++;
}
return ans;
}
// { Driver Code Starts.
int main() {
int T;
cin >> T;
while(T--){
int N, M;
cin >>N >> M;
int arr1[N];
int arr2[M];
for(int i = 0;i<N;i++){
cin >> arr1[i];
}
for(int i = 0;i<M;i++){
cin >> arr2[i];
}
vector<int> ans = findUnion(arr1,arr2, N, M);
for(int i: ans)cout<<i<<' ';
cout << endl;
}
return 0;
} // } Driver Code Ends