Union of Two Sorted Arrays with Duplicate Elements GFG

• Link: https://www.geeksforgeeks.org/problems/union-of-two-sorted-arrays-1587115621/1?utm_source=youtube&utm_medium=collab_striver_ytdescription&utm_campaign=union-of-two-sorted-arrays

Question

Given two sorted arrays a[] and b[], where each array may contain duplicate elements , the task is to return the elements in the union of the two arrays in sorted order.

Union of two arrays can be defined as the set containing distinct common elements that are present in either of the arrays.

Examples:

Input: a[] = [1, 2, 3, 4, 5], b[] = [1, 2, 3, 6, 7]
Output: 1 2 3 4 5 6 7
Explanation: Distinct elements including both the arrays are: 1 2 3 4 5 6 7.

Input: a[] = [2, 2, 3, 4, 5], b[] = [1, 1, 2, 3, 4]
Output: 1 2 3 4 5
Explanation: Distinct elements including both the arrays are: 1 2 3 4 5.

Input: a[] = [1, 1, 1, 1, 1], b[] = [2, 2, 2, 2, 2]
Output: 1 2
Explanation: Distinct elements including both the arrays are: 1 2.

Constraints:
1  <=  a.size(), b.size()  <=  105
-109  <=  a[i] , b[i]  <=  109

Approach 1: Brute Force

Intuition

• As we need unique elements, Data structure that comes to mind is a SET
• In CPP we have an ordered set (set) & an unordered set (unordered_set)
• We'll use an ordered set as we want the output in sorted order.

Algorithm

1. Declare set<int> s
2. Insert the elements of a vector in s
3. Insert the elements of b vector in s
4. Declare vector<int> ans.
5. push_back all the elements of set sin ans
   1. As we used an ordered set we don't have to sort the ans
6. Return ans

Code

class Solution {
public: 
	vector<int> findUnion(vector<int> &a, vector<int> &b) {
		set<int> s(a.begin(), a.end());
		
		for (int i = 0 ; i < b.size() ; i++) {
			s.insert(b[i]);
		}
		
		vector<int> ans(s.begin(), s.end());
		
		return ans;
	}
}

Complexity Analysis

• Time Complexity: $O(n\log (n)+O(m\log (n+m))+O(n+m)$

• Space Complexity: $O(2(n+m))=O(n+m)$

Reference

Set CPP

Approach 2: Optimal

Intuition

• Two Pointers DSA

Algorithm

1. Declare vector<int> ans
2. Declare & initialize int i = 0 for vector a, int j = 0 for vector b
3. While i < a.size() && j < b.size()
   • Push the lesser element in the ans if the last element of ans is not that element and increment its pointer
   1. if a[i] < b[j] && (ans.empty() || ans.back() != a[i]), ans.push_back(a[i++])
   2. if b[j] < a[i] && (ans.empty() || ans.back() != b[i]), ans.push_back(b[j++])
   3. else if (ans.empty() || ans.back() != b[i]), ans.push_back(b[j])
      i++, j++
4. If i < a.size() insert all the elements in the ans array
5. If j < b.size() insert all the elements in the ans array
6. Return ans.

Code

class Solution {
public:
	vector<int> findUnion(vector<int> &a, vector<int> &b) {
		vector<int> ans;
		int i = 0, j = 0;
		
		while (i < a.size() && j < b.size()) {
			if (a[i] < b[j]) {
				if (ans.empty() || ans.back() != a[i]) {
					ans.push_back(a[i]);
				}
				i++;
			} else if (b[j] < a[i]) {
				if (ans.empty() || ans.back() != b[j]) {
					ans.push_back(b[j]);
				}
				j++;
			} else {
				if (ans.empty() || ans.back() != a[i]) {
					ans.push_back(a[i]);
				}
				i++;
				j++;
			}
		}

		while (i < a.size()) {
			if (ans.empty() || ans.back() != a[i]) {
				ans.push_back(a[i]);
			}
			i++;
		}

		while (j < b.size()) {
			if (ans.empty() || ans.back() != b[j]) {
				ans.push_back(b[j]);
			}
			j++;
		}
		
		return ans;
	}
}

Complexity Analysis

• Time Complexity: $O(n+m)$
• Space Complexity:
  • Considering ans vector: $O(n+m)$
  • Not considering ans vector: $O(1)$