Dare2Solve
The problem is to identify the distinct elements between two lists of integers. Specifically, we need to find elements that are present in the first list but not in the second and vice versa. The output should consist of two lists: one for the unique elements in the first list and one for the unique elements in the second list.
The intuition behind this solution is based on leveraging the properties of sets. Sets automatically handle duplicate values and allow for efficient membership testing. By converting the lists into sets, we can easily identify which elements are unique to each list by checking if an element from one set is absent in the other set.
O(n + m), where n is the length of the first list and m is the length of the second list. Converting the lists to sets and performing lookups in sets both run in linear time.
O(n + m) for storing the sets and the result lists.
class Solution {
public:
vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
set<int> set1(nums1.begin(), nums1.end());
set<int> set2(nums2.begin(), nums2.end());
vector<int> nums1Def;
for (int n : set1) {
if (set2.find(n) == set2.end()) {
nums1Def.push_back(n);
}
}
vector<int> nums2Def;
for (int n : set2) {
if (set1.find(n) == set1.end()) {
nums2Def.push_back(n);
}
}
return {nums1Def, nums2Def};
}
};
class Solution:
def findDifference(self, nums1, nums2):
set1 = set(nums1)
set2 = set(nums2)
nums1Def = [n for n in set1 if n not in set2]
nums2Def = [n for n in set2 if n not in set1]
return [nums1Def, nums2Def]
class Solution {
public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
for (int n : nums1) {
set1.add(n);
}
Set<Integer> set2 = new HashSet<>();
for (int n : nums2) {
set2.add(n);
}
List<Integer> nums1Def = new ArrayList<>();
for (int n : set1) {
if (!set2.contains(n)) {
nums1Def.add(n);
}
}
List<Integer> nums2Def = new ArrayList<>();
for (int n : set2) {
if (!set1.contains(n)) {
nums2Def.add(n);
}
}
List<List<Integer>> result = new ArrayList<>();
result.add(nums1Def);
result.add(nums2Def);
return result;
}
}
var findDifference = function (nums1, nums2) {
let set1 = new Set(nums1)
let set2 = new Set(nums2)
const nums1Def = []
for (let n of set1) {
if (!set2.has(n)) nums1Def.push(n)
}
const nums2Def = []
for (let n of set2) {
if (!set1.has(n)) nums2Def.push(n)
}
return [nums1Def, nums2Def]
};