grid47 Exploring patterns and algorithms
Oct 3, 2024
5 min read
Solution to LeetCode 349: Intersection of Two Arrays 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.
Problem
Approach
Steps
Complexity
Input: You are given two integer arrays, nums1 and nums2. The arrays contain integer elements.
• Explanation: The intersection of the two arrays is [1, 3, 7] because these elements appear in both arrays.
• Input: Input: nums1 = [2, 2, 1], nums2 = [2, 3]
• Explanation: The intersection of the two arrays is [2] because 2 is the only common element in both arrays.
Approach: The approach involves converting one of the arrays into a set to ensure uniqueness and facilitate fast lookups. Then, we iterate through the second array to find common elements.
Observations:
• Using a set for the first array will allow for efficient checking of elements in the second array.
• By iterating over the second array, we can check each element's presence in the first array using the set and ensure uniqueness in the result.
Steps:
• Convert nums1 to a set to remove duplicates and enable fast lookup.
• Iterate through nums2 and check if the current element is in the set from nums1.
• If the element is found, add it to the result list and remove it from the set to avoid duplicates in the final result.
Empty Inputs:
• If either nums1 or nums2 is empty, the result should be an empty array.
Large Inputs:
• Ensure that the solution efficiently handles large arrays with sizes up to 1000.
Special Values:
• Handle arrays with no common elements by returning an empty array.
Constraints:
• The algorithm should work efficiently with arrays up to the maximum constraint of 1000 elements.
The function `intersection` takes two integer vectors `nums1` and `nums2` as input and returns a vector containing their intersection, i.e., elements common to both vectors.
2 : Set Initialization
unordered_set<int> m(nums1.begin(), nums1.end());
Create an unordered set `m` initialized with the elements from `nums1`. This allows for efficient O(1) lookups when checking for element existence.
3 : Result Vector Declaration
vector<int> res;
Declare an empty vector `res` to store the elements that are part of the intersection of `nums1` and `nums2`.
4 : Loop Over Second Array
for (autoa : nums2)
Iterate through each element `a` in the second array `nums2`.
5 : Check if Element Exists in Set
if (m.count(a)) {
For each element `a` in `nums2`, check if it exists in the set `m` (i.e., if it is also in `nums1`).
6 : Add to Result
res.push_back(a);
If the element `a` exists in `m`, add it to the result vector `res`.
7 : Erase from Set
m.erase(a);
Remove the element `a` from the set `m` to ensure that each element is added to the result only once, preventing duplicates.
8 : Return Result
return res;
After iterating through `nums2`, return the vector `res` which now contains the intersection of `nums1` and `nums2`.
Best Case: O(n + m)
Average Case: O(n + m)
Worst Case: O(n + m)
Description: The solution iterates through both arrays once, where n and m are the lengths of nums1 and nums2, respectively.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we store the elements of nums1 in a set.
