Good day fellow software developers and engineers! It is a gloomy day in the Twin Cities of Minneapolis and St. Paul. Hopefully the weather is nicer in your neck of the woods.
Today I picked up the LeetCode 349 Intersection of Two Arrays problem. To be honest with you I do not recall why I did it. Due to thunderstorms I had to power down my computers a couple times today. I just lost track of the reason why I picked this problem.
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order. Constraints: o 1 <= nums1.length, nums2.length <= 1000 o 0 <= nums1[i], nums2[i] <= 1000
We are given two integer arrays and are charged with returning an array of all the values that intersect the arrays. In other words the unique common values to both arrays.
In this post we will be solving the problem using the Java programming language and the VSCode IDE on a Windows platform connected to a UPS due to the possibility of thunderstorms in this area. Your choice of platform should not affect the code since Java is quite portable.
We will be generating our own test code since we will be developing the code on my Windows machine. Unless you have a good reason to generate your own test code, you should use the on-line IDE provided by LeetCode. Note that the test code IS NOT PART OF THE SOLUTION!
public int[] intersection(int[] nums1, int[] nums2) {
}
The first two are input lines. They hold the integer values for the two arrays `nums1` and `nums2`. Our test code seems to be able to read the values, populate the two arrays and then display them. This is done to verify that all is well so far.
1,2,2,1 2,2 main <<< nums1: [1, 2, 2, 1] main <<< nums2: [2, 2] main <<< intersection0: [2] main <<< intersection: [2] 4,9,5 9,4,9,8,4 main <<< nums1: [4, 9, 5] main <<< nums2: [9, 4, 9, 8, 4] main <<< intersection0: [4, 9] main <<< intersection: [4, 9]
It seems we have tow implementations. They both seem to provide the same results in the two cases. Hopefully it will carry when the code is submitted at LeetCode.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read `nums1` array ****
int[] nums1 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read `nums2` array ****
int[] nums2 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums1: " + Arrays.toString(nums1));
System.out.println("main <<< nums2: " + Arrays.toString(nums2));
// **** call function of interest and display result ****
System.out.println("main <<< intersection0: " + Arrays.toString(intersection0(nums1, nums2)));
// **** call function of interest and display result ****
System.out.println("main <<< intersection: " + Arrays.toString(intersection(nums1, nums2)));
}
The source code for the test scaffold is self explanatory. I do not have much to add at this time.
/**
* Given two integer arrays nums1 and nums2, return an array of their intersection.
* Each element in the result must be unique and you may return the result in any order.
*
* Sorting arrays.
*
* Runtime: 5 ms, faster than 20.88% of Java online submissions.
* Memory Usage: 38.9 MB, less than 91.27% of Java online submissions.
*
* 55 / 55 test cases passed.
* Status: Accepted
* Runtime: 5 ms
* Memory Usage: 38.9 MB
*/
static int[] intersection0(int[] nums1, int[] nums2) {
// **** initialization ****
List<Integer> ans = new ArrayList<Integer>();
// **** sort arrays - O(n * log(n)) ****
Arrays.sort(nums1);
Arrays.sort(nums2);
// **** traverse arrays looking for intersection(s) ****
int i = 0, j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) i++;
else if (nums1[i] == nums2[j]) {
// **** check for duplicate values ****
if (!ans.contains(nums1[i]))
ans.add(nums1[i]);
// **** ****
i++; j++;
}
else j++;
}
// **** populate result with the contents of the list ****
int[] result = new int[ans.size()];
i = 0;
for (int r : ans)
result[i++] = r;
// **** return int[] result ****
return result;
}
In this implementation we will sort both arrays and then we will traverse them in ascending order looking for the common (intersecting) value(s).
We start by initializing the `ans` list. It will hold the intersecting values.
Next we sort both arrays. We will be traversing the arrays in ascending order using a couple indices while adding intersecting values to the `ans` list.
We declare a couple indices and set them to 0. We then enter the while loop which will cycle while the values of I and j are in range.
We then have logic to check the relative values of the arrays pointed by the indices. There are three conditions. The first and last are just skipping values in the arrays. When the values are the same, we check if we need to add it to the `ans` list. If so we do it. One way or the other we update both indices because the values are the same. We have just dealt with an intersecting value.
After the while loop we need to return the data in the list as an array. There are different approaches we could have used. In this case we declare the `result` array and then populate it with the values in the `ans` list. When all is set and done we return the `result` array.
You can see the execution time and memory usage in the comments section of the function.
/**
* Given two integer arrays nums1 and nums2, return an array of their intersection.
* Each element in the result must be unique and you may return the result in any order.
*
* Using HashSet.
*
* Runtime: 2 ms, faster than 95.11% of Java online submissions.
* Memory Usage: 38.9 MB, less than 82.51% of Java online submissions.
*
* 55 / 55 test cases passed.
* Status: Accepted
* Runtime: 2 ms
* Memory Usage: 39 MB
*/
static int[] intersection(int[] nums1, int[] nums2) {
// **** initialization ****
HashSet<Integer> hs = new HashSet<Integer>();
List<Integer> ans = new ArrayList<Integer>();
// **** populate hash set - O(n) ****
for (int i = 0; i < nums1.length; i++)
hs.add(nums1[i]);
// **** look for common values - O(m) ****
for (int i = 0; i < nums2.length; i++) {
// **** check if this is an intersection ****
if (hs.contains(nums2[i])) {
// **** add value to list ****
ans.add(nums2[i]);
// **** to avoid duplicates ****
hs.remove(nums2[i]);
}
}
// **** populate result with contents of list ****
int[] result = new int[ans.size()];
int j = 0;
for (int r : ans)
result[j++] = r;
// **** return int[] result ****
return result;
}
In this implementation of the function of interest we will use a hash set instead of sorting the arrays.
We start by declaring a couple data structures and then populating the hash set with the values from the `nums1` array.
A loop is then encountered. In this loop we will traverse the contents of the `nums2` array checking for intersections with values in the hash map. When an intersection is found, we update the `ans` list and remove the value form the hash map. We need to do so to avoid multiple instances of the same value.
When all is done, we need to generate and return an integer array. We use the same approach as we did in the previous implementation.
Please check the execution time and space used by this implementation in the comments section of the function.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John