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

Whatsapp Community Link : www.whatsapp.com/channel/0029...
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
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/interse...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
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

[@sahebraojadhav9727]

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

[@learn_in_shorts]

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

[@venkatarohitpotnuru38]

bhaiyya partion dp videos..BTW thank you bhaiyya

[@gauravbanerjee2898]

Thanks a lot bhaiya ❤❤

[@shashanksaurabh6478]

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

[@b_01_aditidonode43]

thanks!!

[@akshatgoel149]

pls take follow up questions also given below the questions

[@RamanKumar-gt8nm]

bhai apki leetcode ki profile ka link dena

[@nawazthezaifre8870]

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

[@shikhajaiswar1067]

leetcode 1267. Count Servers that Communicate
sir please explain this question

[@dibbodas4116]

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

[@himanshujain9933]

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?

[@B-Billy]

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

[@25-cse-csmohitkumarmandal59]

3rd Approach:- Using Binary Search 🔎 in nums2

[@subhajitdey135]

dono ko hi sort karna padega, and then it can be done using lower_bound

[@tarunsingh2480]

Third Approach Using Binary Search:
class Solution {
public:
bool f(vector &nums , int target){
int l=0, r = nums.size()-1;
while(ltarget){
r = m-1;
}
else{
l = m+1;
}
}
return false;
}
vector intersect(vector& nums1, vector& nums2) {
int n = nums1.size();
int m = nums2.size();
vector 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;
}
};

[@pokeindia5361]

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

[@akmarkan2490]

Constraint

[@yogeshchauhan9401]

Like this
class Solution {
public:
vector intersect(vector& nums1, vector& nums2) {
vectorcount(1001,0);
for(auto i:nums1) count[i]++;
vectorans;
for(auto i:nums2)
{
if(count[i]!=0)
{
ans.push_back(i);
count[i]--;
}
}

return ans;
}
};

[@akmarkan2490]

@@yogeshchauhan9401 Yes Bro

[@priyanshkumariitd]

same here bro. I also applied count sort wala concept first & then used next approach of sorting.

[@akmarkan2490]

@@priyanshkumariitd I didn't sort the whole array actually.
Just Count1 and Count 2 mein dono arrays ka count store krke compare krke ans bna liya

[@priyanshkumariitd]

@@akmarkan2490 Haa same maine bhi kya . Mai bol rha hu ki count sort concept se solve karke doosra appsorach sorting aaya dimaag mai

[@dayashankarlakhotia4943]

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);
🎉❤

[@tarunsingh2480]

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

[@subhajitdey135]

1) If the given array is sorted, then we can use two-pointers and binary search to optimize the space.
2) First approach is better in terms of time complexity, and second is better in terms of space complexity.