Introduction

A simple, yet effective algorithm to find the differences between two sets of integers using C++.

Algorithms

Find Difference Algorithm

Logic

• The algorithm first inserts all elements from two input arrays into separate unordered sets to eliminate duplicates and allow for efficient lookup.
• It then iterates through each set, comparing elements to identify which are unique to each array (i.e., present in one but not the other).
• The unique elements are stored in two separate vectors, which are then returned together as a vector of vectors.

Complexity Analysis

• Time Complexity: O(n + m), where n and m are the sizes of the two input arrays. This accounts for the insertion and lookup operations in the unordered sets.
• Space Complexity: O(n + m), primarily due to storage used by the two unordered sets and the two vectors that store unique elements.

Code Snippet

vector<vector<int>> findDifference(const vector<int>& nums1, const vector<int>& nums2) {
	vector<vector<int>> answer;
	unordered_set<int> nums1List;
	unordered_set<int> nums2List;

	// First, place all values from the containers in separate lists
	for (int element : nums1) {
		nums1List.insert(element);
	}
	for (int element : nums2) {
		nums2List.insert(element);
	}

	// Next, for each element in nums1, determine if it exists in nums2
	vector<int> uniqueNums;
	for (int element : nums1List) {
		// If the element is unique, add it to the vector
		if (nums2List.find(element) == nums2List.end()) {
			uniqueNums.push_back(element);
		}
	}

	// Now store the unqiue numbers in set1
	answer.push_back(uniqueNums);

	// Reset containers and repeat for the numbers in set 2
	uniqueNums.clear();

	for (int element : nums2List) {
		// If the element is unique, add it to the vector
		if (nums1List.find(element) == nums1List.end()) {
			uniqueNums.push_back(element);
		}
	}

	answer.push_back(uniqueNums);
	return answer;
}

Test Cases

The main function contains several test cases:

• Arrays with some common elements.
• Arrays with no common elements.
• Identical arrays.
• One array is empty.
• Both arrays are empty.
• Arrays with negative numbers.
• Arrays with duplicate elements.
• Arrays with a larger range of numbers.