algoadvance

Leetcode 349. Intersection of Two Arrays

Problem Statement

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.

Example 1:

Example 2:

Clarifying Questions

  1. Are the input arrays sorted?
    • No, the arrays are not guaranteed to be sorted.
  2. Can we assume the input will always contain integers only?
    • Yes, the problem statement specifies integer arrays.
  3. What should we return if there is no intersection?
    • Return an empty array.
  4. Are there any constraints on the input size?
    • The problem statement does not mention constraints, so we should handle general cases efficiently.

Strategy

  1. Set Data Structure: Use sets to easily manage and find the intersection of elements.

    • Convert both nums1 and nums2 to sets to eliminate duplicates.
    • Use the set_intersection algorithm to find common elements.
  2. Implementation Steps:
    • Convert nums1 and nums2 to sets.
    • Compute the intersection of these sets.
    • Convert the result back to a vector as required by the problem.
  3. Time Complexity:
    • Converting arrays to sets: O(n + m), where n is the size of nums1 and m is the size of nums2.
    • Computing the intersection of two sets: O(min(n, m)).
    • Overall, the time complexity is O(n + m).

Code

#include <vector>
#include <set>
#include <algorithm>

std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
    std::set<int> set1(nums1.begin(), nums1.end());
    std::set<int> set2(nums2.begin(), nums2.end());
    
    std::vector<int> result;
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result));
    
    return result;
}

Explanation

  1. Initialization:
    • We create a set from nums1 and another set from nums2 to eliminate duplicates and facilitate intersection finding.
  2. Finding Intersection:
    • We use std::set_intersection from the Standard Library to find the common elements between the two sets.
  3. Result Compilation:
    • The intersection set is then converted back to a vector and returned as the final result.

This approach ensures that we efficiently find the unique intersection elements between the two input arrays.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI