Problem Statement 1 (Sorted Array)

Given two sorted arrays nums1 and nums2, return an array containing the intersection of these two arrays.

The intersection of two arrays is an array where all values are present in both arrays.

LeetCode:

• https://leetcode.com/problems/intersection-of-two-arrays/

Examples

Example 1:

Input: nums1 = [1, 2, 2, 3, 5], nums2 = [1, 2, 7]
Output: [1, 2]

Explanation: The elements 1, 2 are the only elements present in both nums1 and nums2.

Example 2:

Input: nums1 = [1, 2, 3, 4], nums2 = [5, 6, 7]
Output: []

Explanation: No elements appear in both nums1 and nums2.

Example 3:

Input: nums1 = [-7, 0, 0, 2], nums2 = [-7, 0, 0, 7]
Output: [-7, 0, 0]

Explanation: -7, 0 and 0 is common to both.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Imagine you are organizing two different guest lists for two separate events. Some guests are invited to both events, and you want to create a new list of guests who are attending both.

Here’s how you can figure it out:

• Start by going through the first guest list. For each guest in the first list, check if they are also on the second guest list. If you find a guest who is on both lists, add them to your new list of common guests, but make sure not to add the same guest more than once.

Approach:

• Create an array called visited of the same size as nums2 to keep track of elements that have already been checked in nums2.
• Iterate through loop (let's call the loop variable i) to go through each element in nums1.
• For each element in nums1, use another for loop (let's call the loop variable j) to iterate through nums2.
• For each element nums1[i], check if it is equal to nums2[j] and also ensure visited[j] is 0 (meaning this element of nums2 has not been visited yet).
• If both conditions are met, add nums1[i] to the result array ans and mark visited[j] as 1 to indicate that nums2[j] has been processed.
• Repeat the above steps until all elements in nums1 have been compared with all elements in nums2.

Code:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    //Function to find intersection of two sorted arrays
    vector<int> intersectionArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        // To maintain visited status
        vector<int> visited(nums2.size(), 0);
   
        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++) {

               /*If nums1[i] is equal to nums2[j] and nums2[j]
               is not visited then add nums2[j] in ans.*/
                if (nums1[i] == nums2[j] && visited[j] == 0) {
                    ans.push_back(nums2[j]);
                    
                    // Mark as visited
                    visited[j] = 1;
                    
                    break;
                } 
                /** If num2[j] is greater than nums1[i] 
                break out of the loop */
                else if (nums2[j] > nums1[i])
                    break; 
            }
        }
       //Return ans vector
        return ans;
    }
};

int main() {
    vector<int> nums1 = {1, 2, 3, 3, 4, 5, 6, 7};
    vector<int> nums2 = {3, 3, 4, 4, 5, 8};

    // Create an instance of the Solution class
    Solution finder;

    // Get intersection of nums1 and nums2 using class method
    vector<int> ans = finder.intersectionArrays(nums1, nums2);

    cout << "Intersection of nums1 and nums2 is:" << endl;
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(MxN), where M is the length of nums1 and N is the length of nums2.
• Space Complexity:O(N), where N is size of nums2, extra space to store answer is not considered.

2️⃣ Optimal Approach

Intuition:

Imagine you're organizing two different parties, and each party has a list of guests. Both lists are sorted alphabetically. The goal is to find out which guests are attending both parties. Starting Point: You have two guest lists:

• Party 1: Alice, Bob, Charlie, David
• Party 2: Bob, Charlie, Eve, Frank

To efficiently find the common guests, assign one pointer to the first list (Pointer A) and another pointer to the second list (Pointer B), both starting at the top of their respective lists.

Compare the guest at Pointer A with the guest at Pointer B. If they match (for example, both pointers point to Bob), note Bob as a guest attending both parties. After adding Bob, move both pointers forward to the next guests.
If the guest at Pointer A (like Alice) comes before Pointer B (like Bob), you realize Alice isn't at both parties, so move Pointer A to check the next guest. Conversely, if Pointer B points to a guest (like Eve) who comes before Pointer A, move Pointer B forward.
Keep comparing and moving the pointers until one of the pointers reaches the end of its list.

Approach:

1. Declare two pointers, i for iterating through nums1 and j for iterating through nums2, and set both to 0. Initialize a vector or list to hold the intersection results.
2. Use a while loop to continue the iteration as long as both pointers are within the bounds of their respective arrays.
3. If the elements at nums1[i] and nums2[j] are equal, add that element to the results and increment both pointers i and j by 1.
4. If nums1[i] is less than nums2[j], increment pointer i to check the next element in nums1.
5. If nums2[j] is less than nums1[i], increment pointer j to check the next element in nums2.
6. This process continues until either pointer exceeds the last index of its respective array. Finally, return the vector containing the intersection.

Dry Run:

Initialization:

        +-----+-----+-----+-----+-----+
nums1 : |  1  |  2  |  3  |  3  |  4  |
        +-----+-----+-----+-----+-----+
           0     1     2     3     4
           i
        +-----+-----+-----+-----+
nums2 : |  2  |  3  |  3  |  7  |
        +-----+-----+-----+-----+
           0     1     2     3
           j
         +---------+
newArr : |  empty  |
         +---------+

First Iteration:

        +-----+-----+-----+-----+-----+
nums1 : |  1  |  2  |  3  |  3  |  4  |
        +-----+-----+-----+-----+-----+
           0     1     2     3     4
           i
        +-----+-----+-----+-----+
nums2 : |  2  |  3  |  3  |  7  |
        +-----+-----+-----+-----+
           0     1     2     3
           j
         +--------+
newArr : |  empty |
         +--------+
  since
  nums1[i] < nums2[j]
  so increment i

Second Iteration:

        +-----+-----+-----+-----+-----+
nums1 : |  1  |  2  |  3  |  3  |  4  |
        +-----+-----+-----+-----+-----+
           0     1     2     3     4
                 i
        +-----+-----+-----+-----+
nums2 : |  2  |  3  |  3  |  7  |
        +-----+-----+-----+-----+
           0     1     2     3
           j
         +--------+
newArr : |  empty |
         +--------+
  since
  nums1[i] == nums2[j]
  push nums[i] in newArr, which is 2
  and increment both i and j

Third Iteration:

        +-----+-----+-----+-----+-----+
nums1 : |  1  |  2  |  3  |  3  |  4  |
        +-----+-----+-----+-----+-----+
           0     1     2     3     4
                 i
        +-----+-----+-----+-----+
nums2 : |  2  |  3  |  3  |  7  |
        +-----+-----+-----+-----+
           0     1     2     3
                 j
         +-----+
newArr : |  2  |
         +-----+
  since
  nums1[i] < nums2[j]
  just increment i.

Fourth Iteration:

        +-----+-----+-----+-----+-----+
nums1 : |  1  |  2  |  3  |  3  |  4  |
        +-----+-----+-----+-----+-----+
           0     1     2     3     4
                       i
        +-----+-----+-----+-----+
nums2 : |  2  |  3  |  3  |  7  |
        +-----+-----+-----+-----+
           0     1     2     3
                 j
         +-----+
newArr : |  2  |
         +-----+
  since
  nums1[i] == nums2[j]
  push nums1[i] in newArray, which is 3
  and Increment both i and j.

Fifth Iteration:

        +-----+-----+-----+-----+-----+
nums1 : |  1  |  2  |  3  |  3  |  4  |
        +-----+-----+-----+-----+-----+
           0     1     2     3     4
                             i
        +-----+-----+-----+-----+
nums2 : |  2  |  3  |  3  |  7  |
        +-----+-----+-----+-----+
           0     1     2     3
                       j
         +-----+-----+
newArr : |  2  |  3  |
         +-----+-----+
  since
  nums1[i] == nums2[j]
  push nums1[i] in newArray, which is 3
  and Increment both i and j.

Sixth Iteration:

        +-----+-----+-----+-----+-----+
nums1 : |  1  |  2  |  3  |  3  |  4  |
        +-----+-----+-----+-----+-----+
           0     1     2     3     4
                                   i
        +-----+-----+-----+-----+
nums2 : |  2  |  3  |  3  |  7  |
        +-----+-----+-----+-----+
           0     1     2     3
                             j
         +-----+-----+-----+
newArr : |  2  |  3  |  3  |
         +-----+-----+-----+
  since
  nums1[i] < nums2[j]
  and Increment i.

Loop Termination:

        +-----+-----+-----+-----+-----+
nums1 : |  1  |  2  |  3  |  3  |  4  |
        +-----+-----+-----+-----+-----+
           0     1     2     3     4
                                         i
        +-----+-----+-----+-----+
nums2 : |  2  |  3  |  3  |  7  |
        +-----+-----+-----+-----+
           0     1     2     3
                             j
         +-----+-----+-----+
newArr : |  2  |  3  |  3  |
         +-----+-----+-----+
  
  since i has reached the out of bounds so,
  break the loop and return newArr.

Code:

#include <bits/stdc++.h> // Include all standard libraries
using namespace std;

// Class to implement the solution for finding the intersection of two arrays
class Solution {
public:
    // Function to find the intersection of two sorted arrays
    vector<int> intersectionArray(vector<int>& nums1, vector<int>& nums2) {
        // Vector to store the intersection elements
        vector<int> ans;

        // Pointers to traverse nums1 and nums2
        int i = 0, j = 0;

        // Traverse both arrays using the two-pointer technique
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] < nums2[j]) {
                // If the current element in nums1 is smaller, increment the pointer for nums1
                i++;
            } else if (nums2[j] < nums1[i]) {
                // If the current element in nums2 is smaller, increment the pointer for nums2
                j++;
            } else {
                // If elements are equal, add the element to the result and increment both pointers
                ans.push_back(nums1[i]);
                i++;
                j++;
            }
        }

        // Return the vector containing the intersection of nums1 and nums2
        return ans;
    }
};

int main() {
    // Input: two sorted arrays
    vector<int> nums1 = {1, 2, 3, 3, 4, 5, 6, 7};
    vector<int> nums2 = {3, 3, 4, 4, 5, 8};

    // Create an instance of the Solution class
    Solution finder;

    // Call the intersectionArray method to find the intersection of nums1 and nums2
    vector<int> ans = finder.intersectionArray(nums1, nums2);

    // Output the result
    cout << "Intersection of nums1 and nums2 is:" << endl;
    for (int val : ans) {
        // Print each element of the intersection array
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(M), where M is the length of that array which has less elements.
• Space Complexity:O(1), extra space to store answer is not considered.

Problem Statement (Unsorted Array)

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.

Examples

Example 1:

Input: nums1 = [1, 2, 2, 1], nums = [2, 2]
Output: [2]

Explanation: Only 2 is unique among them.

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Explanation: [4,9] is also accepted.

Different Approaches

1️⃣ Hash Set

Intuition:

• Use a set to store unique elements from one array.
• Then iterate through the second array and check if its elements exist in the set.
• Store the intersection elements in another set to ensure uniqueness.

Steps:

1. Insert all elements of nums1 into a hash set.
2. Iterate through nums2 and check if each element is present in the set.
3. Store the intersection elements in a result set for uniqueness.
4. Convert the result set to a vector for output.

Code:

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

vector<int> intersectionHashSet(vector<int>& nums1, vector<int>& nums2) {


	// Step 1: Populate nums1 elements in set.
    unordered_set<int> set1(nums1.begin(), nums1.end());
    
    unordered_set<int> resultSet;


	// Step 2: Check if any element of nums2 exist in set1.

	// If so, populate in resultSet
    for (int num : nums2) {
        if (set1.count(num)) {
            resultSet.insert(num);
        }
    }

	

	// Step 3: return vector from set.
    return vector<int>(resultSet.begin(), resultSet.end());
}

int main() {
    vector<int> nums1 = {4, 9, 5};
    vector<int> nums2 = {9, 4, 9, 8, 4};
    vector<int> result = intersectionHashSet(nums1, nums2);

    cout << "Intersection: ";
    for (int num : result) {
        cout << num << " ";
    }
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n + m)
  • O(n): To insert nums1 to the set.
  • O(m): To iterate through nums2
• Space Complexity: O(n)
  • To store elements of nums1 in a set.

2️⃣ Sorting and Two Pointer Approach

Intuition:

• Sort both arrays.
• Use two pointers to traverse both arrays and find common elements. Since the arrays are sorted, we can move the pointers intelligently to find matches.

Steps:

1. Sort nums1 and nums2.
2. Use two pointers, one for each array.
3. If the elements at both pointers are equal, add to the result and move both pointers.
4. If the element in nums1 is smaller, move its pointer. Otherwise, move the pointer in nums2.

Code:

#include <iostream>
#include <vector>
#include <algorithm> // Required for the sort function
using namespace std;

// Function to find the intersection of two arrays using the two-pointer approach
vector<int> intersectionTwoPointers(vector<int>& nums1, vector<int>& nums2) {
    // Step 1: Sort both input arrays to enable the two-pointer approach
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    
    // Step 2: Initialize a vector to store the intersection elements
    vector<int> result;

    // Step 3: Use two pointers to traverse both sorted arrays
    int i = 0, j = 0;

    // Step 4: Traverse the arrays until either pointer reaches the end
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] == nums2[j]) {
            // If elements at both pointers are equal and not already in the result
            if (result.empty() || result.back() != nums1[i]) {
                result.push_back(nums1[i]); // Add the element to the result
            }
            // Move both pointers forward
            i++;
            j++;
        } else if (nums1[i] < nums2[j]) {
            // If the current element in nums1 is smaller, move the pointer in nums1 forward
            i++;
        } else {
            // If the current element in nums2 is smaller, move the pointer in nums2 forward
            j++;
        }
    }

    // Step 5: Return the result vector containing the intersection elements
    return result;
}

int main() {
    // Input arrays
    vector<int> nums1 = {4, 9, 5};
    vector<int> nums2 = {9, 4, 9, 8, 4};

    // Step 6: Call the function to compute the intersection of the two arrays
    vector<int> result = intersectionTwoPointers(nums1, nums2);

    // Step 7: Print the intersection result
    cout << "Intersection: ";
    for (int num : result) {
        cout << num << " "; // Print each element in the intersection
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n log n + m log m)
  • O(n log n + m log m): To sort both arrays.
  • O(n + m): To find the intersection using two pointers.
  • Overall: O(n log n + m log m)
• Space Complexity: O(1)
  • As sorting is done in place.

3️⃣ Binary Search

Intuition:

• Sort one array and use binary search to check for each element in the other array.
• Store the elements in a result set to ensure uniqueness.

Steps:

1. Sort nums2.
2. Iterate through nums1 and perform a binary search for each element in nums2.
3. If the element exists, store it in a result set.
4. Convert the result set to a vector for output.

Code:

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

// Function to perform binary search on a sorted array
bool binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    // Perform binary search until the search space is empty
    while (left <= right) {
        // Calculate the middle index
        int mid = left + (right - left) / 2;
        // Check if the middle element matches the target
        if (nums[mid] == target) {
            return true; // Target found
        } 
        // If target is greater, search in the right half
        else if (nums[mid] < target) {
            left = mid + 1;
        } 
        // If target is smaller, search in the left half
        else {
            right = mid - 1;
        }
    }
    return false; // Target not found
}

// Function to find the intersection of two arrays using binary search
vector<int> intersectionBinarySearch(vector<int>& nums1, vector<int>& nums2) {
    // Step 1: Sort the second array to enable binary search
    sort(nums2.begin(), nums2.end());

    // Step 2: Use a set to store unique intersection elements
    unordered_set<int> resultSet;

    // Step 3: Iterate through elements of the first array
    for (int num : nums1) {
        // Check if the current element exists in the second array using binary search
        if (binarySearch(nums2, num)) {
            resultSet.insert(num); // Add it to the result set
        }
    }

    // Step 4: Convert the set to a vector to return as the final result
    return vector<int>(resultSet.begin(), resultSet.end());
}

int main() {
    // Input arrays
    vector<int> nums1 = {4, 9, 5};
    vector<int> nums2 = {9, 4, 9, 8, 4};

    // Find the intersection of the two arrays
    vector<int> result = intersectionBinarySearch(nums1, nums2);

    // Print the intersection result
    cout << "Intersection: ";
    for (int num : result) {
        cout << num << " ";
    }

    return 0; // Exit the program
}

Complexity Analysis:

• Time Complexity: O(m log m + n log n)
  • O(m log m): Sorting nums2.
  • O(n log m): Binary search for each element of nums2.
  • Overall: O(m log m + n log m)
• Space Complexity:
  • O(1): For binary search.
  • O(n): To store the result in a set.

Intersection of Two Arrays 2

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Examples

Example 1:

Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2, 2]

Explanation: The elements [2, 2] are in both the arrays.

Example 2:

Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
Output: [4, 9]

Explanation: [9, 4] is also accepted.

Different Approaches

1️⃣ Using Hash Maps

Intuition:

• Use a hash map to count the frequency of elements in one array.
• Iterate through the second array and decrease the count in the hash map for every matching element.
• Add matching elements to the result.

Steps:

1. Create a hash map (freqMap) to store the frequency of each element in nums1.
2. Iterate through nums2 and check if the element exists in freqMap with a non-zero count.
3. If it exists, add it to the result and decrease its count in the map.
4. Return the result vector.

Code:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> freqMap; // To store frequencies of nums1
    vector<int> result;

    // Step 1: Count frequencies of elements in nums1
    for (int num : nums1) {
        freqMap[num]++;
    }

    // Step 2: Iterate through nums2 and find common elements
    for (int num : nums2) {
        if (freqMap[num] > 0) { // If num exists in nums1 with non-zero count
            result.push_back(num); // Add to result
            freqMap[num]--; // Decrease the count
        }
    }

    return result; // Return the intersection with duplicates
}

int main() {
    vector<int> nums1 = {4, 9, 5, 9};
    vector<int> nums2 = {9, 4, 9, 8, 4};
    vector<int> result = intersect(nums1, nums2);

    cout << "Intersection: ";
    for (int num : result) {
        cout << num << " ";
    }
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n + m)
  • O(n): To build the hash map.
  • O(m): To iterate through nums2.
• Space Complexity: O(n)
  • To store the hash map.

2️⃣ Sorting and Two Pointers

Intuition:

• Sort both arrays.
• Use two pointers to find matching elements while maintaining order.
• Add matching elements to the result.

Steps:

1. Sort both nums1 and nums2.
2. Use two pointers (i and j) to iterate through both arrays.
3. If elements at both pointers are equal, add to the result and move both pointers.
4. If nums1[i] < nums2[j], move the pointer i. Otherwise, move the pointer j.

Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> intersectSorted(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    vector<int> result;

    int i = 0, j = 0;
    // Use two pointers to find intersection
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] == nums2[j]) {
            result.push_back(nums1[i]); // Add common element to result
            i++;
            j++;
        } else if (nums1[i] < nums2[j]) {
            i++; // Move pointer in nums1
        } else {
            j++; // Move pointer in nums2
        }
    }

    return result;
}

int main() {
    vector<int> nums1 = {4, 9, 5, 9};
    vector<int> nums2 = {9, 4, 9, 8, 4};
    vector<int> result = intersectSorted(nums1, nums2);

    cout << "Intersection: ";
    for (int num : result) {
        cout << num << " ";
    }
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n log n + m log m)
  • O(n log n + m log m): Sorting both arrays.
  • O(n + m): To iterate through both arrays with two pointers.
• Space Complexity: O(1)
  • Because sorting is done in place.