Intersection of Two Arrays II | 2 Approaches | Easy Explanations | Leetcode 350 | codestorywithMIK

This is the 45th Video of our Playlist "Leetcode Easy : Popular Interview Problems" by codestorywithMIK

In this video we will try to solve a good practice problem : Intersection of Two Arrays II | 2 Approaches | Easy Explanations | Leetcode 350 | codestorywithMIK

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Intersection of Two Arrays II | 2 Approaches | Easy Explanations | Leetcode 350 | codestorywithMIK
Company Tags : META

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Summary :
Approach 1: Using Hash Map

Time Complexity: O(n) Space Complexity: O(n)

Hash Map for Counting Elements:
Traverse the first array (nums1) and use an unordered_map (or HashMap in Java) to count the occurrences of each element.
Intersection Calculation:
Traverse the second array (nums2).
For each element in nums2, check if it exists in the map with a count greater than zero.
If it exists, add it to the result list and decrement its count in the map.
Advantages:

Efficient in terms of both time and space for large arrays with many duplicate elements.
Approach 2: Using Sorting and Two Pointers

Time Complexity: O(n log n) Space Complexity: O(n)

Sort Both Arrays:
Sort both input arrays (nums1 and nums2).
Two-Pointer Technique:
Use two pointers to traverse the sorted arrays.
If elements at both pointers are equal, add the element to the result list and increment both pointers.
If the element in nums1 is smaller, increment the pointer for nums1.
If the element in nums2 is smaller, increment the pointer for nums2.
Advantages:

Simple and easy to understand.
Efficient when the arrays are already sorted or nearly sorted.
Comparison

Efficiency: The hash map approach has a linear time complexity, making it faster for large arrays. The sorting and two-pointer approach has a higher time complexity due to the sorting step.
Space: Both approaches use extra space, but the hash map approach uses additional space proportional to the number of unique elements in the first array, whereas the sorting approach uses extra space mainly for the sorted arrays.
Use Case: The hash map approach is more efficient for unsorted arrays with many duplicates, while the sorting and two-pointer approach is better for arrays that are already sorted or when space is a concern.

✨ Timelines✨
00:00 - Introduction

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024

[sahebraojadhav]

Bro Isi time harroj upload kiya kro kuch log morning me solve krte hai

[ashwin_anand_dev]

Thank you for explaining bhaiya. Bhaiya, there are some follow up questions as well in the description of this problem. If you get a chance to see this comment, then could you please provide your explanation of them. Here are the questions.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to nums2's size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

It will be really appreciated if you can answer them

[tarunsingh]

Third Approach Using Binary Search:
class Solution {
public:
bool f(vector<int> &nums, int target){
int l=0, r = nums.size()-1;
while(l<=r){
int m =l+(r-l)/2;
if(nums[m]==target){
return true;
}
else if(nums[m]>target){
r = m-1;
}
else{
l = m+1;
}
}
return false;
}
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
vector<int> ans;
sort(begin(nums1), end(nums1));
sort(nums2.begin(), nums2.end());


// for always having nums1 as smallest array
if(n>m){
swap(nums1, nums2);
}
for(auto &it: nums1){
if(f(nums2, it)){
ans.push_back(it);
nums2.erase(find(nums2.begin(), nums2.end(), it));
}
}
return ans;
}
};

[learn_in_shorts]

Bhaiya mujhse pahle 1 approach hit Kiya tha jab mey ye question padha to and then 2 approach 😊

[B-Billy]

This question has already been solved in "Leetcode Easy Playlist" of this channel.

[shashanksaurabh]

bhaiya ek chhota sa video aapke DSA wale reposetry pe bna dijiye please ki usko kaise efficiently use karna hai, uske Arrays wale folder mein bht sara problems hai unke subtopics nhi samjh aa rha

[venkatarohitpotnuru]

bhaiyya partion dp videos..BTW thank you bhaiyya

[himanshujain]

If sort using merge sort then space will be O(n)
And we use heap sort then only space will be O(1) So which sol . is more pref?

[akshatgoel]

pls take follow up questions also given below the questions

[-cse-csmohitkumarmandal]

3rd Approach:- Using Binary Search 🔎 in nums2

[dibbodas]

sir i have a question sort algorithm is taking space but why did you say that space is o(1)??

[RamanKumar-gtnm]

bhai apki leetcode ki profile ka link dena

[tarunsingh]

What should be the answers to the follow up questions??

1 . What if the given array is already sorted? How would you optimize your algorithm?

Two pointer approach to move in respective array while checking for equality.

2. What if nums1's size is small compared to nums2's size? Which algorithm is better?

Dictionary of elements present in num1 will be the used as a frequency table or hashtable to optimize the space

[nawazthezaifre]

Mene bhi first sort karke two pointer apply kiya tha then socha map se bhi ho sakta hai..

[akmarkan]

Constraint <= 1000 the

Toh maine Counting Sort wale concept se Count store krliya(Using one loop) and then loop se usko ans mein daal diya.


What do u think about this??

[dayashankarlakhotia]

I have submitted count sort method my code is this.thank for your previous video for countsort.
public int[]intersect(int[]nums1, int[]nums2){
int[]freq=new int[1001];
int[]ans=new int[1001];
for(int num:nums1)
freq[num]++;
int cnt=0;
for(int num:nums2){
if(freq[num]>0)
ans[cnt++]=num;
freq[num]--;
}
Arrays.copyOfRange(ans, 0, cnt);
}
tc=0(n);
sc=0(n);
🎉❤

[shikhajaiswar]

leetcode 1267. Count Servers that Communicate

sir please explain this question

[pokeindia]

Bhaiya ek baar follow up question ka answer bhi pin kar do please!!