1:14:13
Lecture 30: Trapping Rain Water || 3 SUM || 4 SUM
Coder Army
Overview
यह वीडियो तीन महत्वपूर्ण कोडिंग समस्याओं को हल करने के तरीके पर केंद्रित है: ट्रैपिंग रेन वाटर, 3SUM, और 4SUM। यह प्रत्येक समस्या के लिए ब्रूट-फोर्स समाधानों से शुरू होता है और फिर अधिक कुशल दृष्टिकोणों की ओर बढ़ता है, जिसमें डायनामिक प्रोग्रामिंग, टू-पॉइंटर तकनीक और सॉर्टिंग का उपयोग शामिल है। वीडियो का लक्ष्य कोडिंग इंटरव्यू में पूछे जाने वाली इन सामान्य समस्याओं के लिए मजबूत समझ और कुशल समाधान प्रदान करना है।
How was this?
Save this permanently with flashcards, quizzes, and AI chat
Chapters
- समस्या: इमारतों की एक श्रृंखला (ऊंचाई द्वारा दर्शाई गई) के बीच बारिश के पानी की मात्रा की गणना करना।
- बुनियादी विचार: किसी विशेष स्थान पर संग्रहीत पानी की मात्रा उस स्थान के बाईं ओर की सबसे ऊंची इमारत और दाईं ओर की सबसे ऊंची इमारत के बीच न्यूनतम ऊंचाई से उस स्थान की अपनी ऊंचाई घटाकर निर्धारित की जाती है।
- ब्रूट-फोर्स दृष्टिकोण: प्रत्येक इमारत के लिए, बाईं और दाईं ओर की सबसे ऊंची इमारतों को खोजने के लिए अलग-अलग ट्रैवर्सल करें, फिर पानी की मात्रा की गणना करें और कुल योग करें।
- अनुकूलित दृष्टिकोण (प्री-कंप्यूटेड मैक्स लेफ्ट/राइट): दो अतिरिक्त ऐरे का उपयोग करके प्रत्येक स्थिति के लिए अधिकतम बाईं और अधिकतम दाईं ऊंचाई को पहले से गणना करें। यह प्रत्येक इमारत के लिए अधिकतम बाएं और दाएं को खोजने की आवश्यकता को समाप्त करता है, जिससे समय जटिलता O(N) हो जाती है।
- स्थान-अनुकूलित दृष्टिकोण (टू-पॉइंटर): अतिरिक्त ऐरे के उपयोग को समाप्त करने के लिए दो पॉइंटर्स (एक शुरुआत से, एक अंत से) का उपयोग करें। पॉइंटर्स को तब तक ले जाएं जब तक वे मिलते हैं, प्रत्येक चरण में पानी की मात्रा की गणना करते हैं, हमेशा छोटे बाएं या दाएं अधिकतम के आधार पर। यह O(N) समय और O(1) स्थान जटिलता प्राप्त करता है।
यह समस्या ऐरे मैनिपुलेशन, प्री-कंप्यूटेशन और पॉइंटर तकनीकों का उपयोग करके इष्टतम समाधान खोजने के महत्व को दर्शाती है।
ऊंचाई [0,1,0,2,1,0,1,3,2,1,2,1] के साथ, पानी की मात्रा की गणना करने के लिए, हम प्रत्येक इंडेक्स पर बाईं और दाईं ओर की सबसे ऊंची इमारतों को ढूंढते हैं। उदाहरण के लिए, इंडेक्स 2 पर (ऊंचाई 0), बाईं ओर की सबसे ऊंची इमारत 1 है और दाईं ओर की सबसे ऊंची इमारत 3 है। संग्रहीत पानी की मात्रा min(1, 3) - 0 = 1 है।
- समस्या: दिए गए ऐरे में तीन संख्याओं का एक ट्रिपलेट खोजना जिनका योग एक लक्ष्य मान (k) के बराबर हो।
- ब्रूट-फोर्स दृष्टिकोण: तीन नेस्टेड लूप का उपयोग करके सभी संभावित ट्रिपलेट्स की जांच करें। यह O(N^3) समय जटिलता लेता है।
- अनुकूलित दृष्टिकोण (सॉर्टिंग + बाइनरी सर्च): ऐरे को सॉर्ट करें। फिर, प्रत्येक तत्व के लिए, शेष ऐरे में दो संख्याओं को खोजने के लिए बाइनरी सर्च का उपयोग करें जिनका योग लक्ष्य से शेष के बराबर हो। यह O(N^2 log N) समय जटिलता लेता है।
- इष्टतम दृष्टिकोण (सॉर्टिंग + टू-पॉइंटर): ऐरे को सॉर्ट करें। एक बाहरी लूप के माध्यम से प्रत्येक तत्व को फिक्स करें। आंतरिक रूप से, शेष ऐरे पर दो पॉइंटर्स (एक शुरुआत से, एक अंत से) का उपयोग करें। पॉइंटर्स को ले जाएं और योग की तुलना लक्ष्य से करें, पॉइंटर्स को तदनुसार समायोजित करें। यह O(N^2) समय जटिलता और O(1) अतिरिक्त स्थान (सॉर्टिंग के लिए O(log N) या O(N) को छोड़कर) लेता है।
यह समस्या सॉर्टिंग और टू-पॉइंटर तकनीक के संयोजन का उपयोग करके समस्याओं को कुशलतापूर्वक हल करने के तरीके को प्रदर्शित करती है, जो अक्सर ब्रूट-फोर्स दृष्टिकोण से काफी बेहतर होती है।
ऐरे [-1, 0, 1, 2, -1, -4] और लक्ष्य k = 0 के साथ, सॉर्ट करने के बाद ऐरे [-4, -1, -1, 0, 1, 2] बन जाता है। जब हम -4 को फिक्स करते हैं, तो हमें दो संख्याओं की आवश्यकता होती है जिनका योग 4 हो। टू-पॉइंटर दृष्टिकोण का उपयोग करके, हम पाते हैं कि -1 और 1 का योग 0 है, और 0 और 2 का योग 2 है। जब हम -1 को फिक्स करते हैं, तो हमें दो संख्याओं की आवश्यकता होती है जिनका योग 1 हो। हम 0 और 1 पाते हैं, जिससे ट्रिपलेट [-1, 0, 1] बनता है।
- समस्या: दिए गए ऐरे में चार संख्याओं का एक क्वाड्रप्लेट खोजना जिनका योग एक लक्ष्य मान (k) के बराबर हो।
- ब्रूट-फोर्स दृष्टिकोण: चार नेस्टेड लूप का उपयोग करके सभी संभावित क्वाड्रप्लेट्स की जांच करें। यह O(N^4) समय जटिलता लेता है।
- अनुकूलित दृष्टिकोण (3SUM को कम करना): समस्या को 3SUM में बदलें। ऐरे को सॉर्ट करें। फिर, प्रत्येक तत्व के लिए, शेष ऐरे में तीन संख्याओं को खोजने के लिए 3SUM एल्गोरिथम (O(N^2)) का उपयोग करें जिनका योग लक्ष्य से शेष के बराबर हो। यह O(N^3) समय जटिलता लेता है।
- इष्टतम दृष्टिकोण (2SUM को कम करना): समस्या को 2SUM में बदलें। ऐरे को सॉर्ट करें। सभी संभावित जोड़े (i, j) के योग की पूर्व-गणना करें और उन्हें हैश मैप में संग्रहीत करें। फिर, अन्य दो संख्याओं (k, l) के लिए सभी संभावित जोड़े के योग की गणना करें और हैश मैप में जांचें कि क्या (target - (nums[k] + nums[l])) मौजूद है। यह O(N^2) समय जटिलता और O(N^2) स्थान जटिलता लेता है।
- एक और इष्टतम दृष्टिकोण (सॉर्टिंग + टू-पॉइंटर): ऐरे को सॉर्ट करें। दो बाहरी लूप का उपयोग करके पहले दो तत्वों (i, j) को फिक्स करें। आंतरिक रूप से, शेष ऐरे पर दो पॉइंटर्स (स्टार्ट और एंड) का उपयोग करें ताकि शेष दो संख्याओं को ढूंढा जा सके। यह O(N^3) समय जटिलता लेता है।
4SUM समस्या को हल करने से पता चलता है कि कैसे एक समस्या को छोटी, ज्ञात समस्याओं (जैसे 3SUM या 2SUM) में बदला जा सकता है, जिससे अधिक कुशल समाधान प्राप्त होते हैं।
ऐरे [1, 0, -1, 0, -2, 2] और लक्ष्य k = 0 के साथ, सॉर्ट करने के बाद ऐरे [-2, -1, 0, 0, 1, 2] बन जाता है। हम पहले दो नंबरों को फिक्स करते हैं, जैसे -2 और -1। हमें शेष दो नंबरों का योग 3 चाहिए। टू-पॉइंटर दृष्टिकोण का उपयोग करके, हम 1 और 2 पाते हैं, जिससे ट्रिपलेट [-2, -1, 1, 2] बनता है।
Key takeaways
- समस्याओं को हल करने के लिए ब्रूट-फोर्स से शुरू करें और फिर अधिक कुशल समाधानों की ओर बढ़ें।
- ऐरे मैनिपुलेशन समस्याओं के लिए, प्री-कंप्यूटेशन (जैसे अधिकतम बाएं/दाएं) या टू-पॉइंटर तकनीक समय जटिलता को काफी कम कर सकती है।
- 3SUM और 4SUM जैसी समस्याओं को अक्सर सॉर्टिंग और टू-पॉइंटर या हैश मैप का उपयोग करके हल किया जा सकता है।
- बड़ी समस्याओं को छोटी, ज्ञात उप-समस्याओं (जैसे 4SUM को 3SUM या 2SUM में बदलना) में तोड़ना एक शक्तिशाली समस्या-समाधान रणनीति है।
- समस्याओं को हल करते समय समय और स्थान जटिलता पर विचार करना महत्वपूर्ण है, खासकर कोडिंग इंटरव्यू में।
Key terms
Trapping Rain Water3SUM4SUMBrute ForceTwo PointersSortingBinary SearchHash MapTime ComplexitySpace Complexity
Test your understanding
- ट्रैपिंग रेन वाटर समस्या में, किसी विशेष स्थान पर संग्रहीत पानी की मात्रा निर्धारित करने के लिए कौन से दो मुख्य कारक आवश्यक हैं?
- 3SUM समस्या को हल करने के लिए सॉर्टिंग और टू-पॉइंटर दृष्टिकोण का उपयोग करने का क्या लाभ है?
- 4SUM समस्या को 3SUM समस्या में कैसे बदला जा सकता है?
- क्या आप ट्रैपिंग रेन वाटर समस्या के लिए O(1) स्पेस कॉम्प्लेक्सिटी वाले समाधान का वर्णन कर सकते हैं?
- कोडिंग इंटरव्यू में, यदि आपको किसी समस्या के लिए ब्रूट-फोर्स समाधान पता है, तो अगला कदम क्या होना चाहिए?