Skip to content

प्रॉडक्ट ऑफ़ एरे एक्सेप्ट सेल्फ: ऑप्टिमल DSA समाधान

Convert to note

सवाल को समझना (Problem Understanding)

हमें एक integer array nums दिया गया है, जिसका आकार n है। हमें एक answer array return करना है जहाँ हर answer[i] में, nums[i] को छोड़कर बाकी सभी elements का product होगा।

Important Constraint: हमें डिवीज़न ऑपरेटर (/) का उपयोग नहीं करना है।

Example:

  • Input: nums = [1, 2, 3, 4]
  • Output: [24, 12, 8, 6]
    • answer[0] = 2 · 3 · 4 = 24
    • answer[1] = 1 · 3 · 4 = 12
    • answer[2] = 1 · 2 · 4 = 8
    • answer[3] = 1 · 2 · 3 = 6

1. ब्रूट फोर्स अप्रोच (O(n²) टाइम, O(1) स्पेस)

यह सबसे सीधा तरीका है, लेकिन यह large inputs (जैसे n = 10⁵) के लिए Time Limit Exceeded (TLE) देगा।

तरीका:

  1. Outer loop (i) हर index पर जाएगा।
  2. Inner loop (j) पूरे array को traverse करेगा।
  3. अगर i ≠ j, तो हम nums[j] को product में multiply करेंगे।
  4. Inner loop खत्म होने पर product को answer[i] में store करेंगे।

Pseudo Code:

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 1);

    for (int i = 0; i < n; i++) {
        int product = 1;
        for (int j = 0; j < n; j++) {
            if (i != j) {
                product *= nums[j];
            }
        }
        answer[i] = product;
    }
    return answer;
}

Time Complexity: O(n²) Space Complexity: O(1) (सिर्फ output array को छोड़कर)

2. ऑप्टिमल अप्रोच: प्रीफिक्स और सफिक्स प्रॉडक्ट (O(n) टाइम, O(n) स्पेस)

यह तरीका पिछले वाले से बेहतर है, लेकिन इसमें extra space लगता है।

कोर आइडिया:

  • answer[i] = (i से पहले के सभी elements का product) · (i के बाद के सभी elements का product)
  • इसे हम दो arrays में store कर सकते हैं:
    1. प्रीफिक्स प्रॉडक्ट array: prefix[i] = nums[0] से nums[i-1] तक का product।
    2. सफिक्स प्रॉडक्ट array: suffix[i] = nums[i+1] से nums[n-1] तक का product।

विजुअलाइज़ेशन:

मान लीजिए nums = [1, 2, 3, 4]

Prefix Array Calculation (Left to Right):

  • prefix[0] = 1 (i=0 से पहले कोई element नहीं)
  • prefix[1] = prefix[0] · nums[0] = 1 · 1 = 1
  • prefix[2] = prefix[1] · nums[1] = 1 · 2 = 2
  • prefix[3] = prefix[2] · nums[2] = 2 · 3 = 6

इसलिए, prefix = [1, 1, 2, 6]

Suffix Array Calculation (Right to Left):

  • suffix[3] = 1 (i=3 के बाद कोई element नहीं)
  • suffix[2] = nums[3] · suffix[3] = 4 · 1 = 4
  • suffix[1] = nums[2] · suffix[2] = 3 · 4 = 12
  • suffix[0] = nums[1] · suffix[1] = 2 · 12 = 24

इसलिए, suffix = [24, 12, 4, 1]

Final Answer Calculation:

  • answer[0] = prefix[0] · suffix[0] = 1 · 24 = 24
  • answer[1] = prefix[1] · suffix[1] = 1 · 12 = 12
  • answer[2] = prefix[2] · suffix[2] = 2 · 4 = 8
  • answer[3] = prefix[3] · suffix[3] = 6 · 1 = 6

Pseudo Code:

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> prefix(n, 1), suffix(n, 1), answer(n);

    // Prefix product
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] * nums[i - 1];
    }

    // Suffix product
    for (int i = n - 2; i >= 0; i--) {
        suffix[i] = suffix[i + 1] * nums[i + 1];
    }

    // Final answer
    for (int i = 0; i < n; i++) {
        answer[i] = prefix[i] * suffix[i];
    }

    return answer;
}

Time Complexity: O(n) Space Complexity: O(n) (दो extra arrays के लिए)

3. मोस्ट ऑप्टिमल अप्रोच: कॉन्सटेंट स्पेस (O(n) टाइम, O(1) स्पेस)

इस अप्रोच में हम extra arrays के बजाय output array का ही prefix storage के लिए उपयोग करते हैं, और suffix को एक single variable की मदद से calculate करते हैं। यह दृष्टिकोण 8 Essential LeetCode Patterns to Solve Coding Problems Efficiently में वर्णित प्रीफिक्स/सफिक्स पैटर्न का एक उत्कृष्ट उदाहरण है।

स्टेप-बाय-स्टेप प्रॉसेस:

स्टेप 1: Output Array में Prefixes Store करें

  • answer[0] = 1
  • answer[1] = answer[0] · nums[0] = 1 · 1 = 1
  • answer[2] = answer[1] · nums[1] = 1 · 2 = 2
  • answer[3] = answer[2] · nums[2] = 2 · 3 = 6

इसके बाद, answer = [1, 1, 2, 6]

स्टेप 2: Suffix को Multiply करें (Right to Left)

  • suffix = 1 (rightmost element के लिए)
  • i = 2 (n-2 से शुरू):
    • suffix *= nums[3] ⇒ 1 · 4 = 4
    • answer[2] *= suffix ⇒ 2 · 4 = 8
  • i = 1:
    • suffix *= nums[2] ⇒ 4 · 3 = 12
    • answer[1] *= suffix ⇒ 1 · 12 = 12
  • i = 0:
    • suffix *= nums[1] ⇒ 12 · 2 = 24
    • answer[0] *= suffix ⇒ 1 · 24 = 24

अब answer = [24, 12, 8, 6] जो कि हमारा desired output है।

Pseudo Code:

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 1);

    // Step 1: Calculate prefix products and store in answer
    for (int i = 1; i < n; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }

    // Step 2: Calculate suffix products and multiply directly
    int suffix = 1;
    for (int i = n - 2; i >= 0; i--) {
        suffix *= nums[i + 1];
        answer[i] *= suffix;
    }

    return answer;
}

Time Complexity: O(n) Space Complexity: O(1) (सिर्फ output array को छोड़कर)

निष्कर्ष

  • ब्रूट फोर्स (O(n²)): समझने में आसान, लेकिन बड़े inputs के लिए अव्यावहारिक।
  • प्रीफिक्स/सफिक्स (O(n) टाइम, O(n) स्पेस): एक अच्छा मध्यम रास्ता, लेकिन extra space लगता है।
  • कॉन्सटेंट स्पेस (O(n) टाइम, O(1) स्पेस): इंटरव्यू के लिए सबसे इष्टतम समाधान। यह अप्रोच सीखना ज़रूरी है क्योंकि यह एक सामान्य पैटर्न (prefix/suffix computation) को दिखाता है जिसका उपयोग कई अन्य DSA समस्याओं में भी किया जा सकता है, जैसे Mastering Two Pointer & Sliding Window Techniques in DSA Interviews में वर्णित तकनीकों के साथ।

Keep this summary

Save it to LunaNotes and it becomes a real note in your library — editable, searchable, and ready to turn into flashcards or a diagram. Free to start.

Save to LunaNotes

Or summarise for another video.

32K+ people have turned 65K+ videos into notes

“Very useful tool. I'm using it for the last couple weeks and I'm loving it so far. Makes learning on YouTube a great experience.”
Bhai Chrome Web Store review

This summary and transcript were automatically generated using AI with the Free YouTube transcript summary tool by LunaNotes.

Related summaries

जावा में रिकर्शन: बेसिक्स, स्टैक और प्रॉब्लम्स की पूरी गाइड

जावा में रिकर्शन: बेसिक्स, स्टैक और प्रॉब्लम्स की पूरी गाइड

इस वीडियो में जावा में रिकर्शन (Recursion) को शुरुआत से समझाया गया है। वीडियो में बताया गया है कि रिकर्शन क्या है, यह मेमोरी में स्टैक के रूप में कैसे काम करता है, स्टैक ओवरफ्लो की समस्या क्या है, और बेसिक से लेकर एडवांस लेवल की प्रॉब्लम्स जैसे फैक्टोरियल, फिबोनाची सीरीज और पावर कैलकुलेशन को कैसे हल करें।

रे ऑप्टिक्स: दर्पण एवं अपवर्तन का संपूर्ण निर्देशन एवं डेरिवेशन ट्रिक्स

रे ऑप्टिक्स: दर्पण एवं अपवर्तन का संपूर्ण निर्देशन एवं डेरिवेशन ट्रिक्स

यह लाइव कक्षा रे ऑप्टिक्स चैप्टर का एकदम बेसिक से लेकर एडवांस तक कवरेज करती है। आप मिरर फॉर्मूला, साइन कन्वेंशन, लेंस मेकर फॉर्मूला और स्नेल्स लॉ जैसे सभी डेरिवेशन को याद करने के आसान ट्रिक्स व हैक्स सीखेंगे, साथ ही पिछले वर्षों के प्रश्नों और न्यूमेरिकल्स का अभ्यास भी करेंगे।

Python OOP Concepts: Inheritance, Polymorphism & Advanced Classes Explained

Python OOP Concepts: Inheritance, Polymorphism & Advanced Classes Explained

इस वीडियो में पाइथन की ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग (OOP) के महत्वपूर्ण कॉन्सेप्ट्स जैसे कि इनहेरिटेंस, प्राइवेट एट्रिब्यूट्स, क्लास और स्टैटिक मेथड्स, और पॉलीमॉर्फिज्म को विस्तार से समझाया गया है। साथ ही, वीडियो में ओपनिंग से लेकर क्लास डिफाइनिंग, ऑपरेटर ओवरलोडिंग, प्रॉपर्टी डेकोरेटर्स, और रियल टाइम उदाहरणों द्वारा OOP की समझ बढ़ाई गई है।

रीजनिंग: ब्लड रिलेशन, डायरेक्शन और मैथमेटिकल ऑपरेशन पूरी गाइड

रीजनिंग: ब्लड रिलेशन, डायरेक्शन और मैथमेटिकल ऑपरेशन पूरी गाइड

यह वीडियो रीजनिंग के तीन महत्वपूर्ण टॉपिक्स को कवर करता है: डायरेक्शन एंड डिस्टेंस, ब्लड रिलेशन, और मैथमेटिकल ऑपरेशंस। इसमें बेसिक कॉन्सेप्ट्स से लेकर ट्रिकी सवालों को हल करने की स्मार्ट तकनीकों तक, सब कुछ सरल भाषा में समझाया गया है ताकि आप आसानी से याद रख सकें और परीक्षा में बेहतरीन प्रदर्शन कर सकें।

उत्पादन योजना और सुविधा निर्णय | PPC, क्षमता और लेआउट रणनीतियाँ

उत्पादन योजना और सुविधा निर्णय | PPC, क्षमता और लेआउट रणनीतियाँ

यह वीडियो 'प्रोडक्शन प्लानिंग एंड फैसिलिटी डिसीजन' पर 9वां लेक्चर है, जो Cocoar परीक्षा की तकनीकी श्रृंखला का हिस्सा है। इसमें PPC (रूटिंग, लोडिंग, शेड्यूलिंग, डिस्पैचिंग, एक्सपिडिटिंग), एग्रीगेट प्लानिंग (लेवल, चेज़, मिक्स्ड रणनीतियाँ), क्षमता मापन (डिज़ाइन, प्रभावी, वास्तविक), बॉटलनेक विश्लेषण, और सुविधा स्थान चयन (फैक्टर रेटिंग, ग्रैविटी केंद्र, ब्रेक-ईवन) को कवर किया गया है। वीडियो में विस्तृत उदाहरण और MCQ अभ्यास भी शामिल हैं।

Most viewed summaries

A Comprehensive Guide to Using Stable Diffusion Forge UI

A Comprehensive Guide to Using Stable Diffusion Forge UI

Explore the Stable Diffusion Forge UI, customizable settings, models, and more to enhance your image generation experience.

Kolonyalismo at Imperyalismo: Ang Kasaysayan ng Pagsakop sa Pilipinas

Kolonyalismo at Imperyalismo: Ang Kasaysayan ng Pagsakop sa Pilipinas

Tuklasin ang kasaysayan ng kolonyalismo at imperyalismo sa Pilipinas sa pamamagitan ni Ferdinand Magellan.

Mastering Inpainting with Stable Diffusion: Fix Mistakes and Enhance Your Images

Mastering Inpainting with Stable Diffusion: Fix Mistakes and Enhance Your Images

Learn to fix mistakes and enhance images with Stable Diffusion's inpainting features effectively.

Pamamaraan at Patakarang Kolonyal ng mga Espanyol sa Pilipinas

Pamamaraan at Patakarang Kolonyal ng mga Espanyol sa Pilipinas

Tuklasin ang mga pamamaraan at patakaran ng mga Espanyol sa Pilipinas, at ang epekto nito sa mga Pilipino.

How to Install and Configure Forge: A New Stable Diffusion Web UI

How to Install and Configure Forge: A New Stable Diffusion Web UI

Learn to install and configure the new Forge web UI for Stable Diffusion, with tips on models and settings.

Found this summary useful?

Take it with you. One click puts it in your own LunaNotes library.

Save to LunaNotes

Start taking better notes today with LunaNotes

Start for free