Find the Intersection of Two Arrays

वीडियो #27: लीड कोड: इजी - प्रैक्टिस प्रॉब्लम

प्रोब्लम स्टेटमेंट

• दो नंबर्स एरे दिए हुए हैं: nums1 और nums2
• एक ऐसा एरे रिटर्न करना है जो दोनों एरे के कॉमन एलिमेंट्स को (यूनिक) स्टोर करे
• रिजल्ट का ऑर्डर मायने नहीं रखता

सिंपल अप्रोच (Approach 1)

1. इंटरसेक्शन फाइंड करना:

   • हर एलिमेंट को एक-एक करके चेक करो, कि दूसरे एरे में प्रेज़ेंट है या नहीं
   • क्न खुश यूज़ कर सकते हो यूनिक एलिमेंट स्टोर करने के लिए

2. स्टेप्स:

   • दोनों एरे के कॉमन एलिमेंट्स ढूंढो
   • यूनिक एलिमेंट्स को रिटर्न करो

3. उदाहरण:

   • nums1 = [1, 2, 2, 1], nums2 = [2, 2]
   • कॉमन: [2, 2]
   • यूनिक: [2]

बेटर अप्रोच (Approach 2)

• स्लाइटली बेटर:

  • nums1 के एलिमेंट्स को एक सेट में डाल दो (set1)
  • nums2 के एलिमेंट्स से चेक करो कि set1 में हैं या नहीं
  • अगर मिला तो रिजल्ट सेट में डालो और set1 से हटा दो

इम्प्रूव्ड अप्रोच (Approach 3)

• सॉर्ट एंड बाइनरी सर्च:
  • nums1 को सॉर्ट करो
  • nums2 का हर एलिमेंट सॉर्टेड nums1 में बाइनरी सर्च से ढूंढो
  • रिजल्ट सेट में स्टोर कर लो

बेस्ट अप्रोच (Approach 4)

• टू पॉइंटर अप्रोच:
  • दोनों एरे को सॉर्ट करो
  • दो पॉइंटर्स का यूज करके यूनिक इंटरसेक्शन ढूंढो
  • डुप्लीकेट एलिमेंट्स ठीक तरह से स्किप करो

कोडिंग स्टेप्स

1. अप्रोच 1: यूनिक सेट के साथ

unordered_set<int> set1(nums1.begin(), nums1.end());
unordered_set<int> result;

for (int num : nums2) {
    if (set1.find(num) != set1.end()) {
        result.insert(num);
        set1.erase(num);
    }
}

vector<int> ans(result.begin(), result.end());
return ans;

2. अप्रोच 2: सेट हटा कर

unordered_set<int> set1(nums1.begin(), nums1.end());
vector<int> result;

for (int num : nums2) {
    if (set1.find(num) != set1.end()) {
        result.push_back(num);
        set1.erase(num);
    }
}

return result;

3. अप्रोच 3: सॉर्ट और बाइनरी सर्च

sort(nums1.begin(), nums1.end());
unordered_set<int> result;

for (int num : nums2) {
    if (binary_search(nums1.begin(), nums1.end(), num)) {
        result.insert(num);
    }
}

vector<int> ans(result.begin(), result.end());
return ans;

4. अप्रोच 4: टू पॉइंटर और डुप्लीकेट स्किपिंग

sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());

vector<int> result;
int i = 0, j = 0;

while (i < nums1.size() && j < nums2.size()) {
    if (nums1[i] == nums2[j]) {
        if (result.empty() || result.back() != nums1[i]) {
            result.push_back(nums1[i]);
        }
        i++;
        j++;
    } else if (nums1[i] < nums2[j]) {
        i++;
    } else {
        j++;
    }
}

return result;

निष्कर्ष

• यूनिक एलिमेंट्स ढूंढने के लिए मल्टीपल अप्रोच हैं, हर एक के अपने फायदे और नुकसान हैं.
• set, sort, और binary search के सही उपयोग से टाइम कॉम्प्लेक्सिटी में इम्प्रूवमेंट आ सकता है.
• टू पॉइंटर अप्रोच प्रभावी और समझने में आसान है.
• प्रैक्टिस करते रहना जरूरी है, भले ही क्वेश्चन इजी ही क्यों ना हो, हर अप्रोच कुछ नया सिखाता है.