Ben PereiraIt’s an easy problem with the description being:
Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:
answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
answer[1] is a list of all distinct integers in nums2 which are not present in nums1.
Note that the integers in the lists may be returned in any order.
Example 1:
Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].Example 2:
Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1.
Therefore, answer[1] = [].Constraints:
1 <= nums1.length, nums2.length <= 1000
-1000 <= nums1[i], nums2[i] <= 1000
The idea mainly in this problem is to compare each item and make sure you get the distinct ones and send it as response in a list.
So if we would do it using all that’s written with java in a simple way would be:
class Solution {
public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
// create sets (that avoid repitition) to be used on answer
Set<Integer> nums1Set = new HashSet<>();
Set<Integer> nums2Set = new HashSet<>();
// transform the arrays into lists so contains can be used [boxed needed due int being primitive]
List<Integer> nums1List = Arrays.stream(nums1).boxed().collect(Collectors.toList());
List<Integer> nums2List = Arrays.stream(nums2).boxed().collect(Collectors.toList());
// iteration of nums1
for(int i=0 ; i<nums1.length ; i++) {
if(!nums2List.contains(nums1[i])) {
nums1Set.add(nums1[i]);
}
}
// iterations of nums2
for(int i=0 ; i<nums2.length ; i++) {
if(!nums1List.contains(nums2[i])) {
nums2Set.add(nums2[i]);
}
}
// building answer
List<List<Integer>> answer = new ArrayList<>();
answer.add(new ArrayList<Integer>());
answer.add(new ArrayList<Integer>());
answer.get(0).addAll(nums1Set);
answer.get(1).addAll(nums2Set);
return answer;
}
}
Runtime: 266 ms, faster than 5.01% of Java online submissions for Find the Difference of Two Arrays.
Memory Usage: 44.5 MB, less than 68.11% of Java online submissions for Find the Difference of Two Arrays.
This first solution works fine, but is really slow since there is two iterations and contains comparison between each of the new lists displayed, a better solution which is one that Leet Code describes is:
class Solution {
// Returns the elements in the first arg nums1 that don't exist in the second arg nums2.
List<Integer> getElementsOnlyInFirstList(int[] nums1, int[] nums2) {
Set<Integer> onlyInNums1 = new HashSet<> ();
// Iterate over each element in the list nums1.
for (int num : nums1) {
boolean existInNums2 = false;
// Check if num is present in the second arg nums2.
for (int x : nums2) {
if (x == num) {
existInNums2 = true;
break;
}
}
if (!existInNums2) {
onlyInNums1.add(num);
}
}
// Convert to vector.
return new ArrayList<>(onlyInNums1);
}
public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
return Arrays.asList(getElementsOnlyInFirstList(nums1, nums2), getElementsOnlyInFirstList(nums2, nums1));
}
}
Runtime: 46 ms, faster than 18.35% of Java online submissions for Find the Difference of Two Arrays.
Memory Usage: 44.4 MB, less than 78.60% of Java online submissions for Find the Difference of Two Arrays.
Much faster, still there is two iterations but the concept is little bit difference.
This can be further improved if we use streams concept, like this:
class Solution {
public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
Set<Integer> s1 = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
Set<Integer> s2 = Arrays.stream(nums2).filter(n -> !s1.contains(n)).boxed().collect(Collectors.toSet());
Arrays.stream(nums2).forEach(s1::remove);
return Arrays.asList(new ArrayList<>(s1), new ArrayList<>(s2));
}
}
Runtime: 16 ms, faster than 25.09% of Java online submissions for Find the Difference of Two Arrays.
Memory Usage: 44.3 MB, less than 87.00% of Java online submissions for Find the Difference of Two Arrays.
This solution by climberig shows it how this can be done in four lines and the whole concept is there as well, you create one set based on the first array, then make another one but before boxing you filter out using the first set created.
Then you iterate second array and remove from first one.
This would be ideal, if wasn’t for the constraints that limits the amount of items. With that in mind I believe the best and fastest way to get it done would be just making new lists and sets and removing from the previous, not checking for each if contains it, just remove it and give it as result, like this:
class Solution {
public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
final Set<Integer> set1 = createSetFromNumArray(nums1);
final Set<Integer> set2 = createSetFromNumArray(nums2);
final List<Integer> diff1 = getDiffasList(set1, set2);
final List<Integer> diff2 = getDiffasList(set2, set1);
final List<List<Integer>> result = new ArrayList<>();
result.add(diff1);
result.add(diff2);
return result;
}
public Set<Integer> createSetFromNumArray(final int[] nums) {
final Set<Integer> set = new HashSet<>();
for (int n: nums) {
set.add(n);
}
return set;
}
public List<Integer> getDiffasList(final Set<Integer> set1, final Set<Integer> set2) {
final List<Integer> diff1 = new ArrayList<>(set1);
diff1.removeAll(set2);
return diff1;
}
}
Runtime: 8 ms, faster than 97.07% of Java online submissions for Find the Difference of Two Arrays.
Memory Usage: 44.3 MB, less than 78.60% of Java online submissions for Find the Difference of Two Arrays.
First we remove the duplication by making a Set from the Array, then we get the diffs and last we build the response.
This is the best one, with fastest runtime and still with a good amount of memory usage.
That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.
Until next post! :)
