2215. Find the Difference of Two Arrays
Problem Description
The problem provides us with two integer arrays, nums1
and nums2
, which are both 0-indexed. The goal is to create a list called answer
that consists of two sublists:
answer[0]
should include all unique integers that are found innums1
but not innums2
.answer[1]
should include all unique integers that are found innums2
but not innums1
.
These lists of unique integers should exclude any duplicates and can be returned in any order.
Intuition
To solve this problem, we start by understanding the requirement for unique elements that are present in one array but not the other. This naturally leads us to think of set operations because sets automatically handle uniqueness and provide efficient operations for difference and intersection.
The intuitive approach is to:
- Convert both
nums1
andnums2
into sets to eliminate any repeated numbers within each array. - Use set subtraction (
-
) to find elements that are in one set but not the other.
Set subtraction s1 - s2
yields a set of elements that are in s1
but not in s2
. Here are the steps:
- Convert
nums1
to a sets1
to obtain unique elements fromnums1
. - Convert
nums2
to a sets2
to get unique elements fromnums2
. - Perform
s1 - s2
to find all elements that are innums1
but not innums2
. - Do the reverse and compute
s2 - s1
to find all elements innums2
but not innums1
. - Convert these results back into lists and return them as the
answer
list with two sublists as described above.
This solution is concise, and the key is leveraging set operations to efficiently answer the question without having to implement complex logic for handling uniqueness or element comparison.
Solution Approach
The solution consists of a class Solution
with a method findDifference
which takes two lists, nums1
and nums2
, and returns a list containing two lists representing the differences between the two original lists. Here is a step-by-step explanation of the implementation:
-
First, we need to create two sets:
s1
is created fromnums1
ands2
is created fromnums2
. Using sets is a critical choice here because:- Sets automatically remove duplicate values.
- They provide efficient operations for set difference (
-
), which is directly needed for this problem.
-
s1
is our set representing all unique elements fromnums1
, ands2
fornums2
. Now, we use set subtraction to get the elements that are unique to each set:s1 - s2
will give us a new set of elements that are present ins1
(unique tonums1
) but not ins2
.s2 - s1
will give us a new set of elements that are present ins2
(unique tonums2
) but not ins1
.
-
Finally, these sets are converted back to lists. This is necessary because the problem asks us to return a list of lists; sets wouldnāt be an acceptable return type according to the problem constraints.
-
The two lists are then packed into one list and returned. The order in which the lists are returned is as per the problem requirements: the first sublist represents numbers in
nums1
not present innums2
, and the second sublist for the opposite.
The algorithm's complexity is beneficial because set operations like the difference are generally O(n), where n is the number of elements in the set. This efficiency comes from the fact that sets are usually implemented as hash tables, allowing for constant-time average performance for add, remove, and check-for-existence operations, which is much faster than trying to perform these operations on an unsorted list.
The code is thus:
class Solution:
def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
s1, s2 = set(nums1), set(nums2)
return [list(s1 - s2), list(s2 - s1)]
Using sets not only makes the code cleaner and more readable but also ensures the operations are done as efficiently as possible for the problem's requirements.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the arrays nums1 = [1, 2, 3, 3, 4]
and nums2 = [3, 4, 4, 5, 6]
. We want to use the solution approach to find the differences between these arrays.
Here is the step-by-step walkthrough of the solution:
-
Convert the
nums1
array to a sets1
to remove duplicates and gain unique elements. The conversion results ins1 = {1, 2, 3, 4}
. -
Similarly, convert
nums2
array to a sets2
yieldings2 = {3, 4, 5, 6}
. -
Subtract the set
s2
froms1
to find elements that are unique tonums1
. Performings1 - s2
gives us{1, 2}
since numbers 3 and 4 are present in both sets and are hence not part of the set difference. -
Do the reverse subtraction,
s2 - s1
, to find elements unique tonums2
. We get{5, 6}
because again, 3 and 4 are present in both sets. -
These set differences are converted back to lists:
list(s1 - s2)
becomes[1, 2]
andlist(s2 - s1)
becomes[5, 6]
. Note that the order of elements in these lists doesn't matter. -
Finally, return these lists as sublists in a single list:
[[1, 2], [5, 6]]
.
Using this approach ensures the returned lists have no duplicates and only contain elements that are unique to each of the original lists, nums1
and nums2
. The final answer for our example input is therefore [[1, 2], [5, 6]]
.
Solution Implementation
1class Solution:
2 def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
3 # Convert the lists into sets to eliminate any duplicates and allow set operations.
4 set_nums1, set_nums2 = set(nums1), set(nums2)
5
6 # Calculate the difference between the two sets.
7 # The difference operation (s1 - s2) returns a set with elements in s1 but not in s2.
8 difference1 = list(set_nums1 - set_nums2)
9 difference2 = list(set_nums2 - set_nums1)
10
11 # Return the differences as a list of lists.
12 # The first inner list contains elements unique to nums1.
13 # The second inner list contains elements unique to nums2.
14 return [difference1, difference2]
15
1class Solution {
2
3 // This method finds the difference between two integer arrays.
4 // It returns a list of lists where the first list contains elements unique to nums1
5 // and the second list contains elements unique to nums2.
6 public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
7 // Convert both arrays to sets to remove duplicates and allow for O(1) lookups.
8 Set<Integer> set1 = convertToSet(nums1);
9 Set<Integer> set2 = convertToSet(nums2);
10
11 // Initialize the answer list that will contain two lists.
12 List<List<Integer>> answer = new ArrayList<>();
13 List<Integer> uniqueToNums1 = new ArrayList<>();
14 List<Integer> uniqueToNums2 = new ArrayList<>();
15
16 // Iterate over set1 and add elements not in set2 to uniqueToNums1.
17 for (int value : set1) {
18 if (!set2.contains(value)) {
19 uniqueToNums1.add(value);
20 }
21 }
22
23 // Iterate over set2 and add elements not in set1 to uniqueToNums2.
24 for (int value : set2) {
25 if (!set1.contains(value)) {
26 uniqueToNums2.add(value);
27 }
28 }
29
30 // Add both lists to the answer list.
31 answer.add(uniqueToNums1);
32 answer.add(uniqueToNums2);
33
34 // Return the final list of lists containing unique elements.
35 return answer;
36 }
37
38 // This method converts an integer array to a set to remove duplicates.
39 private Set<Integer> convertToSet(int[] nums) {
40 Set<Integer> set = new HashSet<>();
41 for (int value : nums) {
42 set.add(value);
43 }
44 return set;
45 }
46}
47
1#include <vector>
2#include <unordered_set>
3using namespace std;
4
5class Solution {
6public:
7 vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
8 // Convert vectors to unordered sets to remove duplicates and for constant time lookups
9 unordered_set<int> setNums1(nums1.begin(), nums1.end());
10 unordered_set<int> setNums2(nums2.begin(), nums2.end());
11
12 // Initialize a vector of vectors to store the unique elements from each set
13 vector<vector<int>> uniqueElements(2);
14
15 // Find the elements unique to setNums1 by checking if they are not in setNums2
16 for (int value : setNums1) {
17 if (setNums2.count(value) == 0) {
18 uniqueElements[0].push_back(value);
19 }
20 }
21
22 // Find the elements unique to setNums2 by checking if they are not in setNums1
23 for (int value : setNums2) {
24 if (setNums1.count(value) == 0) {
25 uniqueElements[1].push_back(value);
26 }
27 }
28
29 // Return the vector containing unique elements from both sets
30 return uniqueElements;
31 }
32};
33
1// Finds the difference between two arrays by giving unique elements in each of them
2// that are not present in the other.
3// @param {number[]} firstArray - First input array of numbers
4// @param {number[]} secondArray - Second input array of numbers
5// @return A two-dimensional array where the first subarray contains unique elements
6// from `firstArray` not in `secondArray`, and the second subarray contains unique
7// elements from `secondArray` not in `firstArray`.
8function findDifference(firstArray: number[], secondArray: number[]): number[][] {
9 // Filter elements from the first array that are not present in the second array
10 // and remove duplicates by converting it to a Set, then spread it back to array.
11 const uniqueInFirst = [...new Set<number>(firstArray.filter(value => !secondArray.includes(value)))];
12
13 // Filter elements from the second array that are not present in the first array
14 // and remove duplicates by converting it to a Set, then spread it back to array.
15 const uniqueInSecond = [...new Set<number>(secondArray.filter(value => !firstArray.includes(value)))];
16
17 // Return the two arrays encapsulated in another array.
18 return [uniqueInFirst, uniqueInSecond];
19}
20
Time and Space Complexity
The given Python code defines a function findDifference
that takes two lists of integers, nums1
and nums2
, and returns two lists:
- The first list contains all elements that are in
nums1
but not innums2
. - The second list contains all elements that are in
nums2
but not innums1
.
To achieve this, the function converts both lists to sets, which are then used to find the difference between them.
Time Complexity
The time complexity of the function is determined by multiple operations:
- Converting
nums1
to a set:O(n)
wheren
is the length ofnums1
. - Converting
nums2
to a set:O(m)
wherem
is the length ofnums2
. - Finding the difference
s1 - s2
: This isO(len(s1))
because it essentially involves checking each element ins1
to see if it is not ins2
. - Finding the difference
s2 - s1
: Analogously, this isO(len(s2))
.
Assuming n
is the length of nums1
and m
is the length of nums2
, the overall time complexity is O(n + m)
as the set differences are proportional to the size of the sets.
Space Complexity
The space complexity is also determined by multiple factors:
- The space used by
s1
:O(n)
wheren
is the number of unique elements innums1
. - The space used by
s2
:O(m)
wherem
is the number of unique elements innums2
. - The space used by the output lists: This largely depends on how many elements are unique to each list after the set difference operation. However, in the worst case (where all elements are unique), this would again be
O(n + m)
.
The overall space complexity is thus O(n + m)
where n
is the number of unique elements in nums1
and m
is the number of unique elements in nums2
.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!